Made available in DSpace on 2014-07-29T16:02:20Z (GMT). No. of bitstreams: 1
Dissertacao Jose Carlos Rubianes Silva.pdf: 825326 bytes, checksum: f8797d1d8d333606ebad1d9941d5d26d (MD5)
Previous issue date: 2011-02-18 / 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. / Nesta dissertação consideramos um problema de otimização convexo e estudamos variações
do método subgradiente aplicado ao problema dual obtido via uma função Lagrangiana.
Estudamos o método subgradiente condicional desenvolvido por Larsson et al,
o qual é uma simples variação do método subgradiente usual . A principal diferença é
que os subgradientes são condicionados a um conjunto restrição, mais especificamente, o
comportamento da função fora do conjunto restrição não é levado em conta. Uma motivação
para estudar tais métodos consiste principalmente na sua simplicidade, em especial,
estes métodos são bastante usados em problemas de grande porte. O método subgradiente,
quando aplicado a um problema dual, é relativamente eficaz para obter boas aproximações
de soluções duais e do valor ótimo, no entanto, não possue a mesma eficiência para obter
soluções primais. Analisamos uma estratégia para obter boas aproximações de soluções
primais via método subgradiente condicional, com pouco custo computacional adicional.
Esta estratégia consiste em construir uma sequência ergódica das soluções obtidas durante
a resolução dos subproblemas Lagrangianos. Mostraremos que os pontos limites desta sequência
ergódica são soluções primais. Consideramos diferentes regras para o tamanho
do passo, em particular, seguindo as idéias de Nedic e Ozdaglar, apresentamos estimativas
da sequência ergódica com o conjunto de soluções primais e/ou o conjunto viável quando
usamos a regra de passos constantes.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.bc.ufg.br:tde/1952 |
| Date | 18 February 2011 |
| Creators | SILVA, Jose Carlos Rubianes |
| Contributors | MELO, Jefferson Divino Gonçalves de |
| Publisher | Universidade Federal de Goiás, Mestrado em Matemática, UFG, BR, Ciências Exatas e da Terra |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFG, instname:Universidade Federal de Goiás, instacron:UFG |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.0024 seconds