Article
MSC:
65K05,
65K10,
90C30,
90C33,
90C51 | MR 2476021 | Zbl 1212.65239 | DOI: 10.1007/s10492-009-0004-x
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
extended linear complementarity; self-adaptive trust region method; global convergence; local superlinear convergence; trust region algorithm
extended linear complementarity; self-adaptive trust region method; global convergence; local superlinear convergence; trust region algorithm
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.
References:
[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
[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. DOI 10.1287/moor.21.1.1 | MR 1385864 | Zbl 0846.90109
[3] Clarke, F. H.: Optimization and Nonsmooth Analysis, 2nd ed. Classic Appl. Math. 5. SIAM Philadephia (1990). MR 1058436
[4] Conn, A. R., Gould, N. I. M., Toint, P. H.: Trust-Region Methods. SIAM Philadelphia (2000). MR 1774899 | Zbl 0958.65071
[5] Cottle, R. W., Pang, J.-S., Stone, R. E.: The Linear Complementarity Problem. Academic Press Boston (1992). MR 1150683 | Zbl 0757.90078
[6] Dennis, J. E., Schnabel, R. B.: Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Prentice-Hall Englewood Cliffs (1983). MR 0702023 | Zbl 0579.65058
[7] Facchinei, F., Soares, J.: A new merit function for nonlinear complementarity problems and a related algorithm. SIAM J. Optim. 7 (1997), 225-247. DOI 10.1137/S1052623494279110 | MR 1430565 | Zbl 0873.90096
[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
[9] Fischer, A.: A special Newton-type optimization method. Optimization 24 (1992), 269-284. DOI 10.1080/02331939208843795 | MR 1247636 | Zbl 0814.65063
[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. MR 1459996 | Zbl 0948.90133
[11] Gowda, M. S.: Reducing a monotone horizontal LCP to an LCP. Appl. Math. Lett. 8 (1995), 97-100. DOI 10.1016/0893-9659(94)00118-V | MR 1355159 | Zbl 0813.65092
[12] Gowda, M. S.: On the extended linear complementarity problem. Math. Program. 72 (1996), 33-50. DOI 10.1007/BF02592330 | MR 1385162 | Zbl 0853.90109
[13] G'{u}ler, O.: Generalized linear complementarity problem. Math. Oper. Res. 20 (1995), 441-448. DOI 10.1287/moor.20.2.441 | MR 1342954
[14] Hei, L.: A self-adaptive trust region algorithm. J. Comput. Math. 21 (2003), 229-236. MR 1967988 | Zbl 1028.65072
[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. DOI 10.1137/S1052623495296541 | MR 1617440 | Zbl 0911.90324
[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. MR 1682704 | Zbl 0927.65083
[17] Kanzow, C.: On a semismooth least squares formulation of complementarity problem with gap reduction. Optim. Method Softw. 19 (2004), 507-525. DOI 10.1080/10556780410001683096 | MR 2095350
[18] Kanzow, C., Pieper, H.: Jacobian smoothing methods for nonlinear complementarity problems. SIAM J. Optim. 9 (1999), 342-373. DOI 10.1137/S1052623497328781 | MR 1686823 | Zbl 0986.90065
[19] Mangasarian, O. L., Pang, J. S.: The extended linear complementarity problem. SIAM J. Matrix Anal. Appl. 16 (1995), 359-368. DOI 10.1137/S0895479893262734 | MR 1321784 | Zbl 0835.90103
[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. MR 0386270 | Zbl 0321.90045
[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. DOI 10.1137/S105262340038256X | MR 2048162
[22] Qi, L.: Convergence analysis of some algorithms for solving nonsmooth equations. Math. Oper. Res. 18 (1993), 227-244. DOI 10.1287/moor.18.1.227 | MR 1250115 | Zbl 0776.65037
[23] Qi, L., Sun, J.: A nonsmooth version of Newton's method. Math. Program. 58 (1993), 353-367. DOI 10.1007/BF01581275 | MR 1216791 | Zbl 0780.90090
[24] Sartenaer, A.: Automatic determination of an initial trust region in nonlinear programming. SIAM J. Sci. Comput. 18 (1997), 1788-1803. DOI 10.1137/S1064827595286955 | MR 1480635 | Zbl 0891.90151
[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.
[26] Solodov, M. V.: Some optimization reformulations of the extended linear complementarity problem. Comput. Optim. Appl. 13 (1999), 187-200. DOI 10.1023/A:1008684732567 | MR 1704119 | Zbl 1040.90550
[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. DOI 10.1137/S1052623499356344 | MR 1855213
[28] Xiu, N. H., Zhang, J. Z.: A smoothing Gauss-Newton method for the generalized HLCP. J. Comput. Appl. Math. 129 (2001), 195-208. DOI 10.1016/S0377-0427(00)00550-1 | MR 1823218 | Zbl 0985.65070
[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. DOI 10.1007/s101070050023 | MR 1783980
[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. MR 1911178 | Zbl 1105.90361
[31] Zhang, J. L., Zhang, X. S.: A smoothing Levenberg-Marquardt method for NCP. Appl. Math. Comput. 178 (2006), 212-228. DOI 10.1016/j.amc.2005.11.036 | MR 2248482 | Zbl 1104.65061
Search
Partner of
