×

zbMATH — the first resource for mathematics

Implementable tensor methods in unconstrained convex optimization. (English) Zbl 1459.90157
Summary: In this paper we develop new tensor methods for unconstrained convex optimization, which solve at each iteration an auxiliary problem of minimizing convex multivariate polynomial. We analyze the simplest scheme, based on minimization of a regularized local model of the objective function, and its accelerated version obtained in the framework of estimating sequences. Their rates of convergence are compared with the worst-case lower complexity bounds for corresponding problem classes. Finally, for the third-order methods, we suggest an efficient technique for solving the auxiliary problem, which is based on the recently developed relative smoothness condition [H. H. Bauschke et al., Math. Oper. Res. 42, No. 2, 330–348 (2017; Zbl 1364.90251); H. Lu et al., SIAM J. Optim. 28, No. 1, 333–354 (2018; Zbl 1392.90090)]. With this elaboration, the third-order methods become implementable and very fast. The rate of convergence in terms of the function value for the accelerated third-order scheme reaches the level \(O\left(\frac{1}{k^4}\right)\), where \(k\) is the number of iterations. This is very close to the lower bound of the order \(O\left(\frac{1}{k^5}\right)\), which is also justified in this paper. At the same time, in many important cases the computational cost of one iteration of this method remains on the level typical for the second-order methods.

