How to solve the following non-convex optimization problem?

Question

$$\min \|X\|_{*}+u\|Ax-b\|_2^2+v\|Cx\|_2^2 + wx^THx$$

where $x$ is vec($X$), $u,v$. is constant, H is a symmetric matrix，but it is not semidefinite.

Is there any software to do this? Can the software cvx solve it?

Answer 1

I believe the non-convexity prevents you from actually solving it efficiently, but you can get close using the well known convex-concave procedure. Using eigenvalue decomposition, the symmetric matrix $H$ can be decomposed into $H = P+N$, such that $P$ is positive semidefinite and $N$ is negative definite. According to this, the problem becomes: $$ \min ||X||_* + u||Ax - b||_2^2 + v||Cx||_2^2 + w x^T P x + w x^T N x $$ Everything except the last term is convex, and the last term, $w x^T N x$, is concave.

Then, you approximate the concave part using a linear function. Meaning, you perform the following iterative algorithm: $$ X^{(k+1)} = \operatorname*{argmin}_X \{ ||X||_* + u||Ax - b||_2^2 + v||Cx||_2^2 + w x^T P x + w x^T N x^{(k)} \} $$ Each iteration, of course, requires solving another optimization problem. But this problem is convex and I believe you can find plenty of algorithms for solving it.