III. Solving Linear Programs by Interior-Point Methods

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.

B–76 Optimization Methods — §10.2 A∆x = 0 AT∆π +∆σ = 0 X¯∆σ +Σ∆¯ x = −X¯Σ¯e −∆X∆Σe We would like to solve these m + 2n equations for the steps — the m + 2n ∆-values — but although all the terms on the left are linear in the steps, the term ∆X∆Σe on the right is nonlinear. So long as each ∆xj is small relative to x¯j and each ∆σj is small ...

Loading..

Tags:

  Linear, Step, Points, Solving, Equations, Interior, Solving linear, Interior point

Information

Related search queries