Nonmonotone conic trust region method with line search technique for bound constrained optimization
RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 3, pp. 787-805.

In this paper, we propose a nonmonotone trust region method for bound constrained optimization problems, where the bounds are dealt with by affine scaling technique. Differing from the traditional trust region methods, the subproblem in our algorithm is based on a conic model. Moreover, when the trial point isn’t acceptable by the usual trust region criterion, a line search technique is used to find an acceptable point. This procedure avoids resolving the trust region subproblem, which may reduce the total computational cost. The global convergence and Q-superlinear convergence of the algorithm are established under some mild conditions. Numerical results on a series of standard test problems are reported to show the effectiveness of the new method.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2017054
Classification : 65K05, 90C30
Mots-clés : Nonmonotone technique, conic model, line search, trust region, bound constrained optimization
Zhao, Lijuan 1

1
@article{RO_2019__53_3_787_0,
     author = {Zhao, Lijuan},
     title = {Nonmonotone conic trust region method with line search technique for bound constrained optimization},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {787--805},
     publisher = {EDP-Sciences},
     volume = {53},
     number = {3},
     year = {2019},
     doi = {10.1051/ro/2017054},
     mrnumber = {3973144},
     zbl = {1461.65192},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2017054/}
}
TY  - JOUR
AU  - Zhao, Lijuan
TI  - Nonmonotone conic trust region method with line search technique for bound constrained optimization
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2019
SP  - 787
EP  - 805
VL  - 53
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2017054/
DO  - 10.1051/ro/2017054
LA  - en
ID  - RO_2019__53_3_787_0
ER  - 
%0 Journal Article
%A Zhao, Lijuan
%T Nonmonotone conic trust region method with line search technique for bound constrained optimization
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2019
%P 787-805
%V 53
%N 3
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2017054/
%R 10.1051/ro/2017054
%G en
%F RO_2019__53_3_787_0
Zhao, Lijuan. Nonmonotone conic trust region method with line search technique for bound constrained optimization. RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 3, pp. 787-805. doi : 10.1051/ro/2017054. http://www.numdam.org/articles/10.1051/ro/2017054/

S. Bellavia, M. Macconi and S. Pieraccini, Constrained dogleg methods for nonlinear systems with simple bounds. Comput. Optimiz. Appl. 53 (2012) 771–794. | DOI | MR | Zbl

S. Bellavia, M. Macconi and B. Morini, An affine scaling trust-region approach to bound-constrained nonlinear systems. Appl. Numer. Math. 44 (2003) 257–280. | DOI | MR | Zbl

S. Bellavia and S. Pieraccini, On affine scaling inexact dogleg methods for bound constrained nonlinear systems. Optimiz. Methods Software 30 (2015) 276–300. | DOI | MR | Zbl

T.F. Coleman and Y.Y. Li, An interior trust-region approach for minimization subject to bounds. SIAM J. Optimiz. 6 (1996) 418–445. | DOI | MR | Zbl

A.R. Conn, N.I.M. Gould and Phl Toint, Testing a class of methods for solving minimization problems with simple bounds on the variables. Math. Comput. 50 (1988) 399–430. | DOI | MR | Zbl

Z.C. Cui, B.Y. Wu and S.J. Qu, Combining nonmonotone conic trust region and line search techniques for unconstrained optimization. J. Comput. Appl. Math. 235 (2011) 2432–2441. | DOI | MR | Zbl

W.C. Davidon, Conic approximations and collinear scalings for optimizers. SIAM J. Numer. Anal. 17 (1980) 268–281. | DOI | MR | Zbl

S. Di and W.Y. Sun, A trust region method for conic model to solve unconstrained optimizations. Optimiz. Methods and Software 6 (1996) 237–263. | DOI

J.H. Fu and W.Y. Sun, Nonmonotone adaptive trust-region method for unconstrained optimization problems. Appl. Math. Comput. 163 (2005) 489–504. | MR | Zbl

E.D. Dolan and J.J. Moré, Benchmarking optimization software performance profiles. Math. Program. 91 (2002) 201–213. | DOI | MR | Zbl

L. Grippo, F. Lampariello and S. Lucidi, A nonmonotone line search technique for Newton’s method. SIAM J. Numer. Anal. 23 (1986) 707–716. | DOI | MR | Zbl

N.Z. Gu and J.T. Mo, Incorporating nonmonotone strategies into the trust region method for unconstrained optimization. Comput. Math. Appl. 55 (2008) 2158–2172. | DOI | MR | Zbl

