0
$\begingroup$

I have a sparse optimization problem of the form:

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

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

is positive definite. Ensuring convexity of the problem, but optimizing with dense matrix $Q$ is very slow.

Can we rewrite this problem so that it is accepted by a DCP solver like CVXPY, while keeping sparse structure of the problem ?

PS: problem also includes some constraints, so is non-quadratic

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

Unless you have some funny constraints on $x$ this is a linear problem that can be solved with the conjugate gradient solver:

$$\underbrace{(D^TD+V^TV-W^TW)}_{Q}x = -\frac{1}{2}c.$$

Implement the multiplication $Qx$ as $Qx = y+z-w$ where $y=D^TDx$, $z=V^TVx$, $w=W^TWx$, where each of those is implemented as a sparse multiplication, e.g., $w = W^Tw_0$ where $w_0 = Wx$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ It does include some constraints, I updated the description to reflect this $\endgroup$
    – ADNNNNNNNNNNN
    Commented Nov 20 at 17:22
  • $\begingroup$ @ADNNNNNNNNNNN Can you write down the constraints of the problem? $\endgroup$
    – lightxbulb
    Commented Nov 20 at 17:23
  • $\begingroup$ Plenty! - linear constraints of the type $$x^T v_i \leq f_i$$ as well some quadratic ones $$ x^T \Sigma_i x \leq q_i $$ and also some L1 like $$ \| x \|_1 \leq l $$ CVXPY handles all of that pretty easily. The goal now would be to add this new term $$ -\| W x\|_2^2 $$ on top of these $\endgroup$
    – ADNNNNNNNNNNN
    Commented Nov 20 at 18:53
  • $\begingroup$ @ADNNNNNNNNNNN The only thing for cvxpy on matrix-free methods I found is this: web.stanford.edu/~boyd/papers/abs_ops.html $\endgroup$
    – lightxbulb
    Commented Nov 20 at 19:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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