×

Large-scale unconstrained optimization using separable cubic modeling and matrix-free subspace minimization. (English) Zbl 1432.90119

Summary: We present a new algorithm for solving large-scale unconstrained optimization problems that uses cubic models, matrix-free subspace minimization, and secant-type parameters for defining the cubic terms. We also propose and analyze a specialized trust-region strategy to minimize the cubic model on a properly chosen low-dimensional subspace, which is built at each iteration using the Lanczos process. For the convergence analysis we present, as a general framework, a model trust-region subspace algorithm with variable metric and we establish asymptotic as well as complexity convergence results. Preliminary numerical results, on some test functions and also on the well-known disk packing problem, are presented to illustrate the performance of the proposed scheme when solving large-scale problems.

MSC:

90C26 Nonconvex programming, global optimization
65K10 Numerical optimization and variational techniques
90C06 Large-scale problems in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Bergou, E.; Diouane, Y.; Gratton, S., On the use of the energy norm in trust-region and adaptive cubic regularization subproblems, Comput. Optim. Appl., 68, 533-554 (2017) · Zbl 1390.90511
[2] Bergou, E.; Diouane, Y.; Gratton, S., A line-search algorithm inspired by the adaptive cubic regularization framework and Complexity Analysis, J. Optim. Theory Appl., 178, 885-913 (2018) · Zbl 1417.90097
[3] Birgin, Eg; Martínez, Jm; Ronconi, Dp, Optimizing the packing of cylinders into a rectangular container: a nonlinear approach, Eur. J. Oper. Res., 160, 19-33 (2005) · Zbl 1067.90133
[4] Brown, Pn; Walker, Hf; Wasyk, R.; Woodward, Cs, On using approximate finite-differences in matrix-free Newton-Krylov methods, SIAM J. Numer. Anal., 46, 1892-1911 (2008) · Zbl 1183.65052
[5] Byrd, Rh; Lu, P.; Nocedal, J., A limited memory algorithm for bound constrained optimization, SIAM J. Sci. Stat. Comput., 16, 1190-1208 (1995) · Zbl 0836.65080
[6] Cartis, C.; Gould, Nim; Toint, Pl, On the complexity of steepest descent, Newton’s and regularized Newton’s methods for nonconvex unconstrained optimization, SIAM J. Optim., 20, 2833-2852 (2010) · Zbl 1211.90225
[7] Cartis, C.; Gould, Nim; Toint, Pl, Adaptive cubic regularization methods for unconstrained optimization. Part I: motivation motivation, convergence and numerical results, Math. Program., 127, 245-295 (2011) · Zbl 1229.90192
[8] Cartis, C.; Gould, Nim; Toint, Pl, Adaptive cubic regularization methods for unconstrained optimization. Part II: worst-case function and derivative complexity, Math. Program., 130, 295-319 (2011) · Zbl 1229.90193
[9] Conn, Ar; Gould, Nim; Toint, Phl, Trust Region Methods (2000), Philadelphia: Society for Industrial and Applied Mathematics, Philadelphia · Zbl 0958.65071
[10] Correia, Mh; Oliveira, Jf; Ferreira, Js, Cylinder packing by simulated annealing, Pesqui. Oper., 20, 269-284 (2000) · Zbl 1181.90231
[11] Correia, Mh; Oliveira, Jf; Ferreira, Js, A new upper bound for the cylinder packing problem, Int. Trans. Oper. Res., 8, 571-583 (2001) · Zbl 0992.90056
[12] Curtis, Fe; Robinson, Dp; Samadi, M., A trust-region algorithm with a worst-case iteration complexity of \(O(\varepsilon^{-3/2})\), Math. Program., 162, 1-32 (2017) · Zbl 1360.49020
[13] Demmel, Jw, Applied Numerical Linear Algebra (1997), Philadelphia: SIAM, Philadelphia · Zbl 0879.65017
[14] Fasano, G.; Lucidi, S., A nonmonotone truncated Newton-Krylov method exploiting negative curvature directions, for large scale unconstrained optimization, Optim. Lett., 3, 521-535 (2009) · Zbl 1180.90192
[15] Fasano, G.; Roma, M., Preconditioning Newton-Krylov methods in nonconvex large scale optimization, Comput. Optim. Appl., 56, 253-290 (2013) · Zbl 1314.90063
[16] Gould, Nim; Lucidi, S.; Roma, M.; Toint, Pl, Solving the trust-region subproblem using the Lanczos method, SIAM J. Optim., 9, 504-525 (1999) · Zbl 1047.90510
[17] Grapiglia, G.N., Nesterov, Y.: Globally convergent second-order schemes for minimizing twice differentiable functions. CORE Discussion Paper 2016/28. Université Catholique de Louvain, Louvain, Belgium (2017)
[18] Grapiglia, Gn; Yuan, J-Y; Yuan, Y-X, On the convergence and worst-case complexity of trust-region and regularization methods for unconstrained optimization, Math. Program., 152, 491-520 (2015) · Zbl 1319.90065
[19] Griewank, A.: The modification of Newton’s method for unconstrained optimization by bounding cubic terms. Technical Report NA/12, Department of Applied Mathematics and Theoretical Physics, University of Cambridge (1981)
[20] Komzsik, L., The Lanczos Method: Evolution and Application (2003), Philadelphia: SIAM, Philadelphia · Zbl 1022.65038
[21] Lanczos, C., An iteration method for the solution of the eigenvalue problem of linear differential and integral operators, J. Res. Nat. Bur. Stand., 45, 255-282 (1950)
[22] LAPACK-Linear Algebra PACKage. http://www.netlib.org/lapack (2013)
[23] 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) · Zbl 1268.90048
[24] Martínez, Jm; Raydan, M., Separable cubic modeling and a trust-region strategy for unconstrained minimization with impact in global optimization, J. Glob. Optim., 63, 2, 319-342 (2015) · Zbl 1353.90147
[25] Martínez, Jm; Raydan, M., Cubic-regularization counterpart of a variable-norm trust-region method for unconstrained minimization, J. Glob. Optim., 68, 367-385 (2017) · Zbl 1379.90029
[26] Moré, Jj; Sorensen, Dc, Computing a trust region step, SIAM J. Sci. Stat. Comput., 4, 553-572 (1983) · Zbl 0551.65042
[27] Nash, Sg, Newton-type minimization via the Lanczos method, SIAM J. Numer. Anal., 21, 770-788 (1984) · Zbl 0558.65041
[28] Nesterov, Y.; Polyak, Bt, Cubic reglarization of Newton’s method and its global performance, Math. Program., 108, 177-205 (2006) · Zbl 1142.90500
[29] Packomania. Test instances. http://www.packomania.com/. Accessed 3 Mar 2018
[30] Rojas, M.; Santos, Sa; Sorensen, Dc, A new matrix-free algorithm for the large-scale trust-region subproblem, SIAM J. Optim., 11, 611-646 (2000) · Zbl 0994.65067
[31] Saad, Y., Numerical Methods for Large Eigenvalue Problems (2011), Philadelphia: SIAM, Philadelphia · Zbl 1242.65068
[32] Stewart, Gw, Matrix Algorithms: Eigensystems (2001), Philadelphia: SIAM, Philadelphia · Zbl 0984.65031
[33] Tawarmalani, M.; Sahinidis, Nv, A polyhedral branch-and-cut approach to global optimization, Math. Program., 103, 2, 225-249 (2005) · Zbl 1099.90047
[34] Wang, Z-H; Yuan, Y-X, A subspace implementation of quasi-Newton trust region methods for unconstrained optimization, Numer. Math., 104, 241-269 (2006) · Zbl 1101.65066
[35] Yuan, Y., On the truncated conjugate gradient method, Math. Program., 87, 561-571 (2000) · Zbl 0955.65039
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.