Método Subgradiente Condicional com Sequência Ergódica
Carregando...
Data
2011-02-18
Autores
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Goiás
Resumo
In this dissertation we consider a primal convex optimization problem and we study
variants of subgradient method applied to the dual problem obtained via a Lagrangian
function. We analyze the conditional subgradient method developed by Larsson et al,
which is a variant of the usual subgradient method. In this variant, the subgradients are
conditioned to a constraint set, more specifically, the behavior of the objective function
outside of the constraint set is not taken into account. One motivation for studying
such methods is primarily its simplicity, in particular, these methods are widely used
in large-scale problems. The subgradient method, when applied to a dual problem, is
relatively effective to obtain a good approximation of a dual solution and the optimal
value, but it is not efficient to obtain primal solutions. We study a strategy to obtain
good approximations of primal solutions via conditional subgradient method, under
suitable additional computational costs. This strategy consists of constructing an ergodic
sequence of solutions of the Lagrangian subproblems.We show that the limit points of this
ergodic sequence are primal solutions. We consider different step sizes rule, in particular,
following the ideas of Nedic and Ozdaglar, using the constant step size rule, we present
estimates of the ergodic sequence and primal solutions and / or the feasible set.
Descrição
Citação
SILVA, Jose Carlos Rubianes. Conditional subgradient method with sequence Ergodic. 2011. 101 f. Dissertação (Mestrado em Ciências Exatas e da Terra) - Universidade Federal de Goiás, Goiânia, 2011.