MSC:
90C25 Convex programming
90C06 Large-scale problems in mathematical programming
65K05 Numerical mathematical programming methods
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Agarwal, N., Hazan, E.: Lower Bounds for Higher-Order Convex Optimization (2017). arXiv:1710.10329v1 [math.OC]
[2] Arjevani, Y., Shamir, O., Shiff, R.: Oracle Complexity of Second-Order Methods for Smooth Convex Optimization (2017). arXiv:1705.07260 [math.OC] · Zbl 1430.90460
[3] Baes, M.: Estimate sequence methods: extensions and approximations. Optim. Online (2009)
[4] Bauschke, HH; Bolte, J.; Teboulle, M., A descent lemma beyond Lipschitz gradient continuety: first-order methods revisited and applications, Math. Oper. Res., 42, 330-348 (2017) · Zbl 1364.90251
[5] Bian, W.; Chen, X.; Ye, Y., Complexity analysis of interior-point algorithms for non-Lipschitz and non-convex minimization, Math. Program., 139, 301-327 (2015) · Zbl 1318.90075
[6] Birgin, E.G., Gardenghi, J.L., Martines, J.M., Santos, S.A.: Remark on Algorithm 566: Modern Fortran Routines for Testing Unconsrained Optimization Software with Derivatives up to Third-Order. Technical report, Department of Computer Sciences, University of Sao Paolo, Brazil (2018)
[7] Birgin, E.G., Gardenghi, J.L., Martines, J.M., Santos, S.A.: On the Use of Third-Order Models with Fourth-Order Regularization for Unconstrained Optimization. Technical report, Department of Computer Sciences, University of Sao Paolo, Brazil (2018)
[8] Birgin, EG; Gardenghi, JL; Martines, JM; Santos, SA; Toint, PhL, Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularization models, Math. Program., 163, 359-368 (2017) · Zbl 1365.90236
[9] Carmon, Y., Duchi, J.C., Hinder, O., Sidford, A.: Lower bounds for finding stationary points I. Archiv (2017). arXiv:1710.11606 · Zbl 1451.90128
[10] Carmon, Y., Duchi, J.C., Hinder, O., Sidford, A.: Lower bounds for finding stationary points II. Archiv (2017). arXiv:1711.00841 · Zbl 1451.90128
[11] Cartis, C.; Gould, NIM; Toint, PhL, Adaptive cubic overestimation methods for unconstrained optimization. Part I: motivation, convergence and numerical results, Math. Program., 130, 2, 295-319 (2012) · Zbl 1229.90193
[12] Cartis, C.; Gould, NIM; Toint, PhL, Adaptive cubic overestimation methods for unconstrained optimization. Part II: worst-case function evaluation complexity., Math. Program., 127, 2, 245-295 (2011) · Zbl 1229.90192
[13] Cartis, C.; Gould, NIM; Toint, PhL, Evaluation complexity of adaptive cubic regularization methods for convex unconstrained optimization, Optim. Methods Softw., 27, 2, 197-219 (2012) · Zbl 1252.90061
[14] Cartis, C.; Gould, NIM; Toint, PhL, Universal regularization methods-varying the power, the smoothness and the accuracy, SIAM. J. Optim., 29, 1, 595-615 (2019) · Zbl 1436.90136
[15] Conn, AR; Gould, NIM; Toint, PhL, Trust Region Methods (2000), New York: MOS-SIAM Series on Optimization, New York · Zbl 0958.65071
[16] Gould, NIM; Orban, D.; Toint, PhL, GALAHAD, a library of thread-safe Fortran 90 packages for large-scale nonlinear optimization, ACM Trans. Math. Softw., 29, 4, 353-372 (2003) · Zbl 1068.90525
[17] Grapiglia, GN; Nesterov, Yu, Regularized Newton methods for minimizing functions with Hölder continuous Hessians, SIOPT, 27, 1, 478-506 (2017) · Zbl 1406.49029
[18] Grapiglia, GN; Yuan, J.; Yuan, Y., 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.; Walther, A., Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation. Applied Mathematics (2008), Philadelphia: SIAM, Philadelphia · Zbl 1159.65026
[20] Gundersen, G.; Steihaug, T., On large-scale unconstrained optimization problems and higher order methods, Optim. Methods. Softw., 25, 3, 337-358 (2010) · Zbl 1202.65074
[21] Lu, H.; Freund, R.; Nesterov, Yu, Relatively smooth convex optimization by first-order methods, and applications, SIOPT, 28, 1, 333-354 (2018) · Zbl 1392.90090
[22] Hoffmann, KH; Kornstaedt, HJ, Higher-order necessary conditions in abstract mathematical programming, JOTA, 26, 533-568 (1978) · Zbl 0373.90066
[23] Lasserre, JB, Moments, Positive Polynomials and Their Applications (2010), London: Imperial College Press, London · Zbl 1211.90007
[24] Monteiro, RDC; Svaiter, BF, An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods, SIOPT, 23, 2, 1092-1125 (2013) · Zbl 1298.90071
[25] Nesterov, Yu, Introductory Lectures on Convex Optimization (2004), Boston: Kluwer, Boston · Zbl 1086.90045
[26] Nesterov, Yu, Smooth minimization of non-smooth functions, Math. Program., 103, 1, 127-152 (2005) · Zbl 1079.90102
[27] Nesterov, Yu, Accelerating the cubic regularization of Newton’s method on convex problems, Math. Program., 112, 1, 159-181 (2008) · Zbl 1167.90013
[28] Nesterov, Yu, Gradient methods for minimizing composite functions, Math. Program., 140, 1, 125-161 (2013) · Zbl 1287.90067
[29] Nesterov, Yu, Universal gradient methods for convex optimization problems, Math. Program., 152, 381-404 (2015) · Zbl 1327.90216
[30] Nesterov, Yu; Nemirovskii, A., Interior Point Polynomial Methods in Convex Programming: Theory and Applications (1994), Philadelphia: SIAM, Philadelphia · Zbl 0824.90112
[31] Nesterov, Yu; Polyak, B., Cubic regularization of Newton’s method and its global performance, Math. Program., 108, 1, 177-205 (2006) · Zbl 1142.90500
[32] Schnabel, RB; Chow, TT, Tensor methods for unconstrained optimization using second derivatives, SIAM J. Optim., 1, 3, 293-315 (1991) · Zbl 0758.65047
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.