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 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