Projection-free accelerated method for convex optimization. (2nd January 2022)

• Record Type: Journal Article
• Authors: Gonçalves, Max L. N.; Melo, Jefferson G.; Monteiro, Renato D. C.
• Is Part Of: Optimization methods and software. Volume 37:Number 1(2022)
• Page Start: 214
• Page End: 240
• Publication Date: 2022-01-02
• Subjects: Projection-free method -- accelerated method -- first-order methods -- conditional gradient method; 90C25 -- 90C06 -- 90C22 -- 49M37; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2020.1734806
• Languages: English
• ISSNs: 1055-6788

Abstract

ABSTRACT: In this paper, we propose a projection-free accelerated method for solving convex optimization problems with unbounded feasible set. The method is an accelerated gradient scheme such that each projection subproblem is approximately solved by means of a conditional gradient scheme. Under reasonable assumptions, it is shown that an ϵ -approximate solution (concept related to the optimal value of the problem) is obtained in at most O ( 1 / ε ) gradient evaluations and O ( 1 / ε ) linear oracle calls. We also discuss a notion of approximate solution based on the first-order optimality condition of the problem and present iteration-complexity results for the proposed method to obtain an approximate solution in this sense. Finally, numerical experiments illustrating the practical behaviour of the proposed scheme are discussed.