{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "***\n", "# Problem Sheet 4 Part A - Solutions\n", "***\n", "$\\newcommand{\\vct}[1]{\\mathbf{#1}}$\n", "$\\newcommand{\\mtx}[1]{\\mathbf{#1}}$\n", "$\\newcommand{\\e}{\\varepsilon}$\n", "$\\newcommand{\\norm}[1]{\\|#1\\|}$\n", "$\\newcommand{\\minimize}{\\text{minimize}\\quad}$\n", "$\\newcommand{\\maximize}{\\text{maximize}\\quad}$\n", "$\\newcommand{\\subjto}{\\quad\\text{subject to}\\quad}$\n", "$\\newcommand{\\R}{\\mathbb{R}}$\n", "$\\newcommand{\\trans}{T}$\n", "$\\newcommand{\\ip}[2]{\\langle {#1}, {#2} \\rangle}$\n", "$\\newcommand{\\zerovct}{\\vct{0}}$\n", "$\\newcommand{\\diff}[1]{\\mathrm{d}{#1}}$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Solution to Problem 4.1" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The data for the first linear programming problem is\n", "\n", "\\begin{equation*}\n", " \\mtx{A} = \\begin{pmatrix} 1 & 1\\\\ 1 & -1\\\\ -1 & 0\\end{pmatrix}, \\quad\n", " \\vct{b} = \\begin{pmatrix} 2\\\\1\\\\1 \\end{pmatrix}, \\quad\n", " \\vct{c} = \\begin{pmatrix} 1\\\\2\\end{pmatrix}.\n", "\\end{equation*}\n", "\n", "The minors are\n", "\n", "\\begin{equation*}\n", " \\mtx{A}_{\\{1,2\\}} = \\begin{pmatrix} 1 & 1 \\\\ 1&-1 \\end{pmatrix}, \\ \n", " \\mtx{A}_{\\{1,3\\}} = \\begin{pmatrix} 1 & 1 \\\\ -1&0 \\end{pmatrix}, \\\n", " \\mtx{A}_{\\{2,3\\}} = \\begin{pmatrix} 1 & -1 \\\\ -1&0 \\end{pmatrix}.\n", "\\end{equation*}\n", "\n", "The minors are all invertible, so that the corresponding systems of linear equations $\\mtx{A}_I\\vct{x}=\\vct{b}_I$ have unique solutions, given by\n", "\n", "\\begin{equation*}\n", " \\vct{x}_{\\{1,2\\}} = \\begin{pmatrix} 1.5\\\\0.5\\end{pmatrix}, \\ \n", " \\vct{x}_{\\{1,3\\}} = \\begin{pmatrix} -1\\\\3\\end{pmatrix}, \\\n", " \\vct{x}_{\\{2,3\\}} = \\begin{pmatrix} -1\\\\-2\\end{pmatrix}.\n", "\\end{equation*}\n", "\n", "One easily verifies that each of these solutions also satisfies the remaining inequality, so that they are indeed vertices. This can also easily be seen by drawing the resulting polyhedron as intersection of halfspaces, as in the figure.\n", "\n", "\n", "\n", "The objective values $\\ip{\\vct{c}}{\\vct{x}}$ at these points are\n", "\n", "\\begin{equation*}\n", " \\ip{\\vct{c}}{\\vct{x}_{\\{1,2\\}}} = 2.5, \\ \\ip{\\vct{c}}{\\vct{x}_{\\{1,3\\}}} = 5, \\ \\ip{\\vct{c}}{\\vct{x}_{\\{2,3\\}}} = -5.\n", "\\end{equation*}\n", "\n", "The optimal point is therefore $\\vct{x}_{\\{1,3\\}}=(-1,3)^{\\trans}$. We can also verify this using CVXPY as follows." ] }, { "cell_type": "code", "execution_count": 17, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Optimal solution found: [[-1. 3.]]\n", "Optimal value: 4.99999999538\n" ] } ], "source": [ "import numpy as np\n", "import cvxpy as cvx\n", "\n", "n = 2\n", "A = np.array([[1, 1], \n", " [1,-1],\n", " [-1,0]])\n", "b = np.array([2,1,1])\n", "c = np.array([1,2])\n", "\n", "x = cvx.Variable(n)\n", "constraints = [A*x <= b]\n", "obj = cvx.Maximize( cvx.sum_entries(c*x) )\n", "prob = cvx.Problem(obj, constraints)\n", "prob.solve()\n", "\n", "print \"Optimal solution found: \", x.value.transpose()\n", "print \"Optimal value: \", prob.value" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Finally, we write down the dual problem\n", "\n", "\\begin{equation*}\n", " \\minimize \\ip{\\vct{b}}{\\vct{y}} \\quad \\subjto \\mtx{A}^{\\trans}\\vct{y}=\\vct{c}, \\ \\vct{y}\\geq \\zerovct.\n", "\\end{equation*}\n", "\n", "In our case,\n", "\n", "\\begin{align*}\n", " \\minimize & 2y_1+y_2+y_3\\\\\n", " \\subjto & y_1+y_2-y_3= 1\\\\\n", " & y_1-y_2=2\\\\\n", " & y_i\\geq 0, \\ 1\\leq i\\leq 3.\n", "\\end{align*}\n", "\n", "For the second optimization problem, we begin by sketching the feasible set; this will make it easier to identify the vertices. \n", "\n", "\\begin{equation*}\n", " \\mtx{A} = \\begin{pmatrix} -1 & 1\\\\1 & 1\\\\1 & 2\\\\ 1 & 0\\\\ -1 & 0\\\\ 0 & -1\\end{pmatrix}, \\quad\n", " \\vct{b} = \\begin{pmatrix} 2\\\\8\\\\10\\\\4\\\\0\\\\0 \\end{pmatrix}, \\quad\n", " \\vct{c} = \\begin{pmatrix} 1\\\\1\\end{pmatrix}.\n", "\\end{equation*}\n", "\n", "\n", "\n", "What we see from the sketch is that we can get rid of inequality 2 altogether, as it doesn't contribute to the polyhedron. Among the other inequalities, any two non-parallel lines intersect and therefore give rise to a non-singular minor, but there are only\n", "five of these pairs that give rise to points *in* $P$, and therefore define vertices. These vertices are\n", "\n", "\\begin{equation*}\n", " \\vct{x}_{\\{5,6\\}}=(0,0)^{\\trans}, \\ \\vct{x}_{\\{1,5\\}} = (0,2)^{\\trans}, \\ \\vct{x}_{\\{1,3\\}} = (2,4)^{\\trans}, \\ \\vct{x}_{\\{3,4\\}} = (4,3)^{\\trans}, \\ \\vct{x}_{\\{4,6\\}} = (4,0)^{\\trans}.\n", "\\end{equation*}\n", "\n", "Evaluating the objective functions on these gives the values (in the order of the vertices given above)\n", "\n", "\\begin{equation*}\n", " 0, \\ 2, \\ 6, \\ 7, \\ 4.\n", "\\end{equation*}\n", "\n", "As seen in the sketch, the optimal value is attained at $\\vct{x}_{\\{3,4\\}}=(4,3)^{\\trans}$." ] }, { "cell_type": "code", "execution_count": 18, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Optimal solution found: [[ 4. 3.]]\n", "Optimal value: 6.9999999987\n" ] } ], "source": [ "import numpy as np\n", "import cvxpy as cvx\n", "\n", "n = 2\n", "A = np.array([[-1, 1], \n", " [ 1,-1],\n", " [ 1, 2],\n", " [ 1, 0],\n", " [-1, 0],\n", " [ 0,-1]])\n", "b = np.array([2,8,10,4,0,0])\n", "c = np.array([1,1])\n", "\n", "x = cvx.Variable(n)\n", "constraints = [A*x <= b]\n", "obj = cvx.Maximize( cvx.sum_entries(c*x) )\n", "prob = cvx.Problem(obj, constraints)\n", "prob.solve()\n", "\n", "print \"Optimal solution found: \", x.value.transpose()\n", "print \"Optimal value: \", prob.value" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Finally, the dual problem is given by\n", "\n", "\\begin{align*}\n", " \\minimize & 2y_1+8y_2+10y_3+4y_4\\\\\n", " \\subjto & -1y_1+y_2+y_3+y_4-y_5=1\\\\\n", " & y_1+y_2+2y_3-y_6=1\\\\\n", " & y_i\\geq 0, \\ 1\\leq i\\leq 6.\n", "\\end{align*}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Solution to Problem 4.2" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ " Set\n", " \n", "\\begin{equation*}\n", " \\mu := \\max_{\\vct{x}\\in P} \\ip{\\vct{c}}{\\vct{x}}.\n", "\\end{equation*}\n", "\n", "Then the set $H\\cap P$, with $H=\\{\\vct{x}\\in \\R^n\\mid \\ip{\\vct{x}}{\\vct{c}}=\\mu\\}$ is a face of $P$, and this is itself a bounded polyhedron (just add the equation $\\ip{\\vct{c}}{\\vct{x}}=\\mu$ to the equations for $P$). As a bounded polyhedron, it is the convex hull of its vertices. What remains to be seen is that the vertices of $P\\cap H$ are also vertices of $P$. \n", "So assume $\\vct{x}$ is a vertex of $P\\cap H$ but not of $P$. Then there exist points $\\vct{y},\\vct{z}\\in P$, with (say) $\\vct{y}\\not\\in H$, such that $\\vct{x}$ lives on the line segment joining $\\vct{y}$ and $\\vct{z}$. But this would mean that $\\vct{x}\\not\\in H$, as otherwise the whole line segment would be in $H$. It follows that $\\vct{x}$ is a vertex of $P$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Solution to Problem 4.3" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The first step is to rewrite the problem as a linear programming one,\n", "\n", "\\begin{align*}\n", "\\minimize & t_1+\\cdots +t_n\\\\\n", "\\subjto & -t_1\\leq x_1\\leq t_1\\\\\n", "& \\cdots\\\\\n", "& -t_n\\leq x_n\\leq t_n\\\\\n", "& t_i\\geq 0, \\ 1\\leq i\\leq n.\n", "\\end{align*}\n", "\n", "Note that there are now $2n$ variables, the $t_i$ and the $x_j$, collected in vectors $\\vct{t}$ and $\\vct{x}$. Writing this problem in the form\n", "\n", "\\begin{equation*}\n", " \\maximize \\ip{\\vct{c}}{\\vct{z}}, \\quad \\subjto \\mtx{A}'\\vct{z}\\leq \\vct{b}',\n", "\\end{equation*}\n", "\n", "with $\\vct{z}=(\\vct{t},\\vct{x})$, we see that the matrix $\\mtx{A}'$ and the vectors $\\vct{b}'$ and $\\vct{c}$ are given by\n", "\n", "\\begin{equation*}\n", " \\mtx{A}' = \\begin{pmatrix} \n", " -\\mtx{1} & -\\mtx{1}\\\\\n", " -\\mtx{1} & \\mtx{1}\\\\\n", " -\\mtx{1} & \\zerovct\\\\\n", " \\zerovct & \\mtx{A}\\\\\n", " \\zerovct & -\\mtx{A}\n", " \\end{pmatrix}, \\ \n", " \\vct{b}' = \\begin{pmatrix}\n", " \\zerovct\\\\ \\zerovct \\\\ \\zerovct \\\\ \\vct{b} \\\\ -\\vct{b}\n", " \\end{pmatrix}, \\\n", " \\vct{c} = \\begin{pmatrix}\n", " -\\vct{e}\\\\ \\zerovct\n", " \\end{pmatrix},\n", "\\end{equation*}\n", "\n", "were again $\\vct{e}$ denotes the vector consisting of only $1$'s.\n", "The dual has the form\n", "\n", "\\begin{equation*}\n", " \\minimize \\ip{\\vct{b'}}{\\vct{y}'} \\ \\subjto \\mtx{A}'^{\\trans}\\vct{y}' =\\vct{c}, \\ \\vct{y}'\\geq \\zerovct.\n", "\\end{equation*}\n", "\n", "Writing $\\vct{y}'=(\\vct{y}_1,\\vct{y}_2,\\vct{y}_3,\\vct{y}_4,\\vct{y}_5)$, where the blocks correspond to the block-rows of $\\mtx{A}'$, we can write the dual as\n", "\n", "\\begin{align*}\n", " \\minimize & \\ip{\\vct{b}}{\\vct{y}_4-\\vct{y}_5}\\\\\n", " \\subjto & -(\\vct{y}_1+\\vct{y}_2+\\vct{y}_3) = -\\vct{e}\\\\\n", " & -\\vct{y}_1+\\vct{y}_2 +\\mtx{A}^{\\trans}(\\vct{y}_4-\\vct{y}_5) = \\zerovct\\\\\n", " & \\vct{y}_i\\geq \\zerovct, \\ 1\\leq i\\leq 5.\n", "\\end{align*}\n", "\n", "Set $\\vct{y}=\\vct{y}_4-\\vct{y}_5$. From the first equality and the inequalities, we get that the entries of $\\vct{y}_i$, for $1\\leq i\\leq 3$, are between $0$ and $1$, so that $\\vct{y}_1-\\vct{y}_2$ have entries between $-1$ and $1$. This means that we have the equivalence for the second condition\n", "\n", "\\begin{equation*}\n", " \\mtx{A}^{\\trans}\\vct{y} = \\vct{y}_1-\\vct{y}_2 \\Leftrightarrow \\norm{\\mtx{A}^{\\trans}\\vct{y}}_\\infty \\leq 1. \n", "\\end{equation*}\n", "\n", "The whole dual optimization problem can therefore be written as\n", "\n", "\\begin{align*}\n", " \\minimize & \\ip{\\vct{b}}{\\vct{y}}\\\\\n", " \\subjto & \\norm{\\mtx{A}^{\\trans}\\vct{y}}_\\infty\\leq 1.\n", "\\end{align*}\n", "\n", "Note that the $\\infty$-norm that appears in the constraints is the dual norm of the $1$-norm that appears in the objective of the original problem.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Solution to Problem 4.4" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Suppose that there exists a nonzero $\\vct{x}\\geq \\zerovct$ such that $\\mtx{A}\\vct{x}=\\sum_{i=1}^n x_i\\vct{a}_i=\\zerovct$, where the $\\vct{a}_i$ are the rows of $\\mtx{A}$. Now if there was a $\\zerovct\\neq \\vct{y}\\in \\R^m$ such that $\\mtx{A}^{\\trans}\\vct{y}>0$, then $\\ip{\\vct{a}_i}{\\vct{y}}>0$ for all $1\\leq i\\leq n$, so that\n", "\n", "\\begin{equation*}\n", " 0 =\\ip{\\vct{0}}{\\vct{y}} = \\sum_{i=1}^n x_i \\ip{\\vct{a}_i}{\\vct{y}} >0,\n", "\\end{equation*}\n", "\n", "which is absurd. Therefore, such a $\\vct{y}$ does not exist. Now assuming there is $\\vct{y}$ with $\\mtx{A}^{\\trans}\\vct{y}>0$, then, for all nonzero $\\vct{x}\\geq \\zerovct$,\n", "\n", "\\begin{equation*}\n", " \\ip{\\vct{x}}{\\mtx{A}^{\\trans}\\vct{y}} = \\ip{\\mtx{A}\\vct{x}}{\\vct{y}} \\neq 0, \n", "\\end{equation*}\n", "\n", "which shows that $\\mtx{A}\\vct{x}\\neq \\zerovct$ for all such $\\vct{x}$. \n", "\n", "For the geometric interpretation, consider the following two diagrams.\n", "\n", "\n", "\n", "The interpretation is that either the columns of $\\mtx{A}$, $\\vct{a}_1,\\dots,\\vct{a}_n$, are all on one side of a hyperplane, or $\\zerovct$ can be written as convex combination of the $\\vct{a}_i$. \n", "\n" ] } ], "metadata": { "anaconda-cloud": {}, "kernelspec": { "display_name": "Python [conda root]", "language": "python", "name": "conda-root-py" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 2 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython2", "version": "2.7.12" } }, "nbformat": 4, "nbformat_minor": 0 }