Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

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 $Q$-order $1+t$, under suitable conditions, where $t\in (0,1)$ is an additional parameter.


References [Enhancements On Off] (What's this?)

  • 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 $P_0+R_0$ 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.

Similar Articles

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

American Mathematical Society