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

• Ano de defesa: 2011
• Autor(a) principal: SILVA, Jose Carlos Rubianes
• Orientador(a): MELO, Jefferson Divino Gonçalves de
• 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: Programação Convexa; Métodos Subgradientes; Subgradiente Condicinal; Relaxação Lagrangiana; Dualidade Lagrangiana e Convergência Ergódica
• Palavras-chave em Inglês: Convex programming; Subgradient methods; Conditional subgradient; Lagrangean relaxation; Lagrangean duality and Ergodic convergence
• Área do conhecimento CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::MATEMATICA::MATEMATICA APLICADA
• Link de acesso: http://repositorio.bc.ufg.br/tede/handle/tde/1952

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.