{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "***\n", "# Lecture 10 - A First Algorithm for Linear Programming\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}}$\n", "$\\newcommand{\\conv}{\\operatorname{conv}}$\n", "$\\newcommand{\\inter}{{\\operatorname{int}}}$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "So far we have seen aspects of the geometry of linear programming, discussed the feasible sets (polyhedra) and presented a useful duality theorem:\n", "the optimal value of\n", "\n", "\\begin{equation*}\\tag{P}\n", " \\maximize \\ip{\\vct{c}}{\\vct{x}} \\ \\subjto \\mtx{A}\\vct{x}\\leq \\vct{b}\n", "\\end{equation*}\n", "\n", "coincides with the optimal value of\n", "\n", "\\begin{equation*}\\tag{D}\n", " \\minimize \\ip{\\vct{b}}{\\vct{y}} \\ \\subjto \\mtx{A}^{\\trans}\\vct{y}=\\vct{c}, \\ \\vct{y}\\geq \\zerovct,\n", "\\end{equation*}\n", "\n", "provided both (P) and (D) have a finite solution. \n", "\n", "We now turn attention to algorithms for linear programming. We present the main idea behind the classical Simplex Algorithm and then discuss the more modern class of Interior Point Algorithms in more detail. The latter can be shown to be efficient in a very precise sense (polynomial time) and generalize to non-linear convex optimization." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "## 10.1 A first algorithm for linear programming\n", "---" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "For $\\mtx{A}\\in \\R^{m\\times n}$ and $\\vct{b}\\in \\R^m$ let $P=\\{\\vct{x}\\in \\R^n\\mid \\mtx{A}\\vct{x}\\leq \\vct{b}\\}$ be the polyhedron of feasible points for (P). Recall that a vertex of $P$ is a zero-dimensional face of $P$, or equivalently, a point that cannot be written as convex combination of two distinct points of $P$.\n", "\n", "If the optimization problem (P) has a solution, then it can be shown (Problem Set 4) that there exists a vertex $\\vct{x}^*$ such that\n", "\n", "\\begin{equation*}\n", " \\max_{\\vct{x}\\in P} \\ip{\\vct{c}}{\\vct{x}} = \\ip{\\vct{c}}{\\vct{x}^*}.\n", "\\end{equation*}\n", "\n", "Intuitively this is clear by looking at a picture, as in the figure below: Move a hyperplane orthogonal to the objective $\\vct{c}$ along this direction to the highest level that still intersects a polyhedron $P$, and try to imagine that this intersection *does not* contain a vertex. \n", "\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This crucial observation turns linear programming into a *finite* problem: we only have to test the objective function on the finite set of vertices to determine the maximizer. \n", "We have also seen (Problem Set 3) that the vertices can be identified as the solutions of the systems of equations\n", "\n", "\\begin{equation*}\n", " \\mtx{A}_I\\vct{x}=\\vct{b}_I,\n", "\\end{equation*}\n", "\n", "for which $\\mtx{A}_I$ has full rank and $\\vct{x}\\in P$,\n", "where $I\\subset \\{1,\\dots,m\\}$ is a subset of indices with $|I|=d$, and $\\mtx{A}_I,\\vct{b}_I$ are the matrix and vector arising from $\\mtx{A}$ and $\\vct{b}$ by taking the rows indexed by $I$. This gives a first primitive algorithm for solving the optimization problem (P). " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Example 10.1 ** Consider the linear programming problem\n", " \n", " \\begin{align*}\n", " \\maximize &x_1-3x_2 \\\\\n", " \\subjto &0.5x_1+x_2\\leq 1\\\\\n", " &x_1+0.5x_2\\leq 1\\\\\n", " &-x_1\\leq 0\\\\\n", " &-x_2\\leq 0\\\\\n", " &x_1\\leq 1\n", " \\end{align*}\n", " \n", " " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The matrix $\\mtx{A}$ and vectors $\\vct{b}$ and $\\vct{c}$ are\n", "\n", "\\begin{equation*}\n", " \\mtx{A} = \\begin{pmatrix}\n", " 0.5 & 1\\\\ \n", " 1 & 0.5\\\\\n", " -1 & 0\\\\\n", " 0 & -1\\\\\n", " 1 & 0\n", " \\end{pmatrix},\n", "\\quad \\vct{b} = \\begin{pmatrix}\n", " 1\\\\ 1 \\\\ 0 \\\\ 0 \\\\ 1\n", " \\end{pmatrix},\n", " \\quad\n", " \\vct{c} = \\begin{pmatrix}\n", " 1 \\\\ -3\n", " \\end{pmatrix}.\n", "\\end{equation*}\n", "\n", "We see that the minor $\\mtx{A}_{\\{3,5\\}}=\\begin{pmatrix} -1 & 0\\\\ 1 & 0\\end{pmatrix}$, corresponding to the two parallel hyperplanes $x_1=0$ and $x_1=1$, is singular and does not define a vertex, while all other minors are invertible. For the minor $I=\\{1,2\\}$, $\\mtx{A}_I\\vct{x}=\\vct{b}_I$ has the form\n", "\n", "\\begin{align*}\n", " 0.5x_1+x_2 & = 1\\\\\n", " x_1+0.5x_2 & = 1,\n", "\\end{align*}\n", "\n", "which has the solution $\\vct{x}=(2/3,2/3)^{\\trans}$. Since $\\vct{x}$ also satisfies all the other inequalities, it is a vertex. In a similar fashion we can find all the vertices as the points\n", "\n", "\\begin{equation*}\n", " \\vct{x}_1 = \\begin{pmatrix} 2/3\\\\ 2/3\\end{pmatrix}, \\ \\vct{x}_2 = \\begin{pmatrix} 1\\\\ 0\\end{pmatrix}, \\ \\vct{x}_3 = \\begin{pmatrix} 0\\\\ 1\\end{pmatrix}, \\ \\vct{x}_4 = \\begin{pmatrix} 0\\\\ 0\\end{pmatrix}.\n", "\\end{equation*}\n", "\n", "The values of the objective function at these vertices are\n", "\n", "\\begin{equation*}\n", " \\ip{\\vct{c}}{\\vct{x}_1} = -\\frac{4}{3}, \\ \\ip{\\vct{c}}{\\vct{x}_2} = 1, \\ \\ip{\\vct{c}}{\\vct{x}_3} = -3, \\ \\ip{\\vct{c}}{\\vct{x}_4} = 0.\n", "\\end{equation*}\n", "\n", "It follows that the optimization problem has the optimal value $1$ at $\\vct{x}^*=(1,0)^{\\trans}$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Unfortunately, this method requires solving up to $\\binom{m}{n}$ systems of linear equations, which can be exponential in $n$ in the worst case, making this method not practical. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Example 10.2 **\n", "Consider the hypercube\n", "\\begin{align*}\n", " -1&\\leq x_1\\leq 1\\\\\n", " &\\cdots\\\\\n", " -1&\\leq x_n\\leq 1.\n", "\\end{align*}\n", "It has $2^n$ vertices that need to be checked. Even though there are so many vertices, one can travel along edge between any two vertices in at most $n$ steps." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The simplex algorithm is a way to search through the vertices in a more clever way than just listing all of them. The idea is to start with a vertex and see if there is a vertex connected to it by an edge that has a bigger objective value. If not, we are done. If there is a neighbouring vertex, we move there and continue the process. We keep walking along the vertices of the feasible polytope until we find an optimal one.\n", "\n", "\n", "\n", "The simplex algorithm is one of the most successful algorithms around and usually very fast, even though there examples that show that its worst case running time can be exponential." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "## 10.2 An optimality condition\n", "---" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Recall again the primal/dual pair of linear programming problems,\n", "\n", "\\begin{equation*}\\tag{P}\n", " \\maximize \\ip{\\vct{c}}{\\vct{x}} \\ \\subjto \\mtx{A}\\vct{x}+\\vct{s}= \\vct{b}, \\ \\vct{s}\\geq \\zerovct\n", "\\end{equation*}\n", "\n", "and\n", "\n", "\\begin{equation*}\\tag{D}\n", " \\minimize \\ip{\\vct{b}}{\\vct{y}} \\ \\subjto \\mtx{A}^{\\trans}\\vct{y}=\\vct{c}, \\ \\vct{y}\\geq \\zerovct,\n", "\\end{equation*}\n", "\n", "where we reformulated the primal version to include a set of **slack variables** $\\vct{s}$.\n", "\n", "A useful consequence of the duality theorem is a characterisation of solution tuples $(\\vct{x}^*,\\vct{s}^*,\\vct{y}^*)$. Note that for such an optimal pair,\n", "\n", "\\begin{equation*}\n", " \\ip{\\vct{y}^*}{\\vct{b}} = \\ip{\\vct{c}}{\\vct{x}^*} = \\ip{\\mtx{A}^{\\trans}\\vct{y}^*}{\\vct{x}^*} = \\ip{\\vct{y}^*}{\\mtx{A}\\vct{x}^*},\n", "\\end{equation*}\n", "\n", "where the first equality holds because of the duality theorem. From this we conclude\n", "\n", "\\begin{equation*}\\tag{PD}\n", " \\ip{\\vct{y}^*}{\\vct{b}-\\mtx{A}\\vct{x}^*}=\\ip{\\vct{y}^*}{\\vct{s}^*}=0.\n", "\\end{equation*}\n", "\n", "Since $\\vct{y}^*\\geq \\zerovct$ and $\\vct{s}^*\\geq \\zerovct$, each summand in (PD) is zero. This means that the individual components of $\\mtx{A}\\vct{x}^*-\\vct{b}$ and $\\vct{y}^*$ satisfy\n", "\n", "\\begin{equation*}\n", " y^*_i \\cdot s^*_i = 0, \\ 1\\leq i\\leq m.\n", "\\end{equation*}\n", "\n", "In words, whenever an inequality in (P) is an equality at a maximizer $\\vct{x}^*$, the corresponding component in the *dual* minimizer is zero.\n", "Summarising, we have the following {\\em optimality conditions} for linear programming:\n", "if vectors $(\\vct{x},\\vct{s},\\vct{y})$ are primal/dual optimal solutions to a linear programming problem, then\n", "\n", "\\begin{align*}\\tag{OPT}\n", " \\mtx{A}\\vct{x}+\\vct{s}-\\vct{b} & = \\zerovct\\\\\n", " \\mtx{A}^{\\trans}\\vct{y}-\\vct{c} & = \\zerovct\\\\\n", " y_is_i &= 0, \\ 1\\leq i\\leq m\\\\\n", " \\vct{y}& \\geq \\zerovct\\\\\n", " \\vct{s}& \\geq \\zerovct.\n", "\\end{align*}\n", "\n", "Just as the optimality condition $\\nabla f(\\vct{x})=\\zerovct$ serves as the basis for algorithms for unconstraint optimization, the optimality conditions for linear programming form the basis of the simplex method and of interior point methods. In the simplex method, the conditions are used to verify whether a candidate vertex is an optimal points, while primal/dual interior point methods view (OPT) as a multivariate function in $(\\vct{x},\\vct{s},\\vct{y})$ for which a root satisfying the inequality constraints is sought using Newton's method or similar algorithms.\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "outputs": [], "source": [] } ], "metadata": { "anaconda-cloud": {}, "kernelspec": { "display_name": "Python [conda env:py27]", "language": "python", "name": "conda-env-py27-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 }