On inexact solution of auxiliary problems in tensor methods for convex optimization. (2nd January 2021)

• Record Type: Journal Article
• Authors: Grapiglia, G.N.; Nesterov, Yu.
• Is Part Of: Optimization methods and software. Volume 36:Number 1(2021)
• Page Start: 145
• Page End: 170
• Publication Date: 2021-01-02
• Subjects: Unconstrained minimization -- high-order methods -- tensor methods -- Hölder condition -- worst-case global complexity bounds; 49M15 -- 49M37 -- 58C15 -- 90C25 -- 90C30; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2020.1731749
• Languages: English
• ISSNs: 1055-6788

Abstract

ABSTRACT: In this paper, we study the auxiliary problems that appear in p -order tensor methods for unconstrained minimization of convex functions with ν -Hölder continuous p th derivatives. This type of auxiliary problems corresponds to the minimization of a ( p + ν ) -order regularization of the p th-order Taylor approximation of the objective. For the case p = 3, we consider the use of Gradient Methods with Bregman distance. When the regularization parameter is sufficiently large, we prove that the referred methods take at most O ( log ⁡ ( ϵ − 1 ) ) iterations to find either a suitable approximate stationary point of the tensor model or an ε -approximate stationary point of the original objective function.