Linear Programming Duality
Linear Programming Duality
Linear Programming Duality
Suppose you want to give a lower bound on the optimal value of this LP. What can we say? Since all variables are non-negative, 6x1 + 4x2 + 2x3 4x1 + 2x2 + x3 . So the value of the LP must be at least 5. By the same argument, 6x1 + 4x2 + 2x3 (4x1 + 2x2 + x3 ) + 2(x1 + x2 ) 5 + 2 3 = 11. Again by the same argument, 6x1 +4x2 +2x3 (4x1 +2x2 + x3 )+(x1 + x2 )+(x2 + x3 ) 5+3+4 = 12. How do we determine the best lower bound we can achieve this way? By setting up a dierent LP! Let y1 be the number of times we take the rst constraint, y2 the number of times we take the second constraint and y3 the number of times we take the third constraint. Then the lower bound we get is 5y1 + 3y2 + 4y3 , and we need to ensure that this is a lower bound, i.e. 6x1 + 4x2 + 2x3 y1 (4x1 + 2x2 + x3 ) + y2 (x1 + x2 ) + y3 (x2 + x3 ). We can do this by ensuring that 4y1 + y2 6 (since we have 6x1 in the objective value, and 4x1 in the rst constraint, 1x1 in the second constraint and 0x1 in the third constraint), 2y1 + y2 + y3 4, y1 + y2 2. Also, we need to have y1 , y2 , y3 0 (otherwise the inequalities in the constraints change direction, and we would not get a lower bound). We thus get the following LP for getting the best lower bound: max 5y1 s.t. 4y1 2y1 y1 This is called the dual linear program. Lets consider a second example: min x1 s.t. x1 2x1 x1 0, +2x2 +3x2 x 2 +3x3 =5 +3x3 6 x3 4 x2 0, x3 free. +3y2 +2y2 +y2 +4y3 +y3 +y3 yi 6 4 2 0, for i = 1, 2, 3.
Lets again nd the best possible lower bound on the objective value: We let y1 , y2 , y3 again be the number of times we take the rst, second and third constraint respectively. The lower bound on the optimal value we want to obtain is 5y1 + 6y2 + 4y3 . 1
We need to ensure that x1 + 2x2 + 3x3 y1 (x1 + 3x2 ) + y2 (2x1 x2 + 3x3 ) + y3 (x3 ) = (y1 + 2y2 )x1 + (3y1 y2 )x2 + (3y2 + y3 )x3 , and that y1 (x1 + 3x2 ) + y2 (2x1 x2 + 3x3 ) + y3 (x3 ) 5y1 + 6y2 + 4y3 . First, we derive constraints by using the sign constraints of xj and comparing the coecient of each xj on the left hand side and the right hand side of the rst inequality: know: x1 0 & want: x1 (y1 + 2y2 )x1 know: x2 0 & want: 2x2 (3y1 y2 )x2 know: x3 free & want: 3x3 (3y2 + y3 )x3 y1 + 2y2 1 3y1 y2 2 3y2 + y3 = 3
Then, we derive sign constraints for the variables yi by using the i-th constraint of the linear program and comparing the coecient of each yi on the left hand side and the right hand side of the second inequality: know: x1 + 3x2 = 5 & want: y1 (x1 + 3x2 ) 5 know: 2x1 x2 + 3x3 6 & want: y2 (2x1 x2 + 3x3 ) 6y2 know: x3 4 & want: y3 (x3 ) 4y3 So, we get the following dual linear program max s.t. 5y1 y1 3y1 y1 free, +6y2 +2y2 y 2 3y2 y2 0 +4y3 1 2 =3 y1 free y2 0 y3 0
+y3 y3 0.
We can now give the general rules for nding the dual of a given linear program: minimize maximize Dual bi 0 constraints bi 0 variables = bi free 0 cj variables 0 cj constraints free = cj For a problem in standard form, we thus nd the following pair of primal and dual problem: min cT x s.t. Ax = b x0 There are a few questions we could ask: What happens if we take a dual linear program, multiply its objective by 1 to obtain a minimization problem, and then take the dual of this LP? Suppose we use the dual from our previous example, where we replace the objective max 5y1 +6y2 +4y3 by min 5y1 6y2 4y3 . We also replace yi by x i and we will denote the variables in the dual by y j . min 5 x1 s.t. x 1 3 x1 x 1 free, 6 x2 4 x3 +2 x2 1 x 2 2 3 x2 + x3 =3 x 2 0, x 3 0. 2 max s.t. yT b A yc
T
Primal
The dual is: max s.t. = 5 +3 y3 6 y 3 4 y 1 0, y 2 0, y 3 free . x 1 x1 2x1 x1 0, 2x2 3x2 +x 2 x2 0, 3x3 3x3 x3 x3 free. = 5 6 4 y 1 y 1 2 y1 +2 y2 +3 y2 y 2 +3 y3
We can multiply each of the constraints by 1 and replace the objective by min x1 + 2x2 + 3x3 to see that the dual of the dual is the primal LP! Do we get the same dual linear program if we take the dual directly, and if we rst convert a problem into standard form, and then take the dual? For example, we can take the dual of the following LP directly: min cT x s.t. Ax b x free max s.t. yT b AT y = c y0
or, we can change it into standard form, by replacing x by x+ x and by adding surplus variables, and then take its dual: min s.t. cT x + cT x Ax Ax Is b x+ 0, x 0, s 0
+
max s.t.
yT b A yc AT y c Iy 0 y0
T
It is easy to see that the dual linear programs we derived in these two ways are the same. We state the following two theorems which give the general answers to these two questions without proof (as the proof is just a tedious exercise). Denition 1. Two linear programs are equivalent if they are either both infeasible, or they are both feasible and have the same objective value. Theorem 1. If we transform the dual linear program into an equivalent minimization problem, and take its dual, then we obtain a problem that is equivalent to the original problem. Theorem 2. If we transform a minimization linear program into another equivalent minimization problem , then their duals are also equivalent. We will use the convention that the original LP, which we will call the primal LP is a minimization problem, and that the dual LP is a maximization problem.
Duality Theorem
We derived the dual by trying to nd the best possible lower bound on the objective value of the primal LP. In fact, we constructed the dual so that the objective value of a feasible solution to the dual LP gives a lower bound on the objective value of any feasible solution to the primal LP, as we prove for LPs in standard form: 3
Theorem 3 (Weak duality). If x is a feasible solution to the primal LP and y is a feasible solution to the dual LP, then cT x bT y . Proof. We may restrict our attention to a primal LP in standard form, by Theorem 2. Then, we have cT x (AT y )T x = y T (Ax) y T b, where the rst inequality follows because AT y c and x 0, and the second inequality because Ax = b. Note that it is thus the case that: If the optimal value of the primal LP is , then the dual LP is infeasible. If the optimal value of the dual LP is +, then the primal LP is infeasible. If x is feasible to the primal LP and y is feasible to the dual LP, and cT x = bT y , then x is optimal for the primal and y is optimal for the dual LP. In fact, we can prove the following result, which is the main result on linear programming duality. Theorem 4 (Strong duality). If a linear program has an optimal solution, then so does its dual and the respective objective values are equal. Proof. By Theorem 2, it suces to consider a problem in standard form, i.e., min{cT x : Ax = b, x 0}. The dual is given by max{bT y : AT y c}. Suppose the rows of A are linearly independent, and there exists an optimal solution (if the rows are not linearly independent, we can rst transform it into an equivalent problem by removing redundant constraints). The simplex algorithm algorithm (with an appropriate pivoting rule so that cycling is avoided) will nd an optimal basic feasible solution, say x, and Let AB be the corresponding basis matrix. Note that T 1 cT x = cT B xB = cB AB b. 1 T T T T 1 The reduced costs are all non-negative, so c T = cT cT B AB A 0. We let y = cB AB . Then c y A, T T T T T 1 or A y c. So y is a feasible solution to the dual LP. Also, b y = y b = cB AB b = c x. We nd the following possibilities for the outcome of a linear program and its dual: Primal \ Dual Finite Optimum Unbounded Infeasible Finite optimum possible impossible impossible Unbounded impossible impossible possible Infeasible impossible possible possible (1)