Abstract
The main goals of this paper are to: i) relate two iteration-complexity bounds derived for the Mizuno-Todd-Ye predictor-corrector (MTY P-C) algorithm for linear programming (LP), and; ii) study the geometrical structure of the LP central path. The first iteration-complexity bound for the MTY P-C algorithm considered in this paper is expressed in terms of the integral of a certain curvature function over the traversed portion of the central path. The second iteration-complexity bound, derived recently by the authors using the notion of crossover events introduced by Vavasis and Ye, is expressed in terms of a scale-invariant condition number associated with m × n constraint matrix of the LP. In this paper, we establish a relationship between these bounds by showing that the first one can be majorized by the second one. We also establish a geometric result about the central path which gives a rigorous justification based on the curvature of the central path of a claim made by Vavasis and Ye, in view of the behavior of their layered least squares path following LP method, that the central path consists of \({\mathcal{O}}(n^2)\) long but straight continuous parts while the remaining curved part is relatively “short”.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Dikin I.I. (1974). On the speed of an iterative process. Upravlyaemye Sistemi 12: 54–60
Forsgren A. (1996). On linear least-squares problems with diagonally dominant weight matrices. SIAM J. Matrix Anal. Appl. 17: 763–788
Gonzaga C.C. (1992). Path-following methods for linear programming. SIAM Rev. 34: 167–224
Gonzaga C.C., Lara H.J. (1997). A note on properties of condition numbers. Linear Algebra Appl. 261: 269–273
Karmarkar, N.: Riemannian geometry underlying interior-point methods for linear programming. Mathematical Developments Arising from Linear Programming, In: Brunswick, M.E., (ed), pp. 51–75. Contemporary Mathematics, Vol. 114, American Mathematical Society, Providence, 1990
Megiddo N., Mizuno S., Tsuchiya T. (1998). A modified layered-step interior-point algorithm for linear programming. Math. Program. 82: 339–355
Mizuno S., Todd M.J., Ye Y. (1993). On adaptive-step primal-dual interior-point algorithms for linear programming. Math. Oper. Res. 18: 964–981
Monteiro R.D.C., Tsuchiya T. (1998). Global convergence of the affine scaling algorithm for convex quadratic programming. SIAM J. Optim. 8(1): 26–58
Monteiro R.D.C., Tsuchiya T. (2003). A variant of the Vavasis-Ye layered-step interior-point algorithm for linear programming. SIAM J. Optim. 13: 1054–1079
Monteiro R.D.C., Tsuchiya T. (2004). A new iteration-complexity bound for the MTY predictor-corrector algorithm. SIAM J. Optim. 15: 319–347
Sonnevend G., Stoer J., Zhao G. (1991). On the complexity of following the central path of linear programs by linear extrapolation. II. Math. Program. 52: 527–553
Stewart G.W. (1989). On scaled projections and pseudoinverses. Linear Algebra Appl. 112: 189–193
Todd M.J. (1990). A Dantzig-Wolfe-like variant of Karmarkar’s interior-point linear programming algorithm. Oper. Res. 38: 1006–1018
Todd M.J., Tunçel L., Ye Y. (2001). Characterizations, bounds, and probabilistic analysis of two complexity measures for linear programming problems. Math. Program. 90(1): 59–70
Tsuchiya T. (1992). Global convergence property of the affine scaling method for primal degenerate linear programming problems. Math. Oper. Res. 17: 527–557
Tunçel L. (1999). Approximating the complexity measure of Vavasis-Ye algorithm is NP-hard. Math. Program. 86(1): 219–223
Tunçel L. (1999). On the condition numbers for polyhedra in Karmarkar’s form. Oper. Res. Lett. 24(4): 149–155
Vanderbei R.J., Lagarias J.C. (1990). I. I. Dikin’s convergence result for the affine-scaling algorithm, Vol 17. Contemp. Math. 114: 109–119
Vavasis S., Ye Y. (1996). A primal-dual accelerated interior point method whose running time depends only on A. Math. Program. 74: 79–120
Vavasis, S., Ye, Y.: On the relationship between layered least squares and affine scaling steps. In: The Mathematics of Numerical Analysis, pp. 857–865. Lectures in Applied Mathematics, Vol. 32. American Mathematical Society, Providence, 1996
Zhao G. (1996). On the relationship between the curvature integral and the complexity of path-following methods in linear programming. SIAM J. Optim. 6: 57–73
Zhao G., Stoer J. (1993). Estimating the complexity of a class of path-following methods for solving linear programs by curvature integrals. Appl. Math. Optim. 27: 85–103
Author information
Authors and Affiliations
Corresponding author
Additional information
R. D. C. Monteiro was supported in part by NSF Grants CCR-0203113 and CCF-0430644 and ONR grant N00014-05-1-0183. T. Tsuchiya was supported in part by Japan-US Joint Research Projects of Japan Society for the Promotion of Science “Algorithms for linear programs over symmetric cones” and the Grants-in-Aid for Scientific Research (C) 15510144 of Japan Society for the Promotion of Science.
Rights and permissions
About this article
Cite this article
Monteiro, R.D.C., Tsuchiya, T. A strong bound on the integral of the central path curvature and its relationship with the iteration-complexity of primal-dual path-following LP algorithms. Math. Program. 115, 105–149 (2008). https://doi.org/10.1007/s10107-007-0141-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-007-0141-5
Keywords
- Interior-point algorithms
- Primal-dual algorithms
- Path-following
- Central path
- Layered least squares steps
- Condition number
- Polynomial complexity
- Crossover events
- Scale-invariance
- Predictor-corrector
- Affine scaling
- Strongly polynomial
- Linear programming
- Curvature