Método Subgradiente Condicional com Sequência Ergódica

Detalhes bibliográficos
Ano de defesa: 2011
Autor(a) principal: SILVA, Jose Carlos Rubianes lattes
Orientador(a): MELO, Jefferson Divino Gonçalves de lattes
Banca de defesa: Não Informado pela instituição
Tipo de documento: Dissertação
Tipo de acesso: Acesso aberto
Idioma: por
Instituição de defesa: Universidade Federal de Goiás
Programa de Pós-Graduação: Mestrado em Matemática
Departamento: Ciências Exatas e da Terra
País: BR
Palavras-chave em Português:
Palavras-chave em Inglês:
Área do conhecimento CNPq:
Link de acesso: http://repositorio.bc.ufg.br/tede/handle/tde/1952
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.