# non convex optimization

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?

-
are you missing a $b$ in the $Ax$ term? –  Suvrit Aug 29 '12 at 11:40

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.

-
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:

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

-
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