Proximal decomposition methods for optimization problems with structure

Autor(es)

Felipe Eduardo Atenas Maldonado

• Tipo de documento: Tese de Doutorado
• Imprenta: Campinas, SP.
• Instituição: Universidade Estadual de Campinas (UNICAMP). Instituto de Matemática, Estatística e Computação Científica
• Data de defesa: 2023-04-09

Membros da banca

Paulo José da Silva e Silva; Andrzej Piotr Ruszczynski; Radu Ioan Bot; José Mario Martínez Pérez; Welington Luis de Oliveira

• Orientador: Paulo José da Silva e Silva; Claudia Alejandra Sagastizabal

Resumo

Problemas complexos de otimização de grande porte geralmente apresentam uma estrutura separável por blocos que permite o uso de técnicas de decomposição. Os métodos de decomposição lidam adequadamente com acoplamentos nas restrições ou nas variáveis, para aproveitar essas estruturas separáveis. Essa tese explora algoritmos de decomposição para problemas de otimização convexos e não convexos que, em cada iteração, primeiro resolvem subproblemas descentralizados e depois coordenam a informação distribuída. Nosso objetivo é duplo. Por um lado, propomos uma análise unificadora de convergência de métodos de descida para otimização não convexa, incluindo taxas de convergência sob hipóteses fracas de regularidade. Os algoritmos de decomposição fornecem frequentemente descida para alguma medida de progresso ao longo das iterações, como a redução de alguma função de mérito ou a distância ao conjunto de soluções. As abordagens incluídas em nossa análise são os métodos de feixe proximal e o método de Douglas-Rachford para otimização fracamente convexa. Por outro lado, estendemos a análise unificadora para problemas de otimização restritos a um subespaço linear. Isso nos permite desenvolver técnicas de decomposição que usufruem da separabilidade por cenários de problemas de otimização estocástica multiestágio, uma vez que as restrições acoplantes desses problemas são representadas por um subespaço linear relacionado à não antecipatividade no processo de decisões. Para problemas convexos, propomos dois novos métodos que aproximam o método de Lagrangiano aumentado, ao induzir separabilidade no problema dual. As restrições acopladoras são modeladas com uma função linear construída usando passos forward-backward. Esses dois métodos são variantes do algoritmo Progressive Hedging de Rockafellar e Wets, com a importante diferença de serem convergentes também se o comprimento de passo varia com as iterações. Os dois métodos propostos diferem na forma como o progresso ao longo das iterações é avaliado. O primeiro método corresponde a uma variante do tipo feixe proximal do algoritmo Progressive Hedging, que mede descida suficiente da função de custo. O segundo método é uma técnica de decomposição que emprega um teste de aceitação de erro relativo que avalia a inviabilidade e a precisão do modelo. Ambos os métodos geram sequências primais-duais que convergem a soluções dos problemas primal e dual, respectivamente, com taxa de convergência linear (AU)

• Processo FAPESP: 19/20023-1 - Análise variacional estocástica aplicada à indústria da energia
• Beneficiário: Felipe Eduardo Atenas Maldonado
• Modalidade de apoio: Bolsas no Brasil - Doutorado