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

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.