Métodos de Feixes Inexatos Aplicados à Programação Estocástica
Autores
4951 |
2219,249,473
|
|
4952 |
2219,249,473
|
|
4953 |
2219,249,473
|
Informações:
Publicações do PESC
Título
Métodos de Feixes Inexatos Aplicados à Programação Estocástica
Linha de pesquisa
Otimização
Tipo de publicação
Tese de Doutorado
Número de registro
Data da defesa
31/1/2011
Resumo
Problemas de programação estocástica aparecem em muitas aplicações práticas. Em geral, a formulação determinística equivalente desses problemas podem resultar em problemas de otimização muito grandes, que não podem ser resolvidos diretamente. Para o caso particular dos programas estocásticos com recursos, são consideradas técnicas de decomposição que podem lidar com aproximações na solução dos subproblemas. Do ponto de vista da otimização não diferenciável, essas técnicas consistem na aplicação de métodos de feixes empregados com oráculos inexatos, que realizam avaliações aproximadas da função objetivo e de um subgradiente, com erros de precisão limitados, mas possivelmente desconhecidos.
Ao invés de forçar a terminação antecipada na solução dos subproblemas, para definir os oráculos inexatos, são selecionados alguns subproblemas para os quais a solução é exata. Os demais subproblemas são aproximados por um processo rápido, que não envolve a solução de um problema de otimização. As informações aproximadas fornecidas pelos oráculos são utilizadas para construir linearizações inexatas no programa mestre, que são bem administradas pelos métodos de feixes inexatos recentemente desenvolvidos, e pelos métodos de nível inexatos propostos nesta tese.
Além do desenvolvimento teórico, garantindo o controle na aproximação efetuada, são apresentados resultados numéricos promissores, quando comparados com o método de feixes exato e com a decomposição de Benders clássica.
Ao invés de forçar a terminação antecipada na solução dos subproblemas, para definir os oráculos inexatos, são selecionados alguns subproblemas para os quais a solução é exata. Os demais subproblemas são aproximados por um processo rápido, que não envolve a solução de um problema de otimização. As informações aproximadas fornecidas pelos oráculos são utilizadas para construir linearizações inexatas no programa mestre, que são bem administradas pelos métodos de feixes inexatos recentemente desenvolvidos, e pelos métodos de nível inexatos propostos nesta tese.
Além do desenvolvimento teórico, garantindo o controle na aproximação efetuada, são apresentados resultados numéricos promissores, quando comparados com o método de feixes exato e com a decomposição de Benders clássica.
Abstract
Stochastic programming problems arise in many practical situations. In general, the deterministic equivalents of these problems can be very large and may not be solvable directly by general-purpose optimization approaches. For the particular case of stochastic programs with recourse, we consider decomposition approaches that can handle inexactness in the subproblem solution. From a nonsmooth optimization perspective, these variants amount to applying bundle methods to oracles that give inaccurate values for the objective function and a subgradient. Rather than forcing early termination of the subproblems optimization to define inexact oracles, we select a small subset of scenarios for which the subproblem solution is exact, and replace the information for the remaining scenarios by a fast procedure that does not involve solving an optimization problem. The inaccurate oracle information creates inexact cuts in the master program, that are well handledby the recently introduced inexact bundle methods, and by the proposed inexact level methods. The proposed approaches are validated by encouraging numerical results onseveral stochastic linear programs found in the literature.
Arquivo