3
$\begingroup$

I'm attempting to solve a convex optimization problem where one of the constraints is

$$\|M\|_* \leq a$$

where $\|M\|_*$ denotes the nuclear norm of matrix $M$. I'm using CVXOPT in Python to solve this as a linear program (LP), but the nuclear norm (sum of singular values) isn't a nice linear constraint. How can I formulate this?

Improve this question
$\endgroup$
5
  • $\begingroup$ Your link is not really a linear-programming approach but still a more generalized optimization of some convex problem (therefore IPM-based). I also don't think there is nice-working approach (in practice) to do this within linear-programming. What is the motivation? Bad performance because of the SDP-formulation? Or other reasons? If it's about bad performance, you can always try the SCS solver. (side-note: i think cvxpy is much nicer to use than cvxopt; but maybe you need the more accessible customization possible within cvxopt) $\endgroup$
    – sascha
    Apr 21 '17 at 16:40
  • $\begingroup$ We're attempting to implement Algorithm 1 from this paper. I haven't done a lot with convex optimization, so my apologies if I'm not thinking about this the right way. Everything else is a linear constraint, so I was hoping to fit it within that framework. $\endgroup$
    – Pterosaur
    Apr 21 '17 at 17:12
  • $\begingroup$ This work is not really ready for large-scale, at least without complex customized optimization algorithms. I think it's easy to implement using cvxpy and you can solve it with ecos or scs. But don't expect much performance. But the paper is more about the theory and ignores the real-world performance it seems. (It's very very far away from LP; as i indicated above; and the convex, but non-linear constraint is the core of this approach) $\endgroup$
    – sascha
    Apr 21 '17 at 17:57
  • $\begingroup$ We're not too worried about optimization here; this is a course project. Now it seems like we can get the nuclear norm in the constraints but can't figure out how to set the objective function as the inner product within cvxpy. $\endgroup$
    – Pterosaur
    Apr 21 '17 at 18:15
  • $\begingroup$ Is it not just trace(AB^t). Well... cvxpy's docs are good and there is also the issue-tracker on github with some questions already answered. $\endgroup$
    – sascha
    Apr 21 '17 at 18:36
3
$\begingroup$

Quoting Michael Grant [MG'14]:

The nuclear norm inequality $\|X\|_*\leq y$ is satisfied if and only if there exist symmetric matrices $W_1$, $W_2$ satisfying

$$\begin{bmatrix} W_1 & X \\ X^T & W_2 \end{bmatrix} \succeq 0, ~ \mathop{\textrm{Tr}}W_1 + \mathop{\textrm{Tr}}W_2 \leq 2 y$$

Here, $\succeq 0$ should be interpreted to mean that the $2\times 2$ block matrix is positive semidefinite. Because of this transformation, you can handle nuclear norm minimization or upper bounds on the nuclear norm in any semidefinite programming setting.

Note that CVXOPT has a semidefinite programming (SDP) solver.

[MG'14] Michael Grant, Derivative of the nuclear norm with respect to its argument, Mathematics Stack Exchange, March 2014.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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