{
"metadata": {
"name": "",
"signature": "sha256:bd9e0d5a5740c7b1c5daf4849595c714c96dbbcb68f59c51a690de295d67285f"
},
"nbformat": 3,
"nbformat_minor": 0,
"worksheets": [
{
"cells": [
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Parameters and DCP Errors"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Created by David Stonestrom 6/4/2014.\n",
"\n",
"
\n",
"The purpose of this document is to demonstrate debugging CVXPY DCP errors on a simple problem that requires parameters. \n",
"\n",
"
We will examine a toy problem: \n",
"\n",
"$$ \\textbf{maximize } f \\left( x \\right) = p^{T} \\sqrt{x} $$\n",
"$$ \\text{subject to } A x \\preceq b$$\n",
"\n",
"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."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"import cvxpy as cvx\n",
"import numpy\n",
"\n",
"n = 6; # number of variables (chosen because it can print on one line in my moniter)\n",
"m = 10; # number of constraints. These are included so that the problem is not unbounded\n",
"\n",
"# generate some constraints\n",
"numpy.random.seed(0) # for repeatibility\n",
"A = numpy.random.randn(m,n)\n",
"b = 10 * numpy.random.random([m,1])\n",
"\n",
"# and the parameter\n",
"p = cvx.Parameter(1,n)\n",
"p.value = numpy.random.random([1,n]) # returnes values in the interval [0.0, 1.0)\n",
"\n",
"x = cvx.Variable(n,1) # (n,1) will give a colum vector\n",
"\n",
"objective = cvx.Maximize(p * cvx.sqrt(x))\n",
"constraint = [A*x <= b]\n",
"problem = cvx.Problem(objective, constraint)\n",
"\n",
"# Try solving the problem. Print error if any.\n",
"try:\n",
" problem.solve()\n",
"except Exception as e:\n",
" print e"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Problem does not follow DCP rules.\n"
]
}
],
"prompt_number": 1
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Lets track down where the error comes from:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print \"objective.is_dcp(): \", objective.is_dcp()\n",
"print \"p * cvx.sqrt(x) curvature: \", (p * cvx.sqrt(x)).curvature\n",
"\n",
"print \"\\np value: \", p.value\n",
"print \"p >= 0: \", p.value >= 0\n",
"print \"sqrt(x) curvature: \", cvx.sqrt(x).curvature"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"objective.is_dcp(): False\n",
"p * cvx.sqrt(x) curvature: UNKNOWN\n",
"\n",
"p value: [[ 0.5759465 0.9292962 0.31856895 0.66741038 0.13179786 0.7163272 ]]\n",
"p >= 0: [[ True True True True True True]]\n",
"sqrt(x) curvature: CONCAVE\n"
]
}
],
"prompt_number": 2
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"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$.\n"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print \"p:\"\n",
"print \"sign property: \", p.sign\n",
"print \"value property >= 0: \", p.value >= 0\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"p:\n",
"sign property: UNKNOWN\n",
"value property >= 0: [[ True True True True True True]]\n"
]
}
],
"prompt_number": 3
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": [
"Parameters in cvxpy"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"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:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"q = cvx.Parameter(1,n,nonneg=True)\n",
"print \"q:\"\n",
"print \"sign property: \", q.sign\n",
"try:\n",
" print q.value\n",
"except Exception as e:\n",
" print e"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"q:\n",
"sign property: POSITIVE\n",
"'Parameter' object has no attribute '_value'\n"
]
}
],
"prompt_number": 4
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"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:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"negative_values = numpy.array([range(n)]) - n\n",
"print \"Values to assign to q: \", negative_values\n",
"\n",
"try:\n",
" q.value = numpy.array([range(n)]) - n\n",
"except Exception as e:\n",
" print e\n",
"\n",
"print \"\\nSetting the sign of p for cvx:\"\n",
"try: \n",
" p.sign = 'positive'\n",
"except Exception as e:\n",
" print e"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"Values to assign to q: [[-6 -5 -4 -3 -2 -1]]\n",
"Invalid sign for Parameter value.\n",
"\n",
"Setting the sign of p for cvx:\n",
"can't set attribute\n"
]
}
],
"prompt_number": 5
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"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."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"temp_p_value = p.value\n",
"p = cvx.Parameter(1,n,nonneg=True)\n",
"p.value = temp_p_value\n",
"\n",
"print p.value\n",
"print p.sign"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"[[ 0.5759465 0.9292962 0.31856895 0.66741038 0.13179786 0.7163272 ]]\n",
"POSITIVE\n"
]
}
],
"prompt_number": 6
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"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$:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"objective = cvx.Maximize(p * cvx.sqrt(x))\n",
"problem = cvx.Problem(objective, constraint)\n",
"\n",
"print \"DCP rules test: \", problem.is_dcp()\n",
"try: \n",
" print \"solving... \"\n",
" problem.solve()\n",
"except Exception as e:\n",
" print(e)\n",
"\n",
"# print some stuff\n",
"print problem.status\n",
"print \"Optimal value: \", problem.value\n",
"print \"\\nx:\\n\", x.value\n",
"print \"\\nResidual of constraints:\\n\", A.dot(x.value) - b"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"DCP rules test: True\n",
"solving... \n",
"optimal\n",
"Optimal value: 3.06352173978\n",
"\n",
"x:\n",
"[[ 0.33507522]\n",
" [ 1.86948012]\n",
" [ 1.72354918]\n",
" [ 0.29375524]\n",
" [ 0.04562196]\n",
" [ 0.8269429 ]]\n",
"\n",
"Residual of constraints:\n",
"[[ -2.39630982e-10]\n",
" [ -1.08435749e-09]\n",
" [ -1.93581055e+00]\n",
" [ -1.04169342e+01]\n",
" [ -1.29095914e+00]\n",
" [ -8.16442733e+00]\n",
" [ -4.98444003e+00]\n",
" [ -4.50631266e-09]\n",
" [ -8.60031679e+00]\n",
" [ -2.73497200e-01]]\n"
]
}
],
"prompt_number": 11
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"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. "
]
}
],
"metadata": {}
}
]
}