{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "***\n", "# Lecture 9 - Linear Programming Duality\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": [ "Linear programming duality associates to a linear programming problem a **dual problem**, with the property that the optimal values of the original and of the dual problem coincide. Duality is an important tool in applications and in the design of algorithms. Linear programming duality rests upon an important family of results in convex geometry, known collectively as Farkas' Lemma.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "## 9.1 Farkas' Lemma\n", "---" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Recall the definition of a convex cone. This is a set $C$ such that for all $\\vct{x},\\vct{y}\\in C$ and $\\lambda_1,\\lambda_2\\geq 0$ we have $\\lambda_1\\vct{x}+\\lambda_2\\vct{y}\\in C$. \n", "\n", "**Lemma 9.1 ** (Hyperplane separation for cones)\n", " Let $C\\neq \\R^n$ be a closed convex cone and $\\vct{z}\\not\\in C$. Then there exists a linear hyperplane such that $C\\subseteq H_-$ and $\\vct{z}\\in \\inter H_+$.\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Proof. ** From Lecture 7 we know that there exists an affine hyperplane $H^{a}$ separating $C$ and $\\vct{z}$. Let this affine hyperplane be given by \n", " $\\ip{\\vct{a}}{\\vct{x}}=b$.\n", " We would like to show that $H=\\{\\vct{x}\\mid \\ip{\\vct{a}}{\\vct{x}}=0\\}$ is a linear hyperplane separating $C$ and $\\vct{z}$.\n", " From $\\ip{\\vct{a}}{\\vct{z}}>b$ we clearly get $\\ip{\\vct{a}}{\\vct{z}}>0$. Also, $\\vct{0}\\in H_-$, since $\\ip{\\vct{a}}{\\vct{0}}=0$. Assume now that there exists a point $\\vct{x}\\in C$ such that $\\ip{\\vct{a}}{\\vct{x}}=c>0$. Since $C$ is a cone, for all $\\lambda>0$ we have that $\\lambda\\vct{x}\\in C$. Choosing $\\lambda$ so that $\\lambda>b/c$ we get \n", " \n", " \\begin{equation*}\n", " \\ip{\\vct{a}}{\\lambda\\vct{x}}=\\lambda c>b,\n", " \\end{equation*}\n", "\n", "in contradiction to $C\\subset H^a_-$. This shows that $H$ is a linear separating hyperplane." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Theorem 9.2 ** (Farkas' Lemma)\n", "Given a matrix $\\mtx{A}\\in \\R^{m\\times n}$ and $\\vct{b}\\in \\R^m$, there\n", " exists a vector $\\vct{x}$ such that\n", " \n", " \\begin{equation*}\n", " \\mtx{A}\\vct{x}=\\vct{b}, \\quad \\vct{x}\\geq 0\n", " \\end{equation*}\n", " \n", "if and only if there is not $\\vct{y}\\in \\R^m$ such that\n", "\n", "\\begin{equation*}\n", " \\mtx{A}^{\\trans}\\vct{y}\\geq \\zerovct, \\quad \\ip{\\vct{y}}{\\vct{b}}<0. \n", " \\end{equation*}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Proof. **\n", "Assume $\\mtx{A}\\vct{x}=\\vct{b}$ has a solution $\\vct{x}\\geq 0$. Then for any $\\vct{y}\\neq \\zerovct$ such that $\\mtx{A}^{\\trans}\\vct{y}\\geq \\zerovct$,\n", "\n", "\\begin{equation*}\n", " 0\\leq \\ip{\\mtx{A}^{\\trans}\\vct{y}}{\\vct{x}}=\\ip{\\vct{y}}{\\mtx{A}\\vct{x}}=\\ip{\\vct{y}}{\\vct{b}},\n", "\\end{equation*}\n", "\n", "which shows that $\\mtx{A}^{\\trans}\\vct{y}\\geq \\zerovct$ and $\\ip{\\vct{y}}{\\vct{b}}<0$ are not simultaneously possible. \n", "\n", "Assume now that $\\mtx{A}\\vct{x}=\\vct{b}$ has no solution that satisfies $\\vct{x}\\geq 0$. Let $\\vct{a}_1,\\dots,\\vct{a}_n$ be the columns of $\\mtx{A}$. The set of $\\mtx{A}\\vct{x}$ for $\\vct{x}\\geq \\zerovct$ is the set\n", " of all nonnegative linear combinations\n", "\n", "\\begin{equation*}\n", " C=\\{\\vct{z}\\in \\R^m \\mid \\vct{z} = x_1\\vct{a}_1+\\cdots +x_n\\vct{a}_n, \\ x_i\\geq 0\\},\n", " \\end{equation*}\n", "\n", "and this set is a convex cone. The assumption that there is no nonnegative $\\vct{x}$ such that $\\mtx{A}\\vct{x}=\\vct{b}$ means that $\\vct{b}\\not\\in C$. By Lemma 1, there exists a linear hyperplane $H=\\{\\vct{x} \\mid \\ip{\\vct{y}}{\\vct{x}}=0\\}$ such that $C\\in H_-$ and $\\vct{b}\\in \\inter H_+$. Formulated differently, there exists a $\\vct{y}\\in \\R^m$ such that\n", "\n", "\\begin{equation*}\n", " \\forall \\vct{z}\\in C\\colon \\ip{\\vct{z}}{\\vct{y}}\\geq 0, \\quad \\ip{\\vct{b}}{\\vct{y}}<0.\n", "\\end{equation*}\n", "\n", "Since every $\\vct{z}\\in C$ has the form $\\vct{z}=\\sum_{i=1}^n x_i \\vct{a}_i$ with $x_i\\geq 0$, the relation\n", "\n", "\\begin{equation*}\n", " \\ip{\\vct{z}}{\\vct{y}} = \\sum_{i=1}^n x_i\\ip{\\vct{a}_i}{\\vct{y}}\\geq 0\n", "\\end{equation*}\n", "\n", "for all $\\vct{x}\\geq 0$ is equivalent to the condition that $\\ip{\\vct{a}_i}{\\vct{y}}\\geq 0$ for $1\\leq i\\leq n$, which again is equivalent to $\\mtx{A}^{\\trans}\\vct{y}\\geq \\zerovct$. This concludes the proof." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The following consequence is perhaps a more familiar form of Farkas' Lemma.\n", "\n", "**Corollary 9.3 ** (Farkas 2) Given a matrix $\\mtx{A}\\in \\R^{m\\times n}$ and $\\vct{b}\\in \\R^m$, there exists a vector $\\vct{x}\\neq \\zerovct$ such that \n", "\n", " \\begin{equation*}\n", " \\mtx{A}\\vct{x}\\leq \\vct{b}\n", " \\end{equation*}\n", "\n", "if and only there is no $\\vct{y}$ such that\n", "\n", "\\begin{equation*}\n", " \\vct{y}\\geq \\zerovct, \\quad \\vct{A}^{\\trans}\\mtx{y}=\\zerovct, \\quad \\ip{\\vct{y}}{\\vct{b}}<0.\n", "\\end{equation*}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Proof. ** Consider the matrix\n", " \n", " \\begin{equation*}\n", " \\mtx{A}' := \n", " \\begin{pmatrix}\n", " \\mtx{A} & -\\mtx{A} & \\mtx{I}\n", " \\end{pmatrix},\n", " \\end{equation*}\n", " \n", " where $\\mtx{I}$ is the $m\\times m$ identity matrix. A nonnegative solution of $\\mtx{A}'\\vct{x}'=\\vct{b}$ has the form $\\vct{x}'=(\\vct{x}_1,\\vct{x}_2,\\vct{x}_3)^{\\trans}$, and implies $\\mtx{A}(\\vct{x}_1-\\vct{x}_2)+\\vct{x}_3 = \\vct{b}$. Therefore, such a solution $\\vct{x}'$ exists if and only if the system\n", " \n", " \\begin{equation*}\n", " \\mtx{A}\\vct{x}\\leq \\vct{b}\n", " \\end{equation*}\n", "\n", "has a solution. Applying Farkas' Lemma, the complementary condition is \n", "\n", "\\begin{equation*}\n", " \\mtx{A}'^{\\trans}\\vct{y}\\geq \\zerovct, \\quad \\ip{\\vct{b}}{\\vct{y}}<0,\n", "\\end{equation*}\n", "\n", "which in terms of $\\mtx{A}$ translates to \n", "\n", "\\begin{equation*}\n", " \\mtx{A}^{\\trans}\\vct{y}=\\zerovct, \\quad \\vct{y}\\geq 0, \\quad \\ip{\\vct{b}}{\\vct{y}}<0.\n", "\\end{equation*}\n", "\n", "This concludes the proof." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "One more important corollary will be given without proof.\n", "\n", "**Corollary 9.4 ** (Farkas 3)\n", " Let $\\mtx{A}\\in \\R^{m\\times n}$ and $\\vct{b}\\in \\R^m$. Then for $\\delta>0$ and every vector $\\vct{x}\\in \\R^n$ with $\\mtx{A}\\vct{x}\\leq \\vct{b}$, $\\ip{\\vct{c}}{\\vct{x}}\\leq \\delta$ holds if and only if there exists $\\vct{y}\\in \\R^m$ such that\n", " \\begin{equation*}\n", " \\vct{y}\\geq \\zerovct, \\quad \\mtx{A}^{\\trans}\\vct{y}=\\vct{c}, \\quad \\ip{\\vct{y}}{\\vct{b}}\\leq \\delta.\n", " \\end{equation*}\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "---\n", "## 9.2 Linear programming duality\n", "---" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "After studying the feasible sets of linear programming, the polyhedra, we now return to linear programming itself, in the form\n", "\n", "\\begin{equation*}\n", " \\maximize \\ip{\\vct{c}}{\\vct{x}} \\ \\subjto \\mtx{A}\\vct{x}\\leq \\vct{b}.\n", "\\end{equation*}\n", "\n", "Geometrically this amounts to moving the hyperplane orthogonal to $\\vct{c}$ to the highest level along $\\vct{c}$, under the condition that it still intersects $P=\\{\\vct{x}\\mid \\mtx{A}\\vct{x}\\leq \\vct{b}\\}$. \n", "\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The famous duality theorem for linear programming states that if the maximum exists, then it coincides with the solution of a *dual* linear programming problem.\n", "\n", "**Theorem 9.5 ** (Duality)\n", "Let $\\mtx{A}\\in \\R^{m\\times n}$, $\\vct{b}\\in \\R^m$ and $\\vct{c}\\in \\R^n$. Then\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", "The problem (P) is called the *primal* problem, and (D) the *dual* problem.\n", "\n", "**Example 9.6 ** Consider the simple problem\n", " \n", " \\begin{equation*}\n", " \\maximize x_1 \\ \\subjto x_1+x_2\\leq 1, x_1\\geq 0, x_2\\geq 0.\n", " \\end{equation*}\n", "\n", "The dual problem is\n", "\n", "\\begin{equation*}\n", " \\minimize y_1 \\ \\subjto y_1-y_2=1, y_1-y_3=0, y_1\\geq 0, y_2\\geq 0, y_3\\geq 0. \n", "\\end{equation*}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "For the proof we need the following observation.\n", "\n", "**Lemma 9.7 **\n", " Let $P\\subset \\R^n$ be a polyhedron and $\\vct{c}\\in \\R^n$ such that $\\sup_{\\vct{x}\\in P}\\ip{\\vct{c}}{\\vct{x}}$ is finite. Then the supremum is attained, that is, it is a maximum.\n", "\n", "**Proof of Theorem 9.5 **\n", " Let $P=\\{\\vct{x}\\mid \\mtx{A}\\vct{x}\\in \\vct{b}\\}$ and $D=\\{\\vct{y}\\in \\R^m\\mid \\mtx{A}^{\\trans}\\vct{y}=\\vct{c}, \\vct{y}\\geq \\zerovct\\}$. If $\\vct{x}\\in P$ and $\\vct{y}\\in Q$, then\n", " \n", " \\begin{equation*}\n", " \\ip{\\vct{c}}{\\vct{x}} = \\ip{\\mtx{A}^{\\trans}\\vct{y}}{\\vct{x}} = \\ip{\\vct{y}}{\\mtx{A}\\vct{x}}\\leq \\ip{\\vct{y}}{\\vct{b}},\n", " \\end{equation*}\n", "\n", "so that in particular\n", "\n", "\\begin{equation*}\n", " \\max_{\\vct{x}\\in P}\\ip{\\vct{c}}{\\vct{x}}\\leq \\min_{\\vct{y}\\in Q}\\ip{\\vct{b}}{\\vct{y}},\n", "\\end{equation*}\n", "\n", "which shows one inequality. To show the other inequality, set $\\delta = \\max_{\\vct{x}\\in P} \\ip{\\vct{c}}{\\vct{x}}$. By definition, if $\\mtx{A}\\vct{x}\\leq \\vct{b}$, then $\\ip{\\vct{c}}{\\vct{x}}\\leq \\delta$. By Corollary 9.4, there exists a vector $\\vct{y}\\in \\R^m$ such that\n", "\n", "\\begin{equation*}\n", " \\vct{y}\\geq \\zerovct, \\quad \\mtx{A}^{\\trans}\\vct{y}=\\vct{c}, \\quad \\ip{\\vct{b}}{\\vct{y}}\\leq \\delta.\n", "\\end{equation*}\n", "\n", "In particular,\n", "\n", "\\begin{equation*}\n", " \\min_{\\vct{y}\\in Q} \\ip{\\vct{b}}{\\vct{y}}\\leq \\delta = \\max_{\\vct{x}\\in P}\\ip{\\vct{c}}{\\vct{x}}.\n", "\\end{equation*}\n", "\n", "This finishes the proof.\n" ] } ], "metadata": { "kernelspec": { "display_name": "Python [py27]", "language": "python", "name": "Python [py27]" }, "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 }