{ "cells": [ { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "%matplotlib inline\n", "import numpy as np;\n", "from matplotlib import pyplot as plt" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$\\LaTeX \\text{ commands here}\n", "\\newcommand{\\R}{\\mathbb{R}}\n", "\\newcommand{\\im}{\\text{im}\\,}\n", "\\newcommand{\\norm}[1]{||#1||}\n", "\\newcommand{\\inner}[1]{\\langle #1 \\rangle}\n", "\\newcommand{\\span}{\\mathrm{span}}\n", "\\newcommand{\\proj}{\\mathrm{proj}}\n", "\\newcommand{\\OPT}{\\mathrm{OPT}}\n", "$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "
\n", "\n", "**Georgia Tech, CS 4540**\n", "\n", "# L14: Linear Programming Duality\n", "\n", "Jake Abernethy & Benjamin Bray\n", "\n", "*Thursday, October 17, 2019*" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Reading\n", "\n", "* Tim Roughgarden, Stanford CS261\n", " * [\"Lecture 8: Linear Programming Duality I\"](http://theory.stanford.edu/~tim/w16/l/l8.pdf)\n", " * [\"Lecture 9: Linear Programming Duality II\"](http://theory.stanford.edu/~tim/w16/l/l9.pdf) (Optional)\n", "* Jim Burke, University of Washington MATH 407\n", " * [\"Section 1: Linear Programming\"](https://sites.math.washington.edu/~burke/crs/407/notes/section1.pdf)\n", " * [\"Section 2: Simplex Algorithm\"](https://sites.math.washington.edu/~burke/crs/407/notes/section2.pdf)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$$\n", "\\begin{align}\n", "\\max_{x \\in \\R^n} &\\quad c^T x \\\\\n", "\\text{such that} &\\quad Ax \\leq b & (A \\in \\R^{m \\times n}) \\\\\n", " &\\quad x \\geq 0\n", "\\end{align}\n", "$$" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Farkas Lemma\n", "\n", "We will work towards proving the following Lemma:\n", "\n", "
\n", "Lemma. (Farkas) Let $A \\in \\R^{m \\times n}$ and $b \\in \\R^m$. Then exactly one of the following two statements is true:\n", "\n", "1. There exists $x \\in \\R^n$ such that $Ax = b$ and $x \\geq 0$.\n", "2. There exists $y \\in \\R^m$ such that $y^T A \\geq 0$ and $b^T y < 0$.\n", "
" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Problem: Farkas Lemma, Part 1\n", "\n", "
\n", "Problem: Prove that \n", "$$\n", "(\\exists\\, x \\geq 0 \\text{ s.t. } Ax = b) \\iff b \\in \\mathrm{cone}(a_1, \\dots, a_n)\n", "$$\n", "where $\\mathrm{cone}\\{ a_1, \\dots, a_n \\}$ is the set of all conic combinations of the columns of $A$.\n", "
" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Solution: Farkas Lemma, Part 1\n", "\n", "* $(\\implies)$ Suppose there is $x \\geq 0$ such that $A x = b$ and $x \\geq 0$. Since $A x$ is a linear combination of the columns of $A$ with coefficients from $x$, which has nonnegative entries, $A x = b \\in \\mathrm{cone}\\{ a_1,\\dots,a_n \\}$ by definition.\n", "* $(\\impliedby)$ Similarly, if $b \\in \\mathrm{cone}(a_1,\\dots,a_n)$, then there are coefficients $x_1,\\dots,x_n \\geq 0$ such that $b = \\sum_{k=1}^n x_1 a_1 \\in \\R^m$. Assemble the coefficients into a vector $x = (x_1,\\dots,x_n) \\in \\R^n$. Then $A x = b$." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Problem: Farkas Lemma, Part 2\n", "\n", "
\n", "Problem: (not 1 implies 2) Show that:\n", "\n", "* If there does not exist $x \\geq 0$ such that $Ax = b$...\n", "* then there exists $y \\in \\R^m$ such that $y^T A \\geq 0$ and $b^T y < 0$.\n", "
\n", "\n", "> *Hint:* Use the separating hyperplane theorem, where one set is $\\mathrm{cone}(a_1,\\dots,a_k)$." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Solution: Farkas Lemma, Part 2\n", "\n", "* Assume there is no $x \\geq 0$ such that $Ax = b$. By the previous problem, then $b \\notin \\mathrm{cone}(a_1,\\dots,a_n)$.\n", "* Notice that $y^T A = [ y^T a_1, y^T a_2, \\dots, y^T a_n ] \\in \\R^{1 \\times n}$. So, $y^T A \\geq 0$ is equivalent to:\n", "$$\n", "y^T A \\geq 0\n", "\\iff\n", "y^T a_j \\geq 0 \\quad \\forall\\, j=1,\\dots,n\n", "$$\n", "* Interpret $y$ as the normal vector to a hyperplane. So, we want to show that there is a hyperplane which separates $b \\in \\R^m$ from the columns of $A$.\n", "* By assumption, $b$ is disjoint from $\\mathrm{cone}(a_1,\\dots,a_n)$ and they are both closed sets. Use the separating hyperplane theorem to find $y \\in \\R^m$ separating $b$ from the cone. Since the columns of $A$ belong to the cone, we are done!" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Example: Solving shortest path using Linear Program\n", "\n", "Imagine you have a directed graph graph $G = (V,E)$ where each edge $e \\in E$ has some \"travel time\" $c_e$ associated with it. You have a source $t \\in V$ and a sink $s \\in V$. Formulate a linear program that solves the \"continuous flow\" version of shortest path! Does not need to be in standard form." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Recall: Linear Program in Standard Form\n", "\n", "
\n", "\\begin{align}\n", "\\max_{x \\in \\R^n} &\\quad c^T x \\\\\n", "\\text{such that} &\\quad Ax \\leq b & \\text{(only $\\leq$ constraints)} \\\\\n", " &\\quad x \\geq 0 & \\text{(variables nonnegative)}\n", "\\end{align}\n", "
\n", "\n", "* Decision variables $x \\in \\R^n$\n", "* Linear objective $c^T x$ for $c \\in \\R^n$\n", "* Constraint matrix $A \\in \\R^{m \\times n}$ and vector $b \\in \\R^m$. Each row corresponds to a constraint." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Recall: Geometric Intuition\n", "\n", "* Linear constraints correspond to half-spaces, so the **feasible region** is a polytope.\n", "* Level sets of the objective are parallel hyperplanes, all orthogonal to the coefficient vector $c$.\n", "* The optimum is the farthest vector in the feasible region along the direction $c$.\n", "* For bounded feasible regions, a solution always exists at a vertex.\n", "\n", "![](images/l6-lpexample.png)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Recall: Combinations of Constraints\n", "\n", "If $y = (y_1,\\dots,y_m) \\geq 0$, then $y^T A$ is a nonnegative linear combination of the constraints (the rows of $A$). Look for combinations of constraints that **dominate** the objective,\n", " $$\n", " y^T A = \\sum_{k=1}^m y_k a_k^T \\geq c^T \\implies c^T x \\leq y^T A x \\leq y^T b\n", " $$\n", " \n", "This is an upper bound on the value of the objective function!\n", " \n", "> *Note: People usually write $A^T y \\geq c$, which is equivalent.*" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Recall: Dual Linear Program\n", "\n", "The **dual linear program** searches for the *best* or *tightest* upper bound by looking at all possible combinations of constraints which dominate the objective:\n", "\n", "
\n", "$$\n", "\\begin{align}\n", "\\min_{y \\in \\R^m} &\\quad y^T b \\\\\n", "\\text{such that} &\\quad y^T A \\geq c^T & \\text{(dominates objective)} \\\\\n", " &\\quad y \\geq 0 & \\text{(nonnegative combinations)}\n", "\\end{align}\n", "$$\n", "
\n", "\n", "* The $y=(y_1,\\dots,y_m) \\in \\R^m$ are called **dual variables**.\n", " * (in contrast to **primal variables** $x \\in \\R^n$)\n", "* The new constraint matrix is $A^T \\in \\R^{n \\times m}$.\n", " * One dual constraint per primal variable (if primal was in standard form)." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Weak Duality\n", "\n", "Using the \"tightest upper bound\" interpretation of the dual linear program, it is clear that **weak duality** holds:\n", "\n", "
\n", "Theorem: The optimal value for any (maximization) linear program is no larger than the value of the corresponding dual program, that is, $$\\OPT(Primal) \\leq \\OPT(Dual)$$\n", "
\n", "\n", "* The value of every primal-feasible point is no larger than the value of any dual-feasible point.\n", "* If the optimal value of $Primal$ is unbounded, then $Dual$ is infeasible.\n", "* If the optimal value of $Dual$ is unbounded, then $Primal$ is infeasible." ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Problem: Checking Optimality\n", "\n", "Recall that a feasible solution $x \\in \\R^n$ to *Primal* is called **optimal** if no other feasible solution has a higher objective value.\n", "\n", "
\n", "Problem: Suppose $x \\in \\R^n$ is primal-feasible and $y \\in \\R^m$ is dual-feasible. Prove that if $c^T x = y^T b$, then both $x$ and $y$ are optimal in their respective linear programs. (Hint: Weak Duality)\n", "
" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "**Solution:** Assume towards contradiction that $x' \\in \\R^n$ has a higher objective value, $c^T x' > c^T x$. Then $c^T x' > y^T b$. But since $y$ is dual feasible, this contradicts weak duality!" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Recall: Activity Analysis Problem\n", "\n", "A company has $m$ different resources which can be used to manufacture $n$ different products.\n", "\n", "* $x = (x_1,\\dots,x_n) \\in \\R^n$ is the amount of each product manufactured\n", "* $r = (r_1,\\dots,r_m) \\in \\R^m$ is the supply of each resource\n", "* $c = (c_1,\\dots,c_n) \\in \\R^n$ is the profit generated by each product\n", "* $A = [a_{ij}] \\in \\R^{m \\times n}$, where $a_{ij}$ is the amount of resource $i$ needed to make product $j$\n", "\n", "
\n", "$$\\max_{x \\in \\R^n} \\quad c^T x \\quad\n", "\\text{s.t.} \\quad A x \\leq r \\quad\\text{and}\\quad x \\geq 0$$\n", "
" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Problem: Interpreting the Dual\n", "\n", "
\n", "Problem: Write down the dual linear program for the activity analysis problem. What \"units\" do the dual variables need have? How can they be interpreted?\n", "
\n", "\n", "> If it helps, assume the amount of each resource available is measured in *kilograms*, and our profit is measured in *euros* €. Maybe we're manufacturing rope, so the amount of each product is measured in *meters*." ] } ], "metadata": { "celltoolbar": "Slideshow", "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.3" } }, "nbformat": 4, "nbformat_minor": 4 }