Variantes contemporâneas de métodos de decomposição para otimização de grande porte

• Processo: 22/02208-7
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Doutorado
• Data de Início da vigência: 01 de setembro de 2022
• Data de Término da vigência: 28 de fevereiro de 2023
• Área de conhecimento: Ciências Exatas e da Terra - Matemática - Matemática Aplicada
• Pesquisador responsável: Paulo José da Silva e Silva
• Beneficiário: Felipe Eduardo Atenas Maldonado
• Supervisor: Jonathan Eckstein
• Instituição Sede: Instituto de Matemática, Estatística e Computação Científica (IMECC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Instituição Anfitriã: Rutgers The State University of New Jersey, New Brunswick, Estados Unidos
• Vinculado à bolsa: 19/20023-1 - Análise variacional estocástica aplicada à indústria da energia, BP.DR
• Assunto(s): Métodos de decomposição Análise variacional Otimização estocástica Algoritmos
• Palavra(s)-Chave do Pesquisador: análise variacional estocástica | Métodos de decomposição | problema de otimização com incertezas | sequências de descida | Otimização, Análise variacional estocástica, energía

Resumo

A proposta do projeto é avançar no desenvolvimento dos métodos de decomposição de operadores, explorando três frentes relacionadas, uma teórica e duas de natureza prática. Embora não dependam do trabalho teórico, os dois subprojetos práticos são projetados para aproveitar ao máximo quaisquer avanços obtidos na parte teórica. Os tópicos de pesquisa descritos abaixo são desafiadores, na vanguarda da otimização matemática. Como tal, algumas partes deste programa de pesquisa podem se estender além da visita de seis meses, tomando a forma de uma colaboração de longa distância com o pesquisador anfitrião no exterior. A ideia principal dos aspectos teóricos do projeto proposto é estender o trabalho prévio do candidato sobre convergência de algoritmos de descida a algumas formas de decomposição de operadores, com a intenção de desenvolver algoritmos práticos com propriedades favoráveis de convergência assintótica. O candidato estudará como adaptar vários tipos de iterações de decomposição de operadores ao esquema de descida recentemente desenvolvido por ele e co-autores, e estender a teoria nele contida para obter esquemas que exibam uma taxa superlinear de convergência. Este objetivo pode se mostrar desafiador porque a análise dos métodos de divisão do operador tende a ser baseada na redução da distância ao conjunto de soluções, ao invés de reduzir os valores da função objetivo. Entretanto, os métodos de decomposição utilizam subgradientes de maneira semelhante aos métodos de descida, e algumas das técnicas desenvolvidas pelo pesquisador anfitrião no exterior podem se mostrar úteis. Generalizações e adaptações da estrutura de descida desenvolvida também serão consideradas como necessárias. O interesse geral de uma teoria unificada para a obtenção de taxas superlineares em otimização convexa não suave é apoiado por trabalhos anteriores que foram desenvolvidos separadamente para configurações específicas. Tal é o caso do método VU-bundle, considerando uma certa subsequência de "passos muito sérios". Mais recentemente, foi estabelecida na literatura uma convergência quadrática do esquema prox-linear sob uma condição sharp. A capacidade dos métodos de projective splitting para acomodar mudanças em cada iteração no parâmetro proximal, pode ser útil neste esforço, juntamente com a teoria das sequências de métrica variável quasi-Fejér. Uma ferramenta mais recente é a abordagem de direções superlineares, correspondente a um algoritmo de tipo Newton para encontrar pontos fixos de operadores não-expansivos.O esforço proposto se baseará nestes trabalhos e outros relacionados, conforme apropriado. Há duas aplicações práticas em mente: programação linear de grande porte, e aceleração do algoritmo Progressive Hedging e métodos relacionados para programação estocástica. Quanto à primeira, explorará a possibilidade de usar métodos de primeira ordem e técnicas de decomposição como alternativa aos métodos simplex e Newton de barreira para resolver problemas de programação linear de grande porte. Para à segunda aplicação, o objetivo é investigar melhorias na implementação e convergência de algoritmos de otimização estocástica de tipo progressive hedging. O estudo incluirá o algoritmo de "projective hedging" desenvolvido pelo pesquisador anfitrião no exterior e co-autores, e em particular como ajustar dinamicamente seus parâmetros para melhorar o comportamento da "cauda" sem sacrificar a convergência teórica. (AU)