An Inexact Perturbed Path-Following Method for Lagrangian Decomposition in Large-Scale Separable Convex Optimization

Quoc Tran-Dinh, Dinh Quoc Tran, Ion Necoara, Carlo Savorgnan, Moritz DiehlSIAM J. Optim 2013 · DOI

TL;DR

This paper introduces a novel algorithm for solving large-scale convex optimization problems with a specific structure (separable objective functions and linear coupling constraints). The key innovation is an "inexact perturbed path-following" method that allows for approximate solutions to subproblems, making it more practical and computationally efficient, especially for problems where exact solutions are prohibitively expensive.

What Problem Does This Paper Address?

Many real-world optimization problems, particularly in areas like networked systems, image processing, and control, can be formulated as large-scale separable convex optimization problems. These problems have a structure where the overall objective function is a sum of functions of individual variables, and there are linear constraints that couple these variables. While standard optimization techniques work well for smaller problems, their scalability is limited by the high dimensionality and distributed nature of data in large-scale instances. Lagrangian decomposition offers a way to break down these problems into smaller, more manageable subproblems. However, traditional methods for solving the resulting dual problem can be computationally demanding, often requiring exact solutions to the primal subproblems. This paper addresses the challenge of developing a more efficient and practical approach by allowing for inexact solutions to these subproblems within a path-following framework.

Methods

The paper proposes an "inexact perturbed path-following" algorithm. This method builds upon the idea of smoothing the non-smooth dual function using self-concordant barrier functions. The core of the approach involves two phases:

  1. Phase 1: Finding a starting point: This phase uses an "inexact perturbed damped Newton" iteration to find an initial point in the feasible region that satisfies certain conditions.
  2. Phase 2: Path-following: This phase employs "inexact perturbed full-step Newton" iterations to follow a path towards the optimal solution.

The key novelty lies in the "inexact" nature of the primal subproblem solutions. Instead of requiring exact solutions, the algorithm allows for approximate solutions up to a controllable accuracy. This is achieved by using approximate Hessian matrices and gradient vectors in the Newton-type steps. The algorithm is also designed to be highly parallelizable, as many of the computations can be performed independently for each component of the separable problem. The authors also derive an "exact" variant of their method, which reduces to existing path-following methods when primal subproblems are solved exactly, but with an improved neighborhood of convergence.

Datasets

Not discussed in the paper. The paper focuses on theoretical development and algorithmic design, with numerical tests performed on a "routing problem with congestion cost" which is described as a benchmark problem.

Key Insights and Ideas

  • Practicality through Inexactness: The most significant insight is that allowing inexact solutions to primal subproblems, which are often the computational bottleneck, can lead to a more practical and efficient algorithm for large-scale problems. This contrasts with methods that require exact solutions, which can be computationally prohibitive.
  • Balancing Accuracy and Convergence: The framework allows for a trade-off between the accuracy of solving the primal subproblems and the convergence rate of the overall algorithm. This flexibility is crucial for tailoring the method to specific problem characteristics and computational resources.
  • Self-Concordant Barriers for Smoothness: The use of self-concordant barrier functions is a powerful technique to obtain smooth approximations of the non-smooth dual function, enabling the application of standard smooth optimization techniques.
  • Path-Following for Robustness: The path-following approach, combined with perturbations, helps to navigate the optimization landscape more robustly, especially in the presence of inexactness.

Key Results

The paper presents a theoretical analysis of the proposed algorithm, including convergence guarantees and worst-case complexity estimates.

  • Convergence Analysis: The authors provide a detailed convergence analysis for both the inexact and exact variants of their path-following algorithm under standard assumptions.
  • Complexity Estimates: Worst-case complexity bounds are derived for the proposed algorithms.
  • Improved Neighborhood: The exact variant of the algorithm offers a larger neighborhood of the analytic center where convergence is guaranteed compared to previous methods.
  • Numerical Validation: Numerical experiments on a routing problem with congestion cost demonstrate the effectiveness of the proposed algorithms. Algorithm 1 (inexact) generally outperforms Algorithm 3 (exact) in terms of total CPU time and primal subproblem solving time. The performance is also shown to be sensitive to parameter choices.

Limitations and Future Work

  • Theoretical Focus: The paper is primarily theoretical, with a focus on algorithmic development and convergence analysis. While numerical tests are presented, further exploration of the algorithm's performance on a wider range of problems and its comparison with other state-of-the-art methods could be beneficial.
  • Inexact Linear Algebra: The paper mentions that the inexactness of linear algebra solvers could be further investigated.
  • Distributed Implementation: The authors suggest that extensions to distributed implementation are an interesting and significant future research direction.
  • Parameter Tuning: The performance of the algorithm is shown to be sensitive to parameter choices, suggesting that robust and adaptive parameter selection strategies could be a valuable area for future work.

Summary updated

BibTeX
@article{trandinh2013inexact,
  author = {Quoc Tran-Dinh and Dinh Quoc Tran and Ion Necoara and Carlo Savorgnan and Moritz Diehl},
  title = {{An Inexact Perturbed Path-Following Method for Lagrangian Decomposition in Large-Scale Separable Convex Optimization}},
  journal = {SIAM J. Optim},
  year = {2013},
  doi = {10.1137/11085311x},
}
Figure