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
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 $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. 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 $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: 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