×

The Mizuno-Todd-Ye algorithm in a larger neighborhood of the central path. (English) Zbl 1058.90076

Summary: The Mizuno-Todd-Ye predictor-corrector method based on two neighborhoods \({\mathcal D}(\alpha)\subset {\mathcal D}(\bar \alpha)\) of the central path of a monotone homogeneous linear complementarity problem is analyzed, where \({\mathcal D}(\alpha)\) is composed of all feasible points with \(\delta\)-proximity to the central path less than or equal to \(\alpha\). The largest allowable value for \(\bar\alpha\) is \(\approx 1.76\). For a specific choice of \(\alpha\) and \(\bar\alpha\) a lower bound of \({\mathcal X}/\sqrt n\) is obtained for the stepsize along the affine-scaling direction, where \({\mathcal X}_n\) has an asymptotic value greater than 1.08. For \(n \geq 400\) it is shown that \({\mathcal X}_n>1.05\). The algorithm has \(O(\sqrt n L)\)-iteration complexity under general conditions and quadratic convergence under the strict complementarity assumption.

MSC:

90C51 Interior-point methods
90C05 Linear programming
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)

Software:

PITCON; RODAS
Full Text: DOI

References:

[1] Anitescu, M.; Lesaja, G.; Potra, F. A., An infeasible-interior-point predictor-corrector algorithm for the \(P_*\)-geometric LCP, Applied Mathematics and Optimization, 36, 2, 203-228 (1997) · Zbl 0884.90140
[2] Bonnans, J. F.; Gonzaga, C. C., Convergence of interior point algorithms for the monotone linear complementarity problem, Mathematics of Operations Research, 21, 1-25 (1996) · Zbl 0846.90109
[3] Cottle, R. W.; Pang, J.-S.; Stone, R. E., The Linear Complementarity Problem (1992), Academic Press: Academic Press Boston, MA · Zbl 0757.90078
[4] Hairer, E.; Wanner, G., Solving ordinary differential equations. II, Stiff and differential-algebraic problems, second ed. (1996), Springer-Verlag: Springer-Verlag Berlin · Zbl 0859.65067
[5] Jansen, B.; Roos, C.; Terlaky, T.; Vial, J.-P., Primal-dual algorithms for linear programming based on the logarithmic barrier method, Journal of Optimization Theory and Applications, 83, 1, 1-26 (1994) · Zbl 0820.90068
[6] Jansen, B.; Roos, C.; Terlaky, T.; Vial, J.-Ph., Primal-dual target-following algorithms for linear programming, Annals of Operations Research, 62, 197-231 (1996), Interior point methods in mathematical programming · Zbl 0848.90083
[7] Ji, J.; Potra, F. A.; Huang, S., A predictor-corrector method for linear complementarity problems with polynomial complexity and superlinear convergence, Journal of Optimization Theory and Applications, 84, 1, 187-199 (1995) · Zbl 0824.90129
[8] Kojima, M.; Megiddo, N.; Noma, T.; Yoshise, A., A unified approach to interior point algorithms for linear complementarity problems, Lecture Notes in Computer Science, 538 (1991) · Zbl 0745.90069
[9] Mizuno, S.; Todd, M. J.; Ye, Y., On adaptive-step primal-dual interior-point algorithms for linear programming, Mathematics of Operations Research, 18, 4, 964-981 (1993) · Zbl 0810.90091
[10] Monteiro, R. D.C.; Wright, S. J., Local convergence of interior-point algorithms for degenerate monotone LCP, Computational Optimization and Applications, 3, 131-155 (1994) · Zbl 0801.90110
[11] Potra, F. A., Efficient hybrid algorithms for finding zeros of convex functions, Journal of Complexity, 10, 199-215 (1994) · Zbl 0807.65051
[12] F.A., Potra. A path-following method for linear complementarity problems based on the affine invariant kantorovich theorem. ZIB-Report 00-30, Konrad-Zuse-Zentrum, Berlin, August 2000; F.A., Potra. A path-following method for linear complementarity problems based on the affine invariant kantorovich theorem. ZIB-Report 00-30, Konrad-Zuse-Zentrum, Berlin, August 2000
[13] Rheinboldt, W. C., Numerical Analysis of Parametrized Nonlinear Equations (1986), John Wiley and Sons Inc: John Wiley and Sons Inc New York · Zbl 0572.65034
[14] Roos, C.; Vial, J.-P.; Terlaky, T., Theory and algorithms for linear optimization: An Interior Point Approach, Wiley-Interscience Series in Discrete Mathematics and Optimization (1997), John Wiley and Sons: John Wiley and Sons New York · Zbl 0954.65041
[15] Ye, Y.; Anstreicher, K., On quadratic and \(O(nL)\) convergence of predictor-corrector algorithm for LCP, Mathematical Programming, 62, 3, 537-551 (1993) · Zbl 0799.90111
[16] Ye, Y.; Güler, O.; Tapia, R. A.; Zhang, Y., A quadratically convergent \(OnL)\) iteration algorithm for linear programming, Mathematical Programming, 59, 2, 151-162 (1993) · Zbl 0778.90037
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.