Skip to content

Instantly share code, notes, and snippets.

@chrisdembia

chrisdembia/pa4p1.ipynb

Created February 7, 2014 19:53
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save chrisdembia/8870472 to your computer and use it in GitHub Desktop.
Save chrisdembia/8870472 to your computer and use it in GitHub Desktop.
Download ZIP
pa4p1.ipynb
Display the source blob
Display the rendered blob
Raw
pa4p1.ipynb
{
"metadata": {
"name": "",
"signature": "sha256:416b6b13a26e78fd8c831b4370593f408e336229fb61646588d79e06ea57b7ce"
},
"nbformat": 3,
"nbformat_minor": 0,
"worksheets": [
{
"cells": [
{
"cell_type": "code",
"collapsed": false,
"input": [
"from cvxpy import *\n",
"from numpy import matlib\n",
"import numpy as np"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 53,
"trusted": true
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": [
"Problem formulation"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"n = 2\n",
"n_constr = 3\n",
"u1 = -2\n",
"u2 = -3\n",
"x = Variable(n)\n",
"P = matlib.mat([[ 1, -0.5],\n",
" [-0.5, 2 ]])\n",
"q = matlib.mat([[-1],\n",
" [ 0]])\n",
"A = matlib.mat([[1, 2],\n",
" [1, -4],\n",
" [5, 76]])\n",
"b = matlib.mat([[u1],\n",
" [u2],\n",
" [ 1]])\n",
"objective = Minimize(quad_form(x, P) + q.T * x)\n",
"constraints = [A * x <= b]"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 56,
"trusted": true
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Part a"
]
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": [
"Solve"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"problem = Problem(objective, constraints)\n",
"optimal_value = problem.solve(solver=CVXOPT)\n",
"print optimal_value"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"8.2222221529\n"
]
}
],
"prompt_number": 124,
"trusted": true
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": [
"Primal variable values"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print x.value"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"[-2.33e+00]\n",
"[ 1.67e-01]\n",
"\n"
]
}
],
"prompt_number": 73,
"trusted": true
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": [
"Dual variable values"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"constraint = constraints[0]\n",
"y = constraints[0].dual_value\n",
"print y"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"[ 1.14e+00]\n",
"[ 3.99e+00]\n",
"[ 1.40e-01]\n",
"\n"
]
}
],
"prompt_number": 75,
"trusted": true
},
{
"cell_type": "heading",
"level": 3,
"metadata": {},
"source": [
"KKT conditions"
]
},
{
"cell_type": "heading",
"level": 4,
"metadata": {},
"source": [
"$f_i(\\tilde{x}) \\leq 0$"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"(matlib.mat((A * x - b).value) <= 0).all()"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 90,
"text": [
"False"
]
}
],
"prompt_number": 90,
"trusted": true
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"print (A * x - b).value"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"[-1.41e-08]\n",
"[ 7.01e-09]\n",
"[-3.03e-07]\n",
"\n"
]
}
],
"prompt_number": 91,
"trusted": true
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"UH OH!!! Unsatisifed."
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"matlib.mat((A * x - b).value) <= 0"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 78,
"text": [
"matrix([[ True],\n",
" [False],\n",
" [ True]], dtype=bool)"
]
}
],
"prompt_number": 78,
"trusted": true
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"$h_i(\\tilde{x}) = 0$"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"True # there are no equality constraints"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 79,
"text": [
"True"
]
}
],
"prompt_number": 79,
"trusted": true
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"$\\lambda_i \\geq 0$"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"(matlib.mat(y) >= 0).all()"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 80,
"text": [
"True"
]
}
],
"prompt_number": 80,
"trusted": true
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"$\\tilde{\\lambda}_i f_i(\\tilde{x}) = 0$"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"(np.abs(np.multiply(y, (A * x - b).value)) < 1e-7).all()"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 85,
"text": [
"True"
]
}
],
"prompt_number": 85,
"trusted": true
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"(np.abs(np.multiply(y, (A * x - b).value)) < 1e-8).all()"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 84,
"text": [
"False"
]
}
],
"prompt_number": 84,
"trusted": true
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"$\\nabla f_0 (\\tilde{x}) + \\sum_{i=1}^m \\tilde{\\lambda}_i \\nabla f_i(\\tilde{x}) + \\sum_{i=1}^p \\tilde{\\nu}_i \\nabla h_i(\\tilde{x}) = 0$"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"gradx = (2 * P * x + q).value + A.T * matlib.mat(y)"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 120,
"trusted": true
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"(np.abs(matlib.mat(gradx)) < 1e-3).all()"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 121,
"text": [
"True"
]
}
],
"prompt_number": 121,
"trusted": true
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"(np.abs(matlib.mat(gradx)) < 1e-4).all()"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 122,
"text": [
"False"
]
}
],
"prompt_number": 122,
"trusted": true
},
{
"cell_type": "heading",
"level": 2,
"metadata": {},
"source": [
"Part b"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"def optimal_value_prediction(delta):\n",
" return optimal_value - y.T * delta"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 126,
"trusted": true
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"delta_values = [0, -0.1, 0.1]\n",
"\n",
"for delta1 in delta_values:\n",
" for delta2 in delta_values:\n",
" delta = matlib.mat([[delta1],\n",
" [delta2],\n",
" [0]])\n",
" optimal_value_exact = Problem(objective, [A * x <= (b + delta)]).solve()\n",
" prediction = optimal_value_prediction(delta)\n",
" inequality_holds = prediction <= optimal_value_exact\n",
" print '% .1f % .1f % 5f % 5f %s' % (delta1, delta2,\n",
" prediction,\n",
" optimal_value_exact,\n",
" inequality_holds[0, 0])\n",
" print '--------------------------------------'"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
" 0.0 0.0 8.222222 8.222222 False\n",
" 0.0 -0.1 8.621193 8.706387 True\n",
" 0.0 0.1 7.823251 7.980000 True\n",
"--------------------------------------\n",
"-0.1 0.0 8.336372 8.565000 True\n",
"-0.1 -0.1 8.735343 8.815555 True\n",
"-0.1 0.1 7.937402 8.318887 True\n",
"--------------------------------------\n",
" 0.1 0.0 8.108072 8.222222 True\n",
" 0.1 -0.1 8.507043 8.706387 True\n",
" 0.1 0.1 7.709101 7.751526 True\n",
"--------------------------------------\n"
]
}
],
"prompt_number": 150,
"trusted": true
}
],
"metadata": {}
}
]
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment