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

Research output: Types of ThesisDoctoral ThesisMonograph

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.
Original languageEnglish
Publisher
Publication statusPublished - 10 Aug 2023
Externally publishedYes
MoE publication typeG4 Doctoral dissertation (monograph)

Fingerprint

Dive into the research topics of 'A distributed framework for sparse convex optimization: algorithms and software tools'. Together they form a unique fingerprint.

Cite this