Abstract
A separable cubic model, for smooth unconstrained minimization, is proposed and evaluated. The cubic model uses some novel secant-type choices for the parameters in the cubic terms. A suitable hard-case-free trust-region strategy that takes advantage of the separable cubic modeling is also presented. For the convergence analysis of our specialized trust region strategy we present as a general framework a model \(q\)-order trust region algorithm with variable metric and we prove its convergence to \(q\)-stationary points. Some preliminary numerical examples are also presented to illustrate the tendency of the specialized trust region algorithm, when combined with our cubic modeling, to escape from local minimizers.
![](http://media.springernature.com/m312/springer-static/image/art%3A10.1007%2Fs10898-015-0278-3/MediaObjects/10898_2015_278_Fig1_HTML.gif)
![](http://media.springernature.com/m312/springer-static/image/art%3A10.1007%2Fs10898-015-0278-3/MediaObjects/10898_2015_278_Fig2_HTML.gif)
![](http://media.springernature.com/m312/springer-static/image/art%3A10.1007%2Fs10898-015-0278-3/MediaObjects/10898_2015_278_Fig3_HTML.gif)
![](http://media.springernature.com/m312/springer-static/image/art%3A10.1007%2Fs10898-015-0278-3/MediaObjects/10898_2015_278_Fig4_HTML.gif)
Similar content being viewed by others
References
Benson, H.Y., Shanno, D.F.: Interior-point methods for nonconvex nonlinear programming: cubic regularization. Comput. Optim. Appl. 58, 323–346 (2014)
Bianconcini, T., Liuzzi, G., Morini, B., Sciandrone, M.: On the use of iterative methods in cubic regularization for unconstrained optimization. Comput. Optim. Appl. 60, 35–57 (2015)
Birgin, E.G., Martínez, J.M., Raydan, M.: Nonmonotone spectral projected gradient methods on convex sets. SIAM J. Optim. 10, 1196–1211 (2000)
Birgin, E.G., Martínez, J.M., Raydan, M.: Spectral projected gradient methods. In: Floudas, C.A., Pardalos, P.M. (eds.) Encyclopedia of Optimization, vol. Chapter 19, 2nd edn, pp. 3652–3659. Springer, Berlin (2009)
Birgin, E.G., Martínez, J.M., Raydan, M.: Spectral Projected Gradient methods: Review and Perspectives. J. Stat. Softw. 60(3) (2014)
Cartis, C., Gould, N.I.M., Toint, PhL: Adaptive cubic regularisation methods for unconstrained optimization. Part I: motivation, convergence and numerical results. Math. Program. Ser. A 127, 245–295 (2011)
Cartis, C., Gould, N.I.M., Toint, PhL: Adaptive cubic regularisation methods for unconstrained optimization. Part II: worst-case function- and derivative-evaluation complexity. Math. Program. Ser. A 130, 295–319 (2011)
Cartis, C., Gould, N.I.M., Toint, PhL: On the evaluation complexity of cubic regularization methods for potentially rank-deficient nonlinear least-squares problems and its relevance to constrained nonlinear optimization. SIAM J. Opt. 23, 1553–1574 (2013)
Corradi, G.: A trust region algorithm for unconstrained optimization. Int. J. Comput. Math. 65, 109–119 (1997)
Conn, A.R., Gould, N.I.M., Toint, PhL: Trust-Region Methods. SIAM, Philadelphia (2000)
Dennis Jr, J.E., Schnabel, R.B.: Numerical Methods for Unconstrained Optimization and Nonlinear Equations. SIAM, Philadelphia (1996). Revised edition
Fletcher, R.: Practical Methods of Optimization, 2nd edn. Wiley, New York (1987)
Gay, D.M.: Computing optimal locally constrained steps. SIAM J. Sci. Stat. Comput. 2, 186–197 (1981)
Griewank, A.: The modification of Newtons method for unconstrained optimization by bounding cubic terms, Technical Report NA/12. Department of Applied Mathematics and Theoretical Physics, University of Cambridge (1981)
Gould, N.I.M., Porcelli, M., Toint, PhL: Updating the regularization parameter in the adaptive cubic regularization algorithm. Comput. Optim. Appl. 53, 1–22 (2012)
Hanson, R.J., Krogh, F.T.: A quadratic-tensor model algorithm for nonlinear least-squares problems with linear constraints. ACM Trans. Math. Softw. 18, 115–133 (1992)
Karas, E.W., Santos, S.A., Svaiter, B.F.: Algebraic rules for quadratic regularization of Newton’s method. Comput. Optim. Appl. (2014). doi:10.1007/s10589-014-9671-y
Kelley, C.T.: Iterative Methods for Optimization. SIAM, Philadelphia (1999)
Lu, S., Wei, Z., Li, L.: A trust region algorithm with adaptive cubic regularization methods for nonsmooth convex minimization. Comput. Optim. Appl. 51, 551–573 (2012)
Martínez, J.M., Santos, S.A.: Métodos Computacionais de Otimização. Editorial IMPA, Rio de Janeiro, Brazil (1995)
Martínez, L., Andrade, R., Birgin, E.G., Martínez, J.M.: Packmol: a package for building initial configurations for molecular dynamics simulations. J. Comput. Chem. 30, 2157–2164 (2009)
Moré, J.J., Sorensen, D.C.: Computing a trust region step. SIAM J. Sci. Stat. Comput. 4, 553–572 (1983)
Nesterov, Y., Polyak, B.T.: Cubic regularization of Newton’s method and its global performance. Math. Program. 108(1), 177–205 (2006)
Nesterov, Y.: Accelerating the cubic regularization of Newton’s method on convex problems. Math. Program. Ser. B 112, 159–181 (2008)
Nocedal, J., Wright, S.J.: Numerical Optimization, 2nd edn. Springer, New York (2006)
Schnabel, R.B., Chow, T.-T.: Tensor methods for unconstrained optimization using second derivatives. SIAM J. Opt. 1, 293–315 (1991)
Schnabel, R.B., Frank, P.: Tensor methods for nonlinear equations. SIAM J. Numer. Anal. 21, 815–843 (1984)
Wang, Z.-H., Yuan, Y.-X.: A subspace implementation of quasi-Newton trust region methods for unconstrained optimization. Numer. Math. 104, 241–269 (2006)
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was supported by PRONEX-CNPq/FAPERJ (E-26/111.449/2010-APQ1), CEPID–Industrial Mathematics/FAPESP (Grant 2011/51305-02), FAPESP (Projects 2013/05475-7 and 2013/07375-0), and CNPq (Project 400926/2013-0).
Rights and permissions
About this article
Cite this article
Martínez, J.M., Raydan, M. Separable cubic modeling and a trust-region strategy for unconstrained minimization with impact in global optimization. J Glob Optim 63, 319–342 (2015). https://doi.org/10.1007/s10898-015-0278-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-015-0278-3