MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
are you missing a $b$ in the $Ax$ term? – Suvrit Aug 29 '12 at 11:40
up vote 1 down vote accepted

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.

share|cite|improve this answer
Thanks for these papers. – user26030 Aug 29 '12 at 20:01

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$.

share|cite|improve this answer
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. – user26030 Aug 29 '12 at 20:00

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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