0
$\begingroup$

I have an optimisation problem of the form:

$$\min_x c^T x + \| V x\|^2_2 + \| D x\|^2_2 - \| W x\|^2_2$$

Subject to linear constraints.

$D$ is diagonal and $V$, $W$ are non-square matrices. I know that: $$Q = V V^T - WW^T + D^2 \succ 0$$

Ensuring convexity of the problem.

Can we rewrite this problem so that it is accepted by a DCP solver like CVXPY, while keeping inherent low-rank nature of the problem ?

$\endgroup$
3
  • $\begingroup$ Surely the solution is $x=-{1 \over 2} Q^{-1} c$? $\endgroup$
    – copper.hat
    Commented Nov 20 at 2:33
  • $\begingroup$ That would be true without the linear equality constraints. In the original post, though, don’t we need $V^\top V - W^\top W + D^2 \succ 0$ instead of the stated condition to ensure (strict) convexity? $\endgroup$
    – msantama
    Commented Nov 20 at 5:12
  • $\begingroup$ Yup exactly ! Q is (strictly) positive definite $\endgroup$
    – ADNNNNNNNNNNN
    Commented Nov 20 at 12:40

1 Answer 1

Reset to default
0
$\begingroup$

I would consider the dual problem. Suppose your linear equality constraints are given by $Ax = b$. We form the Lagrangian

$$\mathcal{L}(x, v) = c^\top x + \lVert V x \rVert_2^2 + \lVert D x \rVert_2^2 - \lVert W x \rVert_2^2 + v^\top ( Ax - b )$$

The Lagrange dual function is defined to be

$$g(v) = \min_x \mathcal{L}(x, v)$$

We can solve this minimization problem to find

$$g(v) = \mathcal{L}\left( -\frac{1}{2} Q^{-1}( c + A^{\top}v), v \right)$$

which gives rise to the dual problem $\max_v g(v)$. Lastly, by strong duality the optimal objective value of the dual problem is equal to the optimal objective value of the primal problem.

$\endgroup$
1
  • $\begingroup$ The point is that in my practical case forming $Q$ and inverting is pretty much intractable. Keeping the low rank decomposition would be way nicer. $\endgroup$
    – ADNNNNNNNNNNN
    Commented Nov 20 at 12:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .