non convex optimization - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T16:51:55Z http://mathoverflow.net/feeds/question/105767 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/105767/non-convex-optimization non convex optimization unknown (google) 2012-08-28T21:46:30Z 2012-08-29T11:40:00Z <p>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?</p> http://mathoverflow.net/questions/105767/non-convex-optimization/105799#105799 Answer by leslie for non convex optimization leslie 2012-08-29T07:29:57Z 2012-08-29T07:29:57Z <p>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.</p> <p>Wish these studies can help you. </p> http://mathoverflow.net/questions/105767/non-convex-optimization/105816#105816 Answer by S. Sra for non convex optimization S. Sra 2012-08-29T11:40:00Z 2012-08-29T11:40:00Z <p>Conceptually, for algorithm design, the following version of the problem might be amenable to a larger number of techniques:</p> <p>\begin{equation*} \min_x\quad\|Ax-b\|^2\quad\text{s.t.}\quad \|x\|_1 \le \gamma,\quad\|x\|=1. \end{equation*}</p> <p>There are two reasons behind this reformulation:</p> <ol> <li>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.</li> <li>This formulation makes it easy to use Alternating-Projection approaches.</li> </ol> <p>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$.</p>