4 Duality Theory - University of Washington

1 4 duality TheoryRecall from Section 1 that the dual to an LP in standard form(P)maximizecTxsubject toAx b,0 xis the LP(D)minimizebTysubject toATy c,0 the problemDis a linear program, it too has a dual. Thedualityterminologysuggests that the problemsPandDcome as a pair implying that the dual toDshould :minimizebTysubject toATy c,0 y= maximize ( b)Tysubject to ( AT)y ( c),0 problem on the right is in standard form so we can take its dual to get the LPminimize ( c)Txsubject to ( AT)Tx ( b),0 x=maximizecTxsubject toAx b,0 primal-dual pair of LPsP Dare related via the Weak Duality (Weak Duality Theorem)Ifx2 Rnis feasible forPandy2 Rmisfeasible forD, thencTx yTAx , ifPis unbounded, thenDis necessarily infeasible, and ifDis unbounded, thenPisnecessarily infeasible. Moreover, ifcT x=bT ywith xfeasible forPand yfeasible forD,then xmust solvePand ymust now use The Weak Duality Theorem in conjunction with The Fundamental Theoremof Linear Programming to prove theStrong Duality Theorem.

2 The key ingredient in thisproof is the general form for simplex tableaus derived at the end of Section 2 in ( ).Theorem (The Strong Duality Theorem)If eitherPorDhas a finite optimalvalue, then so does the other, the optimal values coincide, and optimal solutions to :This result states that the finiteness of the optimal value implies the existence ofa solution. This is not always the case for nonlinear optimization problems. Indeed, considerthe problem has a finite optimal value, namely zero; however, this value is not attained byany pointx2R. That is, it has a finite optimal value, but a solution does not exist. Theexistence of solutions when the optimal value is finite is one of the many special propertiesof linear :Since the dual of the dual is the primal, we may as well assume that the primalhas a finite optimal value.

3 In this case, the Fundamental Theorem of Linear Programmingsays that an optimal basic feasible solution exists. By our formula for the general form ofsimplex tableaus ( ), we know that there exists a nonsingular record matrixR2Rn nandavectory2 Rmsuch that the optimal tableau has the form R0 yT1 AIbcT00 = RARRbcT yTA yT yTb .Since this is an optimal tableau we know thatc ATy 0, yT 0withyTbequal to optimal value in the primal problem. But thenATy cand 0 yso thatyis feasible for the dual problemD. In addition, the Weak Duality Theorem implies thatbTy=maximizecTx bTbysubject toAx b,0 xfor every vectorbythat is feasible ,ysolvesD!!!! This is an amazing fact! Our method for solving the primal problemP,thesimplexalgorithm, simultaneously solves the dual problemD!Thisfactwillbeofenormouspractic alvalue when we study sensitivity Complementary SlacknessThe Strong Duality Theorem tells us that optimality is equivalent to equality in the WeakDuality Theorem.

4 That is,xsolvesPandysolvesDif and only if (x, y)isaP Dfeasiblepair andcTx=yTAx= now carefully examine the consequences of this equivalence. Note that the equationcTx=yTAximplies that( )0 =xT(ATy c)=nXj=1xj(mXi=1aijyi cj).In addition, feasibility implies that0 xjand0 mXi=1aijyi cjforj=1,..,n,47and soxj(mXi=1aijyi cj) 0forj=1,.., , the only way ( ) can hold is ifxj(mXi=1aijyi cj)=0 forj=1,.., equivalently,( )xj=0 ormXi=1aijyi=cjor both forj=1,.., , (??)impliesthat0=yT(b Ax)=mXi=1yi(bi nXj=1aijxj).Again, feasibility implies that0 yiand0 bi nXj=1aijxjfori=1,.., , we must haveyi(bi nXj=1aijxj)=0 forj=1,..,n,or equivalently,( )yi=0 ornXj=1aijxj=bior both fori=1,.., two observations ( ) and ( ) combine to yield the following (The Complementary Slackness Theorem)The vectorx2 RnsolvesPand the vectory2 RmsolvesDif and only ifxis feasible forPandyis feasible forDand(i) either0=xjormPi=1aijyi=cjor both forj=1.

5 ,n, and(ii) either0=yiornPj=1aijxj=bior both fori=1,.., :IfxsolvesPandysolvesD,thenbytheStrongDu alityTheoremwehaveequalityin the Weak Duality Theorem. But we have just observed that this implies ( ) and ( )which are equivalent to (i) and (ii) , if (i) and (ii) are satisfied, then we get equality in the Weak Duality , by Theorem ,xsolvesPandysolvesD. The Complementary Slackness Theorem can be used to develop a test of optimality foraputativesolutiontoP(orD). We state this test as a vectorx2 RnsolvesPif and only ifxis feasible forPand there existsa vectory2 Rmfeasible forDand such that(i) for eachi2{1,2,..,m}, ifnPj=1aijxj<bi, thenyi=0, and(ii) for eachj2{1,2,..,n}, if0<xj, thenmPi=1aijyi= :(i) and (ii) implies equality in the Weak Duality Theorem. The primal feasibilityofxand the dual feasibility ofycombined with Theorem yield the result.

6 We now show how to apply this Corollary to test whether or not a given point solvesan LP. Recall that all of the nonbasic variables in an optimal BFS take the value zero,and, if the BFS is nondegenerate, then all of the basic variables are nonzero. That is,mof the variables in the optimal BFS are nonzero since every BFS hasmbasic , among thenoriginal decision variables and themslack variables,mvariablesare nonzero at a nondegenerate optimal BFS. That is, among the constraints0 xjj=1,..,n,0 xn+i=ci Xi2 Naijxji=1,..,mmof them are strict inequalities. If we now look back at Corollary , we see that everynondegenerate optimal basic feasible solution yields a total ofmequations that an optimaldual solutionymust satisfy. That is, Corollary tells us that themoptimal dual variablesyisatisfymequations.

7 Therefore, we can write anm msystem of equations to solve ( )maximize 7x1+6x2+5x3 2x4+3x5subject tox1+3x2+5x3 2x4+2x5 44x1+2x2 2x3+x4+x5 32x1+4x2+4x3 2x4+5x5 53x1+x2+2x3 x4 2x5 10 x1,x2,x3,x4, the pointxT=(x1,x2,x3,x4,x5)=(0,43,23,53,0)s olves this LP? Following Corollary , ifxis optimal, then there exists a vectory2R4feasible for the dual LP to ( ) and which satisfies the conditions given in items (i) and (ii)of the corollary. Pluggingxinto the constraints for ( ) we see that equality is attainedin each of the constraints except the third:(0) + 3 43 +5 23 2 53 +2(0)=44(0) + 2 43 2 23 + 53 +(0)=32(0) + 4 43 +4 23 2 53 +5(0)<53(0) + 43 +2 23 53 2(0) = item (i) of Corollary , we see that the vectory2R4that we seek must have( )y3= >0,x3>0, andx4>0, item (ii) of Corollary implies that the vectorywe arelooking for must also satisfy the equations( )3y1+2y2+4y3+y4=65y1 2y2+4y3+2y4=5 2y1+y2 2y3 y4= ( ) and ( ) together, we see thatymust satisfy266432415 24 2 21 2 1001037750BB@y1y2y3y41 CCA=0BB@65 201 CCA,where the first three rows come from ( ) and the last row comes from ( ).

8 We reduce50the associated augmented system as follows:324165 2425 21 2 1 20010032016r1 4r45 2025r2 4r4 210 1 2r3+2r40010013004r1+r310001r2+2r3 210 1 20010003003r1 r210001010 10r3+2r20010010001r20100113r100100r40001 1 r3+13r1 This givesyT=(1,1,0,1) as the only possible vectorythat can satisfy the requirementsof (i) and (ii) in Corollary To satisfy these requirements, we need only check thatyisfeasible for the dual LP to ( ):minimize4y1+3y2+5y3+y4subject toy1+4y2+2y3+3y4 73y1+2y2+4y3+y4 65y1 2y2+4y3+2y4 5 2y1+y2 2y3 y4 22y1+y2+5y3 2y4 30 y1,y2,y3, , 0 yand by construction the 2nd, 3rd, and 4th of the linear inequality constraintsare satisfied with equality. Thus, it only remains to check the first and fifth inequalities:(1) + 4(1) + 2(0) + 3(1) = 8 72(1) + (1) + 5(0) 2(1) = 16 ,yis not dual feasible.

9 But as observed, this is the only possible vectorysatisfying(i) and (ii) of Corollary ( ), hencexT=(0,43,23,53,0) cannot be a solution to the LP ( ). General Duality TheoryThus far we have discussed Duality Theory as it pertains to LPs in standard form. Of course,one can always transform any LP into one in standard form and then apply the dualitytheory. However, from the perspective of applications, this is cumbersome since it obscuresthe meaning of the dual variables. It is very useful to be able to compute the dual of an LPwithout first converting to standard form. In this section we show how this can easily bedone. For this, we still make use of a standard form, but now we choose one that is muchmore flexible:PmaxPnj=1cjxjsubject toPnj=1aijxj bii2 IPnj=1aijxj=bii2E0 the index setsI, E,andRare such thatI\E=;,I[E={1,2.]}

10 ,m},andR {1,2,..,n}.We use the following primal-dual correspondences to compute the dual of an the DualIn the PrimalRestricted VariablesInequality ConstraintsFree VariablesEquality ConstraintsInequality ConstraintsRestricted VariablesEquality ConstraintsFree VariablesUsing these rules we obtain the dual toPmi=1aijyi cjj2 RPmi=1aijyi=cjj2F0 yii2I,whereF={1,2,..,n}\ example, the LPmaximizex1 2x2+3x3subject to 5x1+x2 2x3 8 x1+5x2+8x3=10x1 10,0 x3has dualminimize 8y1+10y2+10y3subject to 5y1 y2+y3=1y1+5y2= 2 2y1+8y2 30 y1,0 primal-dual pairPandDabove are related by the following weak Duality [General Weak Duality Theorem]LetA2Rm n,b2Rm, feasible forPandy2 Rmis feasible forD,thencTx yTAx , the following statements hold.(i) IfPis unbounded, thenDis infeasible.(ii) IfDis unbounded, thenPis infeasible.