Improving the convergence of non-interior point algorithms for nonlinear complementarity problems

Qi, Liqun; Sun, Defeng

doi:10.1090/S0025-5718-99-01082-0

Improving the convergence of non-interior point algorithms for nonlinear complementarity problems
HTML articles powered by AMS MathViewer

by Liqun Qi and Defeng Sun PDF

Math. Comp. 69 (2000), 283-304 Request permission

Abstract:

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. In this paper, 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.

References

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.
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.
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.
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.
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.
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. MR 1238931, DOI 10.1137/0614081
Bintong Chen and Patrick T. Harker, A continuation method for monotone variational inequalities, Math. Programming 69 (1995), no. 2, Ser. A, 237–253. MR 1348806, DOI 10.1007/BF01585559
Bintong Chen and Patrick T. Harker, Smooth approximations to nonlinear complementarity problems, SIAM J. Optim. 7 (1997), no. 2, 403–420. MR 1443626, DOI 10.1137/S1052623495280615
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.
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. MR 1362957, DOI 10.1007/BF01592244
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. MR 1373293, DOI 10.1007/BF00249052
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. MR 1458218, DOI 10.1090/S0025-5718-98-00932-6
X. Chen and Y. Ye, “On homotopy-smoothing methods for variational inequalities”, to appear in SIAM Journal on Control and Optimization.
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. MR 709590
F. Facchinei, H. Jiang, and L. Qi, “A smoothing method for mathematical programming with equilibrium constraints”, to appear in Mathematical Programming.
M.C. Ferris and J.-S. Pang, “Engineering and economic applications of complementarity problems”, SIAM Review, 39 (1997), 669–713.
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.
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. MR 1073707, DOI 10.1007/BF01582255
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.
Christian Kanzow, Some noninterior continuation methods for linear complementarity problems, SIAM J. Matrix Anal. Appl. 17 (1996), no. 4, 851–868. MR 1410705, DOI 10.1137/S0895479894273134
C. Kanzow and H. Jiang, “A continuation method for (strongly) monotone variational inequalities", Mathematical Programming 81 (1998), 103–125.
Masakazu Kojima, Nimrod Megiddo, and Toshihito Noma, Homotopy continuation methods for nonlinear complementarity problems, Math. Oper. Res. 16 (1991), no. 4, 754–774. MR 1135047, DOI 10.1287/moor.16.4.754
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. MR 1226025, DOI 10.1007/3-540-54509-3
J. M. Ortega and W. C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Academic Press, New York-London, 1970. MR 0273810
Jong-Shi Pang, Complementarity problems, Handbook of global optimization, Nonconvex Optim. Appl., vol. 2, Kluwer Acad. Publ., Dordrecht, 1995, pp. 271–338. MR 1377087, DOI 10.1007/978-1-4615-2025-2_{6}
Li Qun Qi, Convergence analysis of some algorithms for solving nonsmooth equations, Math. Oper. Res. 18 (1993), no. 1, 227–244. MR 1250115, DOI 10.1287/moor.18.1.227
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. MR 1318657, DOI 10.1137/S036301299223619X
Li Qun Qi and Jie Sun, A nonsmooth version of Newton’s method, Math. Programming 58 (1993), no. 3, Ser. A, 353–367. MR 1216791, DOI 10.1007/BF01581275
Stephen M. Robinson, Generalized equations, Mathematical programming: the state of the art (Bonn, 1982) Springer, Berlin, 1983, pp. 346–367. MR 717407
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. MR 934223
Paul Tseng, An infeasible path-following method for monotone complementarity problems, SIAM J. Optim. 7 (1997), no. 2, 386–402. MR 1443625, DOI 10.1137/S105262349427409X
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.
Stephen J. Wright, Primal-dual interior-point methods, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. MR 1422257, DOI 10.1137/1.9781611971453
Stephen Wright and Daniel Ralph, A superlinear infeasible-interior-point algorithm for monotone complementarity problems, Math. Oper. Res. 21 (1996), no. 4, 815–838. MR 1419904, DOI 10.1287/moor.21.4.815
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.
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.