Tuesday, June 27, 2023

CVXPY DCP errors

CVXPY is a popular tool to model and solve convex optimization problems. Sometimes, it throws a "DCP" error, even for convex problems. DCP stands for Disciplined Convex Programming, the underlying framework for working with guaranteed convex models. The error says: I can not verify this is convex.  

Here are some small examples of convex objectives (under minimization) one would expect to work.


ObjectiveCVXPY codeResultNotes
\[\color{darkred}x^T \color{darkred}x\]x.T@xDCP errorprint shows minimize x@x, i.e. transpose is dropped
\[\color{darkred}x^T \color{darkred}x\]x@xDCP error
\[\color{darkred}x^T \color{darkred}x\]cp.sum_squares(x)transformed into quad_over_lin(x, 1.0)
\[\color{darkred}x^T \color{darkblue}Q \color{darkred}x\]x.T@Q@xtransformed into QuadForm(x,Q)
\[\color{darkred}y:=\color{darkred}x-\color{darkblue}p\]\[\color{darkred}x^T \color{darkblue}Q \color{darkred}y\]y=x-p
x.T@Q@y
DCP error
\[\color{darkred}x^T \color{darkblue}Q \color{darkred}x - \color{darkred}x^T \color{darkblue}Q \color{darkblue}p\]x.T@Q@x - x.T@Q@pfirst term transformed into QuadForm(x,Q)

Not everything makes sense to me. I am not sure why x.T@x is not properly recognized, but x.T@Q@x is.

Here is the code I used for experimentation:


import cvxpy as cp
import numpy as np

n = 5
x = cp.Variable(n, "x", nonneg=True)

Q = np.eye(n)
p = np.ones(n)

obj = x.T @ x  # not DCP ??? Print says x @ x
#obj = x @ x    # not DCP
#obj = cp.sum_squares(x)  # transformed into quad_over_lin(x, 1.0)
#obj = x.T @ Q @ x  # transformed into QuadForm(x,Q)

y = x-p
#obj = x.T @ Q @ y # not DCP
#obj = x.T @ Q @ x - x.T @ Q @ p # accepted

prob = cp.Problem(cp.Minimize(obj), [sum(x)==1])
print(prob)
result = prob.solve(verbose=True)

We can use: x = cp.Variable((n,1), "x", nonneg=True).  This would generate an \((n\times 1)\) matrix. The printed model now shows the correct objective (with the transpose): minimize x.T @ x. But still, we are getting:

DCPError: Problem does not follow DCP rules. Specifically:
The objective is not DCP. Its following subexpressions are not:
x.T @ x 

I suspect this is interpreted as \(\color{darkred}x^T\color{darkred}y\), i.e., as two possibly different vectors. Just a guess. Of course, the workarounds are obvious: use cp.sum_squares(x), or use \(\color{darkred}x^T \color{darkblue}I \color{darkred}x\). I think, not being able to recognize \(\color{darkred}x^T\color{darkred}x\) as convex, can be classified as a bug.

No comments:

Post a Comment