Linear Programming: Interior-Point Methods

Chapter 14Linear Programming:Interior-Point MethodsIn the 1980s it was discovered that many large linear programs could be solvedefficiently by formulating them as nonlinear problems and solving them withvarious modifications of nonlinear algorithms such as Newton’s method. Onecharacteristic of these methods was that they required all iterates to satisfythe inequality constraints in the problem strictly, so they became known asinterior-point methods. By the early 1990s, one class—primal-dual methods—had distinguished itself as the most efficient practical approach, and provedto be a strong competitor to the simplex method on large problems. Thesemethods are the focus of this chapter.Interior-point methods arose from the search for algorithms with better theoretical properties than the simplex method. As we mentioned in Chapter ?,the simplex method can be inefficient on certain pathological problems. Roughlyspeaking, the time required to solve a linear program may be exponential in thesize of the problem, as measured by the number of unknowns and the amountof storage needed for the problem data. For almost all practical problems,the simplex method is much more efficient than this bound would suggest, butits poor worst-case complexity motivated the development of new algorithmswith better guaranteed performance. The first such method was the ellipsoidmethod, proposed by Khachiyan [11], which finds a solution in time that is atworst polynomial in the problem size. Unfortunately, this method approachesits worst-case bound on all problems and is not competitive with the simplexmethod in practice.Karmarkar’s projective algorithm [10], announced in 1984, also has the polynomial complexity property , but it came with the added inducement of goodpractical behavior. The initial claims of excellent performance on large linearprograms were never fully borne out, but the announcement prompted a greatdeal of research activity and a wide array of methods described by such labels as“affine-scaling,” “logarithmic barrier,” “potential-reduction,” “path-following,”1

CHAPTER 14. INTERIOR-POINT METHODS2“primal-dual,” and “infeasible interior-point.” All are related to Karmarkar’soriginal algorithm, and to the log-barrier approach described in Chapter ?,but many of the approaches can be motivated and analyzed independently ofthe earlier methods.Interior-point methods share common features that distinguish them fromthe simplex method. Each interior-point iteration is expensive to compute andcan make significant progress towards the solution, while the simplex methodusually requires a larger number of inexpensive iterations. Geometrically speaking, the simplex method works its way around the boundary of the feasiblepolytope, testing a sequence of vertices in turn until it finds the optimal one.Interior-point methods approach the boundary of the feasible set only in thelimit. They may approach the solution either from the interior or the exteriorof the feasible region, but they never actually lie on the boundary of this region.In this chapter, we outline some of the basic ideas behind primal-dual interiorpoint methods, including the relationship to Newton’s method and homotopymethods and the concept of the central path. We sketch the important methodsin this class, and give a comprehensive convergence analysis of a long-step pathfollowing method. We describe in some detail a practical predictor-correctoralgorithm proposed by Mehrotra, which is the basis of much of the currentgeneration of software.14.1Primal-Dual MethodsOutlineWe consider the linear programming problem in standard form; that is,min cT x, subject to Ax b, x 0,(14.1)where c and x are vectors in IRn , b is a vector in IRm , and A is an m n matrix.The dual problem for (14.1) ismax bT λ, subject to AT λ s c, s 0,(14.2)where λ is a vector in IRm and s is a vector in IRn . As shown in Chapter ?, solutions of (14.1),(14.2) are characterized by the Karush-Kuhn-Tucker conditions(?), which we restate here as follows:AT λ s c,(14.3a)Axxi si b,0, i 1, 2, . . . , n,(14.3b)(14.3c)(x, s) 0.(14.3d)Primal-dual methods find solutions (x , λ , s ) of this system by applying variants of Newton’s method to the three equalities in (14.3) and modifying the

14.1. PRIMAL-DUAL METHODS3search directions and step lengths so that the inequalities (x, s) 0 are satisfiedstrictly at every iteration. The equations (14.3a),(14.3b),(14.3c) are only mildlynonlinear and so are not difficult to solve by themselves. However, the problem becomes much more difficult when we add the nonnegativity requirement(14.3d). This nonnegativity condition is the source of all the complications inthe design and analysis of interior-point methods.To derive primal-dual interior-point methods we restate the optimality conditions (14.3) in a slightly different form by means of a mapping F from IR2n mto IR2n m : T A λ s c 0,Ax bF (x, λ, s) (14.4a)XSe(x, s) 0,(14.4b)whereX diag(x1 , x2 , . . . , xn ),S diag(s1 , s2 , . . . , sn ),Tk(14.5)kkand e (1, 1, . . . , 1) . Primal-dual methods generate iterates (x , λ , s ) thatsatisfy the bounds (14.4b) strictly, that is, xk 0 and sk 0. This property isthe origin of the term interior-point. By respecting these bounds, the methodsavoid spurious solutions, that is, points that satisfy F (x, λ, s) 0 but not(x, s) 0. Spurious solutions abound, and do not provide useful informationabout solutions of (14.1) or (14.2), so it makes sense to exclude them altogetherfrom the region of search.Many interior-point methods actually require the iterates to be strictly feasible; that is, each (xk , λk , sk ) must satisfy the linear equality constraints forthe primal and dual problems. If we define the primal-dual feasible set F andstrictly feasible set F o byFFo {(x, λ, s) Ax b, AT λ s c, (x, s) 0},T{(x, λ, s) Ax b, A λ s c, (x, s) 0},(14.6a)(14.6b)the strict feasibility condition can be written concisely as(xk , λk , sk ) F o .Like most iterative algorithms in optimization, primal-dual interior-pointmethods have two basic ingredients: a procedure for determining the step and ameasure of the desirability of each point in the search space. The procedure fordetermining the search direction procedure has its origins in Newton’s methodfor the nonlinear equations (14.4a). Newton’s method forms a linear model forF around the current point and obtains the search direction ( x, λ, s) bysolving the following system of linear equations: xJ(x, λ, s) s F (x, λ, s), λ

