Abstract
A new predictor-corrector algorithm is proposed for solvingP *(κ)-matrix linear complementarity problems. If the problem is solvable, then the algorithm converges from an arbitrary positive starting point (x 0,s 0). The computational complexity of the algorithm depends on the quality of the starting point. If the starting point is feasible or close to being feasible, it has\(O((1 + \kappa )\sqrt {n/\rho _0 } L)\)-iteration complexity, whereρ 0 is the ratio of the smallest and average coordinate ofX 0 s 0. With appropriate initialization, a modified version of the algorithm terminates in O((1+κ)2(n/ρ 0)L) steps either by finding a solution or by determining that the problem has no solution in a predetermined, arbitrarily large, region. The algorithm is quadratically convergent for problems having a strictly complementary solution. We also propose an extension of a recent algorithm of Mizuno toP *(κ)-matrix linear complementarity problems such that it can start from arbitrary positive points and has superlinear convergence without a strictly complementary condition.
Similar content being viewed by others
References
J. Ji and F.A. Potra, An infeasible-interior-point method for theP *-matrix LCP, Reports on Computational Mathematics 52, Department of Mathematics, University of Iowa, Iowa City, IA (1994).
J. Ji, F.A. Potra and R. Sheng, A predictor-corrector method for solving theP *-matrix LCP from infeasible starting points,Optimization Methods and Software 6 (1995) 109–126.
M. Kojima, N. Megiddo, T. Noma and A. Yoshise, A unified approach to interior point algorithms for linear complementarity problems. Lecture Notes in:Comput. Sci. 538 (1991).
J. Miao, A quadratically convergent\(O((1 + \kappa )\sqrt n L)\)-iteration algorithm for theP *(κ)-matrix linear complementarity problem,Mathematical Programming 69 (1995) 355–368.
S. Mizuno, A superlinearly convergent infeasible-interior-point algorithm for geometrical LCPs without a strictly complementary condition, Technical Report Nr. 214, Mathematische Institute der Universität Würzburg, 97074 Würzburg, Germany (1994).
S. Mizuno, F. Jarre and J. Stoer, A unified approach to infeasible-interior-point algorithms via geometrical linear complementarity problems, Preprint Nr. 213, Mathematische Institute der Universität Würzburg, 97074 Würzburg, Germany (1994).
R.D.C. Monteiro and S.J. Wright, Local convergence of interior-point algorithm for degenerate monotone LCP,Computational Optimization and Applications 3 (1993) 131–155.
F.A. Potra, An O(nL) infeasible-interior-point algorithm for LCP with quadratic convergence, Reports on Computational Mathematics 50, Department of Mathematics, The University of Iowa, Iowa City, IA (1994).
R. Sheng and F.A. Potra, A quadratically convergent infeasible-interior-point algorithm for LCP with polynomial complexity, to appear in:SIAM Journal on Optimization.
S.J. Wright, An infeasible interior point algorithm for linear complementarity problems,Mathematical Programming 67 (1) (1994) 29–52.
S.J. Wright, A path-following infeasible-interior-point algorithm for linear complementarity problems,Optimization Methods and Software 2 (1993) 79–106.
S.J. Wright, A path-following interior-point algorithm for linear and quadratic problems, Preprint MCS-P401-1293, Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL (1993).
S.J. Wright and Y. Zhang, A superquadratic infeasible-interior-point algorithm for linear complementarity problems, Preprint MCS-P418-0294, Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL (1994).
Y. Zhang, On the convergence of a class of infeasible interior-point methods for the horizontal linear complementarity problem,SIAM J. Optimization 4 (1) (1994) 208–227.
Author information
Authors and Affiliations
Additional information
The work of this author was supported in part by NSF, Grant DMS 9305760 and by an Oberman fellowship from the University of Iowa Center for Advanced Studies.
Rights and permissions
About this article
Cite this article
Potra, F.A., Sheng, R. Predictor-corrector algorithm for solvingP *(κ)-matrix LCP from arbitrary positive starting points. Mathematical Programming 76, 223–244 (1997). https://doi.org/10.1007/BF02614385
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02614385