Algoritmo do volume e otimização não diferenciável / "Volume Algorithm and Nondifferentiable Optimization"

AUTOR(ES)
DATA DE PUBLICAÇÃO

2007

RESUMO

Uma maneira de resolver problemas de programação linear de grande escala é explorar a relaxação lagrangeana das restrições "difíceise 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.

ASSUNTO(S)

max-cut método de subgradientes lagrangian relaxation algoritmo do volume relaxação lagrangeana bundle method método de feixe volume algorithm max-cut problems on graphs. subgradient method

ACESSO AO ARTIGO

Documentos Relacionados