article

A Smoothing Newton Method for General Nonlinear Complementarity Problems

Authors:

Li-Zhi LiaoAuthors Info & Claims

Computational Optimization and Applications, Volume 17, Issue 2-3

Pages 231 - 253

Published: 01 December 2000 Publication History

Abstract

Smoothing Newton methods for nonlinear complementarity problems NCP(F) often require F to be at least a P₀-function in order to guarantee that the underlying Newton equation is solvable. Based on a special equation reformulation of NCP(F), we propose a new smoothing Newton method for general nonlinear complementarity problems. The introduction of Kanzow and Pieper's gradient step makes our algorithm to be globally convergent. Under certain conditions, our method achieves fast local convergence rate. Extensive numerical results are also reported for all complementarity problems in MCPLIB and GAMSLIB libraries with all available starting points.

References

[1]

1. S. C. Billups, S. P. Dirkse, and M. C. Ferris, "A comparison of algorithms for large scale mixed complementarity problems," Comput. Optim. Appl., vol. 7, pp. 3-25, 1997.

Digital Library

[2]

2. J. Burke and S. Xu, "The global linear convergence of a non-interior path-following algorithm for linear complementarity problems," Math. Oper. Res., vol. 23, pp. 719-734, 1998.

Digital Library

[3]

3. B. Chen and X. Chen, "A global and local superlinear continuation-smoothing method for P ₀ + R ₀ and monotone NCP," SIAM J. Optim., vol. 9, pp. 624-645, 1999.

Digital Library

[4]

4. B. Chen, X. Chen, and C. Kanzow, "A penalized Fischer-Burmeister NCP-function: Theoretical investigation and numerical results," Math. Programming, vol. 88, pp. 211-216, 2000.

[5]

5. B. Chen and P. T. Harker, "A non-interior-point continuation method for linear complementarity problems," SIAM J. Matrix Anal. Appl., vol. 14, pp. 168-1190, 1993.

Digital Library

[6]

6. B. Chen and P. T. Harker, "Smoothing approximations to nonlinear complementarity problems," SIAM J. Optim., vol. 7, pp. 403-420, 1997.

Digital Library

[7]

7. B. Chen and N. Xiu, "A global linear and local quadratic non-interior continuation method for nonlinear complementarity problems based on Chen-Mangasarian smoothing functions," SIAM J. Optim., vol. 9, pp. 605-623, 1999.

Digital Library

[8]

8. C. Chen and O. L. Mangasarian, "Smoothing methods for convex inequalities and linear complementarity problems," Math. Programming, vol. 71, pp. 51-69, 1995.

Digital Library

[9]

9. 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., vol. 67, pp. 519-540, 1998.

Digital Library

[10]

10. X. Chen and Y. Ye, "On smoothing methods for the P ₀ matrix linear complementarity problem," SIAM J. Optim., vol. 11, pp. 341-363, 2000.

Digital Library

[11]

11. X. Chen and Y. Ye, "On homotopy-smoothing methods for variational inequalities," SIAM J. Control Optim., vol. 37, pp. 589-616, 1999.

Digital Library

[12]

12. F. H. Clarke, Optimization and Nonsmooth Analysis, John Wiley & Sons: New York, 1983.

[13]

13. T. De Luca, F. Facchinei, and C. Kanzow, "A semismooth equation approach to the solution of nonlinear complementarity problems," Math. Programming, vol. 75, pp. 407-439, 1996.

Digital Library

[14]

14. T. De Luca, F. Facchinei, and C. Kanzow, "A theoretical and numerical comparison of some semismooth algorithms for complementarity problems," Comput. Optim. Appl., vol. 16, pp. 173-205, 2000.

Digital Library

[15]

15. J. E. Dennis, Jr. and R. B. Schnabel, Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Prentice-Hall: Englewood Cliffs, 1983.

Digital Library

[16]

16. S. P. Dirkse and M. C. Ferris, "MCPLIB: A collection of nonlinear mixed complementarity problems," Optim. Methods Software, vol. 5, pp. 123-156, 1995.

[17]

17. F. Facchinei and J. Soares, "A new merit function for nonlinear complementarity problems and a related algorithm," SIAM J. Optim., vol. 7, pp. 225-247, 1997.

Digital Library

[18]

18. M. C. Ferris and J.-S. Pang, "Engineering and economic applications of complementarity problems," SIAM Review, vol. 39, pp. 669-713, 1997.

Digital Library

[19]

19. A. Fischer, "A special Newton-type optimization method," Optimization, vol. 24, pp. 269-284, 1992.

[20]

