×

Improving the convergence of non-interior point algorithms for nonlinear complementarity problems. (English) Zbl 0947.90117

Summary: Recently, based upon the Chen-Harker-Kanzow-Smale smoothing function and the trajectory and the neighbourhood techniques, Hotta and Yoshise proposed a noninterior point algorithm for solving the nonlinear complementarity problem. Their algorithm is globally convergent under a relatively mild condition. We modify their algorithm and combine it with the superlinear convergence theory for nonlinear equations. We provide a globally linearly convergent result for a slightly updated version of the Hotta-Yoshise algorithm and show that a further modified Hotta-Yoshise algorithm is globally and superlinearly convergent, with a convergence \(Q\)-order \(1+t\), under suitable conditions, where \(t\in(0,1)\) is an additional parameter.

MSC:

90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
90C30 Nonlinear programming
65H10 Numerical computation of solutions to systems of equations
90C51 Interior-point methods
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] J. Burke and S. Xu, “The global linear convergence of a non-interior path-following algorithm for linear complementarity problem”, to appear in Mathematics of Operations Research. · Zbl 1081.90603
[2] J. Burke and S. Xu, “A non-interior predictor-corrector path following algorithm for the monotone linear complementarity problem”, Preprint, Department of Mathematics, University of Washington, Seattle, WA 98195, September, 1997. · Zbl 1081.90603
[3] J. Burke and S. Xu, “A non-interior predictor-corrector path following method for LCP”, in: M. Fukushima and L. Qi, eds., Reformulation - Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods, Kluwer Academic Publisher, Nowell, Maryland, pp. 45-64, 1998.
[4] B. Chen and X. Chen, “A global linear and local quadratic continuation smoothing method for variational inequalities with box constraints”, Preprint, Department of Management and Systems, Washington State University, Pullman, March 1997. · Zbl 0987.90079
[5] B. Chen and X. Chen, “A global and local superlinear continuation-smoothing method for \(P_0+R_0\) and monotone NCP”, to appear in SIAM Journal on Optimization.
[6] Bintong Chen and Patrick T. Harker, A non-interior-point continuation method for linear complementarity problems, SIAM J. Matrix Anal. Appl. 14 (1993), no. 4, 1168 – 1190. · Zbl 0788.65073
[7] Bintong Chen and Patrick T. Harker, A continuation method for monotone variational inequalities, Math. Programming 69 (1995), no. 2, Ser. A, 237 – 253. · Zbl 0844.90093
[8] Bintong Chen and Patrick T. Harker, Smooth approximations to nonlinear complementarity problems, SIAM J. Optim. 7 (1997), no. 2, 403 – 420. · Zbl 0879.90177
[9] B. Chen and N. Xiu, “A global linear and local quadratic non-interior continuation method for nonlinear complementarity problems based on Chen-Mangasarian smoothing function”, to appear in SIAM Journal on Optimization.
[10] Chun Hui Chen and O. L. Mangasarian, Smoothing methods for convex inequalities and linear complementarity problems, Math. Programming 71 (1995), no. 1, Ser. A, 51 – 69. · Zbl 0855.90124
[11] Chunhui Chen and O. L. Mangasarian, A class of smoothing functions for nonlinear and mixed complementarity problems, Comput. Optim. Appl. 5 (1996), no. 2, 97 – 138. · Zbl 0859.90112
[12] X. Chen, L. Qi, and D. Sun, Global and superlinear convergence of the smoothing Newton method and its application to general box constrained variational inequalities, Math. Comp. 67 (1998), no. 222, 519 – 540. · Zbl 0894.90143
[13] X. Chen and Y. Ye, “On homotopy-smoothing methods for variational inequalities”, to appear in SIAM Journal on Control and Optimization. · Zbl 0973.65051
[14] Frank H. Clarke, Optimization and nonsmooth analysis, Canadian Mathematical Society Series of Monographs and Advanced Texts, John Wiley & Sons, Inc., New York, 1983. A Wiley-Interscience Publication. · Zbl 0582.49001
[15] F. Facchinei, H. Jiang, and L. Qi, “A smoothing method for mathematical programming with equilibrium constraints”, to appear in Mathematical Programming. · Zbl 0959.65079
[16] M.C. Ferris and J.-S. Pang, “Engineering and economic applications of complementarity problems”, SIAM Review, 39 (1997), 669-713. CMP 98:06 · Zbl 0891.90158
[17] M. Fukushima, Z.-Q. Luo, and J.-S. Pang, “A globally convergent sequential quadratic programming algorithm for mathematical programming problems with linear complementarity constraints”, Computational Optimization and Applications, 10 (1998), 5-34. CMP 98:09
[18] Patrick T. Harker and Jong-Shi Pang, Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications, Math. Programming 48 (1990), no. 2, (Ser. B), 161 – 220. · Zbl 0734.90098
[19] K. Hotta and A. Yoshise “Global convergence of a class of non-interior-point algorithms using Chen-Harker-Kanzow functions for nonlinear complementarity problems”, Discussion Paper Series No. 708, Institute of Policy and Planning Sciences, University of Tsukuba, Tsukuba, Ibaraki 305, Japan, December 1996. CMP 98:13
[20] Christian Kanzow, Some noninterior continuation methods for linear complementarity problems, SIAM J. Matrix Anal. Appl. 17 (1996), no. 4, 851 – 868. · Zbl 0868.90123
[21] C. Kanzow and H. Jiang, “A continuation method for (strongly) monotone variational inequalities”, Mathematical Programming 81 (1998), 103-125. CMP 98:11 · Zbl 0920.90131
[22] Masakazu Kojima, Nimrod Megiddo, and Toshihito Noma, Homotopy continuation methods for nonlinear complementarity problems, Math. Oper. Res. 16 (1991), no. 4, 754 – 774. · Zbl 0744.90087
[23] 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-Verlag, Berlin, 1991. · Zbl 0745.90069
[24] J. M. Ortega and W. C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Academic Press, New York-London, 1970. · Zbl 0241.65046
[25] Jong-Shi Pang, Complementarity problems, Handbook of global optimization, Nonconvex Optim. Appl., vol. 2, Kluwer Acad. Publ., Dordrecht, 1995, pp. 271 – 338. · Zbl 0833.90114
[26] Li Qun Qi, Convergence analysis of some algorithms for solving nonsmooth equations, Math. Oper. Res. 18 (1993), no. 1, 227 – 244. · Zbl 0776.65037
[27] Li Qun Qi and Xiao Jun Chen, A globally convergent successive approximation method for severely nonsmooth equations, SIAM J. Control Optim. 33 (1995), no. 2, 402 – 418. · Zbl 0833.90109
[28] Li Qun Qi and Jie Sun, A nonsmooth version of Newton’s method, Math. Programming 58 (1993), no. 3, Ser. A, 353 – 367. · Zbl 0780.90090
[29] Stephen M. Robinson, Generalized equations, Mathematical programming: the state of the art (Bonn, 1982) Springer, Berlin, 1983, pp. 346 – 367.
[30] Steve Smale, Algorithms for solving equations, Proceedings of the International Congress of Mathematicians, Vol. 1, 2 (Berkeley, Calif., 1986) Amer. Math. Soc., Providence, RI, 1987, pp. 172 – 195.
[31] Paul Tseng, An infeasible path-following method for monotone complementarity problems, SIAM J. Optim. 7 (1997), no. 2, 386 – 402. · Zbl 0882.90123
[32] P. Tseng, “Analysis of a non-interior continuation method based on Chen-Mangasarian functions for complementarity problems”, in: M. Fukushima and L. Qi, eds., Reformulation - Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods, Kluwer Academic Publisher, Nowell, Maryland, pp. 381-404, 1998. · Zbl 0928.65078
[33] Stephen J. Wright, Primal-dual interior-point methods, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. · Zbl 0863.65031
[34] Stephen Wright and Daniel Ralph, A superlinear infeasible-interior-point algorithm for monotone complementarity problems, Math. Oper. Res. 21 (1996), no. 4, 815 – 838. · Zbl 0867.90112
[35] S. Xu, “The global linear convergence of an infeasible non-interior path-following algorithm for complementarity problems with uniform \(P\)-functions”, Preprint, Department of Mathematics, University of Washington, Seattle, WA 98195, December 1996.
[36] S. Xu, “The global linear convergence and complexity of a non-interior path-following algorithm for monotone LCP based on Chen-Harker-Kanzow-Smale smooth functions”, Preprint, Department of Mathematics, University of Washington, Seattle, WA 98195, February 1997.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.