{ "cells": [ { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "**************\n", "Duality Theory\n", "**************\n", "\n", "The `Advanced Simplex Pivot Tool`_ is useful for the first exercise.\n", "\n", ".. _Advanced Simplex Pivot Tool: http://www.princeton.edu/~rvdb/JAVA/pivot/advanced.html\n", "\n", "General Duality Theory\n", "======================\n", "\n", "While any LP can be dualized after being transformed to standard form, the\n", "meaning of the dual variables will be obscured in the process. In order to\n", "compute the dual of a LP with minimal conversion, :cite:`burke407s4` proposes\n", "a more general notion of standard form:\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\mathcal{P} \\quad \\text{maximize} \\quad\n", " \\sum_{j = 1}^n c_j x_j &\\\\\n", " \\text{subject to} \\quad\n", " \\sum_{j = 1}^n a_{ij} x_j &\\leq b_i \\quad i \\in I\\\\\n", " \\sum_{j = 1}^n a_{ij} x_j &= b_i \\quad i \\in E\\\\\n", " 0 &\\leq x_j \\quad j \\in R\n", " \\end{aligned}\n", " \\quad \\iff \\quad\n", " \\begin{aligned}\n", " \\mathcal{D} \\quad \\text{minimize} \\quad\n", " \\sum_{i = 1}^m b_i y_i &\\\\\n", " \\text{subject to} \\quad\n", " \\sum_{i = 1}^m a_{ij} y_i &\\geq c_j \\quad j \\in R\\\\\n", " \\sum_{i = 1}^m a_{ij} y_i &= c_j \\quad j \\in F\\\\\n", " 0 &\\leq y_i \\quad i \\in I\n", " \\end{aligned}\n", "\n", "where :math:`I \\cap E = \\emptyset`, :math:`I \\cup E = \\{1, 2, \\ldots, m\\}`,\n", ":math:`R \\subset \\{1, 2, \\ldots, n\\}`, and\n", ":math:`F = \\{1, 2, \\ldots, n\\} \\setminus R`. This formulation can be\n", "combined with the rules in Table 5.1 to derive the dual of any LP.\n", "\n", "Duality Gap and Complementary Slackness\n", "=======================================\n", "\n", ":cite:`uvah099` presents an alternative proof to the Strong Duality Theorem\n", "using Farkas' Lemma. As illustrated in :cite:`lrsa18433`, the Weak Duality\n", "Theorem asserts that for a primal linear program :math:`\\mathcal{P}` and its\n", "dual :math:`\\mathcal{D}`, there are only the following possibilities:\n", "\n", "- :math:`\\mathcal{P}` infeasible, :math:`\\mathcal{D}` infeasible (infinite gap).\n", "- :math:`\\mathcal{P}` infeasible, :math:`\\mathcal{D}` unbounded (no gap).\n", "- :math:`\\mathcal{P}` unbounded, :math:`\\mathcal{D}` infeasible (no gap).\n", "- :math:`\\mathcal{P}` feasible, :math:`\\mathcal{D}` feasible.\n", "\n", "The Strong Duality Theorem states that if either :math:`\\mathcal{P}` or\n", ":math:`\\mathcal{D}` has a finite optimal value, there is no duality gap.\n", "\n", "Lastly, given the primal optimal solution, the Complementary Slackness Theorem\n", "enables one to derive the dual optimal solution.\n", "\n", "The Dual Simplex Method\n", "=======================\n", "\n", "The book is vague on how to select the entering and leaving variable. See\n", ":cite:`ellingmnds` for a concise yet clear explanation." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ ".. _vanderbei2014linear-ex-5.1:\n", "\n", "Exercise 5.1\n", "============\n", "\n", "Rewriting the LP to standard form yields\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\mathcal{P} \\quad \\text{maximize} \\quad\n", " x_1 - 2 x_2 &\\\\\n", " \\text{subject to} \\quad\n", " -x_1 - 2 x_2 + x_3 - x_4 &\\leq 0\\\\\n", " 4 x_1 + 3 x_2 + 4 x_3 - 2 x_4 &\\leq 3\\\\\n", " -x_1 - x_2 + 2 x_3 + x_4 &= 1\\\\\n", " 0 &\\leq x_j \\quad j = 2, 3.\n", " \\end{aligned}\n", "\n", "The dual of :math:`\\mathcal{P}` is\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\mathcal{D} \\quad \\text{minimize} \\quad\n", " 3 y_2 + y_3 &\\\\\n", " \\text{subject to} \\quad\n", " -y_1 + 4 y_2 - y_3 &= 1\\\\\n", " -2 y_1 + 3 y_2 - y_3 &\\geq -2\\\\\n", " y_1 + 4 y_2 + 2 y_3 &\\geq 0\\\\\n", " -y_1 - 2 y_2 + y_3 &= 0\\\\\n", " 0 &\\leq y_i \\quad i = 1, 2\n", " \\end{aligned}\n", " \\quad = \\quad\n", " \\begin{aligned}\n", " \\mathcal{D} \\quad -\\text{maximize} \\quad\n", " -3 y_2 - y_3 &\\\\\n", " \\text{subject to} \\quad\n", " y_1 - 4 y_2 + y_3 &= -1\\\\\n", " 2 y_1 - 3 y_2 + y_3 &\\leq 2\\\\\n", " -y_1 - 4 y_2 - 2 y_3 &\\leq 0\\\\\n", " y_1 + 2 y_2 - y_3 &= 0\\\\\n", " 0 &\\leq y_i \\quad i = 1, 2.\n", " \\end{aligned}\n", "\n", "Observe that the dual to :math:`\\mathcal{D}` is indeed :math:`\\mathcal{P}`:\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\mathcal{P} \\quad -\\text{minimize} \\quad\n", " -x_1 + 2 x_2 &\\\\\n", " \\text{subject to} \\quad\n", " x_1 + 2 x_2 - x_3 + x_4 &\\geq 0\\\\\n", " -4 x_1 - 3 x_2 - 4 x_3 + 2 x_4 &\\geq -3\\\\\n", " x_1 + x_2 - 2 x_3 - x_4 &= -1\\\\\n", " 0 &\\leq x_j \\quad j = 2, 3\n", " \\end{aligned}\n", " \\quad = \\quad\n", " \\begin{aligned}\n", " \\mathcal{P} \\quad \\text{maximize} \\quad\n", " x_1 - 2 x_2 &\\\\\n", " \\text{subject to} \\quad\n", " -x_1 - 2 x_2 + x_3 - x_4 &\\leq 0\\\\\n", " 4 x_1 + 3 x_2 + 4 x_3 - 2 x_4 &\\leq 3\\\\\n", " -x_1 - x_2 + 2 x_3 + x_4 &= 1\\\\\n", " 0 &\\leq x_j \\quad j = 2, 3.\n", " \\end{aligned}" ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 5.2\n", "============\n", "\n", "The optimal primal solution for :ref:`Exercise 2.9 `\n", "is\n", "\n", ".. math::\n", "\n", " \\mathbf{x}^* =\n", " \\left( x_1, x_2, x_3 \\right) =\n", " \\left( \\frac{3}{2}, \\frac{5}{2}, 0 \\right)\n", " \\quad \\land \\quad\n", " \\mathbf{w}^* =\n", " \\left( w_1, w_2, w_3 \\right) =\n", " \\left( 0, 0, \\frac{1}{2} \\right).\n", "\n", "The dual of :math:`\\mathcal{P}` is\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\mathcal{D} \\quad \\text{minimize} \\quad\n", " 5 y_1 + 4 y_2 + 7 y_3 &\\\\\n", " \\text{subject to} \\quad\n", " y_2 + y_3 &\\geq 2\\\\\n", " 2 y_1 + y_2 + 2 y_3 &\\geq 3\\\\\n", " 3 y_1 + 2 y_2 + 3 y_3 &\\geq 4\\\\\n", " 0 &\\leq y_i \\quad i = 1, 2, 3\n", " \\end{aligned}\n", "\n", "From the Complementary Slackness Theorem 5.3, the optimal dual solution needs\n", "to satisfy (5.7)\n", "\n", ".. math::\n", "\n", " x_1 z_1 &= x_1 (y_2 + y_3 - 2) = 0\\\\\n", " x_2 z_2 &= x_2 (2 y_1 + y_2 + 2 y_3 - 3) = 0\\\\\n", " x_3 z_3 &= x_3 (3 y_1 + 2 y_2 + 3 y_3 - 4) = 0\\\\\n", " w_1 y_1 &= 0\\\\\n", " w_2 y_2 &= 0\\\\\n", " w_3 y_3 &= 0.\n", "\n", "These constraints yield the following linear system\n", "\n", ".. math::\n", "\n", " \\begin{bmatrix}\n", " 0 & 3 & 3\\\\\n", " 10 & 5 & 10\\\\\n", " 0 & 0 & 1\n", " \\end{bmatrix}\n", " \\begin{bmatrix} y_1\\\\ y_2\\\\ y_3 \\end{bmatrix} =\n", " \\begin{bmatrix} 6\\\\ 15\\\\ 0\\end{bmatrix}.\n", "\n", "Reducing the associated augmented matrix to echelon form gives\n", "\n", ".. math::\n", "\n", " \\mathbf{y} =\n", " \\left( y_1, y_2, y_3 \\right) =\n", " \\left( \\frac{1}{2}, 2, 0 \\right).\n", "\n", "Since :math:`\\mathbf{y}` is feasible, the Strong Duality Theorem guarantees\n", ":math:`\\mathbf{y}^* = \\mathbf{y}`." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 5.3\n", "============\n", "\n", "The optimal primal solution for :ref:`Exercise 2.1 `\n", "is\n", "\n", ".. math::\n", "\n", " \\mathbf{x}^* =\n", " \\left( x_1, x_2, x_3, x_4 \\right) =\n", " \\left( 2, 0, 1, 0 \\right)\n", " \\quad \\land \\quad\n", " \\mathbf{w}^* =\n", " \\left( w_1, w_2 \\right) =\n", " \\left( 0, 0 \\right).\n", "\n", "The dual of :math:`\\mathcal{P}` is\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\mathcal{D} \\quad \\text{minimize} \\quad\n", " 5 y_1 + 3 y_2 &\\\\\n", " \\text{subject to} \\quad\n", " 2 y_1 + y_2 &\\geq 6\\\\\n", " y_1 + 3 y_2 &\\geq 8\\\\\n", " y_1 + y_2 &\\geq 5\\\\\n", " 3 y_1 + 2 y_2 &\\geq 9\\\\\n", " 0 &\\leq y_i \\quad i = 1, 2\n", " \\end{aligned}\n", "\n", "From the Complementary Slackness Theorem 5.3, the optimal dual solution needs\n", "to satisfy (5.7)\n", "\n", ".. math::\n", "\n", " x_1 z_1 &= x_1 (2 y_1 + y_2 - 6) = 0\\\\\n", " x_2 z_2 &= x_2 (y_1 + 3 y_2 - 8) = 0\\\\\n", " x_3 z_3 &= x_3 (y_1 + y_2 - 5) = 0\\\\\n", " x_4 z_4 &= x_4 (3 y_1 + 2 y_2 - 9) = 0\\\\\n", " w_1 y_1 &= 0\\\\\n", " w_2 y_2 &= 0.\n", "\n", "These constraints yield the following linear system\n", "\n", ".. math::\n", "\n", " \\begin{bmatrix}\n", " 4 & 2\\\\\n", " 1 & 1\n", " \\end{bmatrix}\n", " \\begin{bmatrix} y_1\\\\ y_2 \\end{bmatrix} =\n", " \\begin{bmatrix} 12\\\\ 5 \\end{bmatrix}.\n", "\n", "Reducing the associated augmented matrix to echelon form gives\n", "\n", ".. math::\n", "\n", " \\mathbf{y} =\n", " \\left( y_1, y_2 \\right) =\n", " \\left( 1, 4 \\right).\n", "\n", "Since :math:`\\mathbf{y}` is feasible, the Strong Duality Theorem guarantees\n", ":math:`\\mathbf{y}^* = \\mathbf{y}`." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 5.4\n", "============\n", "\n", "The optimal primal solution for :ref:`Exercise 2.2 `\n", "is\n", "\n", ".. math::\n", "\n", " \\mathbf{x}^* =\n", " \\left( x_1, x_2 \\right) =\n", " \\left( 1, 0 \\right)\n", " \\quad \\land \\quad\n", " \\mathbf{w}^* =\n", " \\left( w_1, w_2, w_3, w_4 \\right) =\n", " \\left( 2, 1, 1, 0 \\right).\n", "\n", "The dual of :math:`\\mathcal{P}` is\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\mathcal{D} \\quad \\text{minimize} \\quad\n", " 4 y_1 + 3 y_2 + 5 y_3 + y_4 &\\\\\n", " \\text{subject to} \\quad\n", " 2 y_1 + 2 y_2 + 4 y_3 + y_4 &\\geq 2\\\\\n", " y_1 + 3 y_2 + y_3 + 5 y_4 &\\geq 1\\\\\n", " 0 &\\leq y_i \\quad i = 1, 2, 3, 4\n", " \\end{aligned}\n", "\n", "From the Complementary Slackness Theorem 5.3, the optimal dual solution needs\n", "to satisfy (5.7)\n", "\n", ".. math::\n", "\n", " x_1 z_1 &= x_1 (2 y_1 + 2 y_2 + 4 y_3 + y_4 - 2) = 0\\\\\n", " x_2 z_2 &= x_2 (y_1 + 3 y_2 + y_3 + 5 y_4 - 1) = 0\\\\\n", " w_1 y_1 &= 0\\\\\n", " w_2 y_2 &= 0\\\\\n", " w_3 y_3 &= 0\\\\\n", " w_4 y_4 &= 0.\n", "\n", "These constraints yield the following linear system\n", "\n", ".. math::\n", "\n", " \\begin{bmatrix}\n", " 2 & 2 & 4 & 1\\\\\n", " 1 & 0 & 0 & 0\\\\\n", " 0 & 1 & 0 & 0\\\\\n", " 0 & 0 & 1 & 0\n", " \\end{bmatrix}\n", " \\begin{bmatrix} y_1\\\\ y_2\\\\ y_3\\\\ y_4 \\end{bmatrix} =\n", " \\begin{bmatrix} 2\\\\ 0\\\\ 0\\\\ 0 \\end{bmatrix}.\n", "\n", "Reducing the associated augmented matrix to echelon form gives\n", "\n", ".. math::\n", "\n", " \\mathbf{y} =\n", " \\left( y_1, y_2, y_3, y_4 \\right) =\n", " \\left( 0, 0, 0, 2 \\right).\n", "\n", "Since :math:`\\mathbf{y}` is feasible, the Strong Duality Theorem guarantees\n", ":math:`\\mathbf{y}^* = \\mathbf{y}`." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 5.5\n", "============\n", "\n", "(a)\n", "---\n", "\n", "The dual of :math:`\\mathcal{P}` is\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\mathcal{D} \\quad \\text{minimize} \\quad\n", " 6 y_1 + 1.5 y_2 + 4 y_3 &\\\\\n", " \\text{subject to} \\quad\n", " 2 y_1 - 2 y_2 + 3 y_3 &\\geq 2\\\\\n", " 3 y_1 + 4 y_2 + 2 y_3 &\\geq 8\\\\\n", " 3 y_2 - 2 y_3 &\\geq -1\\\\\n", " 6 y_1 - 4 y_3 &\\geq -2\\\\\n", " 0 &\\leq y_i \\quad i = 1, 2, 3.\n", " \\end{aligned}\n", "\n", "(b)\n", "---\n", "\n", ".. math::\n", "\n", " w_1, x_2, w_3, x_4 \\in \\mathcal{N}\n", " \\quad \\land \\quad\n", " x_1, w_2, x_3 \\in \\mathcal{B}\n", "\n", "(c)\n", "---\n", "\n", "The current primal solution is feasible but degenerate:\n", "\n", ".. math::\n", "\n", " x_1 = 3, \\quad\n", " x_2 = 0, \\quad\n", " x_3 = 2.5, \\quad\n", " x_4 = 0, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = 0, \\quad\n", " w_3 = 0.\n", "\n", "(d)\n", "---\n", "\n", "The corresponding dual dictionary is\n", "\n", ".. math::\n", "\n", " -\\xi &= -3.5 - 3 z_1 - 2.5 z_3\\\\\n", " y_1 &= 0.25 + 0.5 z_1 - 1.25 y_2 + 0.75 z_3\\\\\n", " z_2 &= -6.25 + 1.5 z_1 + 3.25 y_2 + 1.25 z_3\\\\\n", " y_3 &= 0.5 + 1.5 y_2 - 0.5 z_3\\\\\n", " z_4 &= 1.5 + 3 z_1 - 13.5 y_2 + 6.5 z_3.\n", "\n", "(e)\n", "---\n", "\n", "The current dual solution is not feasible:\n", "\n", ".. math::\n", "\n", " y_1 = 0.25, \\quad\n", " y_2 = 0, \\quad\n", " y_3 = 0.5, \\quad\n", " z_1 = 0, \\quad\n", " z_2 = -6.25, \\quad\n", " z_3 = 0, \\quad\n", " z_4 = 1.5.\n", "\n", "(f)\n", "---\n", "\n", "Even though the primal and dual solutions satisfy (5.7), the Complementary\n", "Slackness Theorem 5.3 requires both solutions to be feasible. Therefore, the\n", "zero duality gap does not imply an optimal solution.\n", "\n", "(g)\n", "---\n", "\n", "The current primal solution is not optimal because the set of entering variables\n", "is not empty.\n", "\n", "(h)\n", "---\n", "\n", "Choose :math:`x_2` and :math:`w_2` as the entering and leaving variable\n", "respectively where\n", "\n", ".. math::\n", "\n", " x_2 =\n", " \\min \\left\\{ x_1, w_2, x_3 \\right\\}_{\\geq 0} =\n", " \\min \\left\\{ 2, 0, 2 \\right\\}_{\\geq 0}.\n", "\n", "Pivot the primal dictionary to\n", "\n", ".. math::\n", "\n", " \\zeta &=\n", " \\frac{1}{13} \\left( 45.5 + 28 w_1 - 25 w_2 - 44 w_3 + 318 x_4 \\right)\\\\\n", " x_1 &= \\frac{1}{13} \\left( 39 - 14 w_1 + 6 w_2 + 9 w_3 - 120 x_4 \\right)\\\\\n", " x_2 &= \\frac{1}{13} \\left( 5 w_1 - 4 w_2 - 6 w_3 + 54 x_4 \\right)\\\\\n", " x_3 &= \\frac{1}{13} \\left( 32.5 - 16 w_1 + 5 w_2 + 14 w_3 - 152 x_4 \\right).\n", "\n", "Even though the objective function and primal solution stayed the same, the\n", "pivot is not degenerate by definition because each of the candidate leaving\n", "variable's ratio is finite." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 5.6\n", "============\n", "\n", "The dual of :math:`\\mathcal{P}` is\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\mathcal{D} \\quad \\text{minimize} \\quad\n", " 6 y_1 - y_2 + 6 y_3 + y_4 + 6 y_5 - 3 y_6 &\\\\\n", " \\text{subject to} \\quad\n", " -2 y_1 - 3 y_2 + 9 y_3 + y_4 + 7 y_5 - 5 y_6 &\\geq -1\\\\\n", " 7 y_1 + y_2 - 4 y_3 - y_4 - 3 y_5 + 2 y_6 &\\geq -2\\\\\n", " 0 &\\leq y_i \\quad i = 1, 2, \\ldots, 6.\n", " \\end{aligned}\n", "\n", "Observe that the primal basic solution is infeasible while the dual solution has\n", "a basic feasible solution. The dual simplex method can be used to solve the\n", "primal linear program:\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= -x_1 - 2 x_2\\\\\n", " \\text{subject to} \\quad\n", " w_1 &= 6 + 2 x_1 - 7 x_2\\\\\n", " w_2 &= -1 + 3 x_1 - x_2\\\\\n", " w_3 &= 6 - 9 x_1 + 4 x_2\\\\\n", " w_4 &= 1 - x_1 + x_2\\\\\n", " w_5 &= 6 - 7 x_1 + 3 x_2\\\\\n", " w_6 &= -3 + 5 x_1 - 2 x_2\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, \\ldots, 6.\n", " \\end{aligned}\n", "\n", "Initial infeasible solution:\n", "\n", ".. math::\n", "\n", " x_1 = 0, \\quad\n", " x_2 = 0, \\quad\n", " w_1 = 6, \\quad\n", " w_2 = -1, \\quad\n", " w_3 = 6, \\quad\n", " w_4 = 1, \\quad\n", " w_5 = 6, \\quad\n", " w_6 = -3.\n", "\n", "Choose the leaving variable that satisfies\n", "\n", ".. math::\n", "\n", " \\DeclareMathOperator*{\\argmin}{arg\\,min}\n", " \\argmin_{\\mathcal{B}} \\left\\{ b_i \\right\\}_{< 0} =\n", " \\argmin_{\\mathcal{B}} \\left\\{ w_2 = -1, w_6 = -3 \\right\\}_{< 0} = w_6.\n", "\n", "Choose the entering variable that satisfies\n", "\n", ".. math::\n", "\n", " \\DeclareMathOperator*{\\argmin}{arg\\,min}\n", " \\argmin_{\\mathcal{N}}\n", " \\left\\{ \\frac{\\left\\vert c_j \\right\\vert}{a_{6j}} \\right\\}_{a_{6j} > 0} =\n", " \\argmin_{\\mathcal{N}} \\left\\{\n", " x_1 = \\frac{1}{5}\n", " \\right\\}_{\\geq 0} = x_1.\n", "\n", "Pivot the dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= \\frac{1}{5} \\left( -3 - w_6 - 12 x_2 \\right)\\\\\n", " \\text{subject to} \\quad\n", " w_1 &= \\frac{1}{5} \\left( 36 + 2 w_6 - 31 x_2 \\right)\\\\\n", " w_2 &= \\frac{1}{5} \\left( 4 + 3 w_6 + x_2 \\right)\\\\\n", " w_3 &= \\frac{1}{5} \\left( 3 - 9 w_6 + 2 x_2 \\right)\\\\\n", " w_4 &= \\frac{1}{5} \\left( 2 - w_6 + 3 x_2 \\right)\\\\\n", " w_5 &= \\frac{1}{5} \\left( 9 - 7 w_6 + x_2 \\right)\\\\\n", " x_1 &= \\frac{1}{5} \\left( 3 + w_6 + 2 x_2 \\right)\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, \\ldots, 6.\n", " \\end{aligned}\n", "\n", "Update the current dictionary's solution to\n", "\n", ".. math::\n", "\n", " x_1 = \\frac{3}{5}, \\quad\n", " x_2 = 0, \\quad\n", " w_1 = \\frac{36}{5}, \\quad\n", " w_2 = \\frac{4}{5}, \\quad\n", " w_3 = \\frac{3}{5}, \\quad\n", " w_4 = \\frac{2}{5}, \\quad\n", " w_5 = \\frac{9}{5}, \\quad\n", " w_6 = 0.\n", "\n", "Since both dictionaries are feasible and their corresponding set of\n", "entering variables is empty, both dictionaries are optimal." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 5.7\n", "============\n", "\n", "To make the initial dual dictionary feasible, replace :math:`\\zeta` with\n", ":math:`\\eta = -x_1 - x_2 - x_3` so that\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\eta &= -x_1 - x_2 - x_3\\\\\n", " \\text{subject to} \\quad\n", " w_1 &= -2 + x_1 + x_2 + x_3\\\\\n", " w_2 &= 1 - 2 x_1 + x_2 - x_3\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2, 3\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2.\n", " \\end{aligned}\n", "\n", "Initial infeasible solution:\n", "\n", ".. math::\n", "\n", " x_1 = 0, \\quad\n", " x_2 = 0, \\quad\n", " x_3 = 0, \\quad\n", " w_1 = -2, \\quad\n", " w_2 = 1.\n", "\n", "Choose the leaving variable that satisfies\n", "\n", ".. math::\n", "\n", " \\DeclareMathOperator*{\\argmin}{arg\\,min}\n", " \\argmin_{\\mathcal{B}} \\left\\{ b_i \\right\\}_{< 0} =\n", " \\argmin_{\\mathcal{B}} \\left\\{ w_1 = -2 \\right\\}_{< 0} = w_1.\n", "\n", "Under Bland's rule, choose the entering variable that satisfies\n", "\n", ".. math::\n", "\n", " \\DeclareMathOperator*{\\argmin}{arg\\,min}\n", " \\argmin_{\\mathcal{N}}\n", " \\left\\{ \\frac{\\left\\vert c_j \\right\\vert}{a_{1j}} \\right\\}_{a_{1j} > 0} =\n", " \\argmin_{\\mathcal{N}} \\left\\{\n", " x_1 = \\frac{1}{1}, x_2 = \\frac{1}{1}, x_3 = \\frac{1}{1}\n", " \\right\\}_{\\geq 0} = x_1.\n", "\n", "Pivot the dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\eta &= -2 - w_1\\\\\n", " \\text{subject to} \\quad\n", " x_1 &= 2 + w_1 - x_2 - x_3\\\\\n", " w_2 &= -3 - 2 w_1 + 3 x_2 + x_3\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2, 3\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2.\n", " \\end{aligned}\n", "\n", "Update the current dictionary's solution to\n", "\n", ".. math::\n", "\n", " x_1 = 2, \\quad\n", " x_2 = 0, \\quad\n", " x_3 = 0, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = -3.\n", "\n", "Choose the leaving variable that satisfies\n", "\n", ".. math::\n", "\n", " \\DeclareMathOperator*{\\argmin}{arg\\,min}\n", " \\argmin_{\\mathcal{B}} \\left\\{ b_i \\right\\}_{< 0} =\n", " \\argmin_{\\mathcal{B}} \\left\\{ w_2 = -3 \\right\\}_{< 0} = w_2.\n", "\n", "Under Bland's rule, choose the entering variable that satisfies\n", "\n", ".. math::\n", "\n", " \\DeclareMathOperator*{\\argmin}{arg\\,min}\n", " \\argmin_{\\mathcal{N}}\n", " \\left\\{ \\frac{\\left\\vert c_j \\right\\vert}{a_{2j}} \\right\\}_{a_{2j} > 0} =\n", " \\argmin_{\\mathcal{N}} \\left\\{\n", " x_2 = \\frac{0}{3}, x_3 = \\frac{0}{1}\n", " \\right\\}_{\\geq 0} = x_2.\n", "\n", "Pivot the dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\eta &= -2 - w_1\\\\\n", " \\text{subject to} \\quad\n", " x_1 &= \\frac{1}{3} \\left( 3 + w_1 - w_2 - 2 x_3 \\right)\\\\\n", " x_2 &= \\frac{1}{3} \\left( 3 + 2 w_1 + w_2 - x_3 \\right)\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2, 3\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2.\n", " \\end{aligned}\n", "\n", "Update the current dictionary's solution to\n", "\n", ".. math::\n", "\n", " x_1 = 1, \\quad\n", " x_2 = 1, \\quad\n", " x_3 = 0, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = 0.\n", "\n", "Since both dictionaries are feasible and their corresponding set of\n", "entering variables is empty, both dictionaries are optimal.\n", "\n", "The starting dictionary for Phase II is\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= \\frac{1}{3} \\left( -12 - 10 w_1 - 8 w_2 + 2 x_3 \\right)\\\\\n", " \\text{subject to} \\quad\n", " x_1 &= \\frac{1}{3} \\left( 3 + w_1 - w_2 - 2 x_3 \\right)\\\\\n", " x_2 &= \\frac{1}{3} \\left( 3 + 2 w_1 + w_2 - x_3 \\right)\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2, 3\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2.\n", " \\end{aligned}\n", "\n", "Choose :math:`x_3` and :math:`x_1` as the entering and leaving variable\n", "respectively where\n", "\n", ".. math::\n", "\n", " x_3 = \\min \\left\\{ x_1, x_2 \\right\\}_{\\geq 0} =\n", " \\min \\left\\{ \\frac{3}{2}, 3 \\right\\}_{\\geq 0}.\n", "\n", "Pivot the dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= -3 - x_1 - 3 w_1 - 3 w_2\\\\\n", " \\text{subject to} \\quad\n", " x_2 &= \\frac{1}{2} \\left( 1 + x_1 + w_1 + w_2 \\right)\\\\\n", " x_3 &= \\frac{1}{2} \\left( 3 - 3 x_1 + w_1 - w_2 \\right)\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2, 3\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2.\n", " \\end{aligned}\n", "\n", "Update the current dictionary's feasible solution to\n", "\n", ".. math::\n", "\n", " x_1 = 0, \\quad\n", " x_2 = \\frac{1}{2}, \\quad\n", " x_3 = \\frac{3}{2}, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = 0.\n", "\n", "Since the set of primal entering variables is empty, the dictionary is optimal." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 5.8\n", "============\n", "\n", "The initial dual dictionary is already feasible, so no need to modify the primal\n", "objective function.\n", "\n", "Choose the leaving variable that satisfies\n", "\n", ".. math::\n", "\n", " \\DeclareMathOperator*{\\argmin}{arg\\,min}\n", " \\argmin_{\\mathcal{B}} \\left\\{ b_i \\right\\}_{< 0} =\n", " \\argmin_{\\mathcal{B}} \\left\\{ w_1 = -5 \\right\\}_{< 0} = w_1.\n", "\n", "Choose the entering variable that satisfies\n", "\n", ".. math::\n", "\n", " \\DeclareMathOperator*{\\argmin}{arg\\,min}\n", " \\argmin_{\\mathcal{N}}\n", " \\left\\{ \\frac{\\left\\vert c_j \\right\\vert}{a_{1j}} \\right\\}_{a_{1j} > 0} =\n", " \\argmin_{\\mathcal{N}} \\left\\{\n", " x_2 = \\frac{3}{5}\n", " \\right\\}_{\\geq 0} = x_2.\n", "\n", "Pivot the dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\zeta &= \\frac{1}{5} \\left( -15 - 11 x_1 - 3 w_1 - 8 w_3 \\right)\\\\\n", " \\text{subject to} \\quad\n", " x_2 &= \\frac{1}{5} \\left( 5 + 2 x_1 + w_1 + x_3 \\right)\\\\\n", " w_2 &= \\frac{1}{5} \\left( 25 - 8 x_1 + w_1 - 9 x_3 \\right)\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2, 3\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2.\n", " \\end{aligned}\n", "\n", "Update the current dictionary's feasible solution to\n", "\n", ".. math::\n", "\n", " x_1 = 0, \\quad\n", " x_2 = 1, \\quad\n", " x_3 = 0, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = 5.\n", "\n", "Since both dictionaries are feasible and their corresponding set of\n", "entering variables is empty, both dictionaries are optimal." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 5.9\n", "============\n", "\n", "To make the initial dual dictionary feasible, replace :math:`\\zeta` with\n", ":math:`\\eta = -x_1 - x_2` so that\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\eta &= -x_1 - x_2\\\\\n", " \\text{subject to} \\quad\n", " w_1 &= -3 + x_1 + x_2\\\\\n", " w_2 &= -1 + x_1 - x_2\\\\\n", " w_3 &= 2 - x_1 - 2 x_2\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, 3.\n", " \\end{aligned}\n", "\n", "Initial infeasible solution:\n", "\n", ".. math::\n", "\n", " x_1 = 0, \\quad\n", " x_2 = 0, \\quad\n", " w_1 = -3, \\quad\n", " w_2 = -1, \\quad\n", " w_3 = 2.\n", "\n", "Choose the leaving variable that satisfies\n", "\n", ".. math::\n", "\n", " \\DeclareMathOperator*{\\argmin}{arg\\,min}\n", " \\argmin_{\\mathcal{B}} \\left\\{ b_i \\right\\}_{< 0} =\n", " \\argmin_{\\mathcal{B}} \\left\\{ w_1 = -3, w_2 = -1 \\right\\}_{< 0} = w_1.\n", "\n", "Under Bland's rule, choose the entering variable that satisfies\n", "\n", ".. math::\n", "\n", " \\DeclareMathOperator*{\\argmin}{arg\\,min}\n", " \\argmin_{\\mathcal{N}}\n", " \\left\\{ \\frac{\\left\\vert c_j \\right\\vert}{a_{1j}} \\right\\}_{a_{1j} > 0} =\n", " \\argmin_{\\mathcal{N}} \\left\\{\n", " x_1 = \\frac{1}{1}, x_2 = \\frac{1}{1}\n", " \\right\\}_{\\geq 0} = x_1.\n", "\n", "Pivot the dictionary to\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\text{maximize} \\quad\n", " \\eta &= -3 - w_1\\\\\n", " \\text{subject to} \\quad\n", " x_1 &= 3 + w_1 - x_2\\\\\n", " w_2 &= 2 + w_1 - 2 x_2\\\\\n", " w_3 &= -1 - w_1 - x_2\\\\\n", " x_i &\\geq 0 \\quad i = 1, 2\\\\\n", " w_i &\\geq 0 \\quad i = 1, 2, 3.\n", " \\end{aligned}\n", "\n", "Update the current dictionary's solution to\n", "\n", ".. math::\n", "\n", " x_1 = 3, \\quad\n", " x_2 = 0, \\quad\n", " w_1 = 0, \\quad\n", " w_2 = 2, \\quad\n", " w_3 = -1.\n", "\n", "Choose the leaving variable that satisfies\n", "\n", ".. math::\n", "\n", " \\DeclareMathOperator*{\\argmin}{arg\\,min}\n", " \\argmin_{\\mathcal{B}} \\left\\{ b_i \\right\\}_{< 0} =\n", " \\argmin_{\\mathcal{B}} \\left\\{ w_3 = -1 \\right\\}_{< 0} = w_3.\n", "\n", "Observe that the set of entering variables\n", "\n", ".. math::\n", "\n", " \\left\\{ \\frac{\\left\\vert c_j \\right\\vert}{a_{3j}} \\right\\}_{a_{3j} > 0} =\n", " \\emptyset.\n", "\n", "Examining the dual dictionary reveals that the dual is feasible but unbounded.\n", "Thus, the primal is infeasible according to the Weak Duality Theorem. Note that\n", "one does not have to examine the dual to confirm this: it is evident that\n", ":math:`w_3 < 0` whenever the other nonbasic variables are nonzero." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 5.10 and Exercise 5.11\n", "===============================\n", "\n", "The previous exercises were solved using the proposed tool." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 5.12\n", "=============\n", "\n", "Recall the expression :math:`\\infty - \\infty` is undefined even for an affinely\n", "extended real number system. This means :math:`f(x, y) = x - y` is not a\n", "continuous function assuming :math:`x, y \\in [0, \\infty]`, which means one\n", "cannot apply von Neumann's Minimax Theorem.\n", "\n", "Observe that\n", "\n", ".. math::\n", "\n", " \\min_{y \\geq 0} x - y =\n", " \\begin{cases}\n", " \\text{undefined} & \\text{if } x = \\infty\\\\\n", " -\\infty & \\text{otherwise}\n", " \\end{cases}\n", "\n", "and\n", "\n", ".. math::\n", "\n", " \\max_{x \\geq 0} x - y =\n", " \\begin{cases}\n", " \\text{undefined} & \\text{if } y = \\infty\\\\\n", " \\infty & \\text{otherwise.}\n", " \\end{cases}\n", "\n", "The maximin and minimax solutions are respectively\n", "\n", ".. math::\n", "\n", " \\max_{x \\geq 0} \\min_{y \\geq 0} x - y =\n", " \\begin{cases}\n", " \\text{undefined} & \\text{if } x = \\infty\\\\\n", " -\\infty & \\text{otherwise}\n", " \\end{cases}\n", "\n", "and\n", "\n", ".. math::\n", "\n", " \\min_{y \\geq 0} \\max_{x \\geq 0} x - y =\n", " \\begin{cases}\n", " \\text{undefined} & \\text{if } y = \\infty\\\\\n", " \\infty & \\text{otherwise.}\n", " \\end{cases}" ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 5.13\n", "=============\n", "\n", "The proposed process matches the transformations performed in\n", ":ref:`Exercise 5.1 `, but the logic is incorrect.\n", "\n", "The Weak Duality Theorem ensures the validity of the first inequality. The\n", "second inequality is reformulating the dualized problem into a maximization, so\n", "the dualized problem should be thought of as switching places with the primal\n", "problem as shown in Figure 5.1. The same reasoning applies to the third and\n", "fourth inequalities. One way to visualize this is to treat it as a graph with\n", "four vertices and four edges:\n", "\n", ".. math::\n", "\n", " (\\mathcal{P}, \\leq, \\mathcal{D}) \\quad \\land \\quad\n", " (\\mathcal{D}, \\equiv, \\mathcal{D}_{\\max}) \\quad \\land \\quad\n", " (\\mathcal{D}_{\\max}, \\leq, \\mathcal{P}_{\\min}) \\quad \\land \\quad\n", " (\\mathcal{P}_{\\min}, \\equiv, \\mathcal{P}).\n", "\n", "This process is merely illustrating the dual of the dual is the primal. To turn\n", "all inequalities into equalities, the primal and dual needs to be equal. This\n", "restricts the primal dictionary's matrix form to be antisymmetric because the\n", "dual dictionary is the negative transpose of the primal dictionary." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 5.14\n", "=============\n", "\n", "(a)\n", "---\n", "\n", "Observe that :math:`x_j = 0` and :math:`b_i = 0` is a basic feasible solution.\n", "Furthermore, since :math:`x_j` is bounded above by :math:`u_j`, the LP is\n", "bounded. Note that :math:`b_j`'s lack of an upper bound does not matter because\n", "the simplex method non-decreasingly advances the objective function. Applying\n", "the fundamental theorem of linear programming shows that this problem always\n", "has an optimal solution.\n", "\n", "(b)\n", "---\n", "\n", "The dual of :math:`\\mathcal{P}` is\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\mathcal{D} \\quad \\text{minimize} \\quad\n", " \\sum_{i = 1}^m b_i y_i + \\sum_{j = 1}^n u_j y_{m + j} &\\\\\n", " \\text{subject to} \\quad\n", " y_{m + j} + \\sum_{i = 1}^m y_i a_{ij} &\\geq c_j\n", " \\quad j = 1, 2, \\ldots, n\\\\\n", " 0 &\\leq y_k \\quad k = 1, 2, \\ldots, m + n.\n", " \\end{aligned}\n", "\n", "Given the optimal values for :math:`b^*_i`,\n", ":math:`b^*_i = \\sum_{j = 1}^n a_{ij} x^*_j`.\n", "Assuming the market is in equilibrium, :math:`c_j = \\sum_{i = 1}^m a_{ij} p_i`.\n", "\n", "Combining the foregoing assumptions with the Strong Duality Theorem,\n", "\n", ".. math::\n", "\n", " \\sum_{j = 1}^n c_j x^*_j &=\n", " \\sum_{i = 1}^m b^*_i y_i + \\sum_{j = 1}^n u_j y_{m + j}\\\\\n", " \\sum_{j = 1}^n \\sum_{i = 1}^m x^*_j a_{ij} p_i &=\n", " \\sum_{i = 1}^m \\sum_{j = 1}^n x^*_j a_{ij} y_i +\n", " \\sum_{j = 1}^n u_j y_{m + j}.\n", "\n", "Therefore, :math:`y^*_i = p_i` and :math:`y^*_{m + j} = 0`." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 5.15\n", "=============\n", "\n", "The optimal primal solution for\n", ":ref:`Exercise 2.19 ` is\n", "\n", ".. math::\n", "\n", " \\begin{array}{ccc}\n", " & w^*_0 = 0 &\\\\\n", " j < k & x^*_j = 1 & w^*_j = 0\\\\\n", " j = k & x^*_k = \\frac{\\beta - \\sum_{j = 1}^{k - 1} q_j}{q_k} &\n", " w^*_k = 1 - \\frac{\\beta - \\sum_{j = 1}^{k - 1} q_j}{q_k}\\\\\n", " j > k & x^*_j = 0 & w^*_j = 1.\n", " \\end{array}\n", "\n", "The dual of :math:`\\mathcal{P}` is\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\mathcal{D} \\quad \\text{minimize} \\quad\n", " \\beta y_0 + \\sum_{j = 1}^n y_j &\\\\\n", " \\text{subject to} \\quad\n", " q_j y_0 + y_j &\\geq p_j\\\\\n", " 0 &\\leq y_0\\\\\n", " 0 &\\leq y_j \\quad j = 1, \\ldots, n.\n", " \\end{aligned}\n", "\n", "From the Complementary Slackness Theorem 5.3, the optimal dual solution needs to\n", "satisfy (5.7)\n", "\n", ".. math::\n", "\n", " \\begin{array}{ccc}\n", " & w_0 y_0 = 0 &\\\\\n", " j < k & x_j z_j = (1) \\left( q_j y_0 + y_j - p_j \\right) = 0 &\n", " w_j y_j = (0) y_j = 0\\\\\n", " j = k & x_k z_k =\n", " \\left( \\frac{\\beta - \\sum_{j = 1}^{k - 1} q_j}{q_k} \\right)\n", " \\left( q_k y_0 + y_k - p_k \\right) = 0 &\n", " w_k y_k =\n", " \\left( 1 - \\frac{\\beta - \\sum_{j = 1}^{k - 1} q_j}{q_k} \\right)\n", " y_k = 0\\\\\n", " j > k & x_j z_j = (0) \\left( q_j y_0 + y_j - p_j \\right) = 0 &\n", " w_j y_j = (1) y_j = 0.\n", " \\end{array}\n", "\n", "The constraints imposed by the primal slack variables :math:`w_{j \\geq k}`\n", "forces :math:`y_{j \\geq k} = 0`. The result for :math:`y_k` in turn restricts\n", ":math:`y_0 = \\frac{p_k}{q_k}`. Consequently,\n", "\n", ".. math::\n", "\n", " q_j y_0 + y_j - p_j &= 0\\\\\n", " y_j &= p_j - q_j \\left( \\frac{p_k}{q_k} \\right)\\\\\n", " &= q_j \\left( \\frac{p_j}{q_j} - \\frac{p_k}{q_k} \\right)\n", "\n", "for :math:`j < k`. Since :math:`\\frac{p_1}{q_1} > \\cdots > \\frac{p_n}{q_n}`,\n", "the proposed :math:`\\mathbf{y}` is feasible and is guaranteed to be optimal by\n", "the Strong Duality Theorem." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 5.16\n", "=============\n", "\n", "The dual of :math:`\\mathcal{P}` is\n", "\n", ".. math::\n", "\n", " \\begin{aligned}\n", " \\mathcal{D} \\quad \\text{minimize} \\quad\n", " \\sum_{i = 1}^m -b_i y_i &\\\\\n", " \\text{subject to} \\quad\n", " \\sum_{i = 1}^m -a_{ij} y_i &\\geq -c_j \\quad j = 1, \\ldots, n\\\\\n", " 0 &\\leq y_i \\quad i = 1, \\ldots, m\n", " \\end{aligned}\n", " \\quad \\iff \\quad\n", " \\begin{aligned}\n", " \\mathcal{D} \\quad -\\text{maximize} \\quad\n", " \\sum_{i = 1}^m b_i y_i &\\\\\n", " \\text{subject to} \\quad\n", " \\sum_{i = 1}^m a_{ij} y_i &\\leq c_j \\quad j = 1, \\ldots, n\\\\\n", " 0 &\\leq y_i \\quad i = 1, \\ldots, m.\n", " \\end{aligned}\n", "\n", "Recall that\n", "\n", ".. math::\n", "\n", " b_i = \\text{nutrient}\n", " \\quad \\land \\quad\n", " a_{ij} = \\frac{\\text{nutrient}}{\\text{food}}\n", " \\quad \\land \\quad\n", " x_j = \\text{quantity of food}\n", " \\quad \\land \\quad\n", " c_j = \\frac{\\text{price}}{\\text{food}}.\n", "\n", "Notice that :math:`b_i` could be interpreted as the importance of a particular\n", "nutrient whereas :math:`c_j` prevents overpaying for the nutrients. From\n", "inspection, the dual represents a person that wants to maximize the amount of\n", "money spent per nutrient. Hence :math:`y_j` represents\n", ":math:`\\frac{\\text{price}}{\\text{nutrient}}`." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ "Exercise 5.17\n", "=============\n", "\n", "(1)\n", "---\n", "\n", ".. math::\n", "\n", " \\nabla \\pi =\n", " \\begin{bmatrix}\n", " \\partial \\pi / \\partial x\\\\\n", " \\partial \\pi / \\partial y\\\\\n", " \\end{bmatrix} =\n", " \\begin{bmatrix}\n", " f'(x) - y\\\\\n", " -x + g'(y)\\\\\n", " \\end{bmatrix}\n", "\n", "A vanishing gradient implies :math:`\\nabla \\pi = \\boldsymbol{0}`; consequently,\n", "\n", ".. math::\n", "\n", " f'(x) - y &= -x + g'(y)\\\\\n", " f'(x) + x &= g'(y) + y\\\\\n", " \\phi(x) &= \\varphi(y).\n", "\n", "Recall that a strongly convex function is also strictly convex. Since :math:`f`\n", "is strongly concave and :math:`g` is strongly convex, :math:`f' \\in \\mathbb{R}`\n", "is monotonically decreasing and :math:`g' \\in \\mathbb{R}` is monotonically\n", "increasing. The foregoing implies :math:`\\phi(x)` and :math:`\\varphi(y)` will\n", "have at most one intersection.\n", "\n", "(2)\n", "---\n", "\n", ".. math::\n", "\n", " \\nabla^2 \\pi =\n", " \\begin{bmatrix}\n", " \\frac{\\partial^2 \\pi}{\\partial x^2} &\n", " \\frac{\\partial^2 \\pi}{\\partial x \\partial y}\\\\\n", " \\frac{\\partial^2 \\pi}{\\partial y \\partial x} &\n", " \\frac{\\partial^2 \\pi}{\\partial x^2}\\\\\n", " \\end{bmatrix} =\n", " \\begin{bmatrix} f''(x) & -1\\\\ -1 & g''(y) \\end{bmatrix}\n", "\n", "Recall that an indefinite matrix has both positive and negative eigenvalues.\n", "Inspecting the Hessian of :math:`\\pi` shows that it must be indefinite because\n", "\n", ".. math::\n", "\n", " \\det(\\nabla^2 \\pi) = \\prod_i \\lambda_i = f''(x) g''(y) - 1 < 0.\n", "\n", "Since :math:`(x^*, y^*)` is a critical point and the Hessian is indefinite for\n", "the entire surface, the critical point is also a saddle point.\n", "\n", "Notice that for a fixed :math:`y`, :math:`\\pi(x, \\cdot)` is strongly concave, so\n", "\n", ".. math::\n", "\n", " \\min_y \\max_x \\pi(x, y) \\leq \\min_y \\pi(x^*, y) = \\pi(x^*, y^*).\n", "\n", "When :math:`x` is fixed, :math:`\\pi(\\cdot, y)` is strongly convex, so\n", "\n", ".. math::\n", "\n", " \\max_x \\min_y \\pi(x, y) \\geq \\max_x \\pi(x, y^*) = \\pi(x^*, y^*).\n", "\n", "The foregoing implies\n", "\n", ".. math::\n", "\n", " \\max_x \\min_y \\pi(x, y) \\geq \\min_y \\max_x \\pi(x, y),\n", "\n", "but the max-min inequality states that\n", "\n", ".. math::\n", "\n", " \\max_x \\min_y \\pi(x, y) \\leq \\min_y \\max_x \\pi(x, y).\n", "\n", "Thus\n", "\n", ".. math::\n", "\n", " \\max_x \\min_y \\pi(x, y) = \\pi(x^*, y^*) = \\min_y \\max_x \\pi(x, y).\n", "\n", "(3)\n", "---\n", "\n", "Recall that a sum of convex functions is convex, and adding a constant or\n", "a linear function to a function does not affect its convexity.\n", "\n", "For each :math:`x \\in \\mathbb{R}`, the global maximum of\n", ":math:`\\max_y xy - h(y)` is at\n", "\n", ".. math::\n", "\n", " \\frac{d}{dy} \\left( xy - h(y) \\right) &= 0\\\\\n", " x &= h'(y)\n", "\n", "according to the second derivative test\n", "\n", ".. math::\n", "\n", " \\frac{d^2}{dy^2} \\left( xy - h(y) \\right) = -h''(y) < 0.\n", "\n", "Since :math:`h` is strongly convex, :math:`h'` is monotonically increasing,\n", "which means the intersection between :math:`x` and :math:`h'(y)` is unique.\n", "Thus, the inverse function :math:`{h'}^{-1}(x) = y` exists, is differentiable\n", "with the following derivative\n", "\n", ".. math::\n", "\n", " \\left[ {h'}^{-1} \\right]'(x) = \\frac{1}{h''\\left( {h'}^{-1}(x) \\right)} > 0,\n", "\n", "and is also monotonically increasing. The Legendre transform of :math:`h` can\n", "be simplified to\n", "\n", ".. math::\n", "\n", " L_h(x) = \\max_{y \\in \\mathbb{R}} xy - h(y) =\n", " x {h'}^{-1}(x) - h({h'}^{-1}(x)).\n", "\n", "Examining both the first derivative\n", "\n", ".. math::\n", "\n", " \\frac{d}{dx} L_h(x)\n", " &= {h'}^{-1}(x) + x \\left[ {h'}^{-1} \\right]'(x) -\n", " h'\\left( {h'}^{-1}(x) \\right) \\left[ {h'}^{-1} \\right]'(x)\\\\\n", " &= {h'}^{-1}(x)\n", "\n", "and second derivative\n", "\n", ".. math::\n", "\n", " \\frac{d^2}{dx^2} L_h(x) = \\left[ {h'}^{-1} \\right]'(x)\n", "\n", "shows that :math:`L_h` is strongly convex.\n", "\n", "(4)\n", "---\n", "\n", ".. math::\n", "\n", " \\max_{x \\in \\mathbb{R}} f(x) - L_{g(x)}(x)\n", " &= \\max_{x \\in \\mathbb{R}} f(x) -\n", " \\left[ \\max_{y \\in \\mathbb{R}} xy - g(y) \\right]\\\\\n", " &= \\max_{x \\in \\mathbb{R}} f(x) +\n", " \\min_{y \\in \\mathbb{R}} - xy + g(y)\\\\\n", " &= \\max_{x \\in \\mathbb{R}} \\min_{y \\in \\mathbb{R}}\n", " f(x) - xy + g(y)\\\\\n", " &= \\max_{x \\in \\mathbb{R}} \\min_{y \\in \\mathbb{R}} \\pi(x, y).\n", "\n", ".. math::\n", "\n", " \\min_{y \\in \\mathbb{R}} \\max_{x \\in \\mathbb{R}} \\pi(x, y)\n", " &= \\min_{y \\in \\mathbb{R}} \\max_{x \\in \\mathbb{R}} f(x) - xy + g(y)\\\\\n", " &= \\min_{y \\in \\mathbb{R}} g(y) + \\max_{x \\in \\mathbb{R}} -xy + f(x)\\\\\n", " &= \\min_{y \\in \\mathbb{R}} g(y) + \\max_{x \\in \\mathbb{R}} (-y)x - (-f(x))\\\\\n", " &= \\min_{y \\in \\mathbb{R}} g(y) + L_{-f}(-y).\n", "\n", "(5)\n", "---\n", "\n", "The result from (2) implies that one can solve for :math:`L_h(x)` and then\n", "proceed to solve :math:`L_{L_h}(z)`. Recall from (3) that\n", "\n", ".. math::\n", "\n", " L_h(x) = \\max_{z \\in \\mathbb{R}} xz - h(z) =\n", " x {h'}^{-1}(x) - h\\left( {h'}^{-1}(x) \\right)\n", "\n", "where :math:`{h'}^{-1}(x) = z` and :math:`L_h'(x) = {h'}^{-1}(x)`.\n", "\n", ".. math::\n", "\n", " L_{L_h}(z)\n", " &= \\max_{x \\in \\mathbb{R}} zx - L_h(x)\\\\\n", " &= z {L_h'}^{-1}(z) - L_h({L_h'}^{-1}(z))\\\\\n", " &= zx - L_h(x)\\\\\n", " &= zx - \\left[ x {h'}^{-1}(x) - h\\left( {h'}^{-1}(x) \\right) \\right]\\\\\n", " &= zx - xz + h(z)\\\\\n", " &= h(z)." ] }, { "cell_type": "raw", "metadata": { "raw_mimetype": "text/restructuredtext" }, "source": [ ".. rubric:: References\n", "\n", ".. bibliography:: chapter-05.bib" ] } ], "metadata": { "anaconda-cloud": {}, "celltoolbar": "Raw Cell Format", "kernelspec": { "display_name": "Python [default]", "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.5.2" } }, "nbformat": 4, "nbformat_minor": 1 }