A distributed framework for sparse convex optimization: algorithms and software tools

Abstract

Esta tese aborda problemas de otimização convexa distribuída que incorporam uma restrição de esparsidade. Conhecido como Otimização Convexa Esparsa (SCO, na sigla em inglês), esse problema é definido em uma rede de computadores, onde vários agentes trabalham juntos para resolver o problema de otimização de forma colaborativa. Devido à restrição de esparsidade ser uma combinação de um número finito de subespaços, o problema SCO se enquadra na classe de otimização combinatória, que geralmente é considerada NP-difícil. Esta tese desenvolveu algoritmos distribuídos eficientes e ferramentas de software para resolver problemas SCO com dados descentralizados. Os algoritmos foram projetados para funcionar em uma rede computacional ponto a ponto, onde cada nó lida com uma parte específica do problema em paralelo, colaborando com outros nós. Inspirada em avanços anteriores em otimização inteira mista e computação de alto desempenho, esta tese introduz um framework de Programação Inteira Mista (MIP) distribuída para encontrar soluções exatas para problemas SCO. O framework apresenta novos algoritmos e heurísticas distribuídos, que são implementados em uma ferramenta de software chamada Conjunto de Ferramentas para Otimização Convexa Esparsa (SCOT, na sigla em inglês), especificamente projetada para resolver problemas SCO. Em particular, os algoritmos propostos estendem algoritmos de Aproximação Externa de Múltiplas e Únicas Árvores (OA) incorporando um algoritmo totalmente descentralizado chamado Método dos Multiplicadores de Direção Alternada Híbrido Relaxado (RH-ADMM, na sigla em inglês). Isso leva ao desenvolvimento de dois algoritmos distribuídos de programação não linear inteira mista: Aproximação Externa Primal Distribuída (DiPOA, na sigla em inglês) e Aproximação Externa Híbrida Distribuída (DiHOA, na sigla em inglês). Além disso, várias técnicas de reformulação e heurísticas são descritas e analisadas, visando aproveitar a separabilidade de funções não lineares e melhorar o desempenho dos algoritmos.

Abstract: This thesis addresses distributed convex optimization problems that incorporate a sparsity constraint. Referred to as Sparse Convex Optimization (SCO), this problem emerges from a network of computing nodes where various agents work together to solve the optimization problem collaboratively. Due to the sparsity constraint being a combination of a finite number of subspaces, the SCO problem falls under the class of combinatorial optimization, which is typically considered NP-hard. This thesis develops efficient distributed algorithms and software tools to solve SCO problems with decentralized data. The algorithms were designed to work on a peer-to-peer computational network where each node handles a specific portion of the problem in parallel while collaborating with other nodes. Inspired by previous advancements in mixed-integer optimization and high-performance computing, this thesis introduces a distributed Mixed-Integer Programming (MIP) framework to find exact solutions for SCO problems. The framework presents novel distributed algorithms and heuristics, which were implemented in a software tool called the Sparse Convex Optimization Toolkit (SCOT), specifically designed to solve SCO problems. In particular, the proposed algorithms extend multi- and single-tree Outer Approximation (OA) algorithms by incorporating a fully decentralized algorithm called the Relaxed Hybrid Alternating Direction Method of Multipliers (RH-ADMM). Such developments led to the design of two distributed mixed-integer nonlinear programming algorithms: Distributed Primal Outer Approximation (DiPOA) and Distributed Hybrid Outer Approximation (DiHOA). Additionally, various reformulation and heuristic techniques were introduced to leverage the separability of nonlinear functions and enhance performance.