Spelling suggestions: "subject:"subgradiente"" "subject:"subgradients""
1 |
Métodos subgradientes em otimização convexa não diferenciável / Subgradients methods for otimization of nondiferentiable convex functionSouza, Théssera Christine Araújo de 29 August 2008 (has links)
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.
|
2 |
String-averaging incremental subgradient methods for constrained convex optimization problems / Média das sequências e métodos de subgradientes incrementais para problemas de otimização convexa com restriçõesOliveira, Rafael Massambone de 12 July 2017 (has links)
In this doctoral thesis, we propose new iterative methods for solving a class of convex optimization problems. In general, we consider problems in which the objective function is composed of a finite sum of convex functions and the set of constraints is, at least, convex and closed. The iterative methods we propose are basically designed through the combination of incremental subgradient methods and string-averaging algorithms. Furthermore, in order to obtain methods able to solve optimization problems with many constraints (and possibly in high dimensions), generally given by convex functions, our analysis includes an operator that calculates approximate projections onto the feasible set, instead of the Euclidean projection. This feature is employed in the two methods we propose; one deterministic and the other stochastic. A convergence analysis is proposed for both methods and numerical experiments are performed in order to verify their applicability, especially in large scale problems. / Nesta tese de doutorado, propomos novos métodos iterativos para a solução de uma classe de problemas de otimização convexa. Em geral, consideramos problemas nos quais a função objetivo é composta por uma soma finita de funções convexas e o conjunto de restrições é, pelo menos, convexo e fechado. Os métodos iterativos que propomos são criados, basicamente, através da junção de métodos de subgradientes incrementais e do algoritmo de média das sequências. Além disso, visando obter métodos flexíveis para soluções de problemas de otimização com muitas restrições (e possivelmente em altas dimensões), dadas em geral por funções convexas, a nossa análise inclui um operador que calcula projeções aproximadas sobre o conjunto viável, no lugar da projeção Euclideana. Essa característica é empregada nos dois métodos que propomos; um determinístico e o outro estocástico. Uma análise de convergência é proposta para ambos os métodos e experimentos numéricos são realizados a fim de verificar a sua aplicabilidade, principalmente em problemas de grande escala.
|
3 |
Algoritmo do volume e otimização não diferenciável / \"Volume Algorithm and Nondifferentiable Optimization\"Fukuda, Ellen Hidemi 01 March 2007 (has links)
Uma maneira de resolver problemas de programação linear de grande escala é explorar a relaxação lagrangeana das restrições \"difíceis\'\' e utilizar métodos de subgradientes. Populares por fornecerem rapidamente boas aproximações de soluções duais, eles não produzem diretamente as soluções primais. Para obtê-las com custo computacional adequado, pode-se construir seqüências ergódicas ou utilizar uma técnica proposta recentemente, denominada algoritmo do volume. As propriedades teóricas de convergência não foram bem estabelecidas nesse algoritmo, mas pequenas modificações permitem a demonstração da convergência dual. Destacam-se como adaptações o algoritmo do volume revisado, um método de feixes específico, e o algoritmo do volume incorporado ao método de variação do alvo. Este trabalho foi baseado no estudo desses algoritmos e de todos os conceitos envolvidos, em especial, análise convexa e otimização não diferenciável. Estudamos as principais diferenças teóricas desses métodos e realizamos comparações numéricas com problemas lineares e lineares inteiros, em particular, o corte máximo em grafos. / One way to solve large-scale linear programming problems is to exploit the Lagrangian relaxation of the difficult constraints and use subgradient methods. Such methods are popular as they give good approximations of dual solutions. Unfortunately, they do not directly yield primal solutions. Two alternatives to obtain primal solutions under reasonable computational cost are the construction of ergodic sequences and the use of the recently developed volume algorithm. While the convergence of ergodic sequences is well understood, the convergence properties of the volume algorithm is not well established in the original paper. This lead to some modifications of the original method to ease the proof of dual convergence. Three alternatives are the revised volume algorithm, a special case of the bundle method, and the volume algorithm incorporated by the variable target value method. The aim of this work is to study such algorithms and all related concepts, especially convex analysis and nondifferentiable optimization. We analysed the main theoretical differences among the methods and performed numerical experiments with linear and integer problems, in particular, the maximum cut problem on graphs.
|
4 |
String-averaging incremental subgradient methods for constrained convex optimization problems / Média das sequências e métodos de subgradientes incrementais para problemas de otimização convexa com restriçõesRafael Massambone de Oliveira 12 July 2017 (has links)
In this doctoral thesis, we propose new iterative methods for solving a class of convex optimization problems. In general, we consider problems in which the objective function is composed of a finite sum of convex functions and the set of constraints is, at least, convex and closed. The iterative methods we propose are basically designed through the combination of incremental subgradient methods and string-averaging algorithms. Furthermore, in order to obtain methods able to solve optimization problems with many constraints (and possibly in high dimensions), generally given by convex functions, our analysis includes an operator that calculates approximate projections onto the feasible set, instead of the Euclidean projection. This feature is employed in the two methods we propose; one deterministic and the other stochastic. A convergence analysis is proposed for both methods and numerical experiments are performed in order to verify their applicability, especially in large scale problems. / Nesta tese de doutorado, propomos novos métodos iterativos para a solução de uma classe de problemas de otimização convexa. Em geral, consideramos problemas nos quais a função objetivo é composta por uma soma finita de funções convexas e o conjunto de restrições é, pelo menos, convexo e fechado. Os métodos iterativos que propomos são criados, basicamente, através da junção de métodos de subgradientes incrementais e do algoritmo de média das sequências. Além disso, visando obter métodos flexíveis para soluções de problemas de otimização com muitas restrições (e possivelmente em altas dimensões), dadas em geral por funções convexas, a nossa análise inclui um operador que calcula projeções aproximadas sobre o conjunto viável, no lugar da projeção Euclideana. Essa característica é empregada nos dois métodos que propomos; um determinístico e o outro estocástico. Uma análise de convergência é proposta para ambos os métodos e experimentos numéricos são realizados a fim de verificar a sua aplicabilidade, principalmente em problemas de grande escala.
|
5 |
Algoritmo do volume e otimização não diferenciável / \"Volume Algorithm and Nondifferentiable Optimization\"Ellen Hidemi Fukuda 01 March 2007 (has links)
Uma maneira de resolver problemas de programação linear de grande escala é explorar a relaxação lagrangeana das restrições \"difíceis\'\' e utilizar métodos de subgradientes. Populares por fornecerem rapidamente boas aproximações de soluções duais, eles não produzem diretamente as soluções primais. Para obtê-las com custo computacional adequado, pode-se construir seqüências ergódicas ou utilizar uma técnica proposta recentemente, denominada algoritmo do volume. As propriedades teóricas de convergência não foram bem estabelecidas nesse algoritmo, mas pequenas modificações permitem a demonstração da convergência dual. Destacam-se como adaptações o algoritmo do volume revisado, um método de feixes específico, e o algoritmo do volume incorporado ao método de variação do alvo. Este trabalho foi baseado no estudo desses algoritmos e de todos os conceitos envolvidos, em especial, análise convexa e otimização não diferenciável. Estudamos as principais diferenças teóricas desses métodos e realizamos comparações numéricas com problemas lineares e lineares inteiros, em particular, o corte máximo em grafos. / One way to solve large-scale linear programming problems is to exploit the Lagrangian relaxation of the difficult constraints and use subgradient methods. Such methods are popular as they give good approximations of dual solutions. Unfortunately, they do not directly yield primal solutions. Two alternatives to obtain primal solutions under reasonable computational cost are the construction of ergodic sequences and the use of the recently developed volume algorithm. While the convergence of ergodic sequences is well understood, the convergence properties of the volume algorithm is not well established in the original paper. This lead to some modifications of the original method to ease the proof of dual convergence. Three alternatives are the revised volume algorithm, a special case of the bundle method, and the volume algorithm incorporated by the variable target value method. The aim of this work is to study such algorithms and all related concepts, especially convex analysis and nondifferentiable optimization. We analysed the main theoretical differences among the methods and performed numerical experiments with linear and integer problems, in particular, the maximum cut problem on graphs.
|
6 |
Método Subgradiente Condicional com Sequência Ergódica / Conditional subgradient method with sequence ErgodicSILVA, Jose Carlos Rubianes 18 February 2011 (has links)
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.
|
Page generated in 0.0825 seconds