Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-03-07T13:13:38Z No. of bitstreams: 1 thesserachristinearaujodesouza.pdf: 806744 bytes, checksum: 46be79df1b2c6a463dc51bc0b211dae8 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-03-07T15:04:56Z (GMT) No. of bitstreams: 1 thesserachristinearaujodesouza.pdf: 806744 bytes, checksum: 46be79df1b2c6a463dc51bc0b211dae8 (MD5) / Made available in DSpace on 2017-03-07T15:04:56Z (GMT). No. of bitstreams: 1 thesserachristinearaujodesouza.pdf: 806744 bytes, checksum: 46be79df1b2c6a463dc51bc0b211dae8 (MD5) Previous issue date: 2008-08-29 / Este trabalho tem por finalidade descrever o Estado da Arte acerca de Métodos Subgradientes para otimização de funções convexas não diferenciáveis. Apresenta-se inicialmente um histórico desses métodos, conceitos básicos sobre otimização diferenciável, necessários para o entendimento de certas noções importantes referentes à problemas não diferenciáveis, bem como esses problemas e suas características próprias. Posteriormente, apresenta-se uma breve introdução aos métodos não diferenciáveis para, então dedicar-se ao objetivo principal do trabalho que são os Métodos Subgradientes, suas extensões e trabalhos recentes. Finaliza-se a Dissertação com a apresentação de algumas aplicações, seus resultados e conclusões. / The goal of this work is describe the State of the Art about Subgradients Methods for optimization of nondifferentiable convex functions. We initially present a historical of these methods, basic concepts on differentiable optimization, necessary to the comprehension of certain important notions about nondifferentiable problems, as well as these problems and its own characteristics. Subsequently, a short introduction about nondifferentiable methods is presented for, then, devote to Subgradients Methods, its extensions and recent works. The Dissertation is finished with the presentation of some applications, its results and conclusions.

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.