## non convex optimization

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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? – S. Sra Aug 29 at 11:40

## 2 Answers

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. – unknown (google) Aug 29 at 20:01

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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

-

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. – unknown (google) Aug 29 at 20:00
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 5, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8861281871795654, "perplexity_flag": "middle"}