Created by David Stonestrom 6/4/2014.
The purpose of this document is to walk through the debugging process for DCP errors in CVXPY with a very simple problem.
Problem Statement:
$$\textbf{minimize } f\left(x\right) = \sqrt{1 + ax^2} - \frac{x}{4}$$
with no constraints. Note: the optimization variable $x$ is a scalar and the parameter $a \geq 0$ is problem data. The first attempt is to just type it in and press go.
In [1]:
import cvxpy as cvx
# toy problem: minimize [sqrt(1 + a*x^2) - x/4] with parameter a > 0
x = cvx.Variable()
a = cvx.Parameter(nonneg=True)
a.value = 0.1; # Eventualy we might want a tradeoff curve for a, but that comes after we can solve at least one instance.
# normaly, I don't bother giving the objective expression its own name until things go wrong, but I'll save us some time here.
objectiveExpression = cvx.sqrt(1 + a * cvx.square(x)) - x / 4
# instead I would just encode the objective function in this line
objective = cvx.Minimize(objectiveExpression);
# let's solve the problem:
problem = cvx.Problem(objective)
# Try solving the problem. Print error if any.
try:
problem.solve()
except Exception as e:
print e
This is only easy to do with small funcitons, but I like to plot the functions which may be causing problems. In this case the only function is the objective.
In [2]:
import numpy, matplotlib.pyplot
%matplotlib inline
x = numpy.linspace(0,8,100)
matplotlib.pyplot.plot(x, numpy.sqrt(1 + a.value * x**2) - x / 4)
Out[2]:
Definitely looks convex, let's dig into the expression:
In [3]:
print(objective.is_dcp())
print(objectiveExpression.curvature)
Okay... why? First, lets check that the parameters have signs specified. Compare the declaration and results for a (defined above) and b.
In [4]:
# a = cvx.Parameter(nonneg=True) # copied from above, sign is set here
# a.value = 0.1;
print "a value: ", a.value, "\t a sign: ", a.sign
# b is only included so you can see a common problem for DCP rules
b = cvx.Parameter() # notice that sign is not set here
b.value = 3
print "b value: ", b.value, "\t b sign: ", b.sign
If a could be negative (sign NEGATIVE or UNKNOWN), the expression could be non-convex (plot it with a = -1 if you want to check this).
Since that's not the problem, let's look at the objective expression next. It first breaks apart at the '-'
In [5]:
x = cvx.Variable() # remember we changed x to linspace when plotting? now we want it back as a cvxpy variable
# objectiveExpression = cvx.sqrt(1 + a * cvx.square(x)) - x / 4 # copied from above
expression1 = cvx.sqrt(1 + a * cvx.square(x))
expression2 = - x / 4
print expression1.curvature
print expression2.curvature
So, expression1 is the problem. The outermost function there is sqrt. Its argument is $1 + a x^2$. Note that $1 + ax^2$ is the function $+$ applied to arguments $1$ and $a x^2$, so its curvature depends on its monotonicity and the curvature of cvx.square(x).
In [6]:
print("cvx.sqrt:")
print "curvature: ", cvx.sqrt(x).curvature # note that curvature is a property
print "monotonicity: ", cvx.sqrt(x).monotonicity() # but monotonicity() is a function
expression3 = (1 + a * cvx.square(x))
print "\nexpression3: ", expression3
print "curvature: ", expression3.curvature
print "monotonicity: ", expression3.monotonicity()
print("\na * cvx.square:")
print (a * cvx.square(x)).curvature
Starting from the inside: expression3 is convex since it is an affine function and it is increasing on the constant argument '1' and increasing on the convex argument 'cvx.square.'
Next we consider cvx.sqrt: It is an increasing function and the input is convex, so this seems good for convexity. The problem is that sqrt is a concave function.
Since we're pretty confident that the overall function is convex, we should start looking for different phrasings of the problematic part of the objective that will be recognized as convex by the DCP ruleset.
$$\sqrt{1 + a*x^2} = \sqrt{1^2 + \left(\sqrt{a}*x\right)^2} = \left(1^2 + \left(\sqrt{a}*x\right)^2\right)^\frac{1}{2} = \left(\left[\begin{array}{ll} 1 & \sqrt{a}*x\end{array}\right] \left[\begin{array}{c} 1 \\ \sqrt{a}*x\end{array}\right]\right)^\frac{1}{2}$$Hopefully, one of these popped out to you as $\left|\left|\left[\begin{array}{c} 1 \\ \sqrt{a}*x\end{array}\right]\right|\right|_{2}$. We can rewrite the objective to use this cvxpy defined norm, and fix the DCP issues.
In [7]:
x = cvx.Variable(2) # note x is now a vector, x[0] will be constrained to 1 and x[1] will be x from the earlier attempt
a = cvx.Parameter(nonneg=True)
a.value = 0.1;
#The following is one way of making the objective expression correct with the new vector x:
import math
b = cvx.Parameter(2,2,nonneg=True)
b.value = numpy.array([[1, 0], [0, math.sqrt(a.value)]]) # for a == 1, b is the 2x2 identity
# the 2-norm replaces the first big expression and x[1] replaces the scalar x
objectiveExpression = cvx.norm(b*x, 2) - x[1] / 4
# this constraint forces x[0] to be 1, making the new problem match the origional.
constraint = [x[0] == 1]
# I prefer this version where x[0] is constrained to be 1/sqrt(a), and the whole x vector is multiplied
# by sqrt(a) before taking the norm. Note: the constant sqrt(a) can be pulled out of the norm expression.
objectiveExpression = cvx.sqrt(a)*cvx.norm(x, 2) - x[1] / 4 # no need for the parameter b
constraint = [x[0] == 1/cvx.sqrt(a)]
# form objective
objective = cvx.Minimize(objectiveExpression);
problem = cvx.Problem(objective, constraint)
print "DCP rules test: ", problem.is_dcp()
# and solve it
try:
print "solving... "
problem.solve()
except Exception as e:
print(e)
# Print results.
print problem.status
print "Optimal value: ", problem.value
print "Full variable x: "
print x.value
print "Origional optimization variable: x =", x[1].value
This is the happy outcome for DCP errors; the objective only needed to be restated with a cvxpy built-in function to make things work. The unhappy outcome is that the problem is nonconvex and requires either relaxation or or reformulation to make cvxpy work on it. We'll dive into this in later problems.