Fast inexact decomposition algorithms for large-scale separable convex optimization

Quoc Tran-Dinh, Ion Necoara, Moritz DiehlOptimization 2015 · DOI

TL;DR

This paper introduces a novel decomposition algorithm for efficiently solving large-scale optimization problems with separable structures. By combining dual Lagrangian decomposition, smoothing techniques, and an "excessive gap" condition, the algorithm achieves faster convergence and lower computational cost per iteration compared to existing methods, while automatically adapting its parameters.

What Problem Does This Paper Address?

Many real-world optimization problems, particularly in fields like engineering, network design, and control, involve optimizing a function that can be broken down into smaller, independent "separable" parts, but these parts are linked by shared constraints. Solving these "large-scale separable convex optimization problems" is computationally challenging due to their size. Traditional decomposition methods often struggle with slow convergence or require careful manual tuning of parameters. This paper aims to develop a more efficient and robust algorithm that can handle these problems effectively, even when the individual subproblems can only be solved approximately.

Methods

The core of this work is a new "inexact dual decomposition algorithm." It leverages three key ideas:

  • Dual Lagrangian Decomposition: This standard technique breaks down a large problem into smaller, manageable subproblems by introducing "Lagrange multipliers" for the coupling constraints.
  • Smoothing Technique: The dual function, which arises from the decomposition, can be "nonsmooth" (have sharp corners), making it difficult to optimize. This paper uses a "prox-function" based smoothing technique to create a differentiable approximation of the dual function, making it easier to work with.
  • Excessive Gap Condition: This condition provides a theoretical framework to ensure that the algorithm not only finds a good approximate solution but also that this solution is close to being feasible (satisfies the constraints).

The proposed algorithm is designed to be computationally efficient by requiring only one primal step (solving the original problem's variables) and two dual steps (updating the Lagrange multipliers) per iteration. Crucially, it allows these primal subproblems to be solved "inexactly" (with some error), which is often necessary in practice, and can be done in parallel. A key innovation is the automatic update of algorithmic parameters, eliminating the need for manual tuning. The paper also introduces a "switching variant" that further enhances performance by simultaneously updating smoothness parameters.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and numerical experiments using synthetically generated problems.

Key Insights and Ideas

  • Automatic Parameter Tuning is Key: The ability of the algorithm to automatically update its parameters (like smoothness parameters and step sizes) is a significant advantage, reducing user effort and improving robustness compared to methods requiring manual tuning.
  • Inexactness is a Feature, Not a Bug: Allowing primal subproblems to be solved with a certain level of inaccuracy is not only practical but also theoretically justified, contributing to the algorithm's efficiency and convergence guarantees.
  • Parallelism is Built-in: The decomposition structure naturally lends itself to parallel computation, especially for the primal subproblems, making it suitable for modern multi-core architectures.
  • Theoretical Guarantees for Practical Problems: The paper provides strong theoretical convergence guarantees, including worst-case complexity estimates, which are crucial for understanding the algorithm's performance limits.

Key Results

The paper presents theoretical convergence analysis and numerical results.

  • Theoretical Complexity: The algorithm achieves an $O(1/k)$ convergence rate, where $k$ is the iteration number. This is a significant improvement over some existing subgradient-based methods.
  • Numerical Performance: Extensive numerical tests demonstrate that the proposed algorithms (Algorithm 1 and its switching variant) outperform several state-of-the-art decomposition methods, including those based on alternating direction methods of multipliers (ADMM) and proximal methods, in terms of both the number of iterations and computational time across various problem classes (basic pursuit, nonsmooth separable convex optimization, and separable convex quadratic programming). For instance, in one scenario, Algorithm 1 solved 100% of problems with the best computational time.

Limitations and Future Work

  • Parameter Sensitivity: While the algorithm automatically tunes some parameters, the initial choice of certain parameters (like the initial $\beta_1^0$) can still influence performance, as noted in the theoretical analysis.
  • Distributed Implementation: The paper mentions that the algorithm can be adapted for distributed implementation, but a full exploration of this aspect might be a future direction.
  • Generalization: While the paper focuses on separable convex optimization, extending the framework to more general classes of problems (e.g., non-convex or non-separable problems) could be a valuable future research avenue.
  • Practical Tuning: Although automatic tuning is a strength, understanding the impact of initial parameter choices and exploring adaptive strategies for these initial values could further enhance performance.

Summary updated

Abstract

In this paper, we propose a new inexact dual decomposition algorithm for solving separable convex optimization problems. This algorithm is a combination of three techniques: dual Lagrangian decomposition, smoothing and excessive gap. The algorithm has low computational complexity since it consists in only one primal step and two dual steps at each iteration and allows one to solve the subproblem of each component inexactly and in parallel. Moreover, the algorithmic parameters are updated automatically without any tuning strategy as it happens in augmented Lagrangian approaches. We analyse the convergence of the algorithm and estimate its analytical worst-case complexity for both the primal–dual suboptimality and the primal feasibility violation, where is a given accuracy. Extensive numerical tests confirm that our method is numerically more efficient than the classical decomposition methods from the literature.
BibTeX
@inproceedings{trandinh2015fast,
  author = {Quoc Tran-Dinh and Ion Necoara and Moritz Diehl},
  title = {{Fast inexact decomposition algorithms for large-scale separable convex optimization}},
  booktitle = {Optimization},
  year = {2015},
  doi = {10.1080/02331934.2015.1044898},
}
Figure