M. Heinkenschloss, M. Ulbrich and S. Ulbrich, Superlinear and quadratic convergence of affine scaling interior point Newton methods for problems with simple bounds without strict complementarity assumption. Math. Program. 86 (1999) 615–635. | DOI | MR | Zbl

W. Hock and K. Schittkowski, Test examples for nonlinear programming codes, Springer (1981). | DOI | MR

W.W. Hager, B.A. Mair and H.C. Zhang, An affine scaling interior point CBB method for box constrained optimization. Math. Program. 119 (2009) 1–32. | DOI | MR | Zbl

W.W. Hager and H.C. Zhang, An affine scaling method for optimization with polyhedral constraints. Comput. Optimiz. Appl. 59 (2014) 163–183. | DOI | MR | Zbl

Y. Ji, Y.J. Li, K.C. Zhang and X.L. Zhang, A new nonmonotone trust region method of conic model for solving unconstrained optimization. J. Comput. Appl. Math. 233 (2010) 1746–1754. | DOI | MR | Zbl

C. Kanzow and A. Klug, On affine scaling interior point Newton methods for nonlinear minimization with bound constraints. Comput. Optimiz. Appl. 35 (2006) 177–197. | DOI | MR | Zbl

J. Nocedal and S.J. Wright, Numerical Optimization. Springer, New York (1999). | DOI | MR | Zbl

J. Nocedal and Y. Yuan, Combining trust region and line search techniques, edited by Y. Yuan. Advances in Nonlinear Programming, Kluwer Academic Publishers, Dordrecht (1996) 153–175. | MR | Zbl

Q. Ni, Optimality conditions for trust region subproblems involving a conic model. SIAM J. Optimiz. 15 (2005) 826–837. | DOI | MR | Zbl

S.J. Qu and S.D. Jiang, A trust region method with a conic model for unconstrained optimization. Math. Methods Appl. Sci. 31 (2008) 1780–1808. | DOI | MR | Zbl

W.Y. Sun and Y.X. Yuan, Optimization Theory and Methods: Nonlinear Programming, Vol 1 of Springer Optimization and its Applications, Springer, New York (2006). | Zbl

W.Y. Sun, Nonmonotone trust region method for solving optimization problems. Appl. Math. Comput. 156 (2004) 159–174. | MR | Zbl

D.C. Sorensen, The Q-superlinear convergence of a collinear scaling algorithm for unconstrained optimization. SIAM J. Numer. Anal. 17 (1980) 84–114. | DOI | MR | Zbl

M. Salahi, Exact two steps SOCP/SDP formulation for a modified conic trust region subproblem. Optimiz. Lett. 11 (2017) 1691–1697. | DOI | MR | Zbl

M. Salahi, An iterative algorithm for the conic trust region subproblem. Inter. J. Appl. Comput. Math. 3 (2017) 2553–2558. | DOI | MR | Zbl

Phl Toint, A nonmonotone trust region algorithm for nonlinear optimization subject to convex constraints. Math. Program. 77 (1997) 69–94. | DOI | MR | Zbl

X. Wang, A trust-region affine scaling method for bound constrained optimization. Acta Math. Sci. 29 (2013) 159–182. | MR | Zbl

Z.S. Yu, Solving bound constrained optimization via a new nonmonotone spectral projected gradient method. Appl. Numer. Math. 58 (2008) 1340–1348. | DOI | MR | Zbl

H. Zhang and W. Hager, A nonmonotone line search technique and its application to unconstrained optimization. SIAM J. Optimiz. 14 (2004) 1043–1056. | DOI | MR | Zbl

L.J. Zhao and W.Y. Sun, A conic affine scaling dogleg method for nonlinear optimization with bound constraints. Asia-Pacific J. Operat. Res. 30 (2013) 1–30. | MR | Zbl

D.T. Zhu, Affine scaling inexact generalized Newton algorithm with interior backtracking technique for solving bound-constrained semismooth equations. J. Comput. Appl. Math. 187 (2006) 227–252. | DOI | MR | Zbl

D.T. Zhu, An affine scaling trust-region algorithm with interior backtracking technique for solving bound-constrained nonlinear systems. J. Comput. Appl. Math. 184 (2005) 343–361. | DOI | MR | Zbl

D.T. Zhu, An interior affine scaling projective algorithm for nonlinear equality and linear inequality constrained optimization. J. Comput. Appl. Math. 173 (2005) 115–148. | DOI | MR | Zbl

D.T. Zhu, Affine scaling interior Levenberg-Marquardt method for bound-constrained semismooth equations under local error bound conditions. J. Comput. Appl. Math. 219 (2008) 198–215. | DOI | MR | Zbl

Cité par Sources :