Improving the convergence

of non-interior point algorithms

for nonlinear complementarity problems

Authors:
Liqun Qi and Defeng Sun

Journal:
Math. Comp. **69** (2000), 283-304

MSC (1991):
Primary 90C33; Secondary 90C30, 65H10

Published electronically:
February 19, 1999

MathSciNet review:
1642766

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 -order , under suitable conditions, where is an additional parameter.

**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*.**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.**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.**5.**B. Chen and X. Chen, ``A global and local superlinear continuation-smoothing method for 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. MR**1238931**, 10.1137/0614081**7.**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**, 10.1007/BF01585559**8.**Bintong Chen and Patrick T. Harker,*Smooth approximations to nonlinear complementarity problems*, SIAM J. Optim.**7**(1997), no. 2, 403–420. MR**1443626**, 10.1137/S1052623495280615**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. MR**1362957**, 10.1007/BF01592244**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. MR**1373293**, 10.1007/BF00249052**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. MR**1458218**, 10.1090/S0025-5718-98-00932-6**13.**X. Chen and Y. Ye, ``On homotopy-smoothing methods for variational inequalities'', to appear in*SIAM Journal on Control and Optimization*.**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. MR**709590****15.**F. Facchinei, H. Jiang, and L. Qi, ``A smoothing method for mathematical programming with equilibrium constraints'', to appear in*Mathematical Programming*.**16.**M.C. Ferris and J.-S. Pang, ``Engineering and economic applications of complementarity problems'',*SIAM Review, 39*(1997), 669-713. CMP**98:06****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. MR**1073707**, 10.1007/BF01582255**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. MR**1410705**, 10.1137/S0895479894273134**21.**C. Kanzow and H. Jiang, ``A continuation method for (strongly) monotone variational inequalities",*Mathematical Programming***81**(1998), 103-125. CMP**98:11****22.**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**, 10.1287/moor.16.4.754**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. MR**1226025****24.**J. M. Ortega and W. C. Rheinboldt,*Iterative solution of nonlinear equations in several variables*, Academic Press, New York-London, 1970. MR**0273810****25.**Jong-Shi Pang,*Complementarity problems*, Handbook of global optimization, Nonconvex Optim. Appl., vol. 2, Kluwer Acad. Publ., Dordrecht, 1995, pp. 271–338. MR**1377087**, 10.1007/978-1-4615-2025-2_6**26.**Li Qun Qi,*Convergence analysis of some algorithms for solving nonsmooth equations*, Math. Oper. Res.**18**(1993), no. 1, 227–244. MR**1250115**, 10.1287/moor.18.1.227**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. MR**1318657**, 10.1137/S036301299223619X**28.**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**, 10.1007/BF01581275**29.**Stephen M. Robinson,*Generalized equations*, Mathematical programming: the state of the art (Bonn, 1982) Springer, Berlin, 1983, pp. 346–367. MR**717407****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. MR**934223****31.**Paul Tseng,*An infeasible path-following method for monotone complementarity problems*, SIAM J. Optim.**7**(1997), no. 2, 386–402. MR**1443625**, 10.1137/S105262349427409X**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.**33.**Stephen J. Wright,*Primal-dual interior-point methods*, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1997. MR**1422257****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. MR**1419904**, 10.1287/moor.21.4.815**35.**S. Xu, ``The global linear convergence of an infeasible non-interior path-following algorithm for complementarity problems with uniform -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.

Retrieve articles in *Mathematics of Computation of the American Mathematical Society*
with MSC (1991):
90C33,
90C30,
65H10

Retrieve articles in all journals with MSC (1991): 90C33, 90C30, 65H10

Additional Information

**Liqun Qi**

Affiliation:
School of Mathematics, The University of New South Wales, Sydney 2052, Australia

Email:
L.Qi@unsw.edu.au

**Defeng Sun**

Affiliation:
School of Mathematics, The University of New South Wales, Sydney 2052, Australia

Email:
sun@maths.unsw.edu.au

DOI:
http://dx.doi.org/10.1090/S0025-5718-99-01082-0

Keywords:
Nonlinear complementarity problem,
noninterior point,
approximation,
superlinear convergence

Received by editor(s):
June 9, 1997

Received by editor(s) in revised form:
March 9, 1998

Published electronically:
February 19, 1999

Additional Notes:
This work is supported by the Australian Research Council.

Article copyright:
© Copyright 1999
American Mathematical Society