Created by David Stonestrom 6/4/2014.
The purpose of this document is to demonstrate debugging CVXPY DCP errors on a simple problem that requires parameters.
We will examine a toy problem:
where $x \in \mathbb{R}^n$ is the variable and $p \in \mathbb{R}^{n}_{+}$, $A \in \mathbb{R}^{m \times n}$, and $b \in \mathbb{R}^m$ are the problem data. Note that $f \left( x \right)$ is concave if and only if $p$ is non-negative.
In [1]:
import cvxpy as cvx
import numpy
n = 6; # number of variables (chosen because it can print on one line in my moniter)
m = 10; # number of constraints. These are included so that the problem is not unbounded
# generate some constraints
numpy.random.seed(0) # for repeatibility
A = numpy.random.randn(m,n)
b = 10 * numpy.random.random([m,1])
# and the parameter
p = cvx.Parameter(1,n)
p.value = numpy.random.random([1,n]) # returnes values in the interval [0.0, 1.0)
x = cvx.Variable(n,1) # (n,1) will give a colum vector
objective = cvx.Maximize(p * cvx.sqrt(x))
constraint = [A*x <= b]
problem = cvx.Problem(objective, constraint)
# Try solving the problem. Print error if any.
try:
problem.solve()
except Exception as e:
print e
Lets track down where the error comes from:
In [2]:
print "objective.is_dcp(): ", objective.is_dcp()
print "p * cvx.sqrt(x) curvature: ", (p * cvx.sqrt(x)).curvature
print "\np value: ", p.value
print "p >= 0: ", p.value >= 0
print "sqrt(x) curvature: ", cvx.sqrt(x).curvature
According to the printout above, the objective is not DCP because the curvature is UNKNOWN. However, we can see that it is a positive sum $\left( p \geq 0 \right)$ of concave functions $\left( \sqrt{x_i} \right)$. This should be concave by the DCP rules. To find the disconnect between those rules and the code, we'll look more into the parameter $p$.
In [3]:
print "p:"
print "sign property: ", p.sign
print "value property >= 0: ", p.value >= 0
Here we see that the parameter's sign property is UNKNOWN. This is true even with all the values set to positive numbers. It turns out that cvxpy depends on the sign property not the value property. Compare $p$ above to the parameter $q$ defined below:
In [4]:
q = cvx.Parameter(1,n,nonneg=True)
print "q:"
print "sign property: ", q.sign
try:
print q.value
except Exception as e:
print e
Even without a value assigned, the sign property can be set for a parameter. Lets look at assigning negative values to $q$ and telling CVXPY that $p$ has positive sign:
In [5]:
negative_values = numpy.array([range(n)]) - n
print "Values to assign to q: ", negative_values
try:
q.value = numpy.array([range(n)]) - n
except Exception as e:
print e
print "\nSetting the sign of p for cvx:"
try:
p.sign = 'positive'
except Exception as e:
print e
So CVXPY protects against invalid (sign, value) pairs by enforcing the sign when the value is input and not allowing the sign to be changed except on parameter creation. This means that we will need to remake the parameter $p$ in order to solve the origional problem.
In [6]:
temp_p_value = p.value
p = cvx.Parameter(1,n,nonneg=True)
p.value = temp_p_value
print p.value
print p.sign
Now we have a parameter with the same values as before and with the sign parameter set to positive. Lets try solving the problem with this $p$:
In [11]:
objective = cvx.Maximize(p * cvx.sqrt(x))
problem = cvx.Problem(objective, constraint)
print "DCP rules test: ", problem.is_dcp()
try:
print "solving... "
problem.solve()
except Exception as e:
print(e)
# print some stuff
print problem.status
print "Optimal value: ", problem.value
print "\nx:\n", x.value
print "\nResidual of constraints:\n", A.dot(x.value) - b
So that's it; all it needed was to tell cvxpy that the parameter has a positive sign. When $p$ is a NumPy array or a CVXPY parameter with sign 'UNKNOWN,' CVXPY does not check the signs of the actual floats for the DCP test. If those signs matter, it is up to the user to specify them as part of the parameter declaration. On the other hand, $A$ and $b$ were left as NumPy arrays because their signs are not important to the convexity of any expresions.