CHAPTER 14. INTERIOR-POINT METHODS4where J is the Jacobian of F . (See Chapter ? for a detailed discussion ofNewton’s method for nonlinear systems.) If the current point is strictly feasible(that is, (x, λ, s) F o ), the Newton step equations become x0 AT I0 A 0 .0 λ 0(14.7)S0 X s XSeUsually, a full step along this direction would violate the bound (x, s) 0. Toavoid this difficulty, we perform a line search along the Newton direction so thatthe new iterate is(x, λ, s) α( x, λ, s),for some line search parameter α (0, 1]. Unfortunately, we often can takeonly a small step along this direction (α 1) before violating the condition(x, s) 0. Hence, the pure Newton direction (14.7), which is known as theaffine scaling direction, often does not allow us to make much progress towarda solution.Most primal-dual methods modify the basic Newton procedure in two important ways:1. They bias the search direction toward the interior of the nonnegative orthant (x, s) 0, so that we can move further along the direction beforeone of the components of (x, s) becomes negative.2. They prevent the components of (x, s) from moving “too close” to theboundary of the nonnegative orthant.To describe these modifications, we need to introduce the concept of the centralpath, and of neighborhoods of this path.The Central PathThe central path C is an arc of strictly feasible points that plays a vital rolein primal-dual algorithms. It is parametrized by a scalar τ 0, and each point(xτ , λτ , sτ ) C solves the following system:AT λ sAx c,b,xi si(x, s) τ,0.(14.8a)(14.8b)i 1, 2, . . . , n,(14.8c)(14.8d)These conditions differ from the KKT conditions only in the term τ on theright-hand side of (14.8c). Instead of the complementarity condition (14.3c), werequire that the pairwise products xi si have the same (positive) value for allindices i. From (14.8), we can define the central path asC {(xτ , λτ , sτ ) τ 0}.

14.1. PRIMAL-DUAL METHODS5It can be shown that (xτ , λτ , sτ ) is defined uniquely for each τ 0 if and onlyif F o is nonempty.Another way of defining C is to use the mapping F defined in (14.4) andwrite 0(14.9)F (xτ , λτ , sτ ) 0 ,(xτ , sτ ) 0.τeThe equations (14.8) approximate (14.3) more and more closely as τ goesto zero. If C converges to anything as τ 0, it must converge to a primal-dualsolution of the linear program. The central path thus guides us to a solutionalong a route that maintains positivity of the x and s components and decreasesthe pairwise products xi si , i 1, 2, . . . , n to zero at the same rate.Primal-dual algorithms take Newton steps toward points on C for whichτ 0, rather than pure Newton steps for F . Since these steps are biasedtoward the interior of the nonnegative orthant defined by (x, s) 0, it usuallyis possible to take longer steps along them than along the pure Newton (affinescaling) steps, before violating the positivity condition.To describe the biased search direction, we introduce a centering parameterσ [0, 1] and a duality measure µ defined bynµ xT s1 ,xi si n i 1n(14.10)which measures the average value of the pairwise products xi si . By fixingτ σµ and applying Newton’s method to the system (14.9), we obtain x0 AT I0 A 0 .0 λ 0(14.11) s XSe σµeS0 XThe step ( x, λ, s) is a Newton step toward the point (xσµ , λσµ , sσµ ) C, atwhich the pairwise products xi si are all equal to σµ. In contrast, the step (14.7)aims directly for the point at which the KKT conditions (14.3) are satisfied.If σ 1, the equations (14.11) define a centering direction, a Newton steptoward the point (xµ , λµ , sµ ) C, at which all the pairwise products xi si areidentical to the current average value of µ. Centering directions are usuallybiased strongly toward the interior of the nonnegative orthant and make little,if any, progress in reducing the duality measure µ. However, by moving closerto C, they set the scene for a substantial reduction in µ on the next iteration. Atthe other extreme, the value σ 0 gives the standard Newton (affine scaling)step (14.7). Many algorithms use intermediate values of σ from the open interval(0, 1) to trade off between the twin goals of reducing µ and improving centrality.A Primal-Dual FrameworkWith these basic concepts in hand, we can define a general framework forprimal-dual algorithms.