| Title:
|
A self-adaptive trust region method for the extended linear complementarity problems (English) |
| Author:
|
Yu, Zhensheng |
| Author:
|
Li, Qiang |
| Language:
|
English |
| Journal:
|
Applications of Mathematics |
| ISSN:
|
0862-7940 (print) |
| ISSN:
|
1572-9109 (online) |
| Volume:
|
54 |
| Issue:
|
1 |
| Year:
|
2009 |
| Pages:
|
53-65 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
extended linear complementarity |
| Keyword:
|
self-adaptive trust region method |
| Keyword:
|
global convergence |
| Keyword:
|
local superlinear convergence |
| Keyword:
|
trust region algorithm |
| MSC:
|
65K05 |
| MSC:
|
65K10 |
| MSC:
|
90C30 |
| MSC:
|
90C33 |
| MSC:
|
90C51 |
| idZBL:
|
Zbl 1212.65239 |
| idMR:
|
MR2476021 |
| DOI:
|
10.1007/s10492-009-0004-x |
| . |
| Date available:
|
2010-07-20T12:46:30Z |
| Last updated:
|
2020-07-02 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/140349 |
| . |
| Reference:
|
[1] Andreani, R., Martínez, J. M.: On the solution of the extended linear complementarity problem.Linear Algebra Appl. 281 (1998), 247-257. MR 1645363 |
| Reference:
|
[2] Bonnans, J. F., Gonzaga, C. C.: Convergence of interior point algorithms for the monotone linear complementarity problem.Math. Oper. Res. 21 (1996), 1-25. Zbl 0846.90109, MR 1385864, 10.1287/moor.21.1.1 |
| Reference:
|
[3] Clarke, F. H.: Optimization and Nonsmooth Analysis, 2nd ed. Classic Appl. Math. 5.SIAM Philadephia (1990). MR 1058436 |
| Reference:
|
[4] Conn, A. R., Gould, N. I. M., Toint, P. H.: Trust-Region Methods.SIAM Philadelphia (2000). Zbl 0958.65071, MR 1774899 |
| Reference:
|
[5] Cottle, R. W., Pang, J.-S., Stone, R. E.: The Linear Complementarity Problem.Academic Press Boston (1992). Zbl 0757.90078, MR 1150683 |
| Reference:
|
[6] Dennis, J. E., Schnabel, R. B.: Numerical Methods for Unconstrained Optimization and Nonlinear Equations.Prentice-Hall Englewood Cliffs (1983). Zbl 0579.65058, MR 0702023 |
| Reference:
|
[7] Facchinei, F., Soares, J.: A new merit function for nonlinear complementarity problems and a related algorithm.SIAM J. Optim. 7 (1997), 225-247. Zbl 0873.90096, MR 1430565, 10.1137/S1052623494279110 |
| Reference:
|
[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. MR 3522937 |
| Reference:
|
[9] Fischer, A.: A special Newton-type optimization method.Optimization 24 (1992), 269-284. Zbl 0814.65063, MR 1247636, 10.1080/02331939208843795 |
| Reference:
|
[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. Zbl 0948.90133, MR 1459996 |
| Reference:
|
[11] Gowda, M. S.: Reducing a monotone horizontal LCP to an LCP.Appl. Math. Lett. 8 (1995), 97-100. Zbl 0813.65092, MR 1355159, 10.1016/0893-9659(94)00118-V |
| Reference:
|
[12] Gowda, M. S.: On the extended linear complementarity problem.Math. Program. 72 (1996), 33-50. Zbl 0853.90109, MR 1385162, 10.1007/BF02592330 |
| Reference:
|
[13] G'{u}ler, O.: Generalized linear complementarity problem.Math. Oper. Res. 20 (1995), 441-448. MR 1342954, 10.1287/moor.20.2.441 |
| Reference:
|
[14] Hei, L.: A self-adaptive trust region algorithm.J. Comput. Math. 21 (2003), 229-236. Zbl 1028.65072, MR 1967988 |
| Reference:
|
[15] Jiang, H., Fukushima, M., Qi, L., Sun, D.: A trust region method for solving generalized complementarity problems.SIAM J. Optim. 8 (1998), 140-157. Zbl 0911.90324, MR 1617440, 10.1137/S1052623495296541 |
| Reference:
|
[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. Zbl 0927.65083, MR 1682704 |
| Reference:
|
[17] Kanzow, C.: On a semismooth least squares formulation of complementarity problem with gap reduction.Optim. Method Softw. 19 (2004), 507-525. MR 2095350, 10.1080/10556780410001683096 |
| Reference:
|
[18] Kanzow, C., Pieper, H.: Jacobian smoothing methods for nonlinear complementarity problems.SIAM J. Optim. 9 (1999), 342-373. Zbl 0986.90065, MR 1686823, 10.1137/S1052623497328781 |
| Reference:
|
[19] Mangasarian, O. L., Pang, J. S.: The extended linear complementarity problem.SIAM J. Matrix Anal. Appl. 16 (1995), 359-368. Zbl 0835.90103, MR 1321784, 10.1137/S0895479893262734 |
| Reference:
|
[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. Zbl 0321.90045, MR 0386270 |
| Reference:
|
[21] Qi, H. D., Qi, L., Sun, D. F.: Solving Karush-Kuhn-Tucker systems via the trust region and conjugate gradient methods.SIAM J. Optim. 14 (2003), 439-463. MR 2048162, 10.1137/S105262340038256X |
| Reference:
|
[22] Qi, L.: Convergence analysis of some algorithms for solving nonsmooth equations.Math. Oper. Res. 18 (1993), 227-244. Zbl 0776.65037, MR 1250115, 10.1287/moor.18.1.227 |
| Reference:
|
[23] Qi, L., Sun, J.: A nonsmooth version of Newton's method.Math. Program. 58 (1993), 353-367. Zbl 0780.90090, MR 1216791, 10.1007/BF01581275 |
| Reference:
|
[24] Sartenaer, A.: Automatic determination of an initial trust region in nonlinear programming.SIAM J. Sci. Comput. 18 (1997), 1788-1803. Zbl 0891.90151, MR 1480635, 10.1137/S1064827595286955 |
| Reference:
|
[25] Sznajder, R., Gowda, M. S.: Generalizations of $P_0$ and {\bf P}-properties; extended vertical and horizontal linear complementarity problems.Linear Algebra Appl. 94 (1997), 449-467. |
| Reference:
|
[26] Solodov, M. V.: Some optimization reformulations of the extended linear complementarity problem.Comput. Optim. Appl. 13 (1999), 187-200. Zbl 1040.90550, MR 1704119, 10.1023/A:1008684732567 |
| Reference:
|
[27] Ulbrich, M.: Nonmonotone trust-region methods for bound-constrained semismooth equation with application to nonlinear mixed complementarity problems.SIAM J. Optim. 11 (2001), 889-917. MR 1855213, 10.1137/S1052623499356344 |
| Reference:
|
[28] Xiu, N. H., Zhang, J. Z.: A smoothing Gauss-Newton method for the generalized HLCP.J. Comput. Appl. Math. 129 (2001), 195-208. Zbl 0985.65070, MR 1823218, 10.1016/S0377-0427(00)00550-1 |
| Reference:
|
[29] Zhang, J. Z., Xiu, N. H.: Global $s$-type error bound for the extended linear complementarity problem and its applications.Math. Program. 88 (2000), 391-410. MR 1783980, 10.1007/s101070050023 |
| Reference:
|
[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. Zbl 1105.90361, MR 1911178 |
| Reference:
|
[31] Zhang, J. L., Zhang, X. S.: A smoothing Levenberg-Marquardt method for NCP.Appl. Math. Comput. 178 (2006), 212-228. Zbl 1104.65061, MR 2248482, 10.1016/j.amc.2005.11.036 |
| . |
