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

Página do item simplificado
dc.contributor.advisor1MELO, Jefferson Divino Gonçalves de
dc.contributor.advisor1Latteshttp://lattes.cnpq.br/8296171010616435por
dc.creatorSILVA, Jose Carlos Rubianes
dc.creator.Latteshttp://lattes.cnpq.br/6114855385947020por
dc.date.accessioned2014-07-29T16:02:20Z
dc.date.available2012-06-04
dc.date.issued2011-02-18
dc.description.abstractIn 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.eng
dc.description.provenanceMade 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-18eng
dc.description.resumoNesta 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.por
dc.formatapplication/pdfpor
dc.identifier.citationSILVA, 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.por
dc.identifier.urihttp://repositorio.bc.ufg.br/tede/handle/tde/1952
dc.languageporpor
dc.publisherUniversidade Federal de Goiáspor
dc.publisher.countryBRpor
dc.publisher.departmentCiências Exatas e da Terrapor
dc.publisher.initialsUFGpor
dc.publisher.programMestrado em Matemáticapor
dc.rightsAcesso Abertopor
dc.subjectProgramação Convexapor
dc.subjectMétodos Subgradientespor
dc.subjectSubgradiente Condicinalpor
dc.subjectRelaxação Lagrangianapor
dc.subjectDualidade Lagrangiana e Convergência Ergódicapor
dc.subjectConvex programmingeng
dc.subjectSubgradient methodseng
dc.subjectConditional subgradienteng
dc.subjectLagrangean relaxationeng
dc.subjectLagrangean duality and Ergodic convergenceeng
dc.subject.cnpqCNPQ::CIENCIAS EXATAS E DA TERRA::MATEMATICA::MATEMATICA APLICADApor
dc.thumbnail.urlhttp://repositorio.bc.ufg.br/TEDE/retrieve/4783/Dissertacao%20Jose%20Carlos%20Rubianes%20Silva.pdf.jpg*
dc.titleMétodo Subgradiente Condicional com Sequência Ergódicapor
dc.title.alternativeConditional subgradient method with sequence Ergodiceng
dc.typeDissertaçãopor

Arquivos

Pacote Original
Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
Dissertacao Jose Carlos Rubianes Silva.pdf
Tamanho:
805.98 KB
Formato:
Adobe Portable Document Format
Baixar

Coleções

Mestrado em Matemática (IME)