{ "cells": [ { "cell_type": "markdown", "metadata": { "collapsed": true }, "source": [ "# Duality\n", "## Introduction\n", "The duality principle states that every optimization problem can be represented and analysed in two different formulations, the **primal** and the **dual**. \n", "This means that every problem that we have analysed so far has a **dual** problem formulation with the following characteristics:\n", "\n", "- The dual has an optimal solution **if and only if** the primal has an optimal solution (and vice versa)\n", "- The **optimal value** of the objective function both cases (respective optimal solutions) **is the same** (strong duality principle)\n", "- The dual of dual is the primal\n", "- The solution of the dual problem can be obtained from the solution of the primal and vice versa (using algorithms like the like Simplex)\n", "\n", "### Basic rules for obtaining the dual\n", "The dual of a problem can be obtained applying the following rules: \n", "\n", "- If the **primal problem objective function** is of type **maximise**, the **dual problem objective function** is of type **minimise** (and vice versa)\n", "- If the primal has $m$ constraints, the dual has $m$ decision variables, noted as $u_1$, $u_2$, ..., $u_m$\n", "- The coefficients of the objective function of the dual are the independent terms (RHS) of the constraints of the primal (and vice versa)\n", "- The coefficients of the dependent terms (LHS) of the constraint of the dual can be represented by the transposed matrix $A^T$ that contains the LHS coefficients of the primal (and vice versa)\n", "- All the constraints are of type greater or equal ($\\geq$)\n", "- For maximization problems:\n", " - If the $i^{th}$ constraint of the primal is of type less or equal ($\\leq$), then $u_i$ is non-negative ($\\geq 0$)\n", " - If the $i^{th}$ constraint of the primal is of type greater or equal ($\\geq$), then $u_i$ is non-positive ($\\leq 0$)\n", "- For minimization problems:\n", " - If the $i^{th}$ constraint of the primal is of type less or equal ($\\leq$), then $u_i$ is non-positive ($\\leq 0$)\n", " - If the $i^{th}$ constraint of the primal is of type greater or equal ($\\geq$), then $u_i$ is non-negative ($\\geq 0$)\n", "- If any case, if the $i^{th}$ constraint of the primal is of type equal ($=$), then $u_i$ is unrestricted (can be positive or negative)\n", "\n", "#### Summary\n", "These rules are summarised in the following table: \n", "\n", "| Primal problem | Dual problem |\n", "|----------------------------------------------------------|----------------------------------------------------|\n", "| Objective of type maximize | Objective of type minimize |\n", "| Objective of type minimize | Objective of type maximize |\n", "| Constraint limits, RHS | Decision Variable coefficients |\n", "| Decision Variable coefficients | Constraint limits, RHS |\n", "| Constraint coefficient of decision variable i ($a_{ij}$) | Constraint coefficient of constraint i ($a*_{ji}$) |\n", "\n", "## Simple example\n", "Let us consider the following generic problem with two decision variables: \n", "\n", "$\\max z = c_1*x_1 + c_2*x_2$\n", "\n", "s.t. \n", "\n", "$a_{11}*x_1 + a_{12}*x_2 \\leq b_1$\n", "\n", "$a_{21}*x_1 + a_{22}*x_2 \\leq b_2$\n", "\n", "$a_{31}*x_1 + a_{32}*x_2 \\leq b_3$\n", "\n", "Applying the rules above, the objective function of the dual is of type minimise, there are 3 decision variables, as the \n", "primal has 3 constraints, and the coefficients of the objective function of the dual are the RHS of the primal, hence, \n", "the objective function of the dual becomes: \n", "\n", "$\\min z = b_1*u_1 + b_2*u_2 + b_3*u_3$\n", "\n", "Now, we have two constraints, one per every decision variable. The RHS are the coefficients of the objective function, \n", "and the dependent coefficient are obtained by transposing the coefficients of the primal, hence the dual problem is \n", "subject to the following constraints:\n", "\n", "$a_{11}*u_1 + a_{21}*u_2 + a_{31}*u_3 \\geq c_1$\n", "$a_{12}*u_1 + a_{22}*u_2 + a_{32}*u_3 \\geq c_2$\n", "\n", "Now, since the constraints of the primal are of type $leq$, the three decision variables are non-negative:\n", "\n", "$u_1, u_2, u_3 \\geq 0$\n", "\n", "## Bounding explanation\n", "One way to deduct the dual is by acknowledging that, if the objective function of the primal is of type maximize and all\n", " the constraints are of type less or equal, linear combinations of the constraints provide **upper bounds** for \n", " the objective function. For instance, let us consider the following problem: \n", " \n", "$\\max z = 4*x_1 + x_2 + 5*x_3 + 3*x_4$\n", " \n", " s.t.\n", " \n", "$x_1 - x_2 - x_3 + 4*x_4 \\leq 1$\n", " \n", "$5*x_1 + x_2 + 3*x_3 + 8*x_4 \\leq 55$\n", " \n", "$-x_1 + 2*x_2 + 3*x_3 + 5*x_4 \\leq 3$ \n", "\n", "Note that, if we multiply the second constraint by a factor of 2, we obtain an equivalent constraint: \n", "\n", "$10*x_1 + 2*x_2 + 6*x_3 + 16*x_4 \\leq 110$\n", "\n", "Note also that all the LHS coefficients of this constraint are higher or equal than the coefficients of the objective \n", "function, and therefore: \n", "\n", "$\\max z = 4*x_1 + x_2 + 5*x_3 + 3*x_4 \\leq 10*x_1 + 2*x_2 + 6*x_3 + 16*x_4 \\leq 110$\n", "\n", "This constraint is an upper bound for the objective function, we do not know yet which is the maximum value of z, but we\n", "know that it cannot be higher than 110. \n", "\n", "Note that we can find another upper bound using a linear combination of the second of third constraint, just by adding \n", "both constraints, we obtain: \n", "\n", "$4*x_1 + 3*x_2 + 6*x_3 + 13*x_4 \\leq 58$\n", "\n", "Again, this linear combination is an upper bound of the objective function, since all the coefficients are higher or \n", "equal the coefficients of the objective value, for any value of the decision variables, we have: \n", "\n", "$\\max z = 4*x_1 + x_2 + 5*x_3 + 3*x_4 \\leq 4*x_1 + 3*x_2 + 6*x_3 + 13*x_4 \\leq 58$\n", "\n", "Therefore, even if we do not know which is the optimal value of the objective function, 58 is an upper bound, the \n", "optimal value cannot exceed this bound. \n", "\n", "Note that finding the maximum value of $z$, is equivalent to finding the **minimum upper bound**, hence, the minimum \n", "linear combination of the constraints, or equivalently, the minimum linear combination of the RHSs: \n", "\n", "$min z* = 1*u_1 + 55*u_2 + 4*u_3$\n", "\n", "which yields coefficients that are higher or equal the coefficients of the objective function for every decision \n", "variable: \n", "\n", "$u_1 + 5*u_2 -u_3 \\geq 4$\n", "\n", "$-u_1 + u_2 + 2*u_3 \\geq 1$\n", "\n", "$-u_1 + 3*u_2 + 3*u_3 \\geq 5$\n", "\n", "$4*u_1 + 8*u_2 + 5*u_3 \\geq 3$\n", "\n", "Note that this is the dual of the primal problem. \n", "\n", "## Complementary slackness\n", "Following the reasoning of the previous section, note that the decision variables of the dual are equivalent to the \n", "**Lagrangian multipliers** of the constraints in the Lagrangian of the primal: \n", "\n", "$\\max z = \\sum_{i=1}^n{c_i*x_i} + u_1*(a_{11}*x_1 + a_{12}*x_2 + ... + a_{1n}*x_n) + u_2*(a_{21}*x_1 + a_{22}*x_2 + ... + a_{2n}*x_n) + ...$\n", "\n", "Maximizing the objective function is equivalent to minimizing the part of the Lagrangian multipliers. \n", "\n", "But most importantly, Dual variables represent changes in the primal objective function per unit of constraint, that is, if an RHS of a constraint $i$ is\n", "modified in 1 unit, the objective function is going to change in $u_i$ units.\n", "\n", "For this reason, the decision variables of the dual are referred to as the **shadow prices** of the constraints. The \n", "term shadow highlights that they are not factored in the objective function, and the term price means that they represent\n", "the impact in the objective function.\n", "\n", "It follows that if a constraint is non-binding, meaning that the corresponding slack variable is non-zero, then the \n", "corresponding decision variable, or shadow price must necessarily be zero (that is, the shadow price must be zero, because we have a surplus or excess, and a change in the RHS of the constraint is not going to change the objective variable, just the value of the surplus or excess).\n", "Conversely, if a constraint is binding (meaning that the corresponding slack variable is zero), then the corresponding dual variable (shadow price) is basic (non-zero), because a change in the RHS of the constraint can cause a change in the objective variable.\n", "\n", "Same applies for the dual: If a constraint of the dual is binding (meaning that the slack variable is zero, or non-basic), then the corresponding primal variable is basic. Also, if a constraint of the dual is non-binding (meaning that the slack variable is non-zero, or basic), then the corresponding primal variable is non-basic.\n", "\n", "This principle is called **complementary slackness** meaning that the slack values or *slackness* of dual and primal \n", "are complementary.\n", "\n", "\n", "\n", "\n" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "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.6" }, "pycharm": { "stem_cell": { "cell_type": "raw", "source": [], "metadata": { "collapsed": false } } } }, "nbformat": 4, "nbformat_minor": 0 }