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

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

Published electronically:
February 19, 1999

MathSciNet review:
1642766

Full-text PDF

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.**B. Chen and P.T. Harker, ``A non-interior-point continuation method for linear complementarity problems",*SIAM Journal on Matrix Analysis and Applications, 14*(1993), 1168-1190. MR**94g:90139****7.**B. Chen and P.T. Harker, ``A continuation method for monotone variational inequalities",*Mathematical Programming, 69*(1995), 237-253. MR**96m:90101****8.**B. Chen and P.T. Harker, ``Smooth approximations to nonlinear complementarity problems",*SIAM Journal on Optimization, 7*(1997), 403-420. MR**98e:90192****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.**C. Chen and O.L. Mangasarian, ``Smoothing methods for convex inequalities and linear complementarity problems",*Mathematical Programming, 71*(1995), 51-69. MR**96j:90082****11.**C. Chen and O.L. Mangasarian, ``A class of smoothing functions for nonlinear and mixed complementarity problems",*Computational Optimization and Applications, 5*(1996), 97-138. MR**96m:90102****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",*Mathematics of Computation, 67*(1998), 519-540. MR**98g:90034****13.**X. Chen and Y. Ye, ``On homotopy-smoothing methods for variational inequalities'', to appear in*SIAM Journal on Control and Optimization*.**14.**F.H. Clarke,*Optimization and Nonsmooth Analysis*, Wiley, New York, 1983. MR**85m:49002****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.**P.T. Harker and J.-S. Pang, ``Finite-dimensional variational inequality and nonlinear complementarity problem: A survey of theory, algorithms and applications'',*Mathematical Programming, 48*(1990) 161-220. MR**91g:90166****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.**C. Kanzow, ``Some noninterior continuation methods for linear complementarity problems",*SIAM Journal on Matrix Analysis and Applications, 17*(1996), 851-868. MR**97g:90148****21.**C. Kanzow and H. Jiang, ``A continuation method for (strongly) monotone variational inequalities",*Mathematical Programming***81**(1998), 103-125. CMP**98:11****22.**M. Kojima, N. Megiddo, and T. Noma, ``Homotopy continuation methods for nonlinear complementarity problems'',*Mathematics of Operations Research, 16*(1991), 754-774. MR**93b:90097****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 538, Springer-Verlag, Berlin, Germany, 1991. MR**94e:90004****24.**J.M. Ortega and W.C. Rheinboldt,*Iterative Solution of Nonlinear Equations in Several Variables*, Academic Press, Inc., San Diego, 1970. MR**42:8686****25.**J.-S. Pang, ``Complementarity problems,'' in: R. Horst and P. Pardalos, eds.,*Handbook of Global Optimization*, Kluwer Academic Publishers, Boston, pp. 271-338, 1995. MR**97a:90095****26.**L. Qi, ``Convergence analysis of some algorithms for solving nonsmooth equations'',*Mathematics of Operations Research, 18*(1993), 227-244. MR**95f:65109****27.**L. Qi and X. Chen, ``A globally convergent successive approximation method for severely nonsmooth equations'',*SIAM Journal on Control and Optimization, 33*(1995), 402-418. MR**96a:90035****28.**L. Qi and J. Sun, ``A nonsmooth version of Newton's method'',*Mathematical Programming, 58*(1993), 353-367. MR**94b:90077****29.**S.M. Robinson, ``Generalized equations'', in: A. Bachem, M. Grötschel and B. Korte, eds.,*Mathematical Programming: The State of the Art*, Springer-Verlag, Berlin, pp. 346-347, 1983. MR**85d:90074****30.**S. Smale, ``Algorithms for solving equations",*Proceedings of the International Congress of Mathematicians*(1986), Berkeley, California, pp. 172-195. MR**89d:65060****31.**P. Tseng, ``An infeasible path-following method for monotone complementarity problem",*SIAM Journal on Optimization, 7*(1997), 386-402. MR**98c:90169****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.**S. Wright,*Primal-Dual Interior Point Methods*, SIAM, Philadelphia, PA, 1997. MR**98a:90004****34.**S. Wright and D. Ralph, ``A superlinear infeasible-interior-point algorithm for monotone complementarity problems'',*Mathematics of Operations Research, 21*(1996), 815-838. MR**97j:90076****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:
https://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