Master's Dissertation
DOI
https://doi.org/10.11606/D.45.2007.tde-04062007-115956
Document
Author
Full name
Ellen Hidemi Fukuda
Institute/School/College
Knowledge Area
Date of Defense
Published
São Paulo, 2007
Supervisor
Committee
Silva, Paulo José da Silva e (President)
Humes Junior, Carlos
Sagastizabal, Claudia Alejandra
Title in Portuguese
Algoritmo do volume e otimização não diferenciável
Keywords in Portuguese
Algoritmo do volume
max-cut
método de feixe
método de subgradientes
relaxação lagrangeana
Abstract in Portuguese
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.
Title in English
"Volume Algorithm and Nondifferentiable Optimization"
Keywords in English
bundle method
Lagrangian relaxation
max-cut problems on graphs.
subgradient method
Volume algorithm
Abstract in English
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.
WARNING - Viewing this document is conditioned on your acceptance of the following terms of use:
This document is only for private use for research and teaching activities. Reproduction for commercial use is forbidden. This rights cover the whole data about this document as well as its contents. Any uses or copies of this document in whole or in part must include the author's name.
dissertacao.pdf (733.05 Kbytes)
Publishing Date
2007-09-28