Abstract
A class of algorithms is proposed for solving linear programming problems (withm inequality constraints) by following the central path using linear extrapolation with a special adaptive choice of steplengths. The latter is based on explicit results concerning the convergence behaviour of Newton's method to compute points on the central pathx(r), r>0, and this allows to estimate the complexity, i.e. the total numberN = N(R, δ) of steps needed to go from an initial pointx(R) to a final pointx(δ), R>δ>0, by an integral of the local “weighted curvature” of the (primal—dual) path. Here, the central curve is parametrized with the logarithmic penalty parameterr↓0. It is shown that for large classes of problems the complexity integral, i.e. the number of stepsN, is not greater than constm α log(R/δ), whereα < 1/2 e.g.α = 1/4 orα = 3/8 (note thatα = 1/2 gives the complexity of zero order methods). We also provide a lower bound for the complexity showing that for some problems the above estimation can hold only forα ⩾ 1/3.
As a byproduct, many analytical and structural properties of the primal—dual central path are obtained: there are, for instance, close relations between the weighted curvature and the logarithmic derivatives of the slack variables; the dependence of these quantities on the parameterr is described. Also, related results hold for a family of weighted trajectories, into which the central path can be embedded.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
I. Adler, N. Karmarkar, M.G.C. Resende and G. Veiga, “An implementation of Karmarkar's algorithm for linear programming,”Mathematical Programming 44 (1989) 297–335.
W. Blaschke and K. Reidmeister,Affine Differentialgeometrie (Springer, Berlin, 1924).
P.T. Boggs, P.D. Domich, J.R. Donaldson and C. Witzgall, “Algorithmic enhancements to the method of centers for linear programming,”ORSA Journal on Computing 1 (1989) 159–171.
P.T. Boggs, P.D. Domich, J.R. Donaldson and C. Witzgall, “Optimal 3-dimensional methods for linear programming,” Tehcnical Report NISTIR 89-4225, National Institute of Standards and Technology (Gaithersburg, MD, 1989).
J.L. Goffin, A. Haurie and J.P. Vial, “Decomposition and nondifferentiable optimization with the projective algorithm,” Preprint G-89-25, Faculty of Manamgement, McGill University (Montreal, Que., 1989).
Cl. Gonzaga, “An algorithm for solving linear programming problems in O(n 3 L) operations,” in: N. Meggido, ed.,Progress in Mathematical Programming, Interior Point and Related Methods (Springer, New York, 1988) pp. 1–28.
M. Iri, “Integrability of vector and multivector fields associated with interior point methods for linear programming,”Mathematical Programming (Series B) 52 (1991) 511–525, this issue.
Fl. Jarre, “On the method of analytic centers for solving smooth, convex programs,” in: S. Dolecki, ed.,Optimization, Proceedings of the Fifth French—German Conference. Lecture Notes in Mathematics No. 1405 (Springer, Berlin, 1989) pp. 69–85.
Fl. Jarre, G. Sonnevend and J. Stoer, “An implementation of the method of analytic centers,” in: A. Bensoussan and J.L. Lions, eds.,Analysis and Optimization of Systems. Lecture Notes in Control and Information Sciences No. 111 (Springer, Berlin, 1988) pp. 297–307.
N. Karmarkar, “Riemannian geometry underlying interior point methods,” Lecture and Preprint presented at the13th International Symposium on Mathematical Programming, Tokyo (Tokyo, 1988).
M. Kojima, Sh. Mizuno and A. Yoshise, “An\(O(\sqrt n L)\) iteration potential reduction algorithm for linear complementarity problems,”Mathematical Programming 50 (1991) 331–342.
I.J. Lustig, R.E. Marsten and D.E. Shanno, “Computational experience with a primal-dual interior point method for linear programming,” Technical Report SOR 89-17, School of Engineering and Applied Science, Princeton University (Princeton, NJ, 1989).
A. Marxen, “Primal barrier methods for linear programming,” Ph.D. Thesis, Department of Operations Research, Stanford University (Stanford, CA, 1989).
J. Mennicken, “Implementation of a first order central path following algorithm for solving large linear programs,” Report No. 202, Institut für Angewandte Mathematik und Statistisk, Universität Würzburg (Würzburg, 1990).
S. Mizuno, M.J. Todd and Y. Ye, “Anticipated behaviour of path-following algorithms for linear programming,” Technical Report No. 878-1989, School of Operations Research and Industrial Engineering, Cornell University (Ithaca, NY, 1989).
Ju. Nesterov and A. Nemirovskii,Self-Concordant Functions and Polynomial-Time Algorithms for Convex Programming (Central Economical and Mathematical Institute USSR Academy of Science, Moscow, 1989).
C. Roos and J.-Ph. Vial, “A polynomial method of approximate weighted centers for linear programming,” to appear in:Mathematical Programming (1992).
G. Sonnevend, “Application of analytic centers to feedback design for systems with uncertainties,” in: D. Hinrichsen and B. Martensson, eds.,Control of Uncertain Systems (Birkhäuser, Basel, 1989) pp. 271–289.
G. Sonnevend, “Sequential algorithms of optimal order global error for the uniform recovery of functions with monotonerth derivatives,”Analysis Mathematica 10 (1984) 311–335.
G. Sonnevend and J. Stoer, “Global ellipsoidal approximations and homotopy methods,”Applied Mathematics and Optimization 21 (1989) 139–166.
G. Sonnevend, J. Stoer and G. Zhao, “On the complexity of following the central path of linear programs by linear extrapolation,”Methods of Operations Research 62 (1990) 19–31.
M. Todd, “Recent developments and new directions in linear programming,” in: M. Iri and K. Tanabe, eds.,Mathematical Programming — Recent Developments and Applications (Kluwer Academic Publishers, Dordrecht—Boston—London, 1989) pp. 109–157.
C. Witzgall, P.T. Boggs and P.D. Domich, “On the convergence behavior of trajectories for linear programming,” to appear in:Proceedings of the AMS-IME-SIAM Research Conference on “Mathematical Developments Arising from Linear Programming Algorithms,” June 26–30, 1988, Bowdoin College (Brunswick, ME).
Y. Ye, “A class of potential functions for linear programming,” Preprint, Department of Management Science, The University of Iowa (Iowa City, IA, 1988/1989).
G. Zhao and J. Stoer, “Estimating the complexity of path following methods for solving linear programs by curvature integrals,” Technical Report No. 225, Institut für Angewandte Mathematik und Statistik, Universität Würzburg (Würzburg, 1990).
Author information
Authors and Affiliations
Additional information
On leave from the Institute of Mathematics, Eötvös University Budapest, H-1080 Budapest, Hungary.
Rights and permissions
About this article
Cite this article
Sonnevend, G., Stoer, J. & Zhao, G. On the complexity of following the central path of linear programs by linear extrapolation II. Mathematical Programming 52, 527–553 (1991). https://doi.org/10.1007/BF01582904
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01582904