×

zbMATH — the first resource for mathematics

A self-adaptive trust region method for the extended linear complementarity problems. (English) Zbl 1212.65239
Summary: By using some nonlinear complementarity 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.

MSC:
65K05 Numerical mathematical programming methods
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
90C51 Interior-point methods
PDF BibTeX XML Cite
Full Text: DOI EuDML
References:
[1] R. Andreani, J. M. Martínez: On the solution of the extended linear complementarity problem. Linear Algebra Appl. 281 (1998), 247–257. · Zbl 0932.90044
[2] J. F. Bonnans, C. C. Gonzaga: Convergence of interior point algorithms for the monotone linear complementarity problem. Math. Oper. Res. 21 (1996), 1–25. · Zbl 0846.90109
[3] F. H. Clarke: Optimization and Nonsmooth Analysis, 2nd ed. Classic Appl. Math. 5. SIAM, Philadephia, 1990. · Zbl 0696.49002
[4] A. R. Conn, N. I. M. Gould, P. H. Toint: Trust-Region Methods. SIAM, Philadelphia, 2000.
[5] R. W. Cottle, J.-S. Pang, R. E. Stone: The Linear Complementarity Problem. Academic Press, Boston, 1992.
[6] J. E. Dennis, R. B. Schnabel: Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Prentice-Hall, Englewood Cliffs, 1983.
[7] F. Facchinei, J. Soares: A new merit function for nonlinear complementarity problems and a related algorithm. SIAM J. Optim. 7 (1997), 225–247. · Zbl 0873.90096
[8] J. Y. Fan, Y. X. Yuan: 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, ed.). Hongkong, 2001, pp. 786–794.
[9] A. Fischer: A special Newton-type optimization method. Optimization 24 (1992), 269–284. · Zbl 0814.65063
[10] A. Fischer: An NCP-function and its use for the solution of complementarity problems. Recent Advances in Nonsmooth Optimization (D.-Z. Du, L. Qi, R. Womersley, eds.). World Scientific, Singapore, 1995, pp. 88–105. · Zbl 0948.90133
[11] M. S. Gowda: Reducing a monotone horizontal LCP to an LCP. Appl. Math. Lett. 8 (1995), 97–100. · Zbl 0813.65092
[12] M. S. Gowda: On the extended linear complementarity problem. Math. Program. 72 (1996), 33–50. · Zbl 0853.90109
[13] O. Gúler: Generalized linear complementarity problem. Math. Oper. Res. 20 (1995), 441–448. · Zbl 0837.90113
[14] L. Hei: A self-adaptive trust region algorithm. J. Comput. Math. 21 (2003), 229–236. · Zbl 1028.65072
[15] H. Jiang, M. Fukushima, L. Qi, D. Sun: A trust region method for solving generalized complementarity problems. SIAM J. Optim. 8 (1998), 140–157. · Zbl 0911.90324
[16] C. Kanzow, M. Zupke: Inexact trust-region methods for nonlinear complementarity problems. Reformulation: Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods (M. Fukushima, L. Qi, eds.). Kluwer Academic Publishers, Norwell, 1999, pp. 211–233. · Zbl 0927.65083
[17] C. Kanzow: On a semismooth least squares formulation of complementarity problem with gap reduction. Optim. Method Softw. 19 (2004), 507–525. · Zbl 1097.90062
[18] C. Kanzow, H. Pieper: Jacobian smoothing methods for nonlinear complementarity problems. SIAM J. Optim. 9 (1999), 342–373. · Zbl 0986.90065
[19] O. L. Mangasarian, J. S. Pang: The extended linear complementarity problem. SIAM J. Matrix Anal. Appl. 16 (1995), 359–368. · Zbl 0835.90103
[20] M. J. D. Powell: Convergence properties of a class of minimization algorithms. In: Nonlinear Programming (O. L. Mangasarian, R. R. Meyer, S. M. Robinson, eds.). Academic Press, New York, 1975, pp. 1–27.
[21] H. D. Qi, L. Qi, D. F. Sun: Solving Karush-Kuhn-Tucker systems via the trust region and conjugate gradient methods. SIAM J. Optim. 14 (2003), 439–463. · Zbl 1052.65060
[22] L. Qi: Convergence analysis of some algorithms for solving nonsmooth equations. Math. Oper. Res. 18 (1993), 227–244. · Zbl 0776.65037
[23] L. Qi, J. Sun: A nonsmooth version of Newton’s method. Math. Program. 58 (1993), 353–367. · Zbl 0780.90090
[24] A. Sartenaer: Automatic determination of an initial trust region in nonlinear programming. SIAM J. Sci. Comput. 18 (1997), 1788–1803. · Zbl 0891.90151
[25] R. Sznajder, M. S. Gowda: Generalizations of P 0 and P-properties; extended vertical and horizontal linear complementarity problems. Linear Algebra Appl. 94 (1997), 449–467.
[26] M. V. Solodov: Some optimization reformulations of the extended linear complementarity problem. Comput. Optim. Appl. 13 (1999), 187–200. · Zbl 1040.90550
[27] M. Ulbrich: Nonmonotone trust-region methods for bound-constrained semismooth equation with application to nonlinear mixed complementarity problems. SIAM J. Optim. 11 (2001), 889–917. · Zbl 1010.90085
[28] N. H. Xiu, J. Z. Zhang: A smoothing Gauss-Newton method for the generalized HLCP. J. Comput. Appl. Math. 129 (2001), 195–208. · Zbl 0985.65070
[29] J. Z. Zhang, N. H. Xiu: Global s-type error bound for the extended linear complementarity problem and its applications. Math. Program. 88 (2000), 391–410. · Zbl 1101.90397
[30] X. S. Zhang, J. L. Zhang, L. Z. Liao: An adaptive trust region method and its convergence. Sci. China, Ser. A 45 (2002), 620–631. · Zbl 1105.90361
[31] J. L. Zhang, X. S. Zhang: A smoothing Levenberg-Marquardt method for NCP. Appl. Math. Comput. 178 (2006), 212–228. · Zbl 1104.65061
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.