Search

First-order methods for solving convex optimization problems have been at the forefront of mathematical optimization in the last 20 years. The rapid development of this important class of algorithms is motivated by the success stories reported in various applications, including most importantly machine learning, signal processing, imaging and control theory. First-order methods have the potential to provide low accuracy solutions at low computational complexity which makes them an attractive set of tools in large-scale optimization problems. In this survey, we cover a number of key developments in gradient-based optimization methods. This includes non-Euclidean extensions of the classical proximal gradient method, and its accelerated versions. Additionally we survey recent developments within the class of projection-free methods, and proximal versions of primal-dual schemes. We give complete proofs for various key results, and highlight the unifying aspects of several optimization algorithms.

Orientador: Roberto Andreani Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica Resumo: Neste trabalho desenvolvemos quatro variantes dos métodos de descenso coordenado por blocos para problemas de otimização, sendo três delas para problemas sem restrição e uma para problemas com restrição a uma caixa. Para o desenvolvimento dos quatro métodos,nos baseamos em modelos onde consideramos aproximações polinomiais de Taylor com regularização de ordem superior. Analisamos a complexidade do pior caso para problemas de otimização sem restrição e para problemas restritos a uma caixa, cuja função objetivo tenha derivadas de ordens 1 e p, com p um número natural não nulo, satisfazendo condições de Hölder ou Lipschitz, e sem assumir hipóteses de convexidade. Obtemos resultados de complexidade. Apresentamos casos particulares dos Algoritmos descritos, onde obtemos formas fechadas para os pontos obtidos em cada iteração, evitando neste caso a resolução de subproblemas de minimização em cada iteração durante a execução dos métodos Abstract: In this paper we develop four variants of the block coordinate descent methods for optimization problems, three of them for uncoustrained problems and one for box constrained problems. For the development of the four methods, we based on models where we consider Taylor polynomial approximations with higher order regulation. We analyze the worst-case complexity for unrestricted optimization problems and for a box constrained problem whose objective function has derivatives of order 1 and p, with p a nonzero natural number, satisfying Hölder or Lipschitz conditions, and without assume convexity hypotheses. We obtain results of complexities. We present particular cases of the described Algorithms, where we obtain closed forms for the points obtained in each iteration, avoiding in this case the resolution of minimization subproblems in each iteration during the execution ofthe methods Doutorado Matemática Aplicada Doutor em Matemática Aplicada