1
$\begingroup$

Hi there, In my studies I come up with this nonconvex optimization problem argmin |Ax|_2+lamda*|x|_1 subject to x'x=1 where cost function is nonsmooth but convex and the constrant in nonconvex. I tries subgradient projection method for convex constraints but the global solution is not my desired solution. My question is that I should solve this problem hurestically or there is a reliable method for this nonconvex optimization problem?

$\endgroup$
1
  • $\begingroup$ are you missing a $b$ in the $Ax$ term? $\endgroup$
    – Suvrit
    Aug 29, 2012 at 11:40

2 Answers 2

1
$\begingroup$

You can have a look of these papers: 1. Jonathan H. Manton, Optimization algorithms exploiting unitary constraints. 2. Zaiwen Zai and Wotao Yin, A feasible method for optimization with orthogonality constraints.

Wish these studies can help you.

$\endgroup$
0
0
$\begingroup$

Conceptually, for algorithm design, the following version of the problem might be amenable to a larger number of techniques:

\begin{equation*} \min_x\quad\|Ax-b\|^2\quad\text{s.t.}\quad \|x\|_1 \le \gamma,\quad\|x\|=1. \end{equation*}

There are two reasons behind this reformulation:

  1. The objective function is now differentiable, so without further ado you can invoke the Gradient-Projection method, which under reasonable assumptions can be guaranteed to converge.
  2. This formulation makes it easy to use Alternating-Projection approaches.

Of course, several other numerical ideas also apply. For example, to get a good solution, you could start with $\gamma$ very large so that the $\ell_1$ constraint essentially disappears; then solve the problem exactly, and then gradually tighten $\gamma$.

$\endgroup$
1
  • $\begingroup$ This trick seems interesting but I have no explicit data term in misfit functional and I am solving system of homogenous equations and data term is in the A matrix. So I have problem in using Alternating-Projection approaches with no b in the misfit functional. $\endgroup$
    – user26030
    Aug 29, 2012 at 20:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.