Projection-free accelerated method for convex optimization. (2nd January 2022) - Gonçalves, Max L. N.; Melo, Jefferson G.; Monteiro, Renato D. C.
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.