×

On global minimizers of quadratic functions with cubic regularization. (English) Zbl 1434.90150

Summary: In this paper, we analyze some theoretical properties of the problem of minimizing a quadratic function with a cubic regularization term, arising in many methods for unconstrained and constrained optimization that have been proposed in the last years. First we show that, given any stationary point that is not a global solution, it is possible to compute, in closed form, a new point with a smaller objective function value. Then, we prove that a global minimizer can be obtained by computing a finite number of stationary points. Finally, we extend these results to the case where stationary conditions are approximately satisfied, discussing some possible algorithmic applications.

MSC:

90C26 Nonconvex programming, global optimization
90C20 Quadratic programming

Software:

CUTEst
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bellavia, S., Morini, B.: Strong local convergence properties of adaptive regularized methods for nonlinear least squares. IMA J. Numer. Anal. 35(2), 947-968 (2014) · Zbl 1316.65061 · doi:10.1093/imanum/dru021
[2] Benson, H.Y., Shanno, D.F.: Interior-point methods for nonconvex nonlinear programming: cubic regularization. Comput. Optim. Appl. 58(2), 323-346 (2014) · Zbl 1305.90333 · doi:10.1007/s10589-013-9626-8
[3] Bianconcini, T., Sciandrone, M.: A cubic regularization algorithm for unconstrained optimization using line search and nonmonotone techniques. Optim. Methods Softw. 31(5), 1008-1035 (2016) · Zbl 1351.49040 · doi:10.1080/10556788.2016.1155213
[4] Bianconcini, T., Liuzzi, G., Morini, B., Sciandrone, M.: On the use of iterative methods in cubic regularization for unconstrained optimization. Comput. Optim. Appl. 60(1), 35-57 (2015) · Zbl 1308.90166 · doi:10.1007/s10589-014-9672-x
[5] Birgin, E.G., Gardenghi, J.L., Martínez, J.M., Santos, S.A., Toint, P.L.: Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models. Math. Program. 163(1-2), 359-368 (2017) · Zbl 1365.90236 · doi:10.1007/s10107-016-1065-8
[6] Cartis, C., Gould, N.I.M., Toint, P.L.: Adaptive cubic regularisation methods for unconstrained optimization. Part I: motivation, convergence and numerical results. Math. Program. 127(2), 245-295 (2011) · Zbl 1229.90192 · doi:10.1007/s10107-009-0286-5
[7] Cartis, C., Gould, N.I.M., Toint, P.L.: Adaptive cubic regularisation methods for unconstrained optimization. Part II: worst-case function-and derivative-evaluation complexity. Math. Program. 130(2), 295-319 (2011) · Zbl 1229.90193 · doi:10.1007/s10107-009-0337-y
[8] Cartis, C., Gould, N.I.M., Toint, P.L.: An adaptive cubic regularization algorithm for nonconvex optimization with convex constraints and its function-evaluation complexity. IMA J. Numer. Anal. 32(4), 1662-1695 (2012) · Zbl 1267.65061 · doi:10.1093/imanum/drr035
[9] Conn, A.R., Gould, N.I.M., Toint, P.L.: Trust Region Methods. SIAM, Philadelphia (2000) · Zbl 0958.65071 · doi:10.1137/1.9780898719857
[10] Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91(2), 201-213 (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263
[11] Dussault, J.P.: Simple unified convergence proofs for the trust-region and a new ARC variant. Tech. rep., University of Sherbrooke, Sherbrooke, Canada (2015)
[12] Gould, N.I.M., Porcelli, M., Toint, P.L.: Updating the regularization parameter in the adaptive cubic regularization algorithm. Comput. Optim. Appl. 53(1), 1-22 (2012) · Zbl 1259.90134 · doi:10.1007/s10589-011-9446-7
[13] Gould, N.I.M., Orban, D., Toint, P.L.: CUTEst: a constrained and unconstrained testing environment with safe threads for mathematical optimization. Comput. Optim. Appl. 60(3), 545-557 (2015) · Zbl 1325.90004 · doi:10.1007/s10589-014-9687-3
[14] Griewank, A.: The modification of Newtons method for unconstrained optimization by bounding cubic terms. Tech. Rep. NA/12 (1981)
[15] Lucidi, S., Palagi, L., Roma, M.: On some properties of quadratic programs with a convex quadratic constraint. SIAM J. Optim. 8(1), 105-122 (1998) · Zbl 0910.90227 · doi:10.1137/S1052623494278049
[16] Nesterov, Y.: Cubic regularization of Newton’s method for convex problems with constraints. Tech. Rep. 39, CORE (2006)
[17] Nesterov, Y.: Accelerating the cubic regularization of Newtons method on convex problems. Math. Program. 112(1), 159-181 (2008) · Zbl 1167.90013 · doi:10.1007/s10107-006-0089-x
[18] Nesterov, Y., Polyak, B.T.: Cubic regularization of Newton method and its global performance. Math. Program. 108(1), 177-205 (2006) · Zbl 1142.90500 · doi:10.1007/s10107-006-0706-8
[19] Weiser, M., Deuflhard, P., Erdmann, B.: Affine conjugate adaptive Newton methods for nonlinear elastomechanics. Optim. Methods Softw. 22(3), 413-431 (2007) · Zbl 1128.74007 · doi:10.1080/10556780600605129
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.