×

zbMATH — the first resource for mathematics

Limiting behavior of weighted central paths in linear programming. (English) Zbl 0841.90089
Given the linear programming problem (P): \(\min c^T x\), s.t. \(Ax= b\), \(x\geq 0\), and its dual (D): \(\max b^T y\), s.t. \(A^T y+ s= c\), \(s\geq 0\), with \(A\in \mathbb{R}^{m\times n}\), \(b\in \mathbb{R}^m\) and \(c\in \mathbb{R}^n\), the paper discusses the solutions \((x(\mu), s(\mu))\) of the weighted penalized problems (P\('\)): \(\min c^T x- \mu \sum^n_{i= 1} \omega_i \ln(x_i)\) and (D\('\)): \(\min b^T y+ \mu \sum^n_{i= 1} \omega_i \ln(s_i)\), s.t. to the same restrictions, for \(\mu\in (0, \infty)\) and \(\omega> 0\). In particular, the limiting behaviour of the derivatives \((x^{(k)}(\mu), s^{(k)}(\mu))\), \(\mu> 0\), of the \(\omega\)-central path \((x(\mu), s(\mu))_{\mu> 0}\) is studied when \(\mu\) approaches zero and infinity. It is shown that the derivatives converge if \(\mu\) approaches zero and that the higher order derivatives vanish at infinity. The author concludes that these observations should be helpful in the construction of new locally fast interior-point algorithms.

MSC:
90C05 Linear programming
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] I. Adler and R.D.C. Monteiro, ”Limiting behavior of the affine scaling continuous trajectories for linear programming problems,”Mathematical Programming 50 (1991) 29–51. · Zbl 0719.90044 · doi:10.1007/BF01594923
[2] K.M. Anstreicher, ”Linear programming and the Newton barrier flow,”Mathematical Programming 41 (1988) 363–373. · Zbl 0657.90059 · doi:10.1007/BF01580774
[3] D.A. Bayer and J.C. Lagarias, ”The nonlinear geometry of linear programming, I. affine and projective scaling trajectories, II. Legendre transform coordinates and central trajectories,”Transactions of the American Mathematical Society 314 (1989) 499–581. · Zbl 0671.90046
[4] A. Ben-Israel and T.N.E. Greville,Generalized Inverses: Theory and Applications (John Wiley and Sons, New York, 1974). · Zbl 0305.15001
[5] A.V. Fiacco and G.P. McCormick,Nonlinear Programming: Sequential Unconstrained Minimization Techniques (John Wiley and Sons, New York, 1968). Republished by SIAM (Philadelphia) 1990. · Zbl 0193.18805
[6] A.J. Goldman and A.W. Tucker, ”Theory of linear programming,” in: H.W. Kuhn and A.W. Tucker, eds.,Linear Inequalities and Related Systems, Annals of Mathematical Studies 38 (Princeton University Press, Princeton, New Jersey, 1956) pp 53–97. · Zbl 0072.37601
[7] I.S. Gradshteyn and I.M. Ryzhik,Table of Integrals, Series, and Products, corrected and enlargened edition (Academic Press, New York, 1980). · Zbl 0521.33001
[8] O. Güler, ”Existence of interior points and interior paths in nonlinear monotone complementarity problems,”Mathematics of Operations Research 18 (1993) 128–147. · Zbl 0816.90125 · doi:10.1287/moor.18.1.128
[9] O. Güler, C. Roos, T. Terlaky and J.-Ph. Vial, ”Interior point approach to the theory of linear programming,” Technical Report 1992.3, Faculté des SES, Université de Genève (Genève, Switzerland, 1992). · Zbl 0852.90106
[10] N. Karmarkar, ”A new polynomial-time algorithm for linear programming,”Combinatorica 4 (1984) 373–395. · Zbl 0557.90065 · doi:10.1007/BF02579150
[11] M. Kojima, S. Mizuno and A. Yoshise, ”A polynomial-time algorithm for a class of linear complementarity problems,”Mathematical Programming 44 (1989) 1–26. · Zbl 0676.90087 · doi:10.1007/BF01587074
[12] M. Kojima, S. Mizuno and A. Yoshise, ”An O \((\sqrt {nL} )\) iteration potential reduction algorithm for linear complementarity problem,”Mathematical Programming 50 (1991) 331–342. · Zbl 0738.90077 · doi:10.1007/BF01594942
[13] L. McLinden, ”An analogue of Moreau’s proximation theorem, with applications to the nonlinear complementarity problem,”Pacific Journal of Mathematics 88 (1980) 101–161. · Zbl 0403.90081
[14] L. McLinden, ”The complementarity problem for maximal monotone multifunctions,” in: R.W. Cottle, F. Giannessi and J.L. Lions, eds.,Variational Inequalities and Complementarity Problems (John Wiley and Sons, New York, 1980) pp 251–270. · Zbl 0499.90073
[15] L. McLinden, ”Polyhedral extensions of some theorems of linear programming,”Mathematical Programming 22 (1982) 162–176. · Zbl 0495.90056 · doi:10.1007/BF01585102
[16] N. Megiddo, ”Pathways to the optimal set in linear programming,” in: N. Megiddo, ed.,Progress in Mathematical Programming – Interior Point and Related Methods (Springer Verlag, New York, 1989) pp. 131–158. · Zbl 0687.90056
[17] N. Megiddo and M. Shub, ”Boundary behavior of interior point algorithms in linear programming,”Mathematics of Operations Research 14 (1989) 97–146. · Zbl 0675.90050 · doi:10.1287/moor.14.1.97
[18] S. Mehrotra, ”Quadratic convergence in a primal-dual method,”Mathematics of Operations Research 18 (1993) 741–751. · Zbl 0794.90034 · doi:10.1287/moor.18.3.741
[19] S. Mehrotra, ”Asymptotic convergence in the generalized predictor–corrector method,” Technical Report, Department of IE and MS, Northwestern University (Evanston, Illinois, 1992). · Zbl 0868.90078
[20] S. Mizuno, M.J. Todd and Y. Ye, ”On adaptive-step primal-dual interior-point algorithms for linear programming,”Mathematics of Operations Research 18 (1993) 964–981. · Zbl 0810.90091 · doi:10.1287/moor.18.4.964
[21] R.D.C. Monteiro and I. Adler, ”Interior path following primal-dual algorithms. Part I: Linear programming,”Mathematical Programming 44 (1989) 27–42. · Zbl 0676.90038 · doi:10.1007/BF01587075
[22] Gy. Sonnevend, ”An ’analytic centre’ for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming,” in:Lecture Notes in Control and Information Sciences (Springer Verlag, New York, 1985) pp. 866–876.
[23] A.C. Williams, ”Complementarity theorems in linear programming,”SIAM Review 12 (1970) 135–137. · Zbl 0193.18606 · doi:10.1137/1012015
[24] C. Witzgall, P.T. Boggs and P.D. Domich, ”On the convergence behavior of trajectories for linear programming,”Contemporary Mathematics 114 (1990) 161–187. · Zbl 0725.90060
[25] Y. Ye, ”AnO(n 3 L) potential reduction algorithm for linear programming,”Mathematical Programming 50 (1991) 239–258. · Zbl 0734.90057 · doi:10.1007/BF01594937
[26] Y. Ye, O. Güler, R.A. Tapia and Y. Zhang, ”A quadratically convergent O \((\sqrt {nL} )\) -iteration algorithm for linear programming,”Mathematical Programming 59 (1993) 151–162. · Zbl 0778.90037 · doi:10.1007/BF01581242
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.