PAGE 1
SENSITIVITY ANALYSIS AND THE ANALYTIC CENTRAL PATH by Allen Holder M.S., University of Southern Mississippi, 1993 B.S., University of Southern Mississippi, 1990 A thesis submitted to the University of Colorado at Denver in partial fulfillment of the requirements for the degree of Doctor of Philosophy Applied Mathematics 1998
PAGE 2
This thesis for the Doctor of Philosophy degree by Allen Holder has been approved by Harvey Greenberg Stephen Billups Gary Kochenberger Rich Lundgren Burt Simon Date
PAGE 3
Holder, Allen (Ph.D., Applied Mathematics) Sensitivity Analysis and the Analytic Central Path Thesis directed by Professor Harvey Greenberg ABSTRACT The analytic central path for linear programming has been studied because of its desirable convergence properties. This dissertation presents a detailed study of the analytic central path under perturbation of both the righthand side and cost vectors for a linear program. The analysis is divided into three parts: extensions of results required by the convergence analysis when the data is unperturbed to include that case of data perturbation, marginal analysis of the analytic center solution with respect to linear changes in the righthand side, and parametric analysis of the analytic central path under simultaneous changes in both the righthand side and cost vectors. To extend the established convergence results when the data is fixed, it is first shown that the union of the elements comprising a portion of the perturbed analytic central paths is bounded. This guarantees the existence of subsequences that converge, but these subsequences are not guaranteed to have the same limit without further restrictions on the data movement. Sufficient conditions are provided to insure that the limit is the analytic center of the lll
PAGE 4
limiting polytope. Furthermore, as long at the data converges and the param eter of the path is approaching zero, certain components of the the analytic central path are forced to zero. Since the introduction of the analytic center to the mathematical pro gramming community, the analytic central path has been known to be analytic in both the righthand side and cost vectors. However, since the objective function is a continuous, piecewise linear function of the righthand side, the analytic center solution is not differentiable. We show that this solution is continuous and is infinitely, continuously, onesided differentiable. Further more, the analytic center solution is analytic if the direction of righthand side change is contained in a particular space. Uniform bounds for the first order derivatives are presented. The parametric analysis of the analytic central path follows as a con sequence of characterizing when the parameterized analytic center converges. The development allows for simultaneous changes in the righthand side and cost vectors, provided the cost perturbation is linear. Although the analytic center solution is not a continuous function of the cost vector, the analytic central path is continuous when viewed as a set. This abstract accurately represents the content of the candidate's thesis. I recommend its publication. SignedHarvey Greenberg IV
PAGE 5
DEDICATION This dissertaion is dedicated to my wife for her constant love and support.
PAGE 6
ACKNOWLEDGMENTS My deepest gratitude is given to Dr. Harvey Greenberg; for without his support and encouragement this dissertation would never have been com pleted. His mentoring over the last few years has been invaluable. Dr. Stephen Billups' meticulous review is much appreciated. In addition, I would like to thank: Dr. Richard J. Caron, Markus Emserman, Caroline Heberton, Dr. Gray Kochenberger, Dave Krutsinger, Dr. Richard Lundgren, Francis New man, Dr. Kees Roos, Dr. Burt Simon, Dr. Jeff Stuart, Dr. Jos Sturm, Lexie Taylor, Dr. Tamas Terlaky, Dr. Radek Tezaur, Dr. Ronald Vaniwaarden, John Wilson, and Dr. Shuzhong Zhang. Last, but not least, I would like to thank all those who have made the Saturday afternoon flag football games possible.
PAGE 7
CONTENTS Figures Tables 1. Introduction 1.1 Sensitivity Analysis 1.2 Basic Notation 1.3 Thesis Outline 2. Central Paths .. 2.1 A Brief Historical View 2.2 Analytic Centers .... 2.3 Basic Properties of the Omega Central Path 2.4 Analytic Centers and Data Perturbations 2.5 Chapter Summary . . .. 3. Marginal Analysis of The Analytic Center Solution 3.1 Introduction . . . . . 3.2 Notation, Terminology, and Preliminary Results 3.3 Differentiating the Central Path . . 3.4 Marginal Properties of the Analytic Center Solution with Respect to the RightHand Side 3.5 Bounding the Derivatives of the Analytic Center Solution .. 3.6 Chapter Summary Vll 1 1 2 5 7 7 8 21 34 47 49 49 51 53 63 78 87
PAGE 8
4. The Omega Central Path and Simultaneous Rim Data Perturbations 88 4.1 Introduction . 88 4.2 Convergence Under Linear Cost Changes 89 4.3 Equivalent Dual Statements ....... 114 4.4 Central Path Convergence Under General Rim Data Changes 134 4.5 Chapter Summary 152 5. Conclusion and A venues for Future Research 154 Notation Index 156 References 160 Vlll
PAGE 9
FIGURES Figure 2.1 A central path. 3.1 An example of tracking the analytic center and its marginal derivatives. .......... 4.1 The geometry of central path convergence. 4.2 Two different interpretations of an analytic center. IX 34 78 94 100
PAGE 10
TABLES Table 201 A synopsis of analytic properties of the omega central path 0 22 301 Some higher order limiting derivatives from example 2012 0 0 63 X
PAGE 11
1. Introduction 1.1 Sensitivity Analysis As defined in the Mathematical Programming Glossary [30], sensitivity analysis is The concern with how the solution changes if some changes are made in either the data or in some of the solution values (by fixing their value). Marginal analysis is concerned with the effects of small perturbations, maybe measurable by derivatives. Parametric analysis is concerned with larger changes in parameter values that affect the data in the mathe matical program, such as a cost coefficient or resource limit. The first papers concerned with sensitivity analysis for linear programs were published in the middle to late 1950s. The original two papers were authored by S. Gass and T. Saaty [20, 77], and the topic was parametric behavior of the objective function. H. Mills published the first paper on marginal analysis and linear programs in 1956 [56], and T. Saaty had the second work on this topic in 1959 [76]. The first English monograph on the topic was published by T. Gal [19] in 1973. The study of sensitivity analysis is paramount for many reasons; two of the most important are: 1
PAGE 12
(1) such investigations provide insight into both the mathematical state ment of the problem and its solution, and (2) sensitivity analysis connects the certainty of the mathematical model with the uncertainty of the real world situation it is modeling. With regard to the latter statement, H. Zimmermann [19] wrote that sensitivity analysis is "the bridge between pure dissemination of information and decision making." In the definition, the solution is usually interpreted as either the optimal value of a variable, or the optimal objective value. The differences in studying how the optimal objective function and a optimal value rely on the data are possibly significant. For example, suppose f(x) is the objective func tion and z* = f(x1 ) = f(x2 ) is the optimal objective value. A data perturbation may cause x1 to remain optimal and x2 to become nonoptimal. In such a case, the optimal objective function value may be invariant under such a perturbation, but the set of optimal elements is not. Such discrepancies lead to a plethora of questions for a practitioner of optimization. 1.2 Basic Notation The following notation is used throughout this work. A notation index is included and the Mathematical Programming Glossary [30] is useful to 2
PAGE 13
any reader when faced with an unknown concept. Some definitions from linear algebra [48] are presented first. Let A be an m x n matrix. The row, column, null, and leftnull spaces of A are defined as follows: row(A) col(A) null(A) leftnull(A) {yA: y E lRm} {Ax: X E lRn} {x E lRn: Ax= 0} {y E lRm : yA = 0}. It is well known [48] that row(A) ..l null(A) and col(A) ..l leftnull(A). Generalized inverses are used to establish many results. A generalized inverse of A is any n x m matrix, denoted A+, for which AA+A A+AA+ A and A+. The linear system of equations Ax = b has a solution if, and only if, AA + b = b. Furthermore, the solutions have the form for any z E lRn. If the generalized inverse has the additional property that AA + and A+ A are symmetric, the generalized inverse is unique and is known 3
PAGE 14
as the MoorePenrose generalized inverse. The MoorePenrose generalized in verse allows easy representations of the projections onto row(A) and null(A), which are needed in Chapter 4. Specifically, the projection of x E lRn onto row(A) is projrow(A)x = AA+x, and the projection of x E lRn onto null(A) is projnull(A)x = (IA+ A)x. For any matrix A, A+ is always assumed to be the MoorePenrose generalized inverse. Sequences are enumerated with superscripts. For example, { xk E W} is a sequence of elements from the set W. The convergence of such a sequence is shown by { xk E W} + x E V, which means the sequence converges to the element x in V. If the elements of the sequence are vectors, the components of the vectors are denoted with the corresponding superscript. For example, {zk E lRn} = {(w,v)k E lRn} = {(wk,vk) E lRn}, where wand vindicate a partitioning of z. A polyhedron is a set of the form { x : Ax :::; b }, where A is an m x n matrix and b is a vector of length m. A bounded polyhedron is called a polytope. Much of this work relies on previous results. For completeness, proofs of these results are included, and the author and reference in which the result and proof are found is cited in the label of the statement. If multiple researchers proved the same result, these references are made in the few sentences preclud ing the statement of the result. 4
PAGE 15
1.3 Thesis Outline Chapter 2 begins by establishing the major definitions and any needed background results. The manner in which these results rely on the problem data has not been investigated, and the chapter proceeds by extending some of these results to the case when certain data perturbations are allowed. An example used to exemplify many concepts is developed. Chapter 3 is concerned with the marginal analysis of the analytic center solution and the subsequent information that this analysis yields about the entire central path. Since differentiating the elements of the central path is crucial to the development of these results, a complete investigation of the differential properties of the central path is presented. This analysis was de veloped by Giiler [63] and is extended to show that the analytic center solution is onesided, infinitely, continuously differentiable. Furthermore, a set of di rections along which the analytic center solution is analytic is classified. The chapter ends by providing uniform bounds for the various derivatives. Chapter 4 contains an analysis of the central path under simultaneous changes in the cost coefficients and the righthand side. The questions answered in this chapter show precisely how the central path relies on the rim data of the linear program. The chapter begins by presenting the analysis for linear 5
PAGE 16
changes in the cost coefficients together with arbitrary changes in the righthand side. In an attempt to extend these results to the situation of arbitrary, simultaneous changes in the cost coefficients and righthand side vectors, two new types of convergence are defined. These types of convergence show that the central paths naturally induce an equivalence relation on the set of admissible cost vectors. The chapter concludes by presenting results showing the difficulty of guaranteeing convergence under arbitrary, simultaneous changes in the rim data. 6
PAGE 17
2. Central Paths 2.1 A Brief Historical View In 1979, Khachiyan [42] showed that the class of linear program ming problems is solvable in polynomial time. The algorithm presented by Khachiyan was an interior point algorithm, meaning that it produced points in the relative interior of the feasible region. Although the theoretical, worst case complexity of this algorithm was provably superior to that of the simplex algorithm, implementation showed no such realistic advantage [91]. This was not the first interior point algorithm presented for linear programming. In 1967, Huard [36] suggested using a method of centers to solve mathematical programs problems. Even though Huard proved that these algorithms converge to an optimal solution, the success of Dantzig's simplex method apparently thwarted any attempt of implementation for linear programming at the time. During the same time period in the Soviet Union, Dikin [10, 11] developed another interior point algorithm which was implemented and used to solve economic problems. Although Dikin's method has a simple interpretation as steepest descent on a scaled space, the polynomality of this algorithm is still not proven and it is 7
PAGE 18
not believed to be polynomial. In 1968 the seminal book by Fiacco and McCormick [13] was published and the term "interior point method" was coined. This text contains the first real development of the theory and use of penalty and barrier methods. In 1984, Karmarkar [41] developed another polynomial time algorithm for linear programs and claimed that this algorithm would be far superior computationally to the simplex algorithm. The mathematical pro gramming community was rather shocked by these claims [46]. Some delved into the theory and implementation of this algorithm to investigate the validity of these claims. It is now understood that interior point methods are viable algorithms and appear computationally superior to simplex based approaches when the problems are large [49, 50, 51, 52]. In 1986, Sonnevend [80] introduced the mathematical programming community to the concept of the analytic center. In [81, 82, 83, 84, 85], Son nevend connects this concept to Karmarkar's algorithm, develops his own al gorithm, demonstrates applications, and together with Stoer, shows several complexity results. It is with this idea that we begin our development. 2.2 Analytic Centers Consider the polyhedron P = {x E Rn : Ax = b x 2:: 0} and its strict interior po = {x E Rn : Ax = b x > 0}. For any positive vector 8
PAGE 19
w E 1Rn, define n Pw(x): P0+ 1R: X+ LWiln(xi) i=l The standard notation that capital letters indicate the diagonal matrix of the corresponding vector is employed. For example, D = diag(w1 w2 ... wn) and X= diag(x1 x2 xn) Since, \72pw(x) = nx2 which is negative definite, Pw ( x) is strictly concave. So, if P is bounded, there exists a unique maximizer of Pw(x) over P0 Definition 2.1 Let P = {x : Ax = b x 0} be a polytope with nonempty relative interior, and w E The unique maximizer of Pw(x) is the omega analytic center of P. If w = e, which is the vector of ones, then the omega analytic center is simply called the analytic center ofP. The concept of the analytic center is fundamental to algorithmically attaining the known polynomality of the class of linear programs. In fact, all known polynomial algorithms for solving linear programs incorporate a centering component in their search directions. There are interior point methods that do not use a centering component in their search direction, such as Dikin's original algorithm, and the polynomality of these algorithms is not known and generally not believed [33]. 9
PAGE 20
It has been shown by Atkinson and Vaidya [3], Freund [15], Goffin and Vial [21], and Roos and Hertog [72] that the omega analytic center can be found in polynomial time. The usefulness of adjusting w to solve linear programming problems and linear complementarity problems is investigated in [1, 55, 57]. The most important reason, from an algorithmic perspective, is that if any strictly interior point is known, it is possible to find an w that makes this feasible point a "good" starting point. Furthermore, the basic idea of weighting the terms of Pw(x) has lead to what are known as "target following methods" for solving linear programs [37, 73]. Another byproduct of the flexibility to adjust the components of w is found in theorem 2.2, which states that every point in the relative interior of a polytope is representable as an omega analytic center. Theorem 2.2 Let P = {x : Ax= b, x 0} be a polytope with nonempty strict interior, and let x E po. Then there exists w E such that {x} = argmax{pw(x) : x E P0}. Proof: Let x E po. Since is a convex program, the Lagrange condition, that there exists y satisfying 10
PAGE 21
is necessary and sufficient for x to be a maximizer of Pw over x E Pg. Noticing that with an appropriate choice of w, wT j(l can be any positive vector, all that must be shown is that row(A) contains a strictly positive element. The boundedness assumption implies there does not exist a solution to the system Ax = 0, x 0, and x #0. Hence, Gordon's theorem of the alternative implies there does exist a solution to the system yA > 0. Associated with any linear program, for which po #0, is a geometric structure called the omega central path or omega central trajectory. As is now developed, the central path is an infinitely smooth path of analytic centers. Throughout, the following "standard form" linear program and its associated dual are considered, IP : min{ ex : Ax = b x 0} and W : max{yb : yA + s = c s 0}, where A E lRmxn, m n, c E lRn, bE lRm, X E lRn, y E lRm, s E lRn and c, y, and s are row vectors. The assumption that the rank(A) = m is made, which has the implications that y and s are related by a onetoone linear mapping and that the mapping x r+ Ax is onto. Because y and s are related in a one toone fashion, a dual element may be referred to by (y, s), y, or s. The rank assumption is made without loss in generality because if A did not have full 11
PAGE 22
row rank, row reduction could be used to form an A' and b', such that A' has full row rank and P = { x : A' x = b', x 2: 0}. The b vector is referred to as the righthand side vector and the c vector is referred to as the cost vector. Together, b and care called the rim data for the linear programs stated above, and notationally r = (b, c) is a rim data instance. Defining z* to be the common optimal value of IP and ID, the following set conventions are made: pb { x : Ax = b x 2: 0} De {(y, s) : yA + s = c, s 2: 0} pg {x: Ax= b, x > 0} vo c {(y, s) : yA + s = c, s > 0} P* r { x E P : ex = z*} V* r {(y, s) E V: yb = z*}. The optimality sets, P; and v;, have another important representation that relies upon the optimal partition. The optimal partition is induced by a strictly complementary optimal solution to IP and ID, which is any primaldual pair, x* and (y*, s*), such that s*x* = 0 and (s*f + x* > 0. Such solutions have been known to exist since 1956, when Goldman and Tucker published this result in [22]. Assuming that x* and (y*, s*) are strictly complementary optimal 12
PAGE 23
solutions for the rim data instance r, define the optimal partition by the index sets B(r) and N(r): B(r) { i : x: ( r) > 0} and (2.1) N(r) {1,2,3, ... ,n}\B(r). (2.2) The dependence of the optimal partition on the rim data is used only when clarity is warranted, and when the rim data instance is understood, the optimal partition is denoted (BIN). Vectors and matrices are often decomposed into subvectors and submatrices corresponding to the optimal partition. To facilitate this, two standard notations are used in conjunction with set subscripts. First, a set subscript attached to a vector indicates the subvector corresponding to the elements contained in the set. Second, a set subscript on a matrix is used to denote the submatrix whose columns are indicated by the set. For example, if (BIN) is the optimal partition for the rim data instance r, This notation and the complementarity condition imply that P* r {x E p: XN = 0} (2.3) 13
PAGE 24
and D* r {(y,s)ED:sB=O} (2.4) For a fixed A matrix, define the following sets of admissible rim data, Q {r = (b, c) E lRm X lRn : Pg =/:0 =/:0}, The above definitions do not correspond to the traditional definition of admissible, which usually means that the defined linear programs have a finite optimal solution. Here the definition is more restrictive, in that only rim data for which Pg and are not empty is included. The next theorem establishes that g is open. This is important because this guarantees that a perturbed admissible rim data element remains admissible. Theorem 2.3 g is an open set. Proof: Let (b, c) E Q. Then there exists x and (f), s) such that Ax = b, x > 0, f)A + s = c, and s > 0. Let U be an open set in lRn which contains x and has the property that x E U implies x > 0. Since the rank of A is m, the linear transformation T : lRn + lRm : x+ Ax is onto. Furthermore, since 14
PAGE 25
Tis a continuous mapping, the open mapping theorem [75] implies that T(U) is open. Let E = min{ Si : i = 1, 2, ... 'm }, and define v = { c : lieell < E }. Then, (b, c) E T(U) x V C Q, and the result follows since T(U) x V is open. The next result shows that the elements of Q guarantee that the primal and dual elements having a bounded duality gap are bounded [64, 71]. Notationally, for any rim element r, and any M E 1R+, define .C(r, M) = {(x, (y, s)) E Pb x De: sx M}. Theorem 2.4 (Roos and Vial [74]) Let r E Q. Then, .C(r, M) is bounded for all M 0. Proof: Let M E 1R+ and (x, (y, s)) E Pg x Then, for any primal and dual elements, x and s, we have i;x E null(A), ss E row(A), and 0 = (ss)(xx) = sxsxsx + sx. (2.6) Hence, if (x, (y, s)) E .C(r, M), sx + sx < sx + M, where the first inequality follows from nonnegativity and the first equality fol lows from equation 2.6. This implies that 0 xi A similar argument 15
PAGE 26
shows that s is bounded. All that remains to be shown is that y is bounded. The full rank assumption of A implies and The boundedness of y now follows since II ( c s) II is bounded. Corollary 2.5 If r E Q, then P; and v; are bounded. The converse of theorem 2.4 is also true [53, 54]. Hence, Q is precisely the set of rim data that guarantees the boundedness of .C(r, M). Corollary 2.5 implies that both P; and v; have omega analytic centers. These omega analytic centers are x*(r) and (y*(r), s*(r)), respectively, and {x*(r)} argmax { L wdn(xi) : x E P;} and argmax{Lwiln(si): (y,s) E v;}. {(y*(r), s*(r))} The development of the central path is completed by considering the penalized linear program, min{cxf.tPw(x): Ax= b, x > 0}. (2.7) 16
PAGE 27
Since the Hessian of the objective function is JLnx2 this mathematical program is strictly convex. So, if a solution exists it is unique. To show that there exists a solution for each JL > 0, consider the function n h(x) = s0xJ1 L wi ln(xi) =exJLPw(x) y0b, i=l where (y0 s0 ) E De. Elementary calculus calculations show for any JL > 0, h(x) attains its global minimum over at x = JL(S0)1w. Since the objective function of the mathematical program in 2.7 differs from h by a constant, the mathematical program in 2. 7 has a unique solution for all JL > 0. The unique solution to 2. 7 has a characterization as part of the unique solution to a system of equations, whose only nonlinearities are the bilinear complementarity equations (equation 2.10 below). This system of equations is developed by noticing that the necessary and sufficient Lagrange optimality conditions imply that the gradient of the objective function is contained in row(A). Hence, for all JL > 0, there exists a y such that Allowing s = JLWT x1 the necessary and sufficient conditions for x may be written as: there exists y and s such that Ax b (2.8) 17
PAGE 28
yA+s Sx c JLW. (2.9) (2.10) Notice that equations 2.8, 2.9, and 2.10 imply that x is the unique solution of the mathematical program in 2. 7 if, and only if, there exists a dual solution that allows the componentwise "near" complementarity shown in 2.10. An immediate implication of equation 2.10 is that if the primal problem is bounded, then the dual problem is unbounded. This is because equation 2.10 has a solution for all p, > 0. So, if Pb is bounded, as p, + oo the dual variable must become arbitrarily large. In fact, equation 2.10 implies that if the primal problem is bounded, each component of s may become arbitrarily large. Also, notice that the full row rank assumption implies that the dual elements are unique. The goal is to use this system of equations and the full rank assump tion of A to show that x, y, and s are analytic functions of p,, b, and c. This result follows as a direct consequence of the implicit function theorem. Theorem 2.6 (Sonnevend [80]) Fix A E IRmxn, m n, with rank( A) = m. Given r E Q, w E and p, > 0, let x, y, and s satisfy equations 2.8, 2.9, and 2.10. Then, x, y, and s are analytic functions of (p,, b, c). 18
PAGE 29
Proof: Let r E Q, and Jl > 0. Furthermore, let x and (f), s) satisfy Ax = b, x > 0, f)A + s = c, s > 0, and Sx = jlw. Define Axb 'l1 : lR3n+2m+l + lR2n+m : (x, y, s, f.l,, b, c) + yA + sc XSj.J,W Then, 'll(x, f), s, jl, b, c) = 0. The Jacobian of 'l1 with respect to x, y, and s is A 0 0 Vx,y,s'll(x,y,s,j.J,,b,c) = 0 AT I S 0 X and the rank assumption implies that this Jacobian is nonsingular. Using the fact that each component function is analytic, the general form of the implicit function theorem [12] implies the result. An immediate consequence of Theorem 2.6 is that if { (M, b, c)k E lR++ x 9} + (Jl, b, c) E lR++ X Q, lim x((J.1,,b,c)k) = x(p,b,c). k+oo Theorem 2.6 also shows that the omega central path, defined below, is an infinitely smooth curve over lR++ x Q. Definition 2.7 Let w > 0 andrE Q. Then CPr {(x(J.1,,b,c),y(J.1,,b,c),s(J.1,,b,c)): J.1, > 0} 19
PAGE 30
is called the primaldual omega central path. The primal omega central path is FCPr { x(JL, b, c) : JL > 0} and the dual omega central path is IXJPr {(Y(JL,b,c),s(JL,b,c)): JL > 0}. The primal omega central path is simply referred to as the omega central path and the primal, dual distinctions are used only when clarity is needed. Also, when w = e, the primal omega central path is called the central path. Notice that x(JL, b, c) is the omega analytic center of pb n{ X : ex = cx(JL, b, c)}, which is bounded from theorem 2.4. Hence, the omega central path has the interpretation of being composed of the omega analytic centers of constantcostslices of Pb Renegar's "conceptual" algorithm [67] is based on this perspective. The omega central path has many properties, and in the next section it is shown that the omega central path converges to an optimal omega analytic center and that the objective function is either strictly monotonic or constant along the central path. Also, the special case when the primal or dual central path contains a single element is characterized. 20
PAGE 31
2.3 Basic Properties of the Omega Central Path Much more than the analytic property shown in theorem 2.6 is known. Properties of the central path were investigated by Fiacco and McCormick from the perspective of nonlinear programming [13]. The important fact that cx(J.1,, b, c) is a strictly decreasing function of M is proven here. Hence, the pre viously mentioned constantcostslices are strictly monotonic as they approach the optimal face. Furthermore, as is shown in theorem 2.8, for any fixed r E Q, the limit of x(J.1,, b, c), as M approaches zero, is the omega analytic center of the optimal face. This result is strengthened in Chapter 4, where necessary and sufficient conditions are given for x(J.1,, b, c) to converge, even when both b and c are changing. Others have investigated limiting behavior of the derivatives, but a discussion of this topic is postponed until chapter 3. Table 2.1 gives a short guide to these and other analytic properties of the omega central path. For our purposes, the omega central path is shown to have a unique limit that is optimal, is strictly complementary, and is the omega analytic center of the optimal set. These results are well established, and the techniques of proof are originally in [53]. The proof uses the support set of a vector, which is defined as the index set, a(x) = {i: Xi> 0}, for any x E 21
PAGE 32
I Author I Type of Results Fiacco and McCormick [13] barrier function concept and convergence proofs McLinden [53] analytic centers, complementarity problems, and properties of limit points Bayer and Lagarias [4, 5] many analytic properties about the central path and the Legendre transformation Megiddo [55] primaldual properties are developed through the use of the logarithmic barrier function Zhao and Zhu [100], properties for the curvature and Zhao [101] properties for the curvature integral of the central path Adler and Monteiro [1] and convergence of the first order Witzgall, Boggs, and Domich [90] limiting derivatives Giiler [63] convergence of higher order derivatives Roos, Terlaky, and Vial [73] text on interior point algorithms; convergence rate properties of the central path and first order derivative convergence Wright [95] text on interior point algorithms; convergence rate properties, and infeasible interior point methods bibliographies [47, 94] large interior point method bibliographies on the internet Table 2.1. A synopsis of analytic properties of the omega central path 22
PAGE 33
Theorem 2.8 (McLinden [53]) Let wE andrE Q. Then both lim x(JL, b, c) and lim s(JL, b, c) J,!+0+ J,!+0+ exist and form a strictly complementary optimal solution. Furthermore, the above limits are the omega analytic centers of the primal and dual optimal sets, respectively. Proof: Since, {(x(JL,b,c),y(JL,b,c),s(JL,b,c)): JL > 0} JLn JLn JLn = {(x(;z:;,b,c),y(;z:;,b,c),s(;z:;,b,c)): JL > 0}, ew ew ew we assume without loss of generality that eT w = n. For any JL > 0, the duality gap 1s Hence, Theorem 2.4 implies that {(x(JL, b, c), s(JL, b, c)): 0 JL p} is bounded for any fixed p > 0. This means that there exists a sequence, say {JLk}, such that lim x(JLk,b,c) = x and lim s(JLk,b,c) = 8. Since, x(JLk,b,c) x E null(A) k+oo k+oo and s(JLk, b, c) s E row( A), (2.11) 23
PAGE 34
Using that x and s are optimal, this is equivalent to 1in= L si(Ji,b,c)xi+ L sixi(Ji,b,c). (2.12) iEu(x) iEu(s) Equation 2.10 implies that si(J.i,b,c)xi(Mk,b,c) equation 2.12 is equivalent to, As Mk+ 0, the equality holds if, and only if, a(x)Ua(s) = {1,2,3, ... ,n}. Hence x and s are strictly complementary, and a(x) = B and a(s) = N. So, any cluster point of the omega central path induces the optimal partition. The fact that x and s are the omega analytic centers of P; and v;, respectively, is now shown. The existence of the limits follows by the uniqueness of the analytic center. Let (x*, y*, s*) E P; x v;. Then, since x(Mk, b, c)x* E null(A) and s(j.jk, b, c)s* E row(A), an analogous argument to that above shows "" WiXi "" WiSi nA + A x s iEu(x*) z iEu(s*) z where the subset relations, a(x*) a(x) and a(s*) a(s), are used. After dividing both sides by n, the arithmetic geometric mean inequality implies ( x* ) w; ( s* ) w; 1 ( x* s* ) n II :!II !2:: :!+ 2:: !1. iEu(x*) Xi iEu(s*) 8i n iEu(x*) Xi iEu(s*) 8i 24
PAGE 35
Allowing s* = s yields II (x;)w; ::; II (x;)w;' iEu(x*) iEu(x*) and XB solves max{ IT : x E P;}. Since this means XB also solves iEB max{L wi ln(xi) : x E P;}, iEB x is the analytic center of P;. Upon replacing x* with x, a similar argument completes the dual statement. The proof technique used in theorem 2.8 is now used to show that if either the primal or the dual polyhedron is bounded, then as f.t increases to infinity the omega central path terminates at the omega analytic center of the polytope. Theorem 2.9 (McLinden [53]) Let w E 1R++ and r E Q. If Pb is bounded and x is the omega analytic center of Pb, then lim x(f.t, b, c) = x. /1+00 If De is bounded and (y, s) is the analytic center of De, then lim (Y(f.t,b,c),s(f.t,b,c)) = (y,s). /1+00 Proof: Recall that equation 2.10 implies that at most one of Pb and De is bounded. Assume that Pb is bounded and that f.tk is a sequence increasing to 25
PAGE 36
infinity such that lim x(Jl, b, c) = x. k+oo Then, for any (x, (f), s)) E Pb x De, the orthogonal argument used in the proof of theorem 2.8 implies where it is assumed that eT w = n. Allowing k + oo, n A n = '"""'WiXi L..J i=l X and the arithmeticgeometric mean inequality implies n n II (xi)Wi ::::; II (xi)Wi. i=l i=l Hence, x = x. A similar argument follows for the dual statement. Theorem 2.9 shows that for any c E Yc, lim x(f.t, b, c) solves tt+OO so long as Pb is bounded and b E Yb Hence, this limit does not depend on c, but only on b. Similarly, when lim (Y(f.t, b, c), s(f.t, b, c)) exists, this limit does tt+OO not depend on b, but only on c. The "bar" notation is used to denote these limits: x(b) lim x(f.t, b, c) and tt+OO (y(c), s(c)) lim (Y(f.t, b, c), s(f.t, b, c)), tt+OO 26
PAGE 37
provided the limits exist. The next result shows the relationship between a constant primal ob jective function and the omega central path. In particular, this result demonstrates that the primal objective function is constant if, and only if, the primal omega central path contains a single element. The equivalence of the fourth statement, which shows how the cost vector indicates a single element omega central path, forces the inclusion of a special case in many of the results in Chapter 4. This is because a cost vector may indicate a single element omega central path, while a perturbed cost vector may not have this quality. Theorem 2.10 (Roos, Terlaky, and Vial [73]) The following are equiva lent for the primal problem: (1) ex is constant on Pb (2) x(f.t1 b, c) = x(f.t2 b, c) for all 0 < f.t1 < f.t2 (3) x(f.t1 b, c) = x(f.t2 b, c) for some 0 < f.t1 < f.t2 ( 4) c E row(A) (5) s(f.t,b,c) = f.ts(1,b,c) for all 0 < f.t Similarly, the following are equivalent for the dual problem: (1) yb is constant on De (2) (y(f.t1,b,c),s(f.t\b,c)) = (y(f.t2,b,c),s(f.t2,b,c)) for all 0 < f.t1 < f.t2 (3) (Y(f.t1,b,c),s(f.t\b,c)) = (Y(f.t2,b,c),s(f.t2,b,c)) for some 0 < f.t1 < f.t2 27
PAGE 38
(4) b=O. Proof: Consider the primal statements. We begin by showing 1 ::::} 2 ::::} 3 ::::} 4 ::::} 1. If 1 holds, then the objective function in 2. 7 is independent of both ex and p,, and 1 implies 2. The result that 2 implies 3 is obvious. Assume that 3 is true. Then, because and the dual conditions are y(p,1 b, c)A + p,1wT x1(p,1 b, c) y(p,2 b, c)A + p,2wT x1(p,2 b, c) c and c. So, c E row(A). Assume 4 is true. Fixing i; E Pb, we have Pb{x} null(A). So, for all X E Pb, c(x x) = 0 and 1 follows. The equivalence of the first four statements is now established. Note that 5::::} 2 follows immediately from the equality, X(p,, b, c)s(p,, b, c) = p,w. To 28
PAGE 39
complete the result, 4 ::::} 5 is shown. Assume that 4 is true and let yA = c. Then, s(1, b, c) E row( A) because s(1, b, c)= cy(1, b, c)A = (yy(1, b, c)) A. Therefore, cJLS(1, b, c) E row(A) for all JL E 1R++ and there exists vi! such that Recognizing that (x(1, b, c), (vi!, JLS(1, b, c))) satisfy equations 2.8, 2.9, and 2.10, for all JL E 1R++' it follows that (x(1, b, c), (vi!, JLs(1, b, c)))= (x(JL, b, c), (y(JL, b, c), s(JL, b, c))). Hence, 5 is true. The proof of the equivalence of the dual statements is similar in nature, and we show 1 ::::} 2 ::::} 3 ::::} 4 ::::} 1. Since (y(JL, b, c), s(JL, b, c)) is the unique solution to n max{yb + JL L wi ln(si) : yA + s = c, s > 0}, i=l if yb is constant, (y(JL, b, c), s(JL, b, c)) is independent of yb and JL. Hence, 1 ::::} 2. The fact that 2 ::::} 3 is obvious. Assume that 3 is true. Then, there exists different JL1 and JL2 in 1R++' such that 29
PAGE 40
The necessary and sufficient Lagrange conditions are and x(p,l, b, c) x(p, 2 b, c) p,l p,2 So, from which it follows that b = 0. The fact that 4 implies 1 is obvious, and the proof is complete. The last result of this section establishes that the primal objective function is monotonically decreasing along the omega central path. This result is originally found in [13]. Theorem 2.11 (Fiacco and McCormick [13]) cx(p,\ b, c)< cx(p, 2 b, c), for all 0 p,1 < p,2 if, and only if, c (j. row(A). Also, y(p,1,b,c)b > y(p,2,b,c)b, for all 0 p,1 < p,2 if, and only if, b =/= 0. 30
PAGE 41
Proof: If cx(p/, b, c) < cx(JL2 b, c), theorem 2.10 implies that c tj. row(A). Assume that c tj. row(A) and let 0 J.11 < J.12 Then the strict concavity of the objective function in 2. 7 implies n cx(JL\ b, c)JL1 LWi ln(xi(JL\ b, c)) i=l n < cx(JL2,b,c)JL1 2:wiln(xi(JL2,b,c)) i=l and n cx(JL2 b, c) JL2 L wi ln(xi(JL2 b, c)) i=l n < cx(JL1,b,c)JL2Lwiln(xi(JL1,b,c)). i=l Multiplying the first inequality by J.12 the second inequality by J.11 and adding the two inequalities produces So, j.12CX(JL1 b, c)+ j.11CX(JL2 b, c)(j.12 JL1 wi ln(xi(JL\ b, c)) + JL2 JL1 wi ln(xi(JL2 b, c))) < j12CX(JL2,b,c) + j.11CX(JL1,b,c)(j.12 JL1 wi ln(xi(JL\ b, c)) + JL2 JL1 wi ln(xi(JL2 b, c))) which implies that 31
PAGE 42
The result now follows by the assumption that p,2 > p,1 The dual result follows from an analogous argument. This section ends with the development of a simple example that is used several times. The simplicity of this example allows the central path to be written in closed form, which is valuable when attempting to motivate results. Example 2.12 Consider the linear program min{ ex : 0 :::; x :::; b }, where we assume that the components of e are not all the same. Incorporating the slack vector, bx, the penalized objective function, with w = e, is n n exp, L ln(xi) p, L ln(bixi) (2.13) i=l i=l The ith component of the gradient is e. .!!_ + ___:_/L_ X bX After finding the roots of this gradient, we see that the central path is given by c;b;+2!1ybrc7+4!12 2c; 32
PAGE 43
This means that { b; ( c; lc; I) if Ci 10 x;(b, c) = lim xi (JL, b, c) 2c; J.L+0+ Qi_ if Ci = 0 2 0 if Ci > 0 bi if Ci < 0 Qi_ if Ci = 0 2 This example shows that x*(b, c) is not a continuous function of c. For example, fixing b = e, 0 if Ci > 0 x;(e, c) 1 if Ci < 0 1 if Ci = 0 2 However, x*(b, c) is a continuous function of b for this example. This property is in general true as shown in chapter 3. The central path for min{10x + y + 100z: 0 :=:; x :=:; 1, 0 :=:; y :=:; 1, 0 :=:; z :=:; 1} is shown in Figure 2.1. Notice that the central path terminates at the unique optimal solution. Furthermore, observe that the magnitudes of the components of c affect the path. Since c3 is the largest component, the path first attempts to drive x3 to zero. Once x3 becomes sufficiently small, it turns to decrease 33
PAGE 44
x1 Finally, it turns again to move x2 towards zero. This idea that the central path makes somewhat sudden turns, and that between these sudden turns it is almost linear, was recently proven by Vavasis and Ye [89]. This geometric characterization leads to an algorithm for which the complexity analysis is not dependent upon b or c. 0.8 0.6 N 0.4 0.2 0 1 0.8 0.6 y 0 0 X Figure 2.1. A central path. 2.4 Analytic Centers and Data Perturbations How the central path and the analytic center solution react to changing data is the topic of interest for the remainder of this thesis. For any r E g, 34
PAGE 45
define br = (&, &::) to be a direction of change. Notice that theorem 2.3 guar antees that for any r E Q and any br, there exists ()* > 0 such that for all (} E [0, ()*), r + (}br E Q. Hence, any direction is admissible. To facilitate linear changes in data, define for any r E Q and any br, bP b + p& and where p and T are always assumed nonnegative. This notation is used only when a direction of change is understood. For general, nonlinear changes in rim data, sequences are used. For example, if a general change in b is desired, then a sequence, {bk}, of admissible righthand sides is used. Directions of change for which the optimal partition does not change on the interval [r, r + ()*br], for some ()* > 0, are of particular interest. Define 1l ( r) { br : there exists (}* > 0 for which (B(r + (}br)IN(r + (}br)) = (B(r)IN(r)) for all(} E [0, ()*)}, {&: (&,0) E 1l(r)}, and { &:: : (0, &::) E 1l(r )}. Recent investigations into the properties of these sets are found in [26], [28], and [31]. The next lemma shows that the optimal partition characterizes 1l(r), 1lb ( r), and 1lc ( r). 35
PAGE 46
Lemma 2.13 Let r be admissible. Then, (1) 1lb(r) = col(AB), and (2) 1lc(r) = {&; E 1lc: &;BE row(AB)}. Proof: For r E g, let x* be an associated strictly complementary optimal so lution, and & E IRm. The optimality conditions defining the optimal partition for changes in the righthand side are, ABXB bp yAB CB yAN < CN XB > 0, where p is sufficiently small. If & E col(AB), then there exists x' such that AB(px') = p&. Since px' > 0 for sufficiently small p, the above conditions hold, and col(AB) 1lb(r). If the optimal partition is invariant for sufficiently small p, then there exists xB(P) such that ABxB(P) = bp. Hence, and & E col(AB) 36
PAGE 47
The argument for the second statement is similar, except the optimality conditions defining the optimal partition are Anxn b yAn xn > 0, where T is sufficiently small. In addition to the characterizations in lemma 2.13 for 1lb(r) and 1lc(r), the following decoupling principle is shown in [26], 1l(r) (2.14) The next theorem is an extension of theorem 2.4 to the cases when rim data elements are allowed to change. It establishes the boundedness of the union over a converging sequence of rim data of the primal and dual elements having a bounded duality gap. Theorem 2.14 Let {rk E 9}+ r E Q. Then, for all M E 1R+, U(rk, M) k is bounded. 37
PAGE 48
Proof: For any (xk, sk) E Pgk x the proof of theorem 2.4 demonstrates that when (x, s) E (rk, M), and njl. Since {rk E 9} + r E Q, the analytic properties of x(p,, b, c) and s(p,, b, c) shown in theorem 2.6 imply that sk + s(Jl, b, c) > 0 and xk + x(Jl, b, c) > 0. This implies that there exists a natural number K such that sf > b, c) and xf > b, c), for all k K and i = 1, 2, ... n. Hence, for all (x, y, s) E and when k K. The fact that y is bounded follows from the onetoone linear relationship between y and s. So, U (rk, M) k>K 38
PAGE 49
is bounded. Since U (rk, M) k
PAGE 50
Since, x(11k; bk; ck;) > 0 r ' s(uk; bk; ck;) > 0 and r ' allowing i to go to infinity implies that i; E P; and (f), s) E D;. The result follows because Pi= {x E pb: XN = 0} and v; = {(y, s) E De: SB = 0}. Lemma 2.15leaves open the question of what happens to XB(r)(JLk,bk,ck) and SN(r)(JLk, bk, ck). The results in chapter 4 characterize the conditions needed to guarantee the convergence of these components, provided the cost vector perturbation is linear. The last theorem of this chapter supplies sufficient conditions for x(JL, b, c) to converge to the analytic center of a polytope. Before proving this result, we present two supporting lemmas. Lemma 2.16 For any matrix, Q E lRpxq, and bE lRq, let Qb = { u: Qu = b, u 2: 0}. If {bk} + b and Qb is nonempty and bounded, then is bounded. 40
PAGE 51
Proof: Suppose, for the sake of attaining a contradiction, that is unbounded. Then, there exists { uk} such that and llukll = oo. Since { is bounded, there exists a convergent subse{ uki } A s { bk } 0 Q A 0 H 0 A 0 quence, say lluk; II + u. mce IIJ.Lk; II + u = owever, smce p, > this leads to the contradiction that for any u E Qb and f3 E IR++' u+f3u E Qb Lemma 2.17 Define Qb as in lemma 2.16. Let {bk} + b, be such that Qbk =/= 0, for all k, and Qb =/= 0. Then, (1) for any u E Qb, there exists { uk E Qbk} + u, and (2) if Qg = { u : Qu = b, u > 0} =/= 0, for any u E Qg, there exists { uk E : k K} + u, for some sufficiently large K. Proof: Let u E Qb Because the following system is consistent, u +bit > 0, there exists bit such that 41
PAGE 52
u + bu 0. All solutions of the equation Qbu = bk b have the form where q E null( Q). Hence, there exists q E null( Q) such that Define qk = min{llqll : q E null(Q), u + bu 0}, and set Then, uk 0, and b + (bkb) lim u + buk k+oo u. 42
PAGE 53
This proves the first statement of the lemma. The second statement follows because if u E Qg, there exists K such that k K implies u+Q+(bk b) > 0. Hence, K, qk = 0 and uk E The next theorem provides sufficient conditions for { x(f.tk, bk, ck)} to converge to the omega analytic center of a polytope. Theorem 2.18 Let wE lRn. Also let {f.tk E lR++} and {rk E Q} be such that: (2) Pb is bounded, (3) { is bounded, and (4) every cluster point is contained in row(A). Then, Similarly, if (2) De is bounded, and (3) { + 0, then, 43
PAGE 54
Proof: Let {bk E + b E Pb be bounded, and { be a bounded sequence such that every cluster point is contained in row(A). Lemma 2.16 implies that {x(JLk, bk, ck)} is bounded, so there exists a subsequence such that x and c. Pb. For any i, the necessary and sufficient conditions describing x(JLk;, bk;, ck;) are which are equivalent to Ax(JLk;, bk;, ck;) Y(JLk;' bk;' ck;) A JLk; b 44
PAGE 55
The full rank assumption implies If we prove x > 0, this last equality implies that the sequence { has a limit, say f). Since cis in row(A), this implies the existence of a f) such that Ax b x > 0. Because these are the necessary and sufficient conditions describing x(b), the result would be established. We now show that x > 0. Lemma 2.17 implies the existence of a sequence, {xi E + x E cki n cki n x(11k; bk; ck;) "'wln (x (uk; bk; ck;)) < xz"'wln (xz.) k; (" z J (" k; z J jj j=l jj j=l which is equivalent to Since {xi} is bounded away from zero, the right hand side of this last inequality is bounded below. Suppose, for the sake of attaining a contradiction, that as 45
PAGE 56
implies n L wi ln ( Xj (p,k;' bk;' ck;)) + oo. j=l Hence, 2.15 implies (xi x(p,k;, bk;, ck;)) + oo. However, since c E row( A) and (xx) E null(A), Hence, no such j exists, and x > 0. The dual argument is similar. Again, lemma 2.16 implies that is bounded, and for some subsequence Clearly, (f), s) E De. We show that (f), s) = (y(c), s(c)), from which the result follows because of the uniqueness of (y( c), s( c)). Similar to the primal case, the rewritten as, c 46
PAGE 57
As before, the key element of the proof is showing that s > 0. This is because S1( k bk k) xi d 'f A 0 { xi } A H f.t ', ', c' w = ll'i' an 1 s > ll'i + x. ence, Ax 0 yA+s c sx w s > 0 which implies that (y, s) = (JJ(c), s(c)). We proceed to shows> 0. Lemma 2.17 implies there exists a sequence { (Yi, si) E such that, { si} + s E Vg. The optimality of ( y (f.tki, bki cki), s (f.tki, bki, cki)) implies or equivalently, As before, s > 0 because the lefthand side of the above inequality is bounded 2.5 Chapter Summary The omega central path, primal omega central path, and dual omega central path were defined, and their analyticity with respect to (f.t, b, c) was 47
PAGE 58
established. This result followed from a direct application of the implicit func tion theorem. The traditional convergence properties of x(f.t, b, c), with b and c fixed, were developed after the boundedness of { x(f.t, b, c) : 0 < f.t :::; p} was shown. This result was extended in theorem 2.14 to include the situation of converging rim data. Because much of what is to follow pertains to linear changes in the rim data, notation to accommodate linear changes was introduced. The set of directions for which the optimal partition is invariant, for arbitrarily small amounts of change, was characterized in lemma 2.13. Theorem 2.18 provides sufficient conditions for a sequence { x(f.tk, bk, ck)} to converge to the omega analytic center of a polytope. 48
PAGE 59
3. Marginal Analysis of The Analytic Center Solution 3.1 Introduction This chapter develops the differential properties of the analytic center solution with respect to the rim data elements. Marginal properties of basic optimal solutions are well understood [19], and an analogy to this analysis is made. When dealing with a basic optimal solution, the marginal analysis is of penultimate concern for post optimal queries since the solution is linear along any given direction of righthand side change. To see this, suppose that B is an optimal basis, which is compatible with & [29]. Then, for sufficiently small 0, this basic solution is (3.1) So, the rate of change along &, for this basic solution, is B1&. Such rates of change are useful when anticipating the behavior of a particular solution under fluctuations in constraint levels. When the primal and dual solutions are unique, the linearity of a basic solution along any given direction of righthand side change makes the marginal analysis important and easy to interpret. However, when the primal 49
PAGE 60
and dual solutions are not umque, a simplex based approach may have to pivot to find a compatible basis for the desired direction of change. In such situations, the degenerate pivots are needed to provide a basic variable that accommodates the sought after change. The analysis presented in this chapter deals with the analytic center solution. Since this solution is unique, the analysis does not have to be divided into separate cases for unique and nonunique solutions. However, the analysis is more complicated because the linearity provided by a basic solution is lost. The main results of this chapter are: the analytic center solution is a continuous function of its righthand side, the analytic center solution is analytic almost everywhere, and the analytic center solution is always infinitely, continuously onesided differentiable. The second property implies that the analytic center solution has a Taylor series expansion with a nontrivial radius of convergence, almost everywhere. Noticing that equation 3.1 is the Taylor expansion of a basic optimal solution, we see that such a Taylor expansion is the exact counterpart for the analytic center solution. Furthermore, the Taylor expansion is easy to calculate as seen in section 3.4. 50
PAGE 61
3.2 Notation, Terminology, and Preliminary Results Let f be a differentiable univariant function defined on the interval lim f'(x) and x+x0+ l f(x) f(x0 ) lm x+x0+ X x0 It is worth noting that even if f is continuous at x0 the equality f' ( x0 +) = is not guaranteed. For example, take f(x) = x sin(x), for x0 = 0. The "prime" notation is not precise enough when dealing with multivariable functions. To accommodate the notational requirements needed for differentiable functions from lRn + lRm, define for a differentiable function to be the vector whose jth component is where fj is the jth component function. This notation is extended for the 51
PAGE 62
rightsided limit of the derivative and the rightderivative as follows, and X z X z The word locally is used to distinguish between onesided analytic properties and analytic properties over a neighborhood. For example, x*(bp, c) is said to be locally differentiable along fh if there exists a neighborhood about zero, say N, such that c) exists for all pEN. Notice that to be locally differentiable along &, it is necessary that the directional derivatives corresponding 52
PAGE 63
to fh and & agree when pis zero. In the next section, a set of directions with this property is classified. The formula for the kth derivative of a composition function [24] is used to develop several results. Let h(x) = f(g(x)), where both f : 1R+ 1R and g: 1R+ 1R are in coo on some suitable neighborhoods. Then h(k)(x) is (3.2) k where the sum is taken over all nonnegative integer solutions to 2:: iji = k i=l k and 2:: Ji = m. i=l 3.3 Differentiating the Central Path The goal of this section is to establish the existence of the the limiting derivatives of the central path, with respect to JL. The first order derivatives were addressed by Adler and Monteiro [1] and Witzgall, Boggs, and Domich [90]. The higher order derivatives were investigated by Giiler [63], and this development is followed here. Although the marginal analysis of x* (r) with respect to b and cis of primary interest, the later sections of this chapter show that this analysis follows once the existence of the limiting derivatives, with respect to JL, is established. The first task is to bound the derivatives with respect to JL. Consider 53
PAGE 64
the defining system of equalities for the central path: Ax(J1, b, c) b (3.3) y(J1, b, c)A + s(J1, b, c) c (3.4) S(J1, b, c)x(J1, b, c) = WJ1. (3.5) Using Leibnitz's rule, the kth differential of equation 3.5 is k ( k ) { w if k = 1 L b, c) b, c) = i 0 if k 2' (3.6) where the '' simply means multiplication. For k 2, define r;i(J1, b, c) to be the above sum without the first and last terms: k1 ( k ) p;}(J1, b, c) = i b, c) b, c). Thus, when k 2, the kth derivatives are iteratively the unique solution to 0 (3.7) b, c) A+ b, c) 0 (3.8) S(J1, b, c) b, c)+ X(J1, b, c) b, c) s}(J1,b,c). (3.9) Since 3.7 implies that b, c) E null(A) and 3.8 implies that b, c) E row(A), b, cf b, c) = 0. 54
PAGE 65
Recalling that n = diag(w), the equality X(p,, b, c)S(p,, b, c)= p,n implies, b, c) b, b, c) b, c)) b, cf S(p,, b, c)n1X(p,, b, c) b, c) b, cf b, c) 0. Hence, b, c) b, c) and b, c) b, c) are perpendicular. Now, for any two perpendicular vectors, say v and w, This, together with 3.9, show that, g}(p,, b, c) 112 S(p,, b, c). b, c)+ b, c) b, c) w S(p,, b, c) b, c) 112 + b, c) b, c) 112 Expressing the norms in the last equality as inner products yields (IIS(p,, b, b, c) 112 + IIX (p,, b, b, c) 112 ) z 55
PAGE 66
So, and (IIS(p,, b, b, c)W + IIX(p,, b, b, c)W) IIS(p,, b, b, c) 112 + IIX(p,, b, b, c) 112 min{w;} < i II k( bc)112 max{w;} P JL, 0 i (3010) This last inequality implies that D!xN(JL, b, c) and D!sB(JL, b, c) are uniformly bounded asp,+ o+o This follows since p1(p,, b, c) = w, x'B(r) > 0, sN(r) > 0, and IIS(p,, b, c)D!x(p,, b, c) 112 + IIX(p,, b, c)D!s(p,, b, c) 112 [ SB(J', b, c) b, c) l SN(JL, b, c) 0 Dp,xN(JL, b, c) min{w;} < i llwll2 max{wi} 0 i The next lemma gives a representation of D!xB(JL, b, c) in terms of b, c), xB(JL, b, c), and DixB(JL, b, c), where j k 1. Such a representation allows the use of an induction argument to establish the convergence 56
PAGE 67
of b, c). Before stating the needed representation of b, c), note that if f(x) = and g(v) = x(v), 3.2 shows that, dk f(g(v)) vk kl k ( (l)( ))jz 2:)1)mm!.,., .,x(v)m1II x ,v )1 ... )k l=1 l. (3.11) x(k) (v) 1 ( m( ) '( ) "( ) k1( )) x2(v) + x(v) hk_1 x v x v x v ... x v (3.12) where corresponds to the index (j1 j2 ... jk) = (0, 0, ... 0, 1), and the function hk_1 defined by 3.12 is a polynomial. function. The next lemma is found in [63]. The proof is included here for completeness. 1 Lemma 3.1 (Giiler [63]) Let r E Q and define Hn(JL, b, c) = Xn(JL, b, c). Then, for every k 1 and p, > 0, where 1r is the projection of onto null(AnHn(JL, b, c)) and h(k1,n) is the vector valued function such that the ith component function, fori E B, is the polynomial in 3.12. 57
PAGE 68
Proof: Since sn(JL, b, c)cn E row(An) and cn = cns'B(r) E row(An), we have that Hence, and n:XB1(JL, b, c)en E row(0"B1 An), for all k > 1. Furthermore, 3.12 shows that, n:xB1(JL, b, c)en XB2(JL, b, c) n:xn(JL, b, c) +XB1enh(kl,B) ( XBm(JL, b, c), b, c)), ... n:1x(JL, b, c)) E row ( 0"8 1 A B) Multiplying on the left by b, c) provides, HB1(JL, b, c) n:xn(JL, b, c)nth(kI,n) ( XBm(JL, b, c), b, c)), ... n:1x(JL, b, c)) E row (AnHn(JL, b, c)). For notational convince, let V =row (AnHn(JL, b, c)) and W =null (AnHn(JL, b, c)). 58
PAGE 69
Since, V and W are perpendicular, projw ( Hi/(f.t, b, c) b, c)Hence, 0 ih(kl,B) ( Xi3m(f.t, b, c), D!x(f.t, b, c)), ... b, c))) projw (Hi31(f.t,b,c) projw ( nih(kl,B) (xi3m(f.t, b, c), D!x(f.t, b, c)), ... b, c))) 0. projw (Hi31(f.t,b,c) (3.13) = projw ( nih(kl,B) (xi3m(f.t, b, c), D!x(f.t, b, c)), ... b, c))). To complete the orthogonal decomposition of the projection of this vector onto V is needed. Since, equation 3. 7 implies we have 59
PAGE 70
Also, since (AnHn)+(AnHn) is the projection operator onto V, the last equality implies (3.14) Adding 3.13 and 3.14 shows that Hn1(f.t, b, c) D:xn(f.t, b, c) projw ( nih(kl,B) (xnm(f.t, b, c), D!x(f.t, b, c)), ... n:1x(f.t, b, c))) (AnHn)+ AN. n:xN(f.t, b, c). Multiplying both sides by Hn(f.t, b, c) proves the result. The importance of lemma 3.1 lies not in the specific representation of b, c), but rather that this representation requires only lower order derivatives of x(f.t, b, c) and b, c). This allows the use of an induetion argument to show that all limiting derivatives exist. The next theorem establishes this result and is found in [63]. Theorem 3.2 {Giiler [63]) Let r E Q. Then, lim n:x(f.t, b, c) J,!+0+ exists for all k 2: 1. 60
PAGE 71
Proof: Assume k = 1. Then, the first derivative of xB(JL, b, c), with respect to p,, reduces to (3.15) As already mentioned, D!xN(JL, b, c) is bounded asp,+ o+. Furthermore, since x'B(r) > 0, (ABHB(JL, b, c))+ converges asp,+ o+, see [63]. This implies that D!xB(JL, b, c) also remains bounded as p, + o+. From this boundedness and the fact that xTv(r) = 0 and s'B(r) = 0, we see that lim X(p,, b, b, c)+ S(p,, b, b, c) !1+0+ = [ XB(r) D!+s'B(r) l = w. SF.r(r) D!+xTv(r) So, The existence of lim D!xB(JL, b, c) is now implied by 3.15. !1+0+ (3.16) Suppose that the result is true for all j between 1 and k 1. Since r;i(p,, b, c) contains derivatives whose order is less than k, the induction hypothesis implies that 61
PAGE 72
exists. Since, (x'B(r), sN(r)) > 0, this implies that remain bounded as JL approaches zero. Hence, the representations for as found in lemma 3.1, show that these derivative also stay bounded as JL+ o+. The result follows by letting JL + o+ in 3.6, and applying the representations from lemma 3.1. To illustrate theorem 3.2, consider the central path from example 2.12. Supposing that c > 0, and 1 c z Some higher order limiting derivatives are found in table 3.1 62
PAGE 73
I Order I Derivative II Order I Derivative I 1 _l 6 2! c; bfc? 2 2 7 0 b;cr 3 0 8 5! b7 cB 4 4! 9 0 bfcf 5 0 10 14! J:9:TO bi Ci Table 3.1. Some higher order limiting derivatives from example 2.12 Now that the differential properties of x(J.1,, b, c), with respect toM are established, the next section shows how to exploit these properties to obtain similar differential properties with respect to the righthand side. 3.4 Marginal Properties of the Analytic Center Solution with Respect to the RightHand Side This section investigates the marginal properties of the analytic center solution with respect to linear changes in the righthand side vector. It was seen in 2.3, 2.4, and lemma 2.13 that the optimal partition defines both the optimal sets and the cones of admissible directions for which the optimal partition is invariant, provided the perturbation is sufficiently small. The first result of this section establishes that the optimal partition also yields a set of righthand 63
PAGE 74
side directions along which the analytic center solution is locally analytic. The main result of this section is that even when an admissible direction is not a locally differentiable direction, one sided derivatives still exist. Theorem 3.3 establishes the local analyticity of the analytic center solution along directions in 1lb This result is quite simple, and all that is needed is to invoke the implicit function theorem. Theorem 3.3 Let r E Q. Then, if fh E 1lb, x*(bp, c) is locally analytic along fh. Proof: Lemma 2.13 implies fh E col(AB) So, there exists a full rank matrix submatrix of A, say AB, with rank(AB) = m', such that {x : ABXB = b + pfh} = { x : ABxB = b + p& }. For sufficiently small p, x'B(bp, c) is defined by the following system of equations, ABxB(bp, c) "f(bp, c)AB + c;(bp, c) XB(bp, c)c;(b, c) Similar to the proof of theorem 2.6, define e. ABXBp&b 'lJ : lR?IBI+m' +1 + lR 2IBI+m' : (X B' "/' c;' p) + "/ AB + c; XBc;Te 64 (3.17) (3.18) (3.19)
PAGE 75
Then, 'll is analytic in an open neighborhood of (x'B(b0 c), r(b0 c), c;(b0 c), 0) and 'll ((x'B(b0,c),!(b0,c),c;(b0,c),O)) = 0. Since the Jacobian of 'll taken with respect to ( x B, 1, c;) and evaluated at ( x'B (b0 c), r(b0 c), c;(b0 c), 0) is nonsingular, the implicit function theorem implies that x'B(bp, c) is an analytic function of p in some sufficiently small neighborhood of zero. Notice that it is important for fh E 1lb, since if it were not, row reduction could not be used to form equations 3.17, 3.18, and 3.19. Theorem 3.3 implies that along a direction of change that does not immediately alter the partition, not only is x* (bp, c) of class C00, but x*(bp, c) has a power series expansion. Differentiating 3.17, 3.18 and 3.19 with respect top shows, 1 1 Dpr(bp, c) AB + Dpc;(bp, c) 0 diag (c;(bp, c)) ( c)) T 0. (3.20) This is a nonsingular system of linear equations in c), c) and c). The following are seen to hold after a some algebraic manipulations, (3.21) (3.22) 65
PAGE 76
Equation 3.20 is used iteratively to establish the higher order derivatives. Similar to the previous section, define Then, 2, 0 k k Dp'y(bp, c)AB + Dpc;(bp, c) 0 diag(c;(bp,c)) which implies Since x'Jy(bp, c) = 0 for sufficiently small p, n;x'Jv(bp, c) 0 for all k and sufficiently small p. The Taylor expansion for x*(bp, c) is 00 x*(bp, c)= L, c)/. k=O 66
PAGE 77
The radius of convergence of this power series still needs investigation. Cur rently, interior point solvers are not capable of using this technique to approx imate a solutions behavior under righthand side perturbation; however, the creator of LIPSOL wishes to add these capabilities [99]. Since all the deriva tives rely on the same matrix factorization, the Taylor expansion is relatively cheap as compared to resolving the problem for several righthand sides. The next aim is to establish that even when fh is not in 1lb, onesided derivatives still exist. Four lemmas are presented in support of this aim. The first of these lemmas was originally shown by Berge in ?? (also see [9, 34]), and states that the limit of any convergent sequence in P;k x v;k is contained in p; X 'D;, provided { rk} + r. Lemma 3.4 (Berge [6]) Let A be an m x n matrix, r E Q, and consider the pointtoset mapping X(r) = {(x, y, s) : (x, y, s) E P; x V;}. Then X is a closed map. Proof: Let {rk E Q}+ r E Q, and {(xk,yk,sk) E P;k X v;k}+ (x,y,s). Then, 67
PAGE 78
Allowing k + oo produces Ax b yA+s c Sx 0 X > 0 s > 0, which implies (x, y, s) E p; X D;. The next lemma provides a monotonicity for the optimal partition, with respect to the righthand side. Results similar to lemma 3.5 are found in [2, 40], and are used in [35]. However, these results are only pertain to linear changes in the righthand side, and not general changes in b. Furthermore, the results in both [2, 40] are developed from a parametric analysis of the objective function value, while development below is a simple polyhedral argument. Lemma 3.5 Let c E Yc and {bk E Yb} + b E Yb Furthermore, let (Bk, Nk) be the optimal partition IP(bk,c) and (BIN) be the optimal partition for IP(b,c) 68
PAGE 79
Then, for sufficiently large k, Proof: We prove the equivalent statement that 'D(bk,c) 'D*(b, c), for sufficiently large ko Suppose, for the sake of attaining a contradiction, that for all natural numbers K, there exists k K such that Then there exists a subsequence {bk;}+ b such that, for all i, Because there exists T such that, { 'D(bki ,c) : i = 1, 2, 0 0 0} = { 'D(bkt ,c) : t = 1, 2, 0 0 0 T} This means there exists {( k k k) p* '1"'\* } X ',y ',s' E (bki,c) X v(bki,c) which contains only a finite number of distinct elements, say and for j = 1, 2, 0 0 0, q, ( p. p.) '1"'\* \'1"'\* y J, S 1 E v(bkj ,c) v(b,c)o 69
PAGE 80
Since none of the cluster points of this sequence are in V(b,c), this is in contradiction to lemma 3.4. Hence, for sufficiently large k, V(bk,c) V(b,c)' which implies B Bk and Nk N. The third lemma in support of showing that x* ( r) is onesided, infinitely, continuously, differentiable along any & states that x* ( r) is a continuous function of b. Continuity is the strongest analytic property allowed for x* (b, c) over all b E when c is fixed. This is because the objective function parameterized with respect to the righthand side is piecewise linear (see [2, 39] for a recent development using the analytic center solution). This means that the analytic center solution is not differentiable at the sharp corners of this parameterized objective function. The continuity result found in the following lemma is frequently used in the next chapter. Lemma 3.6 Let {rk = (bk, c) E Q}+ r E Q. Then, lim x*(rk) = x*(r). k+oo Proof: We show that any convergent subsequence of {x*(bk, c)} converges to {x*(b, c)}. From lemma 2.14, is bounded. Without loss in generality, assume that {x*(bk, c)} + x. Let 70
PAGE 81
(BkiNk) be the optimal partition for IP(bk,c) and (BIN) be the optimal partition for IP(b,c). From lemma 3.5, B Bk, for sufficiently large k. This means x*s(bk, c) > 0, for sufficiently large k. Because x*s(bk, c) is the omega analytic center of the following equation is feasible, Set yk = eT (X8(bk,c))1 Since { (X8(bk,c))1 } converges, {yk} con verges, say to f). From lemma 2.15 {xTv(bk, c)}+ 0. Hence, there exists y such that yAB b rxA1 e B XB > 0. These are the necessary and sufficient Lagrange conditions for x*s(b, c). So, {x*(bk, c)}+ x*(b, c). The last of the four supporting lemmas for theorem 3.8 provides some onesided analytic properties of functions and their inverses. 71
PAGE 82
Lemma 3. 7 Consider the function f [0, a*) + [0, {3*) with the following properties: f ([0, a*))= [0, {3*), f is in coo on (0, a*), f'(x) > 0 for all x E (0, a*), f is continuous on [0, a*), J(k) (0+) exists for all k 1, and f'(O+) > 0. Then, g = f1 exists and has the property that g(k) (0+) exists for all k 1. Furthermore, Proof: Let f be as above. The general inverse function theorem [62] establishes that g = f1 exists and is in coo on (0, {3*). The mean value theorem guarantees that for all a E (0, a*), their exists t(a) E (0, a) such that, f(a)f(O) = f'(t(a)). a From the assumption that f'(O+) exists, lim lf(M)f(o)f'(M)I = lim lf'(t(M))!'(M)I = o. tt+O+ M tt+O+ So, = f'(O+) and f' is continuous at zero. Repeated use of the mean value theorem establishes that f is in coo on [0, a*). 72
PAGE 83
Because f is onto [ 0, ;J*) and strictly increasing on [ 0, a*), f ( 0) = g(O) = 0. Since g' ({3) = (!' (gl(;J))) (3.23) for all ;J E (0, ;J*), the assumption that f'(O+) > 0 immediately implies g'(O+) = Applying 3.11 to 3.23 shows that g(k)(f3) is expressible in terms of f'(g({3)), f"(g({3)), f"'(g(;J)) ... J(k)(g(;J)). So g(k)(O+) exists by induction. Now, suppose for the sake of attaining a contradiction that g is not continuous at 0. This means there exists a sequence {;Jk E [0, ;J*)} + 0 such that {g(;Jk)} f+ 0. Since f is a bijection, there exists a unique sequence, {xk E [0, a*)}, such that f(xk) = {3k. This means the supposition is equivalent to {f(xk)} + 0 and { xk} f+ 0. So there exists E > 0 and natural number K such that {xk : k K} c (E, a*), which implies {f(xk)} c f((E, a*)). Since g is continuous on (0, {3*) and g(f((E, a*)))= (E, a*), J((E, a*)) is open. Further more, 0 tJ_ f ( ( E, a*)), and there exists r5 > 0 such that [0, J) n f ( ( E, a*)) = 0. However, this implies the contradiction that {f(xk)} f+ 0. Since g is continuous at 0, the mean value theorem is used as before to show that g(k) (0+) = (0). 73
PAGE 84
The tools are now in hand to prove the main result of this section. Theorem 3.3 already established that x* ( r) is locally analytic along any direction of righthand side change for which the optimal partition is not immedi ately altered, and the next result shows that even when a change in the optimal partition is forced, one sided derivatives still exist. Theorem 3.8 Let r E Q and fh tj_ 1ib Then, D;x* (bo+, c) exists for all k and Proof: Let r and fh be as above. From [28], there exists p > 0 such that (B ((b + pfh, c)) IN ((b, +pfh, c))) is unchanged for all p E (0, p). Denote this optimal partition by (B'IN'). Lemma 3.5 implies N3 B'\B(r) 10. If i E N\N3, xi(bp, c) = 0 for all p E [0, p). Consider the following linear program which has an optimal value of zero: min{p: ABzB + pfh = b, ZB 2: 0, 2: 0, p 2: 0}. Let { ( ZB (p,), (p,), p(p,)) : p, > 0} be the central path. Then and from the continuity of x*(r) in its righthand side, zB(JL)+ > 0, xk(r) = 0, 74
PAGE 85
as J1 + o+. Furthermore, p(JL) + 0, as J1 + o+, and the optimal partition is ( B I Lill U {I B U Lilli + 1}), where the index I B U Lilli + 1 corresponds to p. The proof of theorem 3.2 implies that > 0, and hence there exists some interval, say [0, JL*), where p(JL) is invertible. Denote the inverse by JL(p) and let the corresponding interval be [0, p*). Then for all p E (0, p*), So, for all i E B U Lill, equation 3.2 implies Lemma 3. 7 implies that JL(p) + o+ as p + o+, and theorem 3.2 consequently shows the existence of dmz. lim d (JL(p)). p+0+ Jlm Lemma 3. 7 also shows the existence of fori= 1, 2, ... k. So D;x*(bo+, c) exists. From lemmas 3.4 and 3.6, x*(bp, c) is a continuous function of p, from which lemma 3.7 shows D;+x*(b0 c) D;x*(bo+, c). 75
PAGE 86
This section ends with an example that demonstrates many of the results just developed. Example 3.9 Consider the linear program min{ x2 : 0 ::; x1 ::; 1, 0 ::; x2 ::; 1, x1 + x2 ::; b3}, which is shown in figure 3.1. After adding a slack vector, 1 0 1 0 0 1 A= 0 1 0 1 0 b= 1 and c = (0, 1, 0, 0, 0). 1 1 0 0 1 The analytic center solution is easily verified as The optimal partitions are ( {1, 2, 3, 5}, { 4} ), ( {2, 3}, {1, 4, 5} ), and ( {2, 3, 4}, {1, 5} ), for b3 > 1, b3 = 1, and 0 < b3 < 1, respectively. Furthermore, since x* ( r) is continuous in b3 Let & = (0, 0, 1f. Then, & E col(AB) when b3 > 1 and 0 < b3 < 1. When 76
PAGE 87
which is a locally analytic function of p on (1 b3 b3 1). Similarly, when 0 < b3 < 1, x;(r) = b3 + p, which is locally analytic on ( b3 1 b3). Hence, theorem 3.3 is validated for this example. Set b3 = 1. To illustrate the application of theorem 3.8, both limiting and onesided derivatives need to be calculated. The limiting rightsided derivative is ( 1 [1 2p+3 ] lim x*(r) = lim 3 2VP2+3p+9 ptO+ 3 ptO+ 0 ) (! )Since, (b + plh, c) = 0 and (b + plh, c) = lim 3 + p v' p2 + 3p + 9 ptO+ 3p 1 6' the equality, (b + plh, c) = (b + plh, c), holds. In Figure 3.1, The 3 darkened circles indicate how the analytic center solution moves as b3 decreases from infinity to 0. When b3 = 1, the optimal partition changes under any perturbation. As just shown, the first order limiting derivatives agree with the onesided derivatives when b3 = 1. 77
PAGE 88
Figure 3.1. An example of tracking the analytic center and its marginal derivatives. 3.5 Bounding the Derivatives of the Analytic Center Solution The previous section showed that x* ( r) is a continuous function of b and is analytic along (&, 0) when & E col(AB) Furthermore, theorem 3.8 established that even when x* (r) is not differentiable along &, it is onesided, infinitely, continuously differentiable. The two main results of this section provide uniform bounds on these derivatives. The first of these results show that the derivatives of x*(r) along & are uniformly bounded. The second of 78
PAGE 89
these results shows that is uniformly bounded over {wE llwll = 1}. Both of these results use an observation due to Stewart [86] (see also [10, 14, 87]), which is stated in lemma 3.10. Define D++ to be the set of positive diagonal matrices in lRmxm. For any D E D++ set AD = A and PD = The following lemma shows that PD is uniformly bounded over D++ Lemma 3.10 {Stewart [86]) There is a number k > 0, such that sup IIPDII < k. DED++ Proof: Let C = {u E col(A): llull = 1} and K = U leftnull(DA). DED++ Denoting the closure of K by K, the first fact to establish is that K n C = 0. This would imply inf llvull > 0, (u,v)ECxK 79
PAGE 90
which is then used to complete the result. Suppose for the sake of attaining a contradiction that K n C =/= 0. Then there exists a sequence { vk E K} + u E C. For every k there exists Dk E D++ such that vk E leftnull(Dk A). Hence, 0 = vk Dku = L uid7vi u;#O Since, llull = 1, some ui =/= 0. However, for sufficiently large k, uivf > 0 when ui =/= 0, which implies the contradiction that the righthand side of the last equality is positive. Hence, K n C = 0. Define 1 k II II> o. inf uv (u,v)ECxK For any fixed DE D++ IIPnll = max IIPnwll Let llwll = 1 and w = u + v, llwll=l where u E col(A) and v E leftnull(DA). Then IIPnwll = llull and to bound IIPnll we show that llull is bounded. Without loss of generality, it is assumed that u =I= 0. Since E C and E leftnull(DA), 1 llwll llull llull llu+vll I lull + 1 < k' 80
PAGE 91
So, IIPnll :::; k. Since k is independent of D, sup IIPnll :::; k. DED++ The following corollary contains the exact statements used to establish the desired bounds on the derivatives. Corollary 3.11 (Stewart [86]) If A has full column rank, there exists k such that sup II (AT DA)1 AD II :::; k DED++ and sup IIA+IIk. DED++ Proof: Since the full column rank of A implies the proof of the first inequality is immediate from lemma 3.10, Furthermore, the full column rank assumption implies 81
PAGE 92
Hence, sup II (Dt A)+ Dt II sup IIA+ Pnll DED++ DED++ < IIA+II sup IIPnll DED++ Corollary 3.11 allows the following definition for any full column rank matrix, XA sup II(ATDA)1ADII DED++ The next theorem establishes that the first order derivatives along any fh are uniformly bounded. Theorem 3.12 Let r E Q and fh be fixed. Then, Furthermore, if fh E 1lb, where A and & are defined as in the proof of theorem 3.3. 82
PAGE 93
Proof: Let r and fh be as stated. bP, c) is defined by the following equations: bP, c) fh bp, c)A + bp, c) 0 S(p,, bP, bP, c)+ X(p,, bP, bP, c) 0, which implies Hence, corrallary 3.11 and the assumption that A has full row rank establish the first bound. Similarly, 3.21, theorem 3.8, and corollary 3.11 provide the remaining two bounds. In contrast to theorem 3.12, which provides uniform bounds on the directional derivatives, the forthcoming material shows that b, c) is uniformly bounded over {w E : llwll = 1}. Recalling from theorem 2.2 that any element in the relative interior of a polytope is an omega analytic center, we have that such a result is essentially shows that the bounds provided by theorem 3.12 are independent of a specific omega central path. The result relies on the assumption that the dual is not degenerate. This is because dual nondegeneracy is shown in the next lemma to guarantee that AB has full row 83
PAGE 94
rank, which is needed to invoke corollary 3.11. In the following lemma, the dimension of a set in IR n is defined to be the dimension of the smallest affine subspace containing the set. Lemma 3.13 (Roos, Terlaky, and Vial [73]) Let r E Q. Then, dim(P;) IBI rank(AB) and mrank(AB) Proof: Because P; = {x: ABxB = b,xB O,xN = 0}, the smallest affine subspace containing P; is { x : ABxB = b, XN = 0}. The dimension of this affine space is equal to the dimension of the null(AB) which is lEIrank(AB) Similarly, v; = {(y, s) : yA + s = c, SB = 0, SN 0} and the smallest affine subspace containing D; is {(y, s) : yAB = CB, yAN + SN = CN, SB = 0}. Since sN is uniquely determined by any y that solves yAB = cB, this affine space has the same dimension as the leftnull(AB) The proof is complete because the dim (leftnull(AB)) = mrank(AB) Lemma 3.13 shows that the dual solution is unique if, and only if, AB has full row rank. An explanation of the required dual nondegeneracy follows. Recall that lemma 3.1 showed that 84
PAGE 95
The first problem that a dual nondegeneracy assumption solves is the con vergence of asp,+ o+. The problem here is, that in general, a sequence of matrices {Ak}, which converges to A, does not guarantee { (Ak)+}+ A+. See [8] for an example of such a sequence. However, if AB has full row rank, Since invertible matrices have the desired convergence property, The dual nondegeneracy assumption overcomes a second problem. Because dual nondegeneracy implies that AB has full row rank, this assumption allows the use of corollary 3.11. From 3.16, = wN, and (3.24) Corollary 3.11 guarantees So, if WN is uniformly bounded over llwll = 1}, is uniformly bounded over { w E : II w II = 1}. The next lemma provides such a result, and the statement of the uniform bounds follows. 85
PAGE 96
Lemma 3.14 As in lemmas 2.16 and 2.17 let Q = {u: Qu = b, u 0}, where here we assume that Q is bounded and has a nonempty strict interior. Let u(w) be the omega analytic center of Q. Then, Proof: Since llwll = 1, eT w :::; n. The necessary and sufficient conditions describing u(w) are the existence of (v(w), w(w)) such that Qu(w) b v(w)Q + w(w) 0 U(w)w(w) = w. As in the proof of theorem 2.4, let u E Q0 and (v, w) be such that vQ + w = 0 and w > 0. Then, Since wi(w) = and the last bound given is independent of w, the result is proven. Theorem 3.15 Let r E Q. Then, if the dual solution is unique, sup wE llwll = 1} < oo. 86
PAGE 97
Proof: From equation 3.24, Hence, + < X;](r) X;](r)) +IIIIANIIII ( wN) II +II WN) II The assumption of a unique dual solution, corollary 3.11, and lemma 3.14 provide the result. 3.6 Chapter Summary The results of this chapter establish that the analytic center solution has the following properties: x* ( r) is a continuous function of b, x* ( r) is locally analytic along any & E 1lb, and the one sided derivatives of x*(r), along any&, always exist. Furthermore, theorems 3.12 and 3.15 show that, under a dual nondegeneracy assumption, the first order derivatives are uniformly bounded, independent of which omega central path is of concern. Weather or not this result is true without the nondegeneracy assumption remains an open question. 87
PAGE 98
4. The Omega Central Path and Simultaneous Rim Data Perturbations 4.1 Introduction This chapter establishes a set convergence property for the closure of FCPn denoted FCPr and defined as FCPr U{x*(r)} if Pb is unbounded and FCPrU{x*(r),x(b)} ifPb is bounded. For any r E Q and&, define { z B ( 17, b, &: ) : 17 > 0} to be the omega central path corresponding to (4.1) where (BIN) is the optimal partition for the data instance r. For any eta E lR, zB(rJ, b, &:) is referred to as the 17 point of Because {zB(rJ, b, &:) : 17 > 0} is an omega central path, it has all the properties established in chapter 2. For example, zB(rJ, b, &:) is an analytic function on lR++ x Yb x lRn. The omega analytic center solution for 4.1 is denoted by &:) = lim zB(rJ, b, &:). 1)+0+ (4.2) 88
PAGE 99
Recognizing that {(zB, 0) : ABZB = b, ZB 0} = P;, corollary 2.5 implies that the feasible set for 4.1 is bounded. This together with theorem 2.9 implies, The closure of is defined similarly to FCPr; Specifically, the main result of this chapter is that _lim __ FCP(b,c) = FCPrU (FCP(r,fc) X oiNI)' (b,cr )+(b,c) (4.3) where oiNI is the set containing the zero vector of length INI. This result follows from a parametric analysis of the elements in FCPn with respect to T along a fixed Surprisingly, the parametric analysis presented for T allows general changes in the righthand side vector (notice that b + b in the above limit with no restrictions on {bk} ). This means that simultaneous changes in the cost coefficients and righthand side vectors are allowed, so long as the cost coefficient change is linear. As seen in theorems 4.5 and 4.14, extensions to theorem 2.8 are possible with such as parametric analysis. 4.2 Convergence Under Linear Cost Changes The fact that x* ( r) is not a continuous function of c is demonstrated in example 2.12. Since discontinuities produce severe changes in x*(r), one 89
PAGE 100
might believe that severe changes in the central path must occur. However, there is a continuity of central paths, when central paths are viewed as sets. To motivate this idea consider the following example. Example 4.1 Consider the linear program, The optimal objective value is zero and the analytic center solution is Furthermore, the optimal partition is B {1, 2, ... n} \ {j} and N {j}. Let&:: be such that &:i #0 for some i #j. Using equation 2.13 in Example 2.12, the central path is defined by Ttc;+2ttJT2tcr+4tt2 if i=/::j and &;i #0 2Tfci Xi (M, e, C7 ) = 1 if i#j and &;i = 0 2 l+Tfc;+2ttJ(l+Tfc;)2+4tt2 if 2(1+Tfc;) The question posed is, "How does Xi(J.1,, e, cT) behave as T+ o+?" Consider the three cases, (1) J.1, = 'TJT, for some positive real value 'TJ, (2) M = T 2 and 90
PAGE 101
(3) 11 = y"T. Case 1 Let 'f] be any positive real value. Then making the substitution 11 = 'f]T, Xi('fJT, e, T) Since, we have Tfc;+27)TJ T 2 fcJ+4(7JT) 2 if i=j:j and &;i =I 0 2Tfc; 1 if i=j:j and &;i = 0 2 1 +Tfc;+27)TJ (1 +Tfc;)2+4(7)T )2 if 'l=J 2(1+Tfc;) fc;+2ryJ fcJ+4772 if i=j:j and &;i =I 0 2fc; 1 if i=j:j and &;i = 0 2 1 +Tfc;+27)TJ (1 +Tfc;)2+4(7)T )2 if '{ =J. 2(1+Tfc;) fc;+2ryJ fcJ+4772 2fc; 0 if i =/: j and &;i =/: 0 if i =/: j and &;i = 0 if '{ = J. Notice that O"(x) = B, and hence i; E P*. Upon examining equations describing the central path for min{&;BxB'f] L ln(xi): ABxB = b XB > 0}, iEB 91
PAGE 102
x B is found to be the TJ point of Hence, for any { Tk} + 0 and Case 2 When J1 = T2 &:;+2TJ&:r+4T2 if i=/=j and =I= 0 2&:; Xi(T2,e,T) = 1 if i=/=j and = 0 2 1+T&:;+2T2J(1+T&:;)2+4T4 if '{ =J. 2(1+T&:;) Allowing T + o+ produces, 1 if i=/=j and < 0 0 if i=/=j and > 0 Xi= lim xi(T2 e, T) = T+0+ 1 2 if i=/=j and = 0 0 if '{ =J. Hence, in this case x is the analytic center solution to min{cTx: Ax= b, x 0}, where T > 0 is sufficiently small. Furthermore, x B is the analytic center solution to Case 3 If JL = y'T, T&:;+2y'TJT2&:r+4T if i=/=j and =I= 0 2T&:; Xi( yT, e, T) = 1 if i=/=j and = 0 2 l+T&:;+2y'Tj(1+T&:;)2+4T if '{ =J. 2(1+T&:;) 92
PAGE 103
When T + o+' { .!. if x = lim xi( y'T, e, T) = 2 Tt0+ 0 if i=fj 'l =J, which is precisely the analytic center solution of min {ex : Ax = b x 2: 0}. The idea here is that the perturbed central paths are converging not only to the central path corresponding to the linear program with no data perturbation, but also to the central path corresponding to the minimization of the perturbation direction over the optimal face. Figure 4.1 shows the central paths for {T T } mm x + y + z : 0 < x < 1, 0 < y < 1, 0 < z < 1 4 2000 where T = 1, 0.8, 0.6, 0.4, 0.2 The vertical line is the central path for min { z : 0 :::::; x :::::; 1, 0 :::::; y :::::; 1, 0 :::::; z :::::; 1}, and the path contained in the xy plane is the central path for 0 { 1 1 } mm x + y: 0 < x < 1, 0 < y < 1 4 2000 93
PAGE 104
0.8 0.6 N 0.4 0.2 0 1 0.8 y 0 0 X Figure 4.1. The geometry of central path convergence. The first lemma of this section shows that cnxn is constant on the null space of An. This fact is almost obvious once the optimal set is recognized as an affine transformation of the null space An. Lemma 4.2 cnu = 0 for all u E null(An). Proof: If the columns of An are linearly independent, zero is the only element in null(An) and the result is trivial. Otherwise, let un E null(An) and 0) E (P;)0 Then there exists a> 0 such that 0) + a(u, 0) E (P;)0 Since + aun) = 0 = acnun = cnun. 94
PAGE 105
Although the primary interest in what follows is the behavior of the omega central path under linear parametric changes in c, the addition of al lowing general changes in b presents no difficulty. Historically, the properties of a solution under simultaneous changes have received less attention than the properties of a solution when only one rim data element is perturbed. A recent exception to this is found in [28], where it was shown, using the analytic center solution, that the objective value is a quadratic function of r. The ability of allowing simultaneous changes in b and c is a strength of the forthcoming analysis. The next lemma demonstrates how the constantcostslices corre sponding to each M > 0 are modeled through righthand side changes. A consequence of this modeling is that xB(M, b, c), for any fixed jj > 0, is describ able without the linear portion of the objective function. This follows because the omega central path's reliance on the objective function is implicitly ex pressed through the optimal partition. It is precisely this modeling scheme that allows for the simultaneous changes in the rim data. Lemma 4.3 cBXB is constant on 95
PAGE 106
and consequently x B (JL, b, c7 ) is the unique solution to min{ TfcnxnJ1 L wi ln(xi) : Anxn = bANxN(JL, b, C7 ) xn > 0}. (4.4) iEB Proof: By definition, x(JL, b, c7 ) is the unique solution to n min{ exJ1 L:wdn(xi) + Tfcx: x E Pb} i=l Holding the components of xN(JL, b, c7 ) constant, xn(JL, b, c7 ) is the unique solution of min{ cnxnJ1 L wi ln(xi) + Tfcnxn : Anxn = bANxN(JL, b, cT) xn > 0}. iEB So, once it is shown that cnxn is constant on the result follows. If the columns of An are linearly independent, the result is immediate because this set contains a single element. Otherwise, let xk and be in Then xkE null(An), and lemma 4.2 implies for all 0 a 1, which proves the desired result. 96
PAGE 107
Lemma 4.3 allows the following useful convergence result, which states that if M converges to zero, the righthand side vector converges, and the cost vector is held fixed, then x(jj, b, c) converges to the analytic center solution. The proof is similar to the proof of theorem 2.18. Proof: Let {bk} and {Mk} be as above. From theorem 2.14, {x(jjk, bk, c)} is bounded. Let { x(Mk;, bk;, c)} be a subsequence such that Establishing that x is x*(r) proves the result by of the uniqueness of x*(r). min{L ln(xj) : ABXB = bkiANxN(Mk;' bki' c), XB > 0}. jEB The necessary and sufficient conditions for this math program are that, for any i, there exists yi such that, bki A x bki c) N N r 97
PAGE 108
Let so that If x > 0, {yi} converges, say to f), and because lemma 2.15 shows we then have, Ax b x > 0. Since these are the necessary and sufficient conditions describing x'B(r), the result would follow. The fact that x > 0 is forthcoming. Lemma 2.17 implies the existence of a sequence {ik} such that, bki A X (uki bki c) N N ,_., ik > 0, and lim ik x > 0. The optimality of x B (f.tk;, bk;, c) implies that L bk;, c)) 2: L jEB jEB 98
PAGE 109
As i + oo the righthand side of the above inequality converges to Hence, { x(p,k;, bk;, c)} is bounded away from zero, and x > 0. Lemma 4.3 leads to the following observation: (4.5) which is crucial in establishing subsequent results. In words, each element of the central path is also an element of a central path contained in a constantcostslice and defined by the perturbation direction. Figure 4.2 illustrates these two interpretations of central path elements. The vertical line is the central path for min { z : 0 x 1, 0 y 1, 0 z 1}, the curve in the x, yplane is the central path for 1 mm { x + 10 y : 0 x 1, 0 y 1}, and the curve from to (0, 0, 0) is the central path for IP1 : min{x + 1 1 0y + z: 0 x 1, 0 y 1, 0 z 1}. The constantcostslice is, for some fl > 0, {(x,y,z): 0 x 1,0 y 1,0 z 1,z = z(p,b,c)}, 99
PAGE 110
and the curve on this constantcostslice is the central path for IP2 : min{x + 1 1 0y: 0 x 1,0 y 1,z = z(p,,b,c)}. Equation 4.5 shows how the central paths for IP1 and IP2 intersect. N 0.8 0.6 0.4 0.2 0 1 y 0 0 X Figure 4.2. Two different interpretations of an analytic center. From theorem 2.14, 100
PAGE 111
is bounded, for any p > 0 and 7 > 0, and hence has at least one cluster point. However, if {p,k} and { Tk} are positive sequences converging to 0, the sequence { does not have to have a limit point. Hence, guaranteeing the existence of lim x(p,,b,c7), (tt,b,cr )+(O,b,c) is, in general, not possible. This means extending theorem 2.8 to include shifting rim data is not straightforward. However, the next theorem does extend theorem 2.8 to include the case of general righthand side changes and linear cost coefficient changes. The conditions stated for the extension are "nearly necessary and sufficient", as shown in lemmas 4.6 and 4. 7. Theorem 4.5 Let (p, b, c) E 1R+ x Q and &; be fixed. Also, let {p,k E 1R++} + x(p, b, c) if Jl>O x*(r) if fl = 0 and lim = oo lim x(p,k, bk, C7k) = k+oo 7 k+oo (zB(TJ, b, &;), 0) fl = 0 and lim = TJ > 0 if k+oo 7 (z'1(b, &;), 0) if fl = 0 and lim = 0. k+oo 7 Proof: The case when p > 0 is an immediate consequence of theorem 2.6. So, assume fl = 0 and consider the case when, k l It 0 lm k = TJ > k+oo T 101
PAGE 112
Lemma 2.15 implies that Since, { is bounded away from zero, theorem 2.6 implies that The next situation considered is when, ILk hm k = 0. k+oo T Since lemma 2.15 implies the sequence lemma 4.4 implies that which establishes the result in this case. Lastly, assume that ILk hm k =oo. k+oo T 102
PAGE 113
Once again, lemma 2.15 implies the sequence Furthermore, l &; l" Tk& (A ) 1m k = 1m k= 0 E row B k+ 00 /:!:____ k+ 00 jj Tk Since corollary 2.5 shows that P; is bounded, the conditions to apply theorem 2.18 are satisfied, which states that Together with definition ?? this last result is used to show This means that {xk E FCP(bk,crk)}+ x must imply U(* INI) X E FCPr FCP(r,fc) X 0 verges would be of great use. Theorem 4.5 is used to develop such necessary 103
PAGE 114
and sufficient conditions; almost yielding enough information to state these conditions directly. The problem is that if p = 0, not enough is shown about the last three limiting values stated in theorem 4.5. The next two lemmas add this needed information and theorem 4.8 states the necessary and sufficient conditions. Lemma 4.6 Let r E Q, &; tJ_ 1lc, and {bk E YB} + b. Also, let {p,k E 1R++} + 0 and { Tk E 1R++} + 0 be such that the sequence { } does not converge. Furthermore, let { and { '!J;} be two convergent subsequences, one of which possibly converges to infinity. Then, implies 1 ( k; bk; ) .../.. l" ( kj bkj ) lm X It CTki f lm X It c kj 0 T Proof: Without loss in generality, assume Theorem 4.5 implies that 1 ( k bk ) lm X It ' CTki = (zB(r, &:), 0) 104 l.f 1 i2 o lm kT'
PAGE 115
and k = r? < oo J+00 T J x*(r) k f 1" 1!:....}_ l lm k 00. j+oo T J Since &:: tj. 1t0 lemma 2.13 implies that &:B tj. col(AB) Theorem 2.11 now provides that for any ry1 < ry2 and the result follows. Lemma 4. 7 If r E Q and &:: E 1tc, for all 'T/ E IR++. Proof: Lemma 2.13 implies that &:B E row(AB) and theorem 2.10 implies imply the result. Theorem 4.8 contains necessary and sufficient conditions to assure the 105
PAGE 116
Theorem 4.8 Let r E Q. Also, let {JLk E 1R++}+ 0, {Tk E 1R++}+ 0, and exists if, and only if, { converges, possibly to infinity. Proof: From lemma 4.7, if&: E 1ic, Since lemma 3.6 shows that z1 is a continuous function of its righthand side x*(r). Consider the case when &: tj_ 1ic If { converges, even to infinity, theorem 4.5 demonstrates that the limit exists. If { does not converge, this sequence has at least two cluster points, one of which may be infinity. Hence, 106
PAGE 117
there exist at least two convergent subsequences of { say { and { one of which may converge to infinity, such that Theorem 4.5 implies that both l ( k; bki ) lm X J..l CTki z+oo and exist, and lemma 4.6 implies that these limits are different. So, { x(J..Lk, bk, CTk)} does not converge and the result follows. The following set convergence property is the main result of this chapter, and it shows exactly how the primal omega central path behaves as a set under simultaneous changes in the righthand side vector and cost coefficient vector, provided that the cost coefficient change is linear. Theorem 4.9 If rEg and&; is fixed, 107
PAGE 118
Proof: Let {bk E + b E and { Tk E 1R++} + 0. The first part of the proof establishes Suppose the sequence { xk E FCP(bk,crk)} + x. For each k, let JLk be such that possibly to infinity. To show that x E FCPr U ( FCP(r,&;) x oiNI), three cases are considered. Case 1 If {JLk;} + p > 0, theorem 2.6 implies A 1' ( k bk ) (b ) X = 1m X J1 ', ', C7k; = X Jl, C Since x(p, b, c) E FCPr, this situation is complete. Case 2 Suppose {JLk;} + 0. Theorem 4.8 shows that when &: E 1ic, A 1' ( k bk ) *() FC.'P x = 1m x J1 C7k; = x r E r. Furthermore, theorem 4.8 shows that when &: tJ. 1ic, { must converge, possibly to infinity. From theorem 4.5, x*(r) (zn(b, &:), o) 108 l'f 1' ll.ki 1m T. = oo i+oo 7 l'f 1' ttki 0 lm ::: k+oo 7
PAGE 119
Since x*(r) E FCPr, and both zn(TJ, b, &:) and z'B(b, &:) are in FCP(r,&:)' this case is validated. Case 3 Assume {JLk;} + oo. This case is completed once theorem 2.18 is shown to apply, which in turn provides that A 1" ( k bk ) (b) X = 1m X jL ', ', C7k; = X Since { bk;} + b and { ;:;; } + 0 E row( A), all that is left to establish is that Pb is bounded. Assume for the sake of attaining a contradiction that Pb is unbounded. Then there exists a sequence {xi E Pbk;} such that II xi II + oo and xi lim + = 0, j = 1, 2, ... n. The optimality of x(JLk;, bk;, C7k;) implies J.L n n ( k; bk; ) k; '""' 1 ( ( k; bk; ) ) < i '""' 1 ( i ) C7k; x JL C7k; JL Wi n x j JL C7k; C7k; x Wi n x j j=l j=l or equivalently n n CTki ( i ( k; bk; )) '""' 1 ( ( k; bk; ) '""' 1 ( i) ;;: X X jL C7k; + Wi n X j jL C7k; 2: Wi n X j JL j=l j=l However, since { x(JLk;, bk;, C7k;)} + x and .lim +. = 0, the contradiction J.L that the lefthand side of this inequality is bounded above implies that Pb is bounded. The proof has so far established that if a sequence { xk E FCPw ,(\k)} converges, the limit of this sequence is in FCPr U ( FCP(r,&:) x oiNI). The next part of the proof shows that any element in FCPr u ( FCP(r,&:) X oiNI) is the 109
PAGE 120
Let x E FCPr. In the case where Pb is bounded and x = x(b), theorem 2.18 shows that {x(k, bk, CTk)} + x. If x = x(p,, b, c) or x = x*(r), theorem 4.5 implies 1 k {x(p,+k,b ,cTk)} + x(p,,b,c) and {x(H, bk, cTk)} + x*(r). Let x E FCP(r,&:) x oiNI. If xis either (zn(TJ, b, &:), 0) or (z'B(b, &::), 0), lemma 2.15 and theorem 4.5 imply The possibility that x = x*(r) is taken care of in the previous paragraph. The proof has now established that What remains to be shown is that if a convergent sequence, {xk E FCP(bk,crk)}, contains infinitely many times either x* (bk, CTk) or, in the case when Pb is bounded, x(bk), the limit of this sequence is in FCPr u ( FCP(r,&:) X oiNI). IfPb is bounded, Pbk is bounded for sufficiently large k by lemma 2.16. Furthermore, lemma 3.6 shows that x(b) is a continuous function of b (since 110
PAGE 121
setting c = 0 implies x*(r) = x(b)). So, if {xk E FCP(bk,crk)}+ x and contains x(bk) infinitely many times, x = x(b). Suppose that {xk E FCP(bk,cTk)}+ x and that the sequence contains infinitely many elements of the form x* (bk, CTk). The first step in handling this situation is to show that { x'Jv} + 0. Let E > 0. By definition, So, when xk = x* (bk, CTk), there exists pk > 0 such that f.t E (0, pk) implies there exists natural number K, such that k K implies llxN(f.tk, bk, CTk)ll < Hence, when k K, < f, and { x'N} + 0. Now, using lemmas 3.6 and 4.4 to establish the third and fourth equalities respectively, lim ( lim x B (f.t, bk, CTk )) k+oo J1+0+ lim (lim zn( ANxN(f.t,bk,CTk),fc)) k+oo 11+0+ T 111
PAGE 122
&;). Hence, if { xk E .FCP (bk ,crk)} + x and contains infinitely many elements of the form x*(bk, C7k), x = (z'B(b, &;), 0) E .FCPr and the proof is complete. The proof of theorem 4.9 does not use any dual information. This 1s because it is possible that both the rim data and primal elements converge, while the dual elements diverge. For example, if c E row(A) and {p,k} = {1, 2, 1, 2, 1, 2, ... }, x(p,k, bk, C 7k) converges to the analytic center of P1r However, theorem 2.10 implies that the corresponding dual sequence, {s(p,k, bk, C7k)}, has the two cluster points s(1, b, c) and 2s(1, b, c) = s(2, b, c). The problem here is that the near complementarity constraint implies that sf = The failure of the dual elements to converge is now easily seen from X; the divergence of the sequence {p,k}. In general, even if both {p,k} and {xf} converge, the convergence of the sequence { } is not guaranteed unless lim > 0. k+oo Once the dual counterparts are established in the following section, example 4.19 shows exactly how this can happen. The next theorem does not completely resolve this issue, but it does show when the convergence of {p,k} 112
PAGE 123
is guaranteed. 0. Then, the convergence of { x(ILk, bk, C7k) E FCP(bk,crk)} implies the convergence of {ILk} (possibly to infinity, if Pli is bounded) if, and only if, c rf. row(A). Proof: Suppose that c E row(A). Consider the situation ofPI.i being bounded, {ILk} = {1, 2, 1, 2, ... }, and { Tk} = UJ. Then, ILk hm k =oo, k+oo T and independent of whether or not &; E row(An), Hence, if c E row (A), the convergence of the sequence { x (ILk, bk, C7k)} cannot guarantee the convergence of {ILk}. Assume c rf. row(A) and suppose for the sake of attaining a contradiction that {ILk} does not converge. Then there exist subsequences, {ILk;} and such that 0 ::; lim ILk; < lim ILkj :=::; oo. z+oo J +oo If 0 < lim ILk; = theorem 2.6 implies that z+oo l ( k bk ) ( 1 b ) lm X IL '' CTki = X IL c z+oo 113
PAGE 124
Similarly, theorem 2.6 and theorem 2.9 imply l x(JL2 b, c) lim x(JLki bki c k.) = j+oo T J x(r) if if lim JLki = J.12 < oo J+00 JLki = oo. J+00 However, theorem 2.11 implies cx(JL1 b, c) < cx(JL2 b, c) < cx(r) for all 0 < J.11 < J.12 where the last inequality is included only when x exists. This is a contradiction since this implies l ( k; bki ) 1l" ( kj bkj ) 1m X J1 C7k; 1 1m X J1 C kj J+00 T The only situation left is when Jim Jlk; = 0. However, Jim Jlk; = 0, together z+oo z+oo with lemma 2.15, lead to the contradiction: Hence, {JLk} must converge. 4.3 Equivalent Dual Statements This section presents the dual counterparts of the previous section. There there are no new proof techniques, and consequently, the results of this section may be read without the proofs. Example 4.19 shows exactly how the convergence of both the rim data and primal elements does not guarantee the 114
PAGE 125
convergence of the dual elements. The first Lemma is the dual statement of Lemma 4.2. Lemma 4.11 yb = 0 for all (y, s) E leftnull ( [ :B ] )Proof: Let ( fj, S N) E left null ( [ :B ] ) and (y', s) E ('D; )". Then (y*, (0, sjy)) + O(y, (0, BN)) E v;, for sufficiently small 0. Since (y* + Oy)b = y*b, for sufficiently small 0, yb = 0. The perpendicular property shown in lemma 4.11 is now used to show that (y(p,, bP, c), sN(JL, bP, c)) is uniquely optimal on a cut through the dual feasible region. Lemma 4.12 Let r E Q and & be fixed. Then, yb is constant on and consequently (y(p,, bP, c), sN(JL, bP, c)) is the unique solution to max{py& + p, L wi ln(si) : iEN Proof: By definition (y(p,, bP, c), s(p,, bP, c)) is the unique solution to n max{yb + py& + p, LWi ln(si): i=l 115
PAGE 126
Fixing sB(JL, bp, c), (y(JL, bp, c), sN(JL, bp, c)) is the unique solution to max{yb+py&+JL L Wi ln(si) : yAB = cBsB(JL, bp, c), yAN+sN = cN, BN 2: 0}. iEN So, the result follows once it is shown that yb is constant on If the rows of are linearly independent, then the result follows since this set contains a single element. Otherwise, let (y1 s}v) and (y2 be in Then, and lemma 4.11 implies for all 0 a 1, which proves the result. 116
PAGE 127
As a dual counterpart to define {(p(r],&,c),qN('fJ,&,c)): 'f] > 0} to be the central path corresponding to the linear program, Both IXJP r and IXJP(r,&) are defined as FCP r and FCP(r,&) were defined. As in the previous section, the needed observations provided by lemma 4.12 are that (4.6) and Similar to lemma 4.4, the next lemma provides a useful convergence result when b is held fixed. Lemma 4.13 Let f E Q, { ck E 9c} + c E Yc, and {JLk E 1R++} + 0. Then, Proof: Let { ck} and {JLk} be as above. Theorem 2.14 implies that 117
PAGE 128
is bounded and hence contains a convergent subsequence. Let Showing that (f), s) = (y*(r), s*(r)) proves the result by the uniqueness of (y*(r), s*(r)). Clearly, (f), s) E 'De;. Lemma 4.12 shows that solves max { ln(sj) : yAB = CBBB(Mk;, b, Ck;), yAN + SN = CN, SN > 0}. JEN The necessary and sufficient Lagrange conditions for this mathematical program are the existence of xi such that 0 If s N > 0, { x1v} converges, say to x N. In this case, setting 118
PAGE 129
0. Hence, because Lemma 2.15 shows { sn(JLk;, b, ck;)}+ 0, BN > 0 implies yAn en yAN + SN CN Ax 0 XN f;1 e, which are the necessary and sufficient conditions for (y, s) = (y*(r), s*(r)). The fact that sN > 0 is now established. Lemma 2.17 guarantees the existence of a sequence {(yi, s1v)} that converges to (Y, BN ), where BN > 0 and L ln (sj(JLk;,IJ,ck;)) 2: L ln (sD. jEN jEN 119
PAGE 130
Since the righthand side of this inequality converges to LjEN ln (sj), sN > 0, and the result follows. The next theorem is the dual extension of theorem 2.8 to include the case of general cost coefficient changes and linear righthand side changes. Theorem 4.14 Let (p, r) E IR+ x g and & be fixed. Also, let {p,k E IR++}+ jl, {pk E IR++} + 0, and { ck E Yc} + c. Then, (y(p,b,c),s(p,b,c)) if jl>O (y*(r), s*(r)) if jl = 0' oo k+oo P (p(ry, &, c), (0, qN(rJ, &, c))) if jl = 0 lim J!k = rJ > 0 k+oo pk (p*(&, c), (o, qjy(&, c))) if jl = 0 lim Lt. = 0 k+oo pk Proof: If jl > 0, the result follows as a direct consequence of theorem 2.6. Assume that jl = 0 and consider the case when lim = rJ > 0. Lemma 2.15 k+oo P implies 120
PAGE 131
Since is bounded away from zero, theorem 2.6, together with 4.6, and 4. 7 imply that and k k lim y (p, b pk c ) k+oo p(ry, fh, c) = q(ry,fh,c). The next situation considered is when lim = 0. Since lemma 2.15 k+oo P implies lemma 4.13 implies that k k lim y (p, b pk c ) k+oo p*(fh, c) and q*N(fh, c). 121
PAGE 132
The last case to consider is when lim !:{; = oo. Once again, lemma 2.15 k+oo P implies that Furthermore, lim = 0. k+oo 1!::::... pk Since corollary 2.5 shows that v; is bounded, the conditions to apply theorem 2.18 are met, which implies k k lim y (p, b pk c ) k+oo y*(r) and srv(r). As in the previous section, the goal is to use theorem 4.14 to establish necessary and sufficient conditions for { (p,k, bpk, ck)}, which guarantee the 122
PAGE 133
enough added information to state such conditions. Lemma 4.15 Let r E Q, & t/.1lb, and {ck E Yc}+ c E Yc Also, let {JLk E 1R++} + 0 and {pk E 1R++} + 0 be such that the sequence { } does not k kj converge. Let { ?+} and { ?7} be two convergent subsequences, one of which possibly converges to infinity. Then, implies l ( ( k; b k; ) ( k; b k; ) ) lm y JL pki c s JL pki c Proof: Assume without loss of generality that From theorem 4.14, and l ( ( k; b k; ) ( k; b k; ) ) . lm y JL pki c s JL pki c { (p*(&, c), (o, qN(&, c))) (p(r/,&,c), (O,qN(r/,&,c))) if lim l= 0 i+oo P l"f l" Lt..!:_ l 0 lm k 7] > i+oo P l ( ( k. b k ) ( k b k )) lm y JL J kj c J s JL J kj c J = J+00 p p 123
PAGE 134
l (p(TJ2 &, c), (0, qN(TJ2 &, c))) if lim = TJ2 > 0 J+00 p J k (y*(r), s*(r)) if lim = oo. J+00 p J Since & 1lb, lemma 2.13 and theorem 2.11 imply that for any TJ1 < TJ2 p*(&, c)&> p(TJ\ &, c)&> p(TJ2 &, c)&> y*(r)&, which proves the result. Lemma 4.16 If rEg and & E 1lb, (P(TJ, &, c), (o, qN(TJ, &, c)))= (p*(&, c), (o, q*N(&, c))), for all TJ E 1R++. Proof: Lemma 2.13 implies that & E col(AB) and theorem 2.10 implies that 1R++ Since (p*(&, c), (0, q*(&, c)))= lim (P(TJ, &, c), (0, qN(TJ, &, c))), 1)+0+ the proof is complete. The next theorem characterizes the conditions for which the sequence 124
PAGE 135
Theorem 4.17 Let r E Q. Also, let {JLk E lR++}+ 0, {pk E lR++}+ 0, and exists if, and only if, { } converges, possibly to infinity. Proof: If fh E 1lb, lemma 4.16 implies that and 125
PAGE 136
From lemma 3.6, both p* and q'fv are continuous functions of their right hand p*(fh, c) and = q*N (fh, c). Assume fh tJ_ 1lb If { converges, even to infinity, then theorem 4.14 shows the existence of ( y(f.tk, bpk, ck), s(f.tk, bpk, ck)). If { does not converge, then this sequence has at least two cluster points, one of which may be infinity. Let { and { be two convergent subsequences such that Theorem 4.14 implies that both l ( ( k; b k; ) ( k; b k; ) ) lm y f.t pki c s f.t pki c and 126
PAGE 137
exist and lemma 4.15 implies that these limits are different. The last theorem is the dual analog to theorem 4.9, and it shows how the dual omega central path behaves under simultaneous perturbations in the rim date, provided that the change in b is linear. In the statement of the theorem, WP(i'h,c) x oiBI is used to denote {(y, (0, sN)): (y, sN) E WP(i'h,i'h)} Theorem 4.18 If rEg and & is fixed, Proof: Let { ck E Yc} + c E Yo and {pk E 1R++} + 0. The first part of the proof establishes Suppose the sequence { (yk, sk) E WP(bpk>ck)} converges to (f), s). For each k, let JLk be such that (yk, sk) = ( y(JLk, bpk, ck), s(JLk, bpk, ck)). Consider a subsequence of {JLk}, say {JLk; }, that converges, possible to infinity. The task of showing that (f), s) E WPr u (wP(i'h,c) X oiBI) is divided into three cases. Case 1 If {JLk;} + jl > 0, theorem 2.6 implies (iJ, s) l ( ( k; b k; ) ( k; b k; ) ) lm y J1 pki c s J1 pki c ztoo (y(p,b,c),s(p,b,c)) E WPr, 127
PAGE 138
and this case is complete. Case 2 Suppose {Jtk;} + 0. When fh E 1lb, theorem 4.17 shows that (p*(fh,c), (O,qiv(fh,c))) E IXJP(&,e) x oiBI. Also, when fh 1lb, theorem 4.17 guarantees that { converges, possibly to infinity. Then, from theorem 4.14, ( A A) l" ( ( k; b k;) ( k; b k; )) y' s . lm y Jl pki c s Jl pki c (y*(r), s*(r)) if oo k+oo P (p(ry, &, c), (0, q(ry, &, c))) if lim M: = rJ > 0 k+oo P (p*(fh, c), (o, q*(fh, c))) if 0. k+oo P Since (y*(r), s*(r)), (p(ry, fh, c), (0, q(ry, fh, c))), and (p*(fh, c), (0, q*(fh, c))) are all in IXJP(&,e) X QIBI, this case is dismissed. Case 3 Assume {Jtk;} + oo. This case is completed once it is shown that theorem 2.18 is applicable, which in turn shows that Since { ck} + c and { ::: } + 0, all that is left to show is that 'De is bounded. Assume for the sake of attaining a contradiction that 'De is unbounded. Since 128
PAGE 139
the unboundedness of De means there exists a sequence { (yi, si) E D ck;} such that II si II + oo and { } + 0. The optimality of ( ( k; b k; ) ( k; b k; ) ) y f.t pki c s f.t pki c implies n n ( k; b k; ) b k; '""' 1 ( ( k; b k; ) ) > i b k; '""' 1 ( i ) y f.t pk; c pk; + f.t Wi n s j f.t pk; c y pk; + f.t Wi n s j j=l j=l or equivalently, b k n n ( ( k; b k;) i) p '""' 1 ( ( k; b k;)) > '""' 1 ( i ) y f.t pk; c y + Wi n s j f.t pk; c Wi n s j f.t j=l j=l The contradiction that the left hand side of this last inequality is bounded implies that De is bounded. So far, the proof has shown that if a sequence { ( yk, sk) E WP(b pk ,ck)} converges, the limit point of this sequence must be an element of The next piece of the proof shows that every element in Let (y, s) E WPr. From theorem 2.18, if De is bounded and (y, s) = (y,s) = (Y(f.t,b,c),s(f.t,b,c)) or (y,s) = (y*(r),s*(r)), 129
PAGE 140
theorem 4.14 shows and { (y(j;},bpk,ck),s(j;},bPk'ck))}+ (y*(r),s*(r)). Let (y, s) E IXJP(&,e) x oiBI. If (y, s) is (p('fJ, &, c), (0, qN('fJ, &, c)) or (p*(&, c), (0, q'fv(&, c)), lemma 2.15 and theorem 4.14 demonstrate that { ( y ( 'f] pk, b Pk; ck) s ( 'f] pk b Pk; ck)) } + (p ( 'f], & c) ( 0, q N ( 'f], & c) ) ) and The proof has now established that What remains to be shown is that if the convergent sequence { (yk, sk) E IXJP(bpk>ck)} contains infinitely many of either (y*(bpk,ck),s*(bpk,Ck)), or in the case when De is bounded, ( y( ck), s( ck)), the limit point of the sequence is contained in IXJPr u ( IXJP(&,e) X oiBI). From lemma 2.16, Dck is bounded when De is bounded. Since lemma 3.6 shows that (y(c), s(c)) is a continuous function of c, 130
PAGE 141
when the sequence contains (y(ck), s(ck)) infinitely many times. Suppose { (yk, sk) E IXJP (brhoklck} + (y, s), and that the sequence contains infinitely many elements of the form ( y* (bpk, ck), s* (bpk, ck)). First, the fact that lim s'B(bpk,ck) = 0 is established. By definition, k+oo p, E (0, pk) implies exists natural number K, such that k K implies Hence, when k K, < E, and lim s'B(bpk, ck) = 0. Now, using lemma 4.13 to establish the third equality, k+oo 131
PAGE 142
= (p*(&, c), c)). Hence, if { (yk, sk) E LCP (b pk>ck)} + (y, s), and the sequence contains infinitely many elements of the form ( y* (bpk, ck), s* (bpk, ck)), (y,s) = (p*(&,c), E LCP(&,cb) x oiBI, and the proof is complete. As in the previous section, this last result did not use any primal information in the proof. This is because the primal elements may diverge even when both the rim data elements and p, converge. This section ends with an example demonstrating such behavior. Example 4.19 Consider the linear program, 132
PAGE 143
From example 2.12, { = { 7k{x_;i (1 +pkfh )+2ttk J ( 7k&;i)2 (1 +pkfh )2+(2ttk )2 2T &:; (1 +pk&)+2ttk j (1 +pkfh)2+(2ttk )2 2 if i = 1, 2 if i = 3 + pk&J) + + pk&J)2 + if i = 1, 2 + pk&) +ILk+ pk&J)2 + (2p,k)2 if i = 3. the primal problem is not in symmetric form), it follows that the complementary dual variables are Si(JLk, bpk, C7k) l 2 kTk{x_;i if i = 1, 2 7k{x_;i (1 +pkfh)+2ttk J ( 7k&;i)2 (1 +pkfh)2 +(2ttk )2 2ttk if i=3 (1 +pk&)+2ttk J (1 +pkfh)2+(2ttk )2 { 2 ( ____tL_ )2 ( k&; )2 k&; if i = 1, 2 l+pk& + T i l+pk& T i v ( ttk f 2ttk if i = 3. 2 l+pkfh + 1 l+pkfh 1 IR++} + 0, the sequence { x(p,k, bpk, C7k)} has the two cluster points, 133
PAGE 144
and while the sequence {s(JLk, bPk' C7k)} has the limit, (0, 0, 1). 4.4 Central Path Convergence Under General Rim Data Changes The previous two sections discussed the convergence properties of the central path under linear changes in the objective function. Characterizing the convergence of { x (JL, b, c)} and { (y (JL, b, c), s (JL, b, c))} was paramount in establishing the results of the last two sections. The restriction of allowing only linear changes in the objective function coefficients is relinquished in this section. The analysis becomes significantly more challenging, and characterizing the conditions of { (JL, b, c)} for which the primal and dual elements converge remains an open question. However, this section does develop sufficient conditions on {(JL, b, c)} to guarantee the convergence of {x(JL, b, c)}. These conditions show that the cost coefficient vector need not converge. An example at the end of this section indicates further difficulties in the quest for establishing exactly when { x(JL, b, c)} converges. The sufficient conditions presented for { (JL, b, c)} to guarantee the convergence of { x(JL, b, c)} required that Yc is partitioned into equivalence classes. 134
PAGE 145
For any b E we say that c1 E Yc and c2 E Yc are "Asimilar", denoted The first goal of this section is to show that is an equivalence relation on Yc To show this, the property that central paths may not intersect unless they are equal is proven. The first lemma gives sufficient conditions for the primal central paths to be equivalent. Lemma 4.20 Let bE Yb, c1 E Yo and c2 E Yc Define C l 0 1 d 0 proJnull(A)c an 2 2 Co prOJnull(A)c Then, FCP(b,cl) and Furthermore, if c6 = o:c5, for some a E 1R++' Proof: Let b E Yb, c1 E Yc, and c2 E Yc Also, let 0 2 prOJrow(A)c 135
PAGE 146
so that c1 = c6 + ck and c2 = c6 + Let a E lli++ be such that c6 = o:c6. Since ck and are perpendicular to null(A), ckx = = 0, for all x E null(A). Consequently, theorem 2.10 shows that ckx and are constant on Pb This means that x(J.1,, b, c1 ) is the unique solution to n min{ c6xJ.1, L wi ln(xi) : x E Pb} i=l and x(J.1,, b, c2 ) is the unique solution to n min{ c6xJ.1, L wi ln(xi) : x E Pb}. i=l Hence, Multiplying the objective function of the first math program by a, shows that (4.8) which implies, The following corollary is stated for future reference. Corollary 4.21 Let b E c1 E Yc, and c2 E Yc If 1 2 prOJnull(A)c = o:prOJnull(A)c 136
PAGE 147
for some a E 1R++, then Proof: The result is immediate from the proof of lemma 4.20. The next theorem establishes the result that for any polyhedron, the central paths defined in this polyhedron are either the same or disjoint. Since the definition of PCPr is concerned only with elements corresponding to positive p, values, this does not say that two different central paths may not terminate at the same point. However, it does say that two different central paths may not cross enroute to either x*(r) or x(b). Theorem 4.22 Let b E c1 E Yc, and c2 E Yc If there exists p,1 and p,2 in 1R++ such that x(p,l, b, c1 ) = x(p,2 b, c2), then PCP(b,cl) = PCP(b,c2). Proof: Let b E Yb, c1 E Yc, and c2 E Yc Lemma 4.20 implies that there is no loss of generality by assuming that c1 and c2 are in null(A). Let p,1 and p,2 be in 1R++' such that x(p,l,b,c1 ) = x(p,2,b,c2). Then, cl p,leT x1 (p,l' b, cl) y(p,l' b, cl )A = 0, and 137
PAGE 148
Multiplying the first equation by :1 the second equation by :2 and subtracting yields ( 1 1 1 2) ( 1 1 1 1 2 2 ) /L1 c /L2 c = /L1 y(p, b, c ) /L2 y(p, b, c ) A. Since the lefthand side of the above equality is in the null(A) and the righthand side is in the row(A), both must be zero. Hence, and lemma 4.20 implies Two important corollaries follow. The first is used to show that is an equivalence relation, and the second is used to establish the equivalence classes associated with Corollary 4.23 Let b E c1 E Yc, and c2 E Yc Then, if c1 c2 in lR++ such that, x(p,I, b, c1 ) = x(p,2 b, c2), and the result follows immediately from theorem 4.22. 138
PAGE 149
Corollary 4.24 Let b E c1 E Yc, and c2 E Yc Then 1 2 proJnull(A)c = aproJnull(A)c for some a E 1R++, if, and only if Proof: The sufficiency is established in lemma 4.20. The necessity follows since and the proof of theorem 4.22 shows that 1 2 prOJnull(A)c = aprOJnull(A)c for some a E 1R++. The next result shows that is indeed an equivalence relation. Theorem 4.25 is an equivalence relation on Yc Furthermore, the equivalence class of c1 E Yc is, 139
PAGE 150
Proof: Let b E and c1 c2 c3 E Yc Clearly c1 c1 and c1 c2 implies c2 c1 So is reflexive and symmetric. Corollary 4.23 implies that if c1 c2 and c2 c3 which implies c1 c3 Hence is transitive and is an equivalence relation. Theorem 4.22 and corollary 4.24 imply that the equivalence classes are as stated. Notice that row(A) is equivalent to [0]. This equivalence class is problematic as demonstrated in example 4.30. To demonstrate that the cost vector need not converge for { x(JL, b, c)} to converge, two new types of convergence are defined. The first type of new convergence is called class convergence. To define this concept adequately, some notation is introduced. For a sequence { xk}, let C( { xk}) be the set of cluster points of { xk}. Furthermore, for any sequence { ck E 9c}, set Notice that :F contains all of the limiting directions of a sequence of cost vectors. The concept behind class convergence is that all of these limiting directions are contained in the same equivalence class. Definition 4.26 The sequence, { ck E 9c}, is class convergent to [c], 140
PAGE 151
The definition of class convergence does not imply that the sequence { ck} actually converges; however, if { ck} does converge then it is also class convergent. The second type of convergence is called proportional convergence. The idea is that the sequence { (JLk, ck)} is proportionately convergent if the sets C ( { 11t:11 : ck =/= 0}) and C ( { ck}) are, in some sense, proportional. Definition 4.27 The sequence, { (JLk, ck)} c IR++ x Yc, is proportionately convergent if, whenever two subsequences of {ck}, say {ck;} and { ckj }, have the properties that, ( ) 1 cki 1 1 .1m11k.11=c, ztoo c ( ) ckj 2 2 11 kll = c, and )tOO C J ( 3 ) 1 2 c IR proJnull(A)c = aproJnull(A)c 10r some a E ++' we also have The next lemma is a relaxation of theorem 2.14, and provides less stringent conditions for the boundedness of the sequence {x(JL, b, c)}. Lemma 4.28 Let W be a closed subset of g and { (JLk, rk)} c IR++ x W be a sequence with the following properties: (1) { 11t:11} is bounded, and 141
PAGE 152
(2) {bk} converges to b E (;h. Proof: Let M. Suppose, for the sake of attaining a contradiction, that { x(p,k, bk, ck)} is not bounded. Without loss in generality assume that Let { be a convergent subsequence of { }. Because the following inner product inequality holds: This implies is a subset of By assumption, any cluster point of { is an element of Yc Hence, theorem 2.14 implies the above union is bounded. Since 142
PAGE 153
we have a contradiction, and the result follows. Theorem 4.29 gives sufficient conditions for { (JLk, bk, ck)} to guaran tee the convergence of { x(JLk, bk, ck)} to an element of a central path. These conditions do not include that { ck} converges, but instead that { ck} is class convergent. As example 4.30 shows, this condition is still too restrictive for ne cessity. Characterizing the conditions of { (JLk, bk, ck)} for which { x(JLk, bk, ck)} converges remains an open question. Such a classification is needed before generalizing the set convergence results of the previous two sections. Theorem 4.29 Let r E Q, and assume { ck E 9c} is a sequence such that C({ck}) Yc\row(A). Then {x(JLk,bk,ck)}+ x E PCP(b,c) if, (1) {bk E Yb}+ bE Yb, (2) { ck E 9c} is class convergent to [c], (3) { (JLk, ck) : ck #0} is proportionately convergent, and (4) there exists ME 1R++ such that if :::::; { :::::; M. Proof: Because c tj_ row(A), the sequence {ck} contains zero at most a finite number of times. So, without loss in generality, zero is assumed not to be contained in { ck}. The result is established by showing that all cluster points of {x(JLk,bk,ck)} are equal. Since C({ck}) Yc\row(A) and {bk E Yb}+ bE Yb, there exists a closed set W c Q such that { (ck, bk)} c W. Because of the 143
PAGE 154
assumption that { is bounded, { x(p,k, bk, ck)} is bounded from lemma 4.28. Hence, there exist subsequences such that cl, and { + c2 Clearly, i;1 and i;2 are in Ptr The class convergence implies the existence of k o?projnull(A) II 2 A2 a proJnull(A)c cki a2projnull(A) llcki II' The proportional convergence assumption, together with the assumption that { is bounded away from zero, implies From corollary 4.21, ( ) x alllck; II' bk;' alprojnull(A) lick; II and 2 fL J k 2 c J ( k k ) x a llcki II' b ; 'a prOJnull(A) llcki II 144
PAGE 155
This and theorem 2.6 yield, xl .lim x(p,ki' bki' cki) ztoo x II' bk;' alprojnull(A) II) x(Jl, b, c) ( 2 p,ki k 2 cki ) x a llcki II' b J' a proJnull(A) llcki II x (p,ki, bki, cki) )tOO Hence, { x (p,k, bk, ck)} converges to an element in FCP(b,c.). Unlike theorems 4.5 and 4.14, the conditions required in theorem 4.29 are much too restrictive for necessity. The following example has the desirable property that { ck} converges; but, even with this property, the convergence of { x(p,, b, c)} requires the analysis of several nested linear programs. The example hints at what might be required to obtain the elusive necessary and sufficient conditions. Example 4.30 Let p,k f;, and consider the following linear programming 145
PAGE 156
data for the linear program min{ ex :Ax :::; b, x 0}, 1 1 1 0 0 k ck = 1 b= 1 and A= 0 1 0 v'k 1 1 0 0 1 v'k To analyze the behavior of { x(JLk, b, ck) }, a sequence of problems is considered. The idea is to iteratively reduce the original problem. This is done using the results for linear changes in the cost coefficients found in section 4.2, and at each step identifying an increasingly larger subset of variables that must be zero. The 'root' problem uses the limiting rim data. So, zero is the cost vector of the root problem since { ck} + 0 c[O], and the root problem is min{ Ox: Ax:::; b, x 0}. The optimal partition for the root problem is B[O] = {1, 2, 3} and N[O] = 0. To define the first 'subproblem', set llck[o]c[OJII = + 1 JLk[O] 1 Tk[1J v2k + 1, b[O]AN[o]XN[oJ(JLk[O], b[O], ck[O]), and ck[O] c[O] 1 ( ) Tk[1J = v2k+1 1 Jk Jk 146
PAGE 157
where the [0] indicates the original sequence data. With this notation, Notice that the sequence { ck [1]} no longer converges to zero, but rather 0 lim ck[1] = 1 k+oo y'2 1 V2 Furthermore, {bk[1]}+ b because N[O] = 0. However, lemma 2.15 would imply this even when N[O] #0. Defining the first subproblem is min{c[1]z[1] : An[oJz[1] b, z[1] 0}, or equivalently The optimal partition for this problem is B[1] = {1} and N[1] = {2, 3}. More importantly, analogous to 4.5, Xn[o](ti[O], b[O], c[O] + Tk[1]ck[1]) z[1] z[1] bk[1], ck[1J). 147
PAGE 158
Similar to the first subproblem, the second 'subproblem' relies on p,k[2] llck[1]c[1JII p,k[1] Tk[2] b[1]AN[l]XN[IJ(JLk[1], b[1], ck[1]), and ck[1]c[1] Tk[2] where { ck [2]} is defined only for the elements in B[1] (so only the first coordinate of the original cremains for this subproblem). This notation allows, It is easily checked that c[2] lim ck [2] 1. k+oo The most important observation hear is that {p,k[2]} does not converge to zero. The second subproblem is min{c[2]z[2] : An[1Jz[2] b, z[2] 0}, which is same as min{z[2] : 0 z[2] 1 }. 148
PAGE 159
Using the 'z' notation recursively, 4.5 shows XB[l](P,k[O], b[O], c[O]Tk[1]ck[1]) ZB[lJ[1] ( bk[1], ck[1]) ZB[lj[1] bk[1], ck[1J) ZB[1J[1] bk[1], c[1] + T[2]kck[2J) z[2] ( bk [2], ck [2]) z[2] [2], bk [2], ck [2]) Because each of these problems are variants of example 2.12, the convergence of each problem is easily examined. The central path for the original problem is defined by Hence, 0 This seems odd since the central path for the first root problem is P(b,o) = He}. The problem is that {p,k[O]} = H}+ o+. If the change in the cost coefficients 149
PAGE 160
had been linear, theorems 4.5 and 4.8 would have applied to deduce that the limit of {x(Jtk[O], b[O], ck[O])} is an element of a central path defined on the optimal face of the root problem. The limit point of { ck [1]} attempts to define this central path, even though the change is nonlinear. Although c[1] does not actually indicate this central path, lemma 2.15 implies that any components that are zero in the solution to the first subproblem, which uses c[1] as the cost vector, are also zero in any cluster point of { x(Jtk[O], b[O], ck[O]) }. The elements of the central path for the first subproblem are 1 2 I 1 4 72k+1 + 72k+lv 2k+1 + 2k+1 2 v'2k+1,__ 1 2 I k 4 72k+1 + 72k+lv 2k+1 + 2k+1 2[J; ,1 2 I k 4 72k+1 + 72k+l\L 2k+1 + 2k+1 2[J; l (1 + __2_ J1 + ) 2 v'k k 150
PAGE 161
Once again, this shows lim x(Ji, b, ck) = 0 k+oo 0 However, the problem of {p,k[1]}+ o+ reoccurs in the first subproblem. Notice that none of the variables become zero in the root problem, and that the second and third variables become zero in the first subproblem. This is good news, since these are all the variables that must become zero. Once these variables are identified, the parameter for the second subproblem may not converge to zero, i.e. {p,k[2]} f+ 0. Theorem 2.6 shows that lim z[2] (p,k [2], bk [2], ck [2]) k+oo z[2](1, b, c[2]) z[2](1, b, 1) 1+2VT+4 2 3V5 2 If the original problem were not so simple, the challenge of directly evaluating the limit point of {x(p,k[O], b, ck[O])} is substantial. However, calculating the limit point of { ck [0]} allows the formation of the root problem. This produces an optimal partition, which shows some of the variables that must go to zero. 151
PAGE 162
If {p,k [1]} does not converge to zero, theorem 2.6 is used to calculate the com ponents that are positive. If {p,k [1]} does converge to zero, the limit point of { ck[1]} is calculated, and the first subproblem is solved. The process repeats until either all variables are forced to zero, or {p,k[i]} does not converge to zero. 4.5 Chapter Summary The main result characterizes when converge. The generality of allowing simultaneous changes in the rim data, so long as the objective function perturbation is linear, is obtained from a mod eling scheme that shows how to model the changes in both rim data elements as only righthand side perturbations. The new model retains !'cnxn as a term in the objective function, and as a consequence the set convergence property for the omega central path shows that the central path converges to the union of the original central path and a central path on the optimal set defined by !'cnxn. The last section demonstrated the difficulty of extending these re sults when the restriction of linearity is removed from the objective change. Sufficient conditions are given to guarantee the convergence of { x(p,, b, c)}, and 152
PAGE 163
these conditions show that it is not necessary for the cost coefficients to converge. In support of these sufficient conditions, the collection of central paths was shown to induce an equivalence relation on Yc An interesting, unanswered question is whether U PCP(b,c) = Pg. cE9c Example 4.30 alludes to an algorithm that is capable of finding the limit of {x(Jl,, b, c)}, provided the limit exists. The algorithm is greedy in the sense that it creates an increasingly larger set of variables that are forced to zero. Finding conditions for which this algorithm converge seems equivalent to finding the necessary conditions for the convergence of { x(Jl,, b, c)}. 153
PAGE 164
5. Conclusion and A venues for Future Research The immediate question from chapter 3 is whether or not the unique dual assumption is removable from theorem 3.15. This assumption essentially provides a rank argument, and this assumption may be found unnecessary upon a closer examination of XAB. Many questions remain open from chapter 4; the most intriguing be ing the characterization of when x(f.t, b, c) converges. These conditions appear equivalent to establishing when the algorithm hinted at in example 4.30 con verges. Another question from this chapter is, "Does the collection of central paths cover the relative interior of the polyhedron?" If this is true, every in terior element of a polyhedron is associated with an equivalence class of cost vectors. Several results from this work are finding themselves useful elsewhere. The parametric analysis has been experimentally used to find radiation plans in the field of radiation oncology. A question that has arisen from this work is whether or not the parametric analysis presented here may be used to find minimal support sets. More recently, R. Caron, H. Greenberg, and A. Holder 154
PAGE 165
are working on the development of a theory of repelling constraints. Several of the techniques and insights gained from this work have proven themselves worthy in this en devour. 155
PAGE 166
NOTATION INDEX (BIN) is the optimal partition for IPr B = { i : xi ( r) > 0} bp = b + p& C( { xk}) is the set of cluster points of { xk} col(A) = {z: Ax= z for some x} CPr = {(x(p,,b,c),y(p,,b,c),s(p,,b,c)): p, > 0} IXJPr = {(y(p,,b,c),s(p,,b,c)): p, > 0} { IXJPU{(y*(r), s*(r))} IXJPr = IXJPU{(y*(r), s*(r)), (y(r), s(r))} if V c is unbounded if V c is bounded = {(p(7J, r, &), (0, q(7J, r, &))) : 17 > 0} IXJP(r,&) = U{(y*(r), s*(r)), (p*(r, &), (0, q*(r, &)))} DxJ(xo) = where 11&11 = 1 is k applications of the derivative operator on f with respect 156
PAGE 167
Dk f(x0 ) = lim f(xo+O&;)f(xo) where & is the ith unit vector x;+ 0tO+ 0 'De= {(y, s) : yA + s = c, s 0} = {(y, s) : yA + s = c, s > 0} v; = { (y, s) E 'De : yb is optimal toW} fh is a direction of change for b in IPr &:: is a direction of change for c in IPr &is a direction of change for b and c in IPr e = (1, 1, 1, ... 1f F ({ ck}) C ({ ck}) U C ( { : ck =J 0}) Q = {r : Pg =J 0, =J 0} Yb = {b: Pg =J 0} 1l = { &E 1l : the optimal partition is invariant on [r, r + ()Jr] for some sufficiently small positive (}} 1lb = {fh: (&, 0) E 1} 1le = { &; : ( 0, &:: ) E 1} leftnull(A) = {y: yA = 0} (r,M) = {(x,y,s) E Pb X 'De: sx:::; M} IPr min{cx: Ax= b,x 0} Wr max{yb: yA + s = c, s 0} 157
PAGE 168
null(A) = {x: Ax= 0} N = { i : xi ( r) = 0} 0 = diag(w) where wE lRn opt(b) is the optimal objective function value of IP, relative to the righthand side b (p(ry,r,&),q(ry,r,fh)) is the unique solution to (p(r), q(r)) = lim (p(ry, r, &), q(ry, r, &)) 'f}+00 (p*(r, &), q*(r, &)) = lim(p(ry, r, fh), q(ry, r, &)) ry+0 Pb = { x : Ax= b, x 0} Pg = {x: Ax= b, x > 0} P; = {x E Pb: ex is optimal to IP} (P;)0 = {X E P; : XB > 0} PCPr = {x(jt,b,c): Jl > 0} { PCPr U{x*(r)} PCPr = PCPrU{x*(r),x(b)} if Pb is bounded if Pb is unbounded = { (zB(T/, b, 0) : T/ > 0} PCP(r,fc) = PCP(r,fc) U{x*(r), (z*(b, 0)} row(A) = {z: z = yA for some y} 158
PAGE 169
= {(xi,x2,x3,,xn): Xi E lR,xi > O,i = 1,2,3, ... ,n} r = (b, c) S = diag(s) where s E lRn a(x) = {i: Xi> 0} where x E X= diag(x) where x E lRn x(p,, b, c) is the unique solution to x(b) = lim x(p,, b, c), if Pb is bounded tt+OO x* ( r) is the analytic center of P; (y(p,, b, c), s(p,, b, c)) is the unique solution to max{yb + p, 2:7 wdn(si) : yA + s = c, s 2: 0} (y(c), s(c)) = lim (y(p,, b, c), s(p,, b, c)), if 'De is bounded tt+OO (y*(r),s*(r)) = lim(y(p,,b,c),s(p,,b,c)) tt+0 zn(TJ, b, &;) is the unique solution to zn(b) = lim z(TJ, b, &;) f/+00 z'B(b, &;) = lim z(TJ, b, &;) f/+0+ 159
PAGE 170
REFERENCES [1] I. Adler and R. Monteiro. Limiting behavior of the affine scaling contin uous trajectories for linear programming problems. Mathematical Pro gramming, 50:2951, 1991. [2] I. Adler and R. Monteiro. A geometric view of parametric linear pro gramming. Algorithmica, 8:161176, 1992. [3] D. Atkinson and P. Vaidya. A scaling technique for finding the weighted analytic center of a polytope. Mathematical Programming, 57:163192, 1992. [4] D. Bayer and J. Lagarias. The nonlinear geometry of linear programming I. Transactions of the American Mathematical Society, 314(2):499526, 1989. [5] D. Bayer and J. Lagarias. The nonlinear geometry of linear programming II. Transactions of the American Mathematical Society, 314(2):527581, 1989. [6] C. Berge. Topological Spaces. The McMillan Company, New York, NY, 1963. [7] J. Bonnans and F. Porta. Infeasible path following algorithms for lin ear complementarity problems. Raport de recherche 2445, Institur Na tional De Recherche en Informatique Et En Automatique, Rocquencourt, France, 1994. [8] S. Campbell and Jr. C. Meyer. Generalized Inverses of Linear Transfor mations. Fearon Pitman Publishers Inc., Belmont, CA, 1979. [9] G. Dantzig, J. Folkman, and N. Shapiro. On the continuity of the minumum set of a continuous function. Journal of Mathematical Analysis and Applications, 17:519548, 1967. 160
PAGE 171
[10] I. Dikin. Iterative solution of problems of linear and quadratic program ming. Doklady Akademii Nauk SSSR, 174:747748, 1967. [11] I. Dikin. On the convergence of an iterative process. Upravlyaemye Sistemi, 12:5460, 1974. [12] A. Fiacco. Introduction to Sensitivity and Stabilty Analysis in Nonlinear Programming. Academic Press, New York, NY, 1983. [13] A. Fiacco and G. McCormick. Nonlinear Programming: Sequential Unconstrained Minimization Techniques. John Wiley & Sons, New York, 1968. [14] A. Forsgren. On linear leastsquares problems with diagonally dominant weight matrices. Technical Report TRITAMAT19950S2, Royal Institute of Technology, Stockholm, Sweden, 1995. [15] R. Freund. Projective transformation for interiorpoint algorithms, and superlinearly convergent algorithm for thewcenter problem. Mathemat ical Programming, 58:385414, 1993. [16] R. Freund. Following a balanced trajectory from an infeasible point to an optimal linear programming solution with a polynomialtime algorithm. Mathematics of Operations Research, 21(4):839859, 1996. [17] R. Freund, F. Jarre, and S. Mizuno. Convergence of a class of inex act interiorpoint algorithms for linear programs. Numerical Analysis Manuscript 97311, Bell Laboratories, Murry Hill, New Jersey, 1997. [18] R. Freund and M. Nunez. Condition measures and properties of the central trajectory of a linear program. Working Paper, 1996. [19] T. Gal. Postoptimal analysis, parametric programming, and related top ics: degeneracy, multicrtiteria decision making, redundancy. Walter de Gruyter & Co., New York, NY, 2nd edition, 1995. [20] S. Gass and T. Saaty. Parametric objective function (part 2) general ization. Operations Research, 3(4):395401, 1955. [21] J.1. Goffin and J.Ph. Vial. On the computation of weighted analytic centers and dual ellipsoids with the projective algorithm. Mathematical Programming, 60:8192, 1993. 161
PAGE 172
[22] A. Goldman and A. Tucker. Theory of linear programming. In H. Kuhn and A. Tucker, editors, Linear Inequalities and Related Systems, vol ume 38, pages 5397. Princeton University Press, Princeton, New Jersey, 1956. [23] C. Gonzaga. Pathfollowing methods for linear programming. SIAM Review, 34(2):167224, 1992. [24] I. S. Gradshteyn and I. M. Ryzhik. Table of Integrals, Series, and Prod ucts. Academic Press, New York, NY, 1979. [25] H. Greenberg. A ComputerAssisted Analysis System for Mathemati cal Programming Models and Solutions: A User's Guide for ANALYZE. Kluwer Academic Publishers, Boston, MA, 1993. [26] H. Greenberg. Quantitative sensitivity analysis. Class notes used m Advanced Linear Programming, 1994. [27] H. Greenberg. The use of the optimal partition in a linear program ming solution for postoptimal analysis. Operations Research Letters, 15(4):179185, 1994. [28] H. Greenberg. Rim sensitivity analysis from an interior solution. Tech nical Report CCM No. 86, University of Colorado, at Denver, 1996. [29] H. Greenberg. An analysis of degeneracy. Naval Logistics Research Quar terly, 33:635655, 861. [30] H. Greenberg. Mathematical Programming Glossary. World Wide Web, http:/ /wwwmath.cudenver.edu;hgreenbe/ glossary /glossary.html, 19961998. [31] H. Greenberg, A. Holder, C. Roos, and T. Terlaky. On the dimension of the set of rim perturbations for optimal partition invariance. Technical Report CCM No. 94, University of Colorado, at Denver, 1996. To appear in SIAM Journal of Optimization. [32] B. Grunbaum. Convex Polytopes. Wileylnterscience, New York, NY, 1967. 162
PAGE 173
[33] D. Den Hertog and C. Roos. A survey of search directions in inte rior point methods for linear programming. Mathematical Programming, 52(2):481510, 1991. [34] W. Hogan. Pointtoset maps in mathematical programming. SIAM Review, 15(3):591603, 1973. [35] A. Holder, J. Sturm, and S. Zhang. The analytic central path, sensitivity analysis, and parametric programming. Technical Report CCM No. 118, University of Colorado at Denver, 1997. [36] P. Huard. Resolution of mathematical programming with nonlinear con straints by the method of centres. In J. Abadie, editor, Nonlinear Pro gramming, chapter 8, pages 209219. John Wiley & Sons, Inc., New York, NY, 1967. [37] B. Jansen. Interior Point Techniques in Optimization. PhD thesis, Delft University of Technology, Delft, Netherlands, 1995. [38] B. Jansen, J.J. de Jong, C. Roos, and T. Terlaky. Sensitivity analysis in linear programming: Just be careful! Technical Report AMER.93.022, Royal/Shell Laboratories Amsterdam, Amsterdam, Netherlands, 1993. [39] B. Jansen, C. Roos, and T. Terlaky. An interior point approach to post optimal and parametric analysis in linear programming. Technical Report 9221, Delft University of Technology, Faculty of Technical Mathe matics and Computer Science, Delft, Netherlands, 1992 1992. [40] B. Jansen, C. Roos, T. Terlaky, and J.Ph. Vial. Interiorpoint method ology for linear programming: duality, sensitivity analysis and computa tional aspects. Technical Report 9328, Delft University of Technology, Faculty of Technical Mathematics and Computer Science, Delft, Nether lands, 1993. [41] N. Karmarkar. A new polynomialtime algorithm for linear program ming. Combinatorica, 4:373395, 1984. [42] L. Khachiyan. A polynomial algorithm in linear programming. Doklady Akademiia Nauk SSSR, 244:10931096, 1979. [43] M. Kojima. Basic lemmas in polynomialtime infeasibleinteriorpoint 163
PAGE 174
methods for linear programs. Annals of Operations Research, 62:128, 1996. [44] M. Kojima, N. Megiddo, and S. Mizuno. A general framework of contin uation methods for complementarity problems. Mathematics of Opera tions Research, 18:945963, 1993. [45] M. Kojima, S. Mizuno, and A. Yoshi. A primal dual interior point method for linear programming. InN. Megiddo, editor, Progress in Math ematical Programming: InteriorPoint Algorithms and Related Methods. SpringerVerlag, New York, 1989. [46] A. Kozlov. The Karmarkar algorithm: Is it for real? SIAM News, 18(6):1,4, 1985. [47] E. Kranich. Interior Point Method Bibliography. World Wide Web, http:/ /netlib.org/bib/intbib.bib, 1993. [48] P. Lancaster and M. Tismenetsky. The Theory of Matrices. Academic Press, Inc., New York, NY, 1985. [49] I. Lustig, R. Marsten, and D. Shanno. Computational experience with a primaldual interior point method for linear programming. Techni cal report, Department of Civil Engineering and Operations Research, Princton University, Princeton, NJ, 1989. [50] I. Lustig, R. Marsten, and D. Shanno. Interior point methods for lin ear programming: Computational state of the art. ORSA Journal on Computing, 6:114, 1994. [51] R. Marsten, M. Saltzman, D. Shanno, G. Pierce, and J. Ballintijn. Im plementation of a dual affine interior point algorithm for linear program ming. ORSA Journal on Computing, 1(4):287297, 1989. [52] R. Marsten, R. Subramanian, I. Lustig, and D. Shanno. Interior point methods for linear programming: Just call Newton, Lagrange, and Fiacco and McCormick. Interfaces, 20(4):105116, 1990. [53] L. McLinden. An analogue of Moreau's proximation theorem, with ap plications to the nonlinear complementary problem. Pacific Journal of Mathematics, 88(1):101161, 1980. 164
PAGE 175
[54] L. McLinden. The complementarity problem for maximal monotone mul tifunctions. In R. Cottle, R. Giannessi, and J. Lions, editors, Variational Inequalities and Complementarity Probelems, pages 251270. John Wiley & Sons, 1980. [55] N. Megiddo. Pathways to the optimal set in linear programming. In N. Megiddo, editor, Progress in Mathematical Programming: Interior Point Algorithms and Related Methods, pages 131158. SpringerVerlag, New York, 1989. [56] H. Mills. Marginal values of matrix games and linear programs. In H. Kuhn and A. Tucker, editors, Linear Inequalities and Related Systems. Princeton University Press, Princeton, NJ, 1956. [57] S. Mizuno. A new polynomial time method for a linear complementarity problem. Mathematical Programming, 56:3143, 1992. [58] S. Mizuno and F. Jarre. Global and polynomialtime convergence of an infeasibleinteriorpoint algorithm using inexact computation. Research memorandum 605, The Institute of Statistical Mathematics, Tokyo, Japan, 1996. [59] S. Mizuno, M. Todd, andY. Ye. A surface of analytic centers and primal dual infeasibleinterior point algorithms for linear programming. Mathe matics of Operations Research, 20(1):135162, 1995. [60] R. Monteiro and I. Adler. Interior pathfollowing primadual algorithms, part I: Linear programming. Mathematical Programming, 44:2741, 1989. [61] R. Monteiro and S. Mehrotra. A general parametric analysis approach and its implication to sensitivity analysis in interior point methods. Mathematical Programming, 72:6582, 1996. [62] J. Munkres. Analysis on Manifolds. AddisonWesley Publishing Com pany, Redwood City, CA, 1991. [63] 0. Giiler. Limiting behavior of weighted central paths in linear program ming. Mathematical Programming, 65:347363, 1994. [64] 0. Giiler and C. Roos and T. Terlaky and J.Ph. Vial. A survey of the implications of the behavior of the central path for duality theory of linear programming. Management Science, 41(12):19221934, 1995. 165
PAGE 176
[65] F. Porta. A quadratically convergent predictorcorrector method for solv ing linear programs from infeasible starting points. Mathematical Pro gramming, 67:383406, 1994. [66] R. Tiitiincii. An infeasibleinteriorpoint potentialreduction algorithm for linear programming. Technical Report 1136, School of Operations Re search and Industrial Enginering, Cornell University, Ithaca, NY, 1996. [67] J. Renegar. A polynomialtime algorithm, based on Newton's method, for linear programming. Mathematical Programming, 40:5993, 1988. [68] J. Renegar. Some perturbation theory for linear programming. Mathe matical Programming, 65:7391, 1994. [69] J. Renegar. Incorporating condition measures into the complexity theory of linear programming. SIAM Journal of Optimization, 5(3):506524, 1995. [70] J. Renegar. Linear programming, complexity theory, and elementary elementary functional analysis. Mathematical Programming, 70 ( 3): 279351, 1995. [71] C. Roos. Interior point approach to linear programming: Theory, al gorithms & parametric analysis. In A. van der Burgh and J. Simonis, editors, Topics in Engineering Mathematics, pages 181216. Kluwer Aca demic Publishers, Netherlands, 1992. [72] C. Roos and D. Hertog. A polynomial method of approximate weighted centers for linear programming. Technical Report 8913, Delft University of Technology, Delft, Netherlands, 1989. [73] C. Roos, T. Terlaky, and J.Ph. Vial. Theory and Algorithms for Linear Optimization: An Interior Point Approach. John Wiley & Sons, New York, NY, 1997. [74] C. Roos and J.Ph. Vial. Interiorpoint methods for linear programming. Technical Report 9477, Delft University of Technology, Delft, Nether lands, 1994. [75] W. Rudin. Real and Complex Analysis. McGrawHill Book Company, New York, NY, 1987. 166
PAGE 177
[76] T. Saaty. Coefficient perturbation of a constrained extremum. Opera tions Research, 7:294302, 1959. [77] T. Saaty and S. Gass. Parametric objective function (part 1). Operations Research, 2(3):316319, 1954. [78] A. Seifi and L. Tuncel. A constantpotential infeasiblestart interiorpoint algorithm with computational experiments and applications. In Compu tational Optimization and Applications, pages 150. Kluwer Academic Publishers, Boston, MA, 1996. [79] E. Simantiraki and D. Shanno. An infeasibleinteriorpoint method for linear complementarity problems. RUTCOR Research Report RRR 795, Rutgers Center for Operational Research, New Brunswick, NJ, 1996. [80] G. Sonnevend. An "analytic centre" for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming. In A. Prekopa, J. Szelezsan, and B. Strazicky, editors, Lecture Notes in Control and Information Sciences, volume 84, pages 866875. Springer Verlag, Heidelberg, Germany, 1986. [81] G. Sonnevend. An implementation of the method of analytic centers. In A. Bensoussan and J. Lions, editors, Lecture Notes in Control and Information Sciences, volume 111, pages 297308. SpringerVerlag, Hei delberg, Germany, 1988. [82] G. Sonnevend. New algorithms in convex programming based on a no tion of "Centre" (for systems of analytic inequalities) and on rational extrapolation. In K. Hoffman and et al, editors, International Series of Numerical Mathematics, volume 84, pages 311326. Birkhauser Verlag Basel, Germany, 1988. [83] G. Sonnevend. Applications of the notion of analytic center in approx imation (estimation) problems. Journal of Computational and Applied Mathematics, 28:349358, 1989. [84] G. Sonnevend and J. Stoer. Global ellipsoidal approximations and homo topy methods for solving convex analytic programs. Applied Mathematics and Optimization, 21:139165, 1990. [85] G. Sonnevend, J. Stoer, and G. Zhao. On the complexity offollowing the 167
PAGE 178
central path of linear programs by linear extrapolation II. Mathematical Programming, 52:527553, 1991. [86] B. Stewart. On scaled projections and pseudoinverses. Linear Algebra and its Applications, 112:189193, 1989. [87] M. Todd. A DantzigWolfelike variant of Karmarkar's interiorpoint linear programming algorithm. Operations Research, 38:10061018, 1990. [88] P. Tseng. Analysis of an infeasible interior pathfollowing method for complementarity problems. Technical report, Department of Mathematics, University of Washington, Seattle, WA, 1997. [89] S. Vavasis andY. Ye. A primaldual interior point method whose running time depends only on the constraint matrix. Mathematical Programming, 74:79120, 1996. [90] C. Witzgall, P. Boggs, and P. Domich. On the convergence behav ior of trajectories for linear programming. Contemporary Mathematics, 114:161187, 1990. [91] M. Wright. The interiorpoint revolution in constrained optimization. Technical Report 98409, Bell Laboratories, Murray Hill, New Jersey, 1998. [92] S. Wright. An infeasibleinteriorpoint algorithm for linear complementarity problems. Mathematical Programming, 67:2952, 1994. [93] S. Wright. A pathfollowing interiorpoint algorithm for linear and quadratic problems. Annals of Operations Research, 62:103130, 1996. [94] S. Wright. Interior Point Methods Online. World Wide Web, http:/ /www.mcs.anl.gov /home/otc/InteriorPoint/index.html, 1997. [95] S. Wright. PrimalDual InteriorPoint Methods. SIAM, Philadelphia, PA, 1997. [96] S. Wright and D. Ralph. A superlinear infeasibleinteriorpoint algorithm for monotone complementarity problems. Mathematics of Operations Research, 21( 4):815838, 1996. [97] S. Wright and Y. Zhang. A superquadratic infeasibleinteriorpoint 168
PAGE 179
method for linear complementarity problems. Research Report YZ9403, Department of Mathematics and Statistics, University of Maryland, Baltimore County, MD, 1994. [98] Y. Zhang. On the convergence of a class of infeasibleinteriorpoint meth ods for the horizontal linear complementarity problem. SIAM Journal of Optimization, 4:208227, 1994. [99] Y. Zhang. User's guide to LIPSOL. Technical report, University of Maryland Baltimore County, Department of Mathematics and Statistics, Baltimore, Maryland 212285398, 1995. [100] G. Zhao. On the relationship between the curvature integral and the com plexity of pathfollowing methods in linear programming. SIAM Journal of Optimization, 6(1):5773, 1986. [101] G. Zhao and J. Zhu. Analytic properties of the central trajectory in inte rior point methods. In D. Du and J. Sun, editors, Advances in Optimiza tion and Approximation, pages 362375. Kluwer Academic Publishers, The Netherlands, 1994. 169