20. A. Fischer, "Solution of monotone complementarity problems with locally Lipschitzian functions," Math. Programming, vol. 76, pp. 513-532, 1997.

Digital Library

[21]

21. S. A. Gabriel and J. J. Moré, "Smoothing of mixed complementarity problems," in Complementarity and Variational Problems: State of the Art, M. C. Ferris and J.-S. Pang (Eds.), SIAM: Philadelphia, PA, pp. 105- 116, 1997.

[22]

22. P. T. Harker and J.-S. Pang, "Finite-dimensional variational inequality and nonlinear complementarity problems: A survey of theory, algorithms and applications," Math. Programming, vol. 48, pp. 161-220, 1990.

Digital Library

[23]

23. K. Hotta and A. Yoshise, "Global convergence of a class of non-interior-point algorithms using Chen-Harker-Kanzow functions for nonlinear complementarity problems," Math. Programming, vol. 86, pp. 105-133, 1999.

[24]

24. H. Jiang, "Smoothed Fischer-Burmeister equation methods for the complementarity problem," Technical Report, Department of Mathematics, The University of Melbourne, Parkville, Victoria, Australia, June 1997.

[25]

25. H. Jiang and L. Qi, "A new nonsmooth equations approach to nonlinear complementarity problems," SIAM J. Control Optim., vol. 35, pp. 178-193, 1997.

Digital Library

[26]

26. C. Kanzow, "Some noninterior continuation methods for linear complementarity problems," SIAM J. Matrix Anal. Appl., vol. 17, pp. 851-868, 1996.

Digital Library

[27]

27. C. Kanzow, "A new approach to continuation methods for complementarity problems with uniform P-functions," Oper. Res. Lett., vol. 20, pp. 85-92, 1997.

Digital Library

[28]

28. C. Kanzow and H. Kleinmichel, "A new class of semismooth Newton-type methods for nonlinear complementarity problems," Comput. Optim. Appl., vol. 11, pp. 227-251, 1998.

Digital Library

[29]

29. C. Kanzow and H. Pieper, "Jacobian smoothing methods for general nonlinear complementarity problems," SIAM J. Optim., vol. 9, pp. 342-372, 1999.

Digital Library

[30]

30. L. Qi, "Convergence analysis of some algorithms for solving nonsmooth equations," Math. Oper. Res., vol. 18, pp. 227-244, 1993.

Digital Library

[31]

31. L. Qi and D. Sun, "Improving the convergence of non-interior point algorithms for nonlinear complementarity problems," Math. Comp., vol. 69, pp. 283-304, 2000.

Digital Library

[32]

32. L. Qi and J. Sun, "A nonsmooth version of Newton's method," Math. Programming, vol. 58, pp. 353-367, 1993.

Digital Library

[33]

33. S. M. Robinson, "Strongly regular generalized equations," Math. Oper. Res., vol. 5, pp. 43-62, 1980.

Digital Library

[34]

34. P. Tseng, "Analysis of a non-interior continuation method based on Chen-Mangasarian smoothing functions for complementarity problems," in Reformulation-Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods, M. Fukushima and L. Qi (Eds.), Kluwer Academic Publisher: Nowell, Maryland, pp. 381-404, 1999.

[35]

35. 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," Technical Report, Department of Mathematics, University of Washington, Seattle, WA, Feb. 1997.

[36]

36. S. Xu and J. V. Burke, "A polynomial time interior-point path-following algorithm for LCP based on Chen-Harker-Kanzow smoothing techniques," Math. Programming, vol. 86, pp. 91-103, 1999.

Cited By

Chen PLin GZhu XBai F(2021)Smoothing Newton method for nonsmooth second-order cone complementarity problems with application to electric power marketsJournal of Global Optimization10.1007/s10898-021-00993-580:3(635-659)Online publication date: 1-Jul-2021
https://dl.acm.org/doi/10.1007/s10898-021-00993-5
Chen PZhang PZhu XLin G(2019)Modified Jacobian smoothing method for nonsmooth complementarity problemsComputational Optimization and Applications10.1007/s10589-019-00136-375:1(207-235)Online publication date: 10-Oct-2019
https://dl.acm.org/doi/10.1007/s10589-019-00136-3
Ling CYin HZhou G(2011)A smoothing Newton-type method for solving the L2 spectral estimation problem with lower and upper boundsComputational Optimization and Applications10.1007/s10589-010-9356-050:2(351-378)Online publication date: 1-Oct-2011
https://dl.acm.org/doi/10.1007/s10589-010-9356-0
Show More Cited By

Index Terms

