Mathematics of Computation

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

Author(s): Liqun Qi; Defeng Sun.
Journal: Math. Comp. 69 (2000), 283-304.
MSC (1991): Primary 90C33; Secondary 90C30, 65H10
Posted: February 19, 1999
Retrieve article in: PDF DVI PostScript
This article is available free of charge

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 $t\in (0,1)$ 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 $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.

Retrieve articles in Mathematics of Computation with MSC (1991): 90C33, 90C30, 65H10

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: 10.1090/S0025-5718-99-01082-0
PII: S 0025-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
Posted: February 19, 1999
Additional Notes: This work is supported by the Australian Research Council.
Copyright of article: Copyright 1999, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS