Lecture 6 1 The Dual of Linear Program

1 Stanford University CS261: OptimizationHandout 6 Luca TrevisanJanuary 20, 2011 Lecture 6In which we introduce the theory of duality in Linear The Dual of Linear ProgramSuppose that we have the following Linear Program in maximization standard form:maximizex1+ 2x2+x3+x4subject tox1+ 2x2+x3 2x2+x4 1x1+ 2x3 1x1 0x2 0x3 0(1)and that an LP-solver has found for us the solutionx1:= 1,x2:=12,x3:= 0,x4:=12of cost How can we convince ourselves, or another user, that the solution is indeedoptimal, without having to trace the steps of the computation of the algorithm?Observe that if we have two valid inequalitiesa bandc dthen we can deduce that the inequalitya+c b+d(derived by summing the left hand sides and the right hand sides of our originalinequalities) is also true. In fact, we can also scale the inequalities by a positivemultiplicative factor before adding them up, so for every non-negative valuesy1, y2 0we also have1y1a+y2c y1b+y2dGoing back to our Linear Program (1), we see that if we scale the first inequality by12, add the second inequality, and then add the third inequality scaled by12, we getthat, for every (x1, x2, x3, x4) that is feasible for (1),x1+ 2x2+ +x4 so, for every feasible (x1, x2, x3, x4), its cost isx1+ 2x2+x3+x4 x1+ 2x2+ +x4 that a solution of cost is indeed general, how do we find a good choice of scaling factors for the inequalities, andwhat kind of upper bounds can we prove to the optimum?

2 Suppose that we have a maximization Linear Program in standard +.. cnxnsubject toa1,1x1+..+a1,nxn ,1x1+..+am,nxn bmx1 0(2)For every choice of non-negative scaling factorsy1, .. , ym, we can derive the inequalityy1 (a1,1x1+..+a1,nxn)+ +yn (am,1x1+..+am,nxn) y1b1+ ymbmwhich is true for every feasible solution (x1, .. , xn) to the Linear Program (2). Wecan rewrite the inequality as(a1,1y1+ am,1ym) x1+ 2+(a1,ny1 am,nym) xn y1b1+ ymbmSo we get that a certain Linear function of thexiis always at most a certain value,for every feasible (x1, .. , xn). The trick is now to choose theyiso that the linearfunction of thexifor which we get an upper bound is, in turn, an upper bound tothe cost function of (x1, .. , xn). We can achieve this if we choose theyisuch thatc1 a1,1y1+ am, a1,ny1 am,nym(3)Now we see that for every non-negative (y1, .. , ym) that satisfies (3), and for every(x1, .. , xn) that is feasible for (2),c1x1+.

3 Cnxn (a1,1y1+ am,1ym) x1+ +(a1,ny1 am,nym) xn y1b1+ ymbmClearly, we want to find the non-negative valuesy1, .. , ymsuch that the above upperbound is as strong as possible, that is we want tominimizeb1y1+ bmymsubject toa1,1y1+..+am,1ym ,1y1+..+am,nym cny1 0(4)So we find out that if we want to find the scaling factors that give us the best possibleupper bound to the optimum of a Linear Program in standard maximization form, weend up with a new Linear Program , in standard minimization 1 IfmaximizecTxsubject toAx bx 0(5)is a Linear Program in maximization standard form, then its dual is the minimizationlinear programminimizebTysubject toATy cy 0(6)So if we have a Linear Program in maximization Linear form, which we are going tocall theprimallinear Program , its dual is formed by having one variable for eachconstraint of the primal (not counting the non-negativity constraints of the primalvariables), and having one constraint for each variable of the primal (plus the non-negative constraints of the dual variables).

4 We change maximization to minimization,we switch the roles of the coefficients of the objective function and of the right-handsides of the inequalities, and we take the transpose of the matrix of coefficients of theleft-hand side of the optimum of the dual is now an upper bound to the optimum of the do we do the same thing but starting from a minimization Linear Program ?We can rewriteminimizecTysubject toAy by 0in an equivalent way asmaximize cTysubject to Ay by 0If we compute the dual of the above Program we getminimize bTzsubject to ATz cz 04that is,maximizebTzsubject toATz cy 0So we can form the dual of a Linear Program in minimization normal form in the sameway in which we formed the dual in the maximization case: switch the type of optimization, introduce as many dual variables as the number of primal constraints (notcounting the non-negativity constraints), define as many dual constraints (not counting the non-negativity constraints)as the number of primal variables.

5 Take the transpose of the matrix of coefficients of the left-hand side of theinequality, switch the roles of the vector of coefficients in the objective function and thevector of right-hand sides in the that:Fact 2 The dual of the dual of a Linear Program is the Linear Program have already proved the following:Fact 3If the primal (in maximization standard form) and the dual (in minimizationstandard form) are both feasible, thenopt(primal) opt(dual)Which we can generalize a littleTheorem 4 (Weak Duality Theorem)IfLP1is a Linear Program in maximiza-tion standard form,LP2is a Linear Program in minimization standard form, andLP1andLP2are duals of each other then: IfLP1is unbounded, thenLP2is infeasible;5 IfLP2is unbounded, thenLP1is infeasible; IfLP1andLP2are both feasible and bounded , thenopt(LP1) opt(LP2)Proof:We have proved the third statement already. Now observe that the thirdstatement is also saying that ifLP1andLP2are both feasible, then they have to bothbe bounded , because every feasible solution toLP2gives a finite upper bound to theoptimum ofLP1(which then cannot be + ) and every feasible solution toLP1givesa finite lower bound to the optimum ofLP2(which then cannot be ).

6 What is surprising is that, for bounded and feasible Linear programs, there is alwaysa dual solution that certifies the exact value of the 5 (Strong Duality)If eitherLP1orLP2is feasible and bounded , thenso is the other, andopt(LP1) =opt(LP2)To summarize, the following cases can arise: If one ofLP1orLP2is feasible and bounded , then so is the other; If one ofLP1orLP2is unbounded, then the other is infeasible; If one ofLP1orLP2is infeasible, then the other cannot be feasible and bounded ,that is, the other is going to be either infeasible or unbounded. Either case will return to the Strong Duality Theorem, and discuss its proof, later in