Abstract
In this paper, we propose a predictor—corrector-type algorithm for solving the linear complementarity problem (LCP), and prove that the actual number of iterations needed by the algorithm is bounded from above and from below by a curvature integral along the central trajectory of the problem. This curvature integral is not greater than, and possibly smaller than, the best upper bound obtained in the literature to date.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
J. Ji, F. Potra and S. Huang, “A predictor—corrector method for linear complementarity problems with polynomial complexity and superlinear convergence,” Report No. 18, Department of Mathematics, The University of Iowa (Iowa City, IA, 1991).
N. Karmarkar, “Riemannian geometry underlying interior point methods for linear programming”, in: J.C. Lagarias and M. Todd, eds.,Mathematical Developments Arising from Linear Programming, Contemporary Mathematics, Vol. 114 (American Mathematical Society, Providence, RI, 1990) pp. 51–75.
N.K. Karmarkar, J.C. Lagarias, L. Slutsman and P. Wang, “Power series variants of Karmarkar-type algorithms,”AT & T Technical Journal 68 (1989) 20–36.
M. Kojima, N. Megiddo, T. Noma and A. Yoshise,A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems, Lecture Notes in Computer Science, Vol. 538 (Springer, Berlin, 1991).
M. Kojima, S. Mizuno and A. Yoshise, “A polynomial-time algorithm for a class of linear complementarity problems,” Mathematical Programming 44 (1989) 1–26.
S. Mizuno, M.J. Todd and Y. Ye, “Anticipated behaviour of path-following algorithm for linear programming,” Technical Report No. 878, School of Operations Research and Industrial Engineering, Cornell University (Ithaca, NY, 1989).
S. Mizuno, M.J. Todd and Y. Ye, “On adaptive-step primal-dual interior-point algorithm for linear programming,”Mathematics of Operations Research 18 (1993) 964–981.
C. Roos and J.P. Vial, “A polynomial method of approximate centers for linear programming,”Mathematical Programming 54 (1992) 295–305.
G. Sonnevend, J. Stoer and G. Zhao, “On the complexity of following the central path of linear programs by linear extrapolation II,”Mathematical Programming 52 (1991) 527–553.
Y. Ye, O. Güler, R.A. Tapia and Y. Zhang, “A quadratically convergent O(\(\sqrt n L\))-iteration algorithm for linear programming,”Mathematical Programming 59 (1993) 151–162.
G. Zhao, “Estimating the complexity of path-following methods in linear programming by curvature integrals along the central trajectory,” Ph.D. Thesis, University of Würzburg, Germany, 1991.
G. Zhao and J. Stoer, “Estimating the complexity of a class of path-following methods for solving linear programs by curvature integrals,”Applied Mathematics Optimization 27 (1993) 85–103.
J. Zhu, “A path-following algorithm for a class of convex programming problems,”Zeitschrift für Operations Research 36 (1993) 359–377.
Author information
Authors and Affiliations
Additional information
Corresponding author.
This author's research was partially supported by Research Grant No. RP920068, National University of Singapore, Singapore.
Rights and permissions
About this article
Cite this article
Zhao, G., Zhu, J. The curvature integral and the complexity of linear complementarity problems. Mathematical Programming 70, 107–122 (1995). https://doi.org/10.1007/BF01585931
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01585931