Predictor-corrector method for linear complementarity problems with polynomial complexity and superlinear convergence. (English) Zbl 0824.90129
Summary: We extend the Mizuno-Todd-Ye predictor-corrector algorithm for solving monotone linear complementarity problems. We prove that the extended algorithm is globally \(Q\)-linearly convergent and solves problems with integer data of bilength \(L\) in at most \(O(\sqrt nL)\) iterations. We also prove that the duality gap converges to zero \(Q\)-superlinerly for problems having strictly complementary solutions. Our results generalize the results obtained by Ye, Tapia, and Zhang for linear programming.
MSC:
| 90C33 | Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) |
Keywords:
superlinear convergence; predictor-corrector algorithm; monotone linear complementarity problemsReferences:
| [1] | Ding, J., andLi, T. Y.,A Polynomial-Time Predictor-Corrector Algorithm for a Class of Linear Complementarity Problems, SIAM Journal on Optimization, Vol. 1, pp. 83–92, 1991. · Zbl 0752.90079 · doi:10.1137/0801007 |
| [2] | Kojima, M., Megiddo, N., andYe, Y.,An Interior-Point Potential Reduction Algorithm for the Linear Complementarity Problem, Mathematical Programming, Vol. 54, pp. 267–279, 1992. · Zbl 0764.90083 · doi:10.1007/BF01586054 |
| [3] | Kojima, M., Mizuno, S., andYoshise, A.,A Primal-Dual Algorithm for a Class of Linear Complementarity Problems, Mathematical Programming, Vol. 44, pp. 1–26, 1989. · Zbl 0676.90087 · doi:10.1007/BF01587074 |
| [4] | Mizuno, S.,An O(n 3 L)-Algorithm Using a Sequence for Linear Complementarity Problems, Journal of the Operations Research Society of Japan, Vol. 33, pp. 66–75, 1990. · Zbl 0715.90091 |
| [5] | Mizuno, S.,A New Polynomial Time Method for a Linear Complementarity Problem, Mathematical Programming, Vol. 56, pp. 31–43, 1992. · Zbl 0769.90077 · doi:10.1007/BF01580891 |
| [6] | Ye, Y.,Bimatrix Equilibrium Points and Potential Functions, Working Paper 88-16, Department of Management Sciences, University of Iowa, Iowa City, Iowa, 1988. |
| [7] | Zhang, Y., Tapia, R. A., andPotra, F. A.,On the Superlinear Convergence of Interior-Point Algorithms for a General Class of Problems, SIAM Journal on Optimization, Vol. 3, pp. 413–422, 1993. · Zbl 0781.90074 · doi:10.1137/0803019 |
| [8] | Kojima, M., Kurita, Y., andMizuno, S.,Large-Step Interior-Point Algorithms for Linear Complementarity Problems, SIAM Journal on Optimization, Vol. 3, pp. 398–412, 1993. · Zbl 0781.90085 · doi:10.1137/0803018 |
| [9] | Ji, J., Potra, F. A., Tapia, R., andZhang, Y.,An Interior-Point Algorithm with Polynomial Complexity and Superlinear Convergence for Linear Complementarity Problems, Technical Report 91-23, Department of Mathematical Sciences, Rice University, Houston, Texas, 1991. |
| [10] | Mizuno, S., Todd, M., andYe, Y.,On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming, Mathematics of Operations Research, Vol. 18, pp. 964–981, 1993. · Zbl 0810.90091 · doi:10.1287/moor.18.4.964 |
| [11] | Ye, Y., Tapia, R. A., andZhang, Y., A Superlinearly Convergent \(O(\sqrt n L)\) -Iteration Algorithm for Linear Programming, Technical Report 91-22, Department of Mathematical Sciences, Rice University, Houston, Texas, 1991. |
| [12] | Kojima, M., Mizuno, S., andYoshise, A., An \(O(\sqrt n L)\) -Iteration Potential Reduction Algorithm for Linear Complementarity Problems, Mathematical Programming, Vol. 50, pp. 331–342, 1991. · Zbl 0738.90077 · doi:10.1007/BF01594942 |
| [13] | Zhang, Y., andTapia, R. A.,A Superlinearly Convergent Polynomial Primal-Dual Interior-Point Algorithm for Linear Programming, SIAM Journal on Optimization, Vol. 3, pp. 118–133, 1993. · Zbl 0781.90067 · doi:10.1137/0803006 |
| [14] | Güler, O., andYe, Y.,Convergence Behavior of Some Interior-Point Algorithms, Mathematical Programming, Vol. 60, pp. 215–228, 1993. · Zbl 0803.90087 · doi:10.1007/BF01580610 |
| [15] | Potra, F. A., andYe, Y.,Interior-Point Methods for Nonlinear Complementarity Problems, Technical Report 15, Department of Mathematics, University of Iowa, Iowa City, Iowa, 1991. |
| [16] | Monteiro, R. D. C., andWright, S. J.,Local Convergence of Interior-Point Algorithm for Degenerate Monotone LCP, Preprint MCS-P357-0493, Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, Illinois, 1993. |
| [17] | Bonnans, J. F., andGonzaga, C. C. Convergence of Interior-Point Algorithms for the Monotone Linear Complementarity Problem, Research Report, INRIA, Rocquencourt, France, 1993. |
| [18] | Ye, Y., andAnstreicher, K. M., On Quadratic Convergence and \(O(\sqrt n L)\) -Convergence of Predictor-Corrector Algorithms for LCP, Mathematical Programming, Vol. 62, pp. 37–551, 1993. · Zbl 0799.90111 · doi:10.1007/BF01585182 |
| [19] | Ye, Y., Güler, O., Tapia, R. A., andZhang, Y., A Quadratically Convergent \(O(\sqrt n L)\) -Iteration Algorithm for Linear Programming, Mathematical Programming, Vol. 59, pp. 151–162, 1993. · 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
