A self-adaptive trust region method for the extended linear complementarity problems

Zhensheng Yu; Qiang Li

Applications of Mathematics (2009)

  • Volume: 54, Issue: 1, page 53-65
  • ISSN: 0862-7940

Abstract

top
By using some NCP functions, we reformulate the extended linear complementarity problem as a nonsmooth equation. Then we propose a self-adaptive trust region algorithm for solving this nonsmooth equation. The novelty of this method is that the trust region radius is controlled by the objective function value which can be adjusted automatically according to the algorithm. The global convergence is obtained under mild conditions and the local superlinear convergence rate is also established under strict complementarity conditions.

How to cite

top

Yu, Zhensheng, and Li, Qiang. "A self-adaptive trust region method for the extended linear complementarity problems." Applications of Mathematics 54.1 (2009): 53-65. <http://eudml.org/doc/37807>.

@article{Yu2009,
abstract = {By using some NCP functions, we reformulate the extended linear complementarity problem as a nonsmooth equation. Then we propose a self-adaptive trust region algorithm for solving this nonsmooth equation. The novelty of this method is that the trust region radius is controlled by the objective function value which can be adjusted automatically according to the algorithm. The global convergence is obtained under mild conditions and the local superlinear convergence rate is also established under strict complementarity conditions.},
author = {Yu, Zhensheng, Li, Qiang},
journal = {Applications of Mathematics},
keywords = {extended linear complementarity; self-adaptive trust region method; global convergence; local superlinear convergence; trust region algorithm; extended linear complementarity; global convergence; local superlinear convergence; trust region algorithm},
language = {eng},
number = {1},
pages = {53-65},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {A self-adaptive trust region method for the extended linear complementarity problems},
url = {http://eudml.org/doc/37807},
volume = {54},
year = {2009},
}

TY - JOUR
AU - Yu, Zhensheng
AU - Li, Qiang
TI - A self-adaptive trust region method for the extended linear complementarity problems
JO - Applications of Mathematics
PY - 2009
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 54
IS - 1
SP - 53
EP - 65
AB - By using some NCP functions, we reformulate the extended linear complementarity problem as a nonsmooth equation. Then we propose a self-adaptive trust region algorithm for solving this nonsmooth equation. The novelty of this method is that the trust region radius is controlled by the objective function value which can be adjusted automatically according to the algorithm. The global convergence is obtained under mild conditions and the local superlinear convergence rate is also established under strict complementarity conditions.
LA - eng
KW - extended linear complementarity; self-adaptive trust region method; global convergence; local superlinear convergence; trust region algorithm; extended linear complementarity; global convergence; local superlinear convergence; trust region algorithm
UR - http://eudml.org/doc/37807
ER -

References

top
  1. Andreani, R., Martínez, J. M., On the solution of the extended linear complementarity problem, Linear Algebra Appl. 281 (1998), 247-257. (1998) MR1645363
  2. Bonnans, J. F., Gonzaga, C. C., 10.1287/moor.21.1.1, Math. Oper. Res. 21 (1996), 1-25. (1996) Zbl0846.90109MR1385864DOI10.1287/moor.21.1.1
  3. Clarke, F. H., Optimization and Nonsmooth Analysis, 2nd ed. Classic Appl. Math. 5, SIAM Philadephia (1990). (1990) MR1058436
  4. Conn, A. R., Gould, N. I. M., Toint, P. H., Trust-Region Methods, SIAM Philadelphia (2000). (2000) Zbl0958.65071MR1774899
  5. Cottle, R. W., Pang, J.-S., Stone, R. E., The Linear Complementarity Problem, Academic Press Boston (1992). (1992) Zbl0757.90078MR1150683
  6. Dennis, J. E., Schnabel, R. B., Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Prentice-Hall Englewood Cliffs (1983). (1983) Zbl0579.65058MR0702023
  7. Facchinei, F., Soares, J., 10.1137/S1052623494279110, SIAM J. Optim. 7 (1997), 225-247. (1997) Zbl0873.90096MR1430565DOI10.1137/S1052623494279110
  8. Fan, J. Y., Yuan, Y. X., A new trust region algorithm with trust region radius converging to zero, In: Proceedings of the 5th International Conference on Optimization: Techniques and Applications (Hongkong, December 2001) D. Li Hongkong (2001), 786-794. (2001) MR3522937
  9. Fischer, A., 10.1080/02331939208843795, Optimization 24 (1992), 269-284. (1992) Zbl0814.65063MR1247636DOI10.1080/02331939208843795
  10. Fischer, A., An NCP-function and its use for the solution of complementarity problems, D.-Z. Du, L. Qi, R. Womersley Recent Advances in Nonsmooth Optimization World Scientific Singapore (1995), 88-105. (1995) Zbl0948.90133MR1459996
  11. Gowda, M. S., 10.1016/0893-9659(94)00118-V, Appl. Math. Lett. 8 (1995), 97-100. (1995) Zbl0813.65092MR1355159DOI10.1016/0893-9659(94)00118-V
  12. Gowda, M. S., 10.1007/BF02592330, Math. Program. 72 (1996), 33-50. (1996) Zbl0853.90109MR1385162DOI10.1007/BF02592330
  13. G'{u}ler, O., 10.1287/moor.20.2.441, Math. Oper. Res. 20 (1995), 441-448. (1995) MR1342954DOI10.1287/moor.20.2.441
  14. Hei, L., A self-adaptive trust region algorithm, J. Comput. Math. 21 (2003), 229-236. (2003) Zbl1028.65072MR1967988
  15. Jiang, H., Fukushima, M., Qi, L., Sun, D., 10.1137/S1052623495296541, SIAM J. Optim. 8 (1998), 140-157. (1998) Zbl0911.90324MR1617440DOI10.1137/S1052623495296541
  16. Kanzow, C., Zupke, M., Inexact trust-region methods for nonlinear complementarity problems, M. Fukushima, L. Qi Reformulation: Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods Kluwer Academic Publishers Norwell (1999), 211-233. (1999) Zbl0927.65083MR1682704
  17. Kanzow, C., 10.1080/10556780410001683096, Optim. Method Softw. 19 (2004), 507-525. (2004) MR2095350DOI10.1080/10556780410001683096
  18. Kanzow, C., Pieper, H., 10.1137/S1052623497328781, SIAM J. Optim. 9 (1999), 342-373. (1999) Zbl0986.90065MR1686823DOI10.1137/S1052623497328781
  19. Mangasarian, O. L., Pang, J. S., 10.1137/S0895479893262734, SIAM J. Matrix Anal. Appl. 16 (1995), 359-368. (1995) Zbl0835.90103MR1321784DOI10.1137/S0895479893262734
  20. Powell, M. J. D., Convergence properties of a class of minimization algorithms, In: Nonlinear Programming O. L. Mangasarian, R. R. Meyer, S. M. Robinson Academic Press New York (1975), 1-27. (1975) Zbl0321.90045MR0386270
  21. Qi, H. D., Qi, L., Sun, D. F., 10.1137/S105262340038256X, SIAM J. Optim. 14 (2003), 439-463. (2003) MR2048162DOI10.1137/S105262340038256X
  22. Qi, L., 10.1287/moor.18.1.227, Math. Oper. Res. 18 (1993), 227-244. (1993) Zbl0776.65037MR1250115DOI10.1287/moor.18.1.227
  23. Qi, L., Sun, J., 10.1007/BF01581275, Math. Program. 58 (1993), 353-367. (1993) Zbl0780.90090MR1216791DOI10.1007/BF01581275
  24. Sartenaer, A., 10.1137/S1064827595286955, SIAM J. Sci. Comput. 18 (1997), 1788-1803. (1997) Zbl0891.90151MR1480635DOI10.1137/S1064827595286955
  25. Sznajder, R., Gowda, M. S., Generalizations of P 0 and P-properties; extended vertical and horizontal linear complementarity problems, Linear Algebra Appl. 94 (1997), 449-467. (1997) 
  26. Solodov, M. V., 10.1023/A:1008684732567, Comput. Optim. Appl. 13 (1999), 187-200. (1999) Zbl1040.90550MR1704119DOI10.1023/A:1008684732567
  27. Ulbrich, M., 10.1137/S1052623499356344, SIAM J. Optim. 11 (2001), 889-917. (2001) MR1855213DOI10.1137/S1052623499356344
  28. Xiu, N. H., Zhang, J. Z., 10.1016/S0377-0427(00)00550-1, J. Comput. Appl. Math. 129 (2001), 195-208. (2001) Zbl0985.65070MR1823218DOI10.1016/S0377-0427(00)00550-1
  29. Zhang, J. Z., Xiu, N. H., 10.1007/s101070050023, Math. Program. 88 (2000), 391-410. (2000) MR1783980DOI10.1007/s101070050023
  30. Zhang, X. S., Zhang, J. L., Liao, L. Z., An adaptive trust region method and its convergence, Sci. China, Ser. A 45 (2002), 620-631. (2002) Zbl1105.90361MR1911178
  31. Zhang, J. L., Zhang, X. S., 10.1016/j.amc.2005.11.036, Appl. Math. Comput. 178 (2006), 212-228. (2006) Zbl1104.65061MR2248482DOI10.1016/j.amc.2005.11.036

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.