III. Solving Linear Programs by Interior-Point Methods

1 Optimization MethodsDraft of August 26, Linear Programsby Interior-Point MethodsRobert FourerDepartment of Industrial Engineering and Management SciencesNorthwestern UniversityEvanston, Illinois 60208-3119, (847) 4er/Copyrightc 1989 2004 Robert FourerB 72 Optimization Methods of August 26, 2005B 7310. Essential FeaturesSimplex Methods get to the solution of a Linear program by moving fromvertex to vertex along edges of the feasible region. It seems reasonable thatsome better method might get to an optimum faster by instead moving throughtheinteriorof the region, directly toward the optimal point. This is not as easyas it sounds, in other respects the low-dimensional geometry of Linear Programs can bemisleading. It is convenient to think of two-dimensional and three-dimensionalfeasible regions as being polyhedrons that are fairly round in shape, but theseare the cases in which a long step through the middle is easy to see and makesgreat progress.

2 When there are thousands or even millions of variables, it isquite another matter to see a path through the feasible polyhedron, whichtypically is highly elongated. One possibility, building on the simplex method,would be to increase from zero not one but all variables that have negativereduced costs. No practical way has been found, however, to compute stepsbased only on the reduced costs that tend to move through the center of thepolyhedron toward the optimum rather than across to boundary points that arefar from the optimum (and are not necessarily vertex points ).The key to an effectiveinterior-point methodis to borrow a few simple ideasfrom nonlinear optimization. In the context of Linear programming, these ideasare sufficiently elementary that we can develop them independently.

3 Applica-tions to general nonlinear programming will be taken up in subsequent PreliminariesWe show in this chapter how an effective Interior-Point method can be de-rived from a simple idea for Solving the optimality conditions for Linear pro-gramming. We consider in particular thecomplementary slacknessconditionsthat were derived in Part III for primal and dual Linear Programs in the formMinimizecTxMaximizebT Subject toAx=bSubject toAT cx 0 Complementary slackness says thatx and are optimal provided that feasibility:Ax =b,x feasibility:AT :Eitherx j=0 oraTj j=cj(or both), for eachj=1,..,nTo make these conditions easier to work with, we begin by writing them asequations in nonnegative variables. We treat all vectors as column start by introducing a vector ofslack variables, , so thatAT cmay be expressed equivalently byAT + =cand 0.

4 In these terms,B 74 Optimization Methods =cif and only if =0, so the complementary slackness conditionsbecomex j=0 or j=0 (or both). But saying thatx j=0 or j=0 isequivalent to saying thatx j j=0. Thus we have the following equivalentstatement of the complementary slackness conditions:x and are optimalprovided that they feasibility:Ax =b,x feasibility:AT + =c, :x j j=0 for everyj=1,..,nThese conditions comprise a square system ofm+2nequations in them+2nvariables(x, , ), plus nonnegativity ofxand .It remains to collect the equationsxj j=0 into a matrix equation. For thispurpose, we definediagonalmatricesXand whose only nonzero elements areXjj=xjand jj= j, respectively. For example, forn=4,X= x10 0 00x20 00 0x300 0 0x4 and = 10 0 00 20 00 0 300 0 0 4.

5 The diagonal elements ofX arexj j, exactly the expressions that must be zeroby complementary slackness, so we could express complementary slackness asX = x1 10000x2 20000x3 30000x4 4 = 0 0 0 00 0 0 00 0 0 00 0 0 0 .But this isn2equations, of which all butnare 0=0. Instead we collapse theequations to thensignificant ones by writingX e= x1 10000x2 20000x3 30000x4 4 1111 = x1 1x2 2x3 3x4 4 = 0000 .whereeis a vector whose elements are all 1. We will write this asX e=0, withthe 0 understood as in previous chapters to refer to a vector of have now shown that Solving the primal optimization problem forxand the dual optimization problem for is equivalent to Solving the followingcombined system of equations and nonnegativity restrictions:Ax=bAT + =cX e=0x 0, 0 Draft of August 26, 2005B 75We can regard theinterior points ( x, , )of this system to be those that satisfythe inequalities strictly: x>0, >0.

6 Our goal is to show how interior -pointmethods can generate a series of such points that tend toward a solution of thelinear matrices will prove to be convenient throughout the developmentof Interior-Point Methods . IfFandGare matrices having the vectorsf=(f1,..,fn)andg=(g1,..,gn)on their diagonals and zeroes elsewhere, a diagonal matrix having nonzero 1is a diagonal matrix having nonzero elementsf 1j, or 1 1G=GF 1is a diagonal matrix having nonzero , andF 1f=e, whereeis a vector of all 1 writeF=diag(f)to say thatFis the diagonal matrix constructed in these examples, we will normally use lower-case letters for vectors and thecorresponding upper-case letters for the corresponding diagonal A simple Interior-Point methodMuch as we did in the derivation of the simplex method, we ll start off byassuming that we already know primal-feasible and dual-feasible interior -pointsolutions xand( , ).

7 A x=b, x>0 AT + =c, >0 Our goal is to find solutionsx and( , )such thatAx =bandAT + =c, but withx and being not interior but instead complementary:x j 0, j 0, and at least one of the two is=0, for eachj=1,..,n. We lllater show (in Section ) that the Interior-Point approach is easily extended tostart from any point( x, , )that has x>0 and >0, regardless of whetherthe equations are initially can now give an elementary explanation of the method. Starting from afeasible, Interior-Point solution( x, , ), we wish to find astep( x, , )such that( x+ x, + , + )is a better such solution, in the sense thatit comes closer to satisfying the complementarity find the desired step, we substitute( x+ x, + , + )into the equa-tions for feasibility and complementarity of the solution.

8 Writing X=diag(x), =diag( )and X=diag( x), =diag( )in line with our previousnotation, we haveA( x+ x)=bAT( + )+( + )=c( X+ X)( + )e=0 Since we re givenA x=bandAT + =c, these equations simplify toB 76 Optimization Methods x=0AT + =0 X + x= X e X eWe would like to solve thesem+2nequations for the steps them+2n -values but although all the terms on the left are Linear in the steps, theterm X eon the right is nonlinear. So long as each xjis small relative to xjand each jis small relative to j, however, we can expect each xj jto be especially small relative to xj j. This suggests that we can get a reason-able approximate solution for the steps by Solving the Linear equations that areproduced by dropping the X eterm from the above equations.

9 (The sameapproach will return in a later chapter, in a more general setting, asNewton smethodfor Solving nonlinear equations.)With the X eterm dropped, we can solve the third equation for , = X 1( X e x)= X 1 x,and substitute for in the second equation to getA x=0AT X 1 x= The matrix X 1requires no special work to compute; because Xhas nonzeroentries only along its diagonal, so does X 1, with the entries being 1 our equations in matrix terms, we have an(m+n) (m+n)equation system in the unknowns xand :[ X 1 ATA0][ x ]=[ 0].Because X 1 is another diagonal matrix it has entries j/ xjalong its diago-nal we can optionally solve for x, x= X 1( AT )= x+( X 1)AT ,and substitute for xinA x=0 to arrive at anm mequation system,A( X 1)AT =A x= special forms of these equation systems guarantee that they have solutionsand allow them to be solved this point we could hope to use( x+ x, + , + )as our new,improved solution.

10 Some of the elements of x+ xand + might turn outto be negative, however, whereas they must be positive to keep our new solutionwithin the interior of the feasible region. To prevent this, we instead take ournew solution to be( x+ ( x), + ( ), + ( ))Draft of August 26, 2005B 77where is a positive fraction 1. Because the elements of the vectors xand are themselves>0, we know that x+ ( x)and + ( )will also be strictlypositive so long as is chosen small enough. (The vectors xand servehere as what are known asstep directionsrather than whole steps, and is thestep length.)The derivation of a formula for is much like the derivation of the min-imum ratio criterion for the simplex method (Part II). For each xj 0, thevalue of x+ ( x)can only increase along with ; but for xj<0, the valuedecreases.