{
"metadata": {
"name": "",
"signature": "sha256:21ca62c8754564686ce9b77ba97605c6383bef9a290ad53d69ff7dd9c7ae3588"
},
"nbformat": 3,
"nbformat_minor": 0,
"worksheets": [
{
"cells": [
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Solver Errors in CVXPY"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"David Stonestrom 6/4/2014\n",
"\n",
"
\n",
"Writing a tutorial that demonstrates dealing with solver errors is tricky because the people who write/maintain the solvers are constantly updating the solvers to deal with known issues. There is a solid chance that by the time you are reading this the code below will no longer generate errors. However, the notes which accompany the code are still the correct procedure for handling solver errors. As of the time of this writing, the exact problem below resulted in three different outcomes depending on which solver was used. The problem is:\n",
"\n",
"$$ \\textbf{maximize } f\\left(x\\right) = p^{T}\\sqrt{x}$$\n",
"\n",
"$$\\text{subject to } Ax \\preceq b$$\n",
"\n",
"
\n",
"where $A$ is one row and has one negative entry and $p \\succeq 0$. The negative entry in $A$ makes the problem unbounded, so the correct solution is:\n",
"\n",
"objective value: inf\n",
"\n",
"status: unbounded\n"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"import cvxpy as cvx\n",
"import numpy\n",
"\n",
"n = 6; \n",
"m = 1; \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",
"p = cvx.Parameter(1,n,nonneg=True)\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",
"print \"A: \", A\n",
"print \"b: \", b\n",
"print \"p: \", p.value"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"A: [[ 1.76405235 0.40015721 0.97873798 2.2408932 1.86755799 -0.97727788]]\n",
"b: [[ 4.37587211]]\n",
"p: [[ 0.891773 0.96366276 0.38344152 0.79172504 0.52889492 0.56804456]]\n"
]
},
{
"output_type": "stream",
"stream": "stderr",
"text": [
"/Users/stevend2/anaconda/envs/cvxpy/lib/python2.7/site-packages/ecos-1.0.4-py2.7-macosx-10.5-x86_64.egg/_ecos.py:3: UserWarning: Module cvxpy was already imported from /Users/stevend2/anaconda/envs/cvxpy/lib/python2.7/site-packages/cvxpy-0.2.0-py2.7.egg/cvxpy/__init__.pyc, but /Users/stevend2/PythonProjects/cvxpy/examples/notebooks is being added to sys.path\n"
]
}
],
"prompt_number": 1
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": [
"ECOS"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"try:\n",
" print problem.solve(solver = cvx.ECOS) # the default\n",
" print problem.status\n",
"except Exception as e:\n",
" print e"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"None\n",
"solver_error\n"
]
}
],
"prompt_number": 2
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"This is the classic solver error outcome. The objective is 'None' and the status is 'solver_error.' Note that it did not raise an exception. \n",
"\n",
"When this happens, the next step is to just try the other available solvers to see what they do."
]
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": [
"CVXOPT"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"try:\n",
" print problem.solve(solver=cvx.CVXOPT)\n",
" print problem.status\n",
"except Exception as e:\n",
" print e"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"math domain error\n"
]
}
],
"prompt_number": 3
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Using CVXOPT throws an exception: 'math domain error.' This will probably be rolled into the solver_error case above at some point. \n",
"\n",
"SCS is the only solver left to try."
]
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": [
"SCS"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"try:\n",
" print problem.solve(solver=cvx.SCS)\n",
" print problem.status\n",
"except Exception as e:\n",
" print e"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"2082.01956591\n",
"optimal\n"
]
}
],
"prompt_number": 4
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Here the numerical imprecision of SCS lets it find an optimal value. Note the printed objective value: 2082. Compare it to the numpy computed objective for the optimal value of x below:"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print \"numpy calculated objective value:\", p.value.dot(numpy.sqrt(x.value))"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"numpy calculated objective value: [[ 2322.27407977]]\n"
]
}
],
"prompt_number": 5
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The two values differ by over 10%. Next is a demonstration of a better feasible point."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print \"SCS objective value: \", p.value.dot(numpy.sqrt(x.value))\n",
"print \"SCS constraint violation: \", A.dot(x.value) - b\n",
"\n",
"x_better = x.value + [[0],[0],[9900000],[0],[0],[10000000]]\n",
"print \"\\nHigher objective and lower constraint violation:\"\n",
"print \"objective: \", p.value.dot(numpy.sqrt(x_better))\n",
"print \"constraint violation: \", A.dot(x_better) - b"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"SCS objective value: [[ 2322.27407977]]\n",
"SCS constraint violation: [[ 0.00387292]]\n",
"\n",
"Higher objective and lower constraint violation:\n",
"objective: [[ 4672.30778292]]\n",
"constraint violation: [[-83272.75224437]]\n"
]
}
],
"prompt_number": 6
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Another problem"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Compare the above results to the following unbounded problem which ECOS solves corectly.\n",
"\n",
"$$ \\textbf{maximize } f\\left(x\\right) = \\sum_{i=1}^{6}\\sqrt{x_i}$$"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"x = cvx.Variable(6)\n",
"problem = cvx.Problem(cvx.Maximize(cvx.sum(cvx.sqrt(x))))\n",
"\n",
"try:\n",
" print \"ECOS:\\n\", problem.solve(solver=cvx.ECOS)\n",
" print problem.status\n",
" print \"\\nSCS:\\n\", problem.solve(solver=cvx.SCS)\n",
" print problem.status\n",
" print \"\\nCVXOPT:\\n\", problem.solve(solver=cvx.CVXOPT)\n",
" print problem.status\n",
" \n",
"except Exception as e:\n",
" print \"Error Error Error\"\n",
" print e\n"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"ECOS:\n",
"inf\n",
"unbounded\n",
"\n",
"SCS:\n",
"3257.630475\n",
"optimal\n",
"\n",
"CVXOPT:\n",
"Error Error Error"
]
},
{
"output_type": "stream",
"stream": "stdout",
"text": [
"\n",
"math domain error\n"
]
}
],
"prompt_number": 7
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The takeaway from all of this is to try all the solvers and make sure that you believe the answer they give. One of the important pieces of this is manually testing the constraint violations and objective value. Also consider what the value of the objective and variables are saying about the origional problem. \n",
"\n",
"Finally, please keep in mind that this is an open source project and is provided \"as is\" with no guarintee of correctness. "
]
}
],
"metadata": {}
}
]
}