MÉTODO PROXIMAL INCREMENTAL EM OTIMIZAÇÃO CONVEXA

Abstract

RESUMO: Neste trabalho consideramos um método incremental relativamente novo para problemas de otimização convexa em larga escala: método proximal-subgradiente incremental (Bertsekas, 2010). Visando uma melhor compreensão deste método, fazemos uma breve abordagem sobre os métodos subgradiente incremental e proximal incremental (Wajs e Bertsekas, 2003) e provamos uma relação entre suas iterações, conseguindo também uma estimativa útil para a análise de convergência do método em questão. Para esta análise consideramos o método sob a ordem cíclica, usando algumas hipóteses e a noção de quase- Fejér convergência obtemos uma estimativa do número de iterações necessárias para se obter certo nível de otimalidade e em que condições essa convergência se torna exata. ABSTRACT: In this work we consider a relatively new incremental method for large-scale convex optimization problems: incremental proximal-subgradient method (Bertsekas, 2010). Aiming at a better understanding of this method, we make a brief approach to the incremental proximal and incremental subgradient methods (Wajs and Bertsekas, 2003) and prove a relation between their iterations, also obtaining a useful estimate for the convergence analysis of the method in question. For this analysis we consider the method under the cyclic order, using some hypotheses and the notion of quase-Fejér convergence we obtain an estimate of the number of iterations necessary to have a certain level of optimality and what conditions this convergence becomes accurate.