A Smoothing Newton Method for General Nonlinear Complementarity Problems
1. Mathematics of computing
  1. Mathematical analysis
  2. Probability and statistics
    1. Probabilistic reasoning algorithms
      1. Markov-chain Monte Carlo methods
        Markov-chain Monte Carlo convergence measures
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization

Recommendations

The convergence of a one-step smoothing Newton method for P0-NCP based on a new smoothing NCP-function

The nonlinear complementarity problem (denoted by NCP(F)) can be reformulated as the solution of a nonsmooth system of equations. By introducing a new smoothing NCP-function, the problem is approximated by a family of parameterized smooth equations. A ...
A new smoothing quasi-Newton method for nonlinear complementarity problems

The nonlinear complementarity problem can be reformulated as a nonsmooth equation. In this paper we propose a new smoothing quasi-Newton method for the solution of the nonlinear complementarity problems by constructing a new smoothing approximation ...
Quadratic one-step smoothing Newton method for P0-LCP without strict complementarity

In this paper we propose a modified one-step smoothing Newton method for solving the P"0 linear complementarity problem (P"0-LCP) based on Kanzow's smoothing function. Our smoothing Newton method solves only one linear system of equations and performs ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Computational Optimization and Applications

Computational Optimization and Applications Volume 17, Issue 2-3

December 2000

222 pages

ISSN:0926-6003

Issue’s Table of Contents

Copyright © Copyright © 2000 Kluwer Academic Publishers.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 December 2000

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chen PLin GZhu XBai F(2021)Smoothing Newton method for nonsmooth second-order cone complementarity problems with application to electric power marketsJournal of Global Optimization10.1007/s10898-021-00993-580:3(635-659)Online publication date: 1-Jul-2021
https://dl.acm.org/doi/10.1007/s10898-021-00993-5
Chen PZhang PZhu XLin G(2019)Modified Jacobian smoothing method for nonsmooth complementarity problemsComputational Optimization and Applications10.1007/s10589-019-00136-375:1(207-235)Online publication date: 10-Oct-2019
https://dl.acm.org/doi/10.1007/s10589-019-00136-3
Ling CYin HZhou G(2011)A smoothing Newton-type method for solving the L2 spectral estimation problem with lower and upper boundsComputational Optimization and Applications10.1007/s10589-010-9356-050:2(351-378)Online publication date: 1-Oct-2011
https://dl.acm.org/doi/10.1007/s10589-010-9356-0
Liu STang JMa C(2010)A new modified one-step smoothing Newton method for solving the general mixed complementarity problemApplied Mathematics and Computation10.1016/j.amc.2010.02.006216:4(1140-1149)Online publication date: 1-Apr-2010
https://dl.acm.org/doi/10.1016/j.amc.2010.02.006
Chen JPan S(2008)A regularization semismooth Newton method based on the generalized Fischer-Burmeister function for P0-NCPsJournal of Computational and Applied Mathematics10.1016/j.cam.2007.08.020220:1-2(464-479)Online publication date: 1-Oct-2008
https://dl.acm.org/doi/10.1016/j.cam.2007.08.020
Chen JPan S(2008)A family of NCP functions and a descent method for the nonlinear complementarity problemComputational Optimization and Applications10.1007/s10589-007-9086-040:3(389-404)Online publication date: 1-Jul-2008
https://dl.acm.org/doi/10.1007/s10589-007-9086-0
Majig MHedar AFukushima M(2007)Hybrid evolutionary algorithm for solving general variational inequality problemsJournal of Global Optimization10.1007/s10898-006-9102-438:4(637-651)Online publication date: 1-Aug-2007
https://dl.acm.org/doi/10.1007/s10898-006-9102-4
Huang ZWang H(2006)Smoothing-type algorithm for solving linear programs by using an augmented complementarity problemApplied Mathematics and Computation10.1016/j.amc.2005.11.012177:1(330-345)Online publication date: 1-Jun-2006
https://dl.acm.org/doi/10.1016/j.amc.2005.11.012
Huang ZQi LSun D(2004)Sub-quadratic convergence of a smoothing Newton algorithm for the P0--- and monotone LCPMathematical Programming: Series A and B10.5555/3114182.311442399:3(423-441)Online publication date: 1-Apr-2004
https://dl.acm.org/doi/10.5555/3114182.3114423
Qi LYin H(2003)A Strongly Semismooth Integral Function and Its ApplicationComputational Optimization and Applications10.1023/A:102296950799425:1-3(223-246)Online publication date: 20-Mar-2003
https://dl.acm.org/doi/10.1023/A%3A1022969507994
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents