Search code examples
pythonmathematical-optimizationcvxpyconvex-optimization

Matrix-based CVXPY quadratic program not DCP

cvxpy supports matrix-based expressions, but seems to not recognise them as quadratic programs.

Here's a super-simple example:

import cvxpy
Pi = cvxpy.Variable((10, 5))

objective = cvxpy.Minimize( cvxpy.trace(Pi.T @ Pi) )
problem = cvxpy.Problem(objective)
problem.solve()

Trace(Pi.T @ Pi) is just the sum of squares of entries of Pi (so convex/quadratic etc.), yet I get this exception:

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

Am I doing something wrong, or is this how it is?

This is a super-simple example, I'm trying to solve something more complex, but perhaps this is the simplest place to start. I'm using cvxpy version 1.1.1 .

Solution

  • cvxpy has a DCP ruleset to be able to prove things by construction. As the general problem of deciding convexity is NP-hard, there are of course limitations on what (or how efficient) this language can express.

    Sometimes you just need to provide more structure.

    Rule number 1:

    In your case:

    • norm(X, “nuc”)
      • the root should probably be irrelevant in your case