Proximal decomposition methods for optimization problems with structure [recurso eletrônico] = Métodos de decomposição proximal para problemas de otimização com estrutura
Felipe Eduardo Atenas Maldonado
TESE
Inglês
T/UNICAMP At27p
[Métodos de decomposição proximal para problemas de otimização com estrutura]
Campinas, SP : [s.n.], 2023.
1 recurso online (184 p.) : il., digital, arquivo PDF.
Orientadores: Paulo José da Silva e Silva, Claudia Alejandra Sagastizabal
Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica
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...
Ver mais
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
Ver menos
Abstract: Complex large-scale optimization problems usually display a block-separable structure that allows the use of decomposition techniques. Decomposition methods appropriately handle couplings in the constraints or in the variables in order to exploit the separable structure. This thesis...
Ver mais
Abstract: Complex large-scale optimization problems usually display a block-separable structure that allows the use of decomposition techniques. Decomposition methods appropriately handle couplings in the constraints or in the variables in order to exploit the separable structure. This thesis explores decomposition methods for convex and nonconvex optimization problems, that first solve decentralized subproblems, and then coordinate the distributed information. Our goal is two-fold. On one hand, we propose a general unifying framework for convergence analysis of descent methods in nonconvex optimization, including rates of convergence under mild regularity assumptions. Decomposition algorithms frequently provide descent for some improvement measure throughout iterations, such as reduction of some merit function or the distance to the set of solutions. Approaches included in this framework are proximal bundle methods, and the Douglas-Rachford splitting method for weakly convex optimization. On the other hand, we extend the unifying analysis to constrained optimization problems over a linear subspace. This allows us to develop decomposition techniques that capitalize on the scenario separability of multistage stochastic optimization problems, since the linking constraints for these problems are represented by certain linear subspace, related to nonanticipativity in the decision process. For convex problems, we propose two novel methods that replace certain Augmented Lagrangian by separable approximations inducing separability in the dual problem. The coupling constraints are modeled with a linear function constructed using forward-backward steps. These methods are variants of the Progressive Hedging algorithm by Rockafellar and Wets, with the key difference of being convergent also with varying stepsizes along iterations. The two proposed methods differ in the way that improvement along iterations is evaluated. The first method corresponds to a proximal bundle-like adaptation of the Progressive Hedging algorithm, that measures sufficient descent of the cost function. The second one is a splitting technique that employs a relative-error acceptance test, assessing infeasibility and model accuracy. Both methods are shown to generate primal-dual sequences that convergence to solutions to the primal and dual problems, respectively, with linear speed of convergence
Ver menos
Silva, Paulo José da Silva e, 1973-
Orientador
Sagastizabal, Claudia Alejandra, 1961-
Coorientador
Ruszczynski, Andrzej Piotr
Avaliador
Bot, Radu Ioan
Avaliador
Martínez Pérez, José Mario, 1948-
Avaliador
Oliveira, Welington Luis de
Avaliador
Proximal decomposition methods for optimization problems with structure [recurso eletrônico] = Métodos de decomposição proximal para problemas de otimização com estrutura
Felipe Eduardo Atenas Maldonado
Proximal decomposition methods for optimization problems with structure [recurso eletrônico] = Métodos de decomposição proximal para problemas de otimização com estrutura
Felipe Eduardo Atenas Maldonado