An Accelerated Inexact Dampened Augmented Lagrangian Method for Linearly-Constrained Nonconvex Composite Optimization Problems

Weiwei Kong, Renato D. C. MonteiroComput. Optim. Appl 2021

Abstract

This paper proposes and analyzes an accelerated inexact dampened augmented Lagrangian (AIDAL) method for solving linearly-constrained nonconvex composite optimization problems. Each iteration of the AIDAL method consists of: (i) inexactly solving a dampened proximal augmented Lagrangian (AL) subproblem by calling an accelerated composite gradient (ACG) subroutine; (ii) applying a dampened and under-relaxed Lagrange multiplier update; and (iii) using a novel test to check whether the penalty parameter of the AL function should be increased. Under several mild assumptions involving the dampening factor and the under-relaxation constant, it is shown that the AIDAL method generates an approximate stationary point of the constrained problem in ${\cal O}(\varepsilon^{-5/2}\log\varepsilon^{-1})$ iterations of the ACG subroutine, for a given tolerance $\varepsilon>0$. Numerical experiments are also given to show the computational efficiency of the proposed method.

Introduction

Linearly-constrained nonconvex composite optimization (NCO) represents a significant challenge in mathematical optimization. These problems involve finding a stationary point for a nonconvex objective function subject to linear constraints, a scenario common in high-dimensional data analysis and engineering. Traditionally, the Augmented Lagrangian (AL) method has been the workhorse for such problems, converting constrained tasks into a sequence of unconstrained subproblems.

However, classical AL methods often struggle with nonconvexity. They frequently require restrictive assumptions—such as starting with a feasible point—or exhibit poor iteration complexity, typically $\mathcal{O}(\varepsilon^{-3})$. This paper introduces the Accelerated Inexact Dampened Augmented Lagrangian (AIDAL) method, which achieves a state-of-the-art complexity of $\mathcal{O}(\varepsilon^{-5/2} \log \varepsilon^{-1})$, providing a significant theoretical and practical speedup.

The AIDAL Framework

The AIDAL method is built upon three innovative components that stabilize the optimization path and accelerate convergence:

  1. Dampened Multiplier Updates: The algorithm introduces a dampening factor $\theta \in (0, 1)$ into the Lagrange multiplier update. This perturbation provides the mathematical stability necessary to improve the global complexity bound beyond the standard $\mathcal{O}(\varepsilon^{-3})$.
  2. Inexact Subproblems via ACG: Solving internal subproblems to optimality is often computationally prohibitive. AIDAL utilizes an Accelerated Composite Gradient (ACG) subroutine to solve these subproblems inexactly but sufficiently, allowing the algorithm to maintain progress without excessive per-iteration costs.
  3. Adaptive Penalty Parameter Management: A novel test determines when to increase the penalty parameter (the weight assigned to constraint violations). By preventing the penalty from growing unnecessarily fast, the method avoids the numerical ill-conditioning that often plagues standard AL implementations.

Furthermore, the method employs an under-relaxation constant ($\chi$), which helps smooth the trajectory toward a stationary point and ensures the Lagrange multipliers remain bounded throughout the execution.

Theoretical Contributions

The primary contribution of this work is the rigorous proof of a $\mathcal{O}(\varepsilon^{-5/2} \log \varepsilon^{-1})$ iteration complexity. This improvement is substantial; for a target precision of $\varepsilon = 10^{-3}$, the AIDAL method is theoretically up to 30 times more efficient than classical methods.

Key theoretical insights include:

  • Stepsize Independence: Unlike previous attempts at dampened methods, AIDAL’s stepsize ($\lambda$) does not need to vanish as the dampening factor changes, allowing the algorithm to remain aggressive.
  • Initial Feasibility: The method does not require an initial feasible point ($Az=b$), making it highly flexible for real-world applications where finding a feasible starting point is itself a difficult task.
  • Bounded Multipliers: The authors demonstrate that the Lagrange multipliers are bounded by a constant independent of the accuracy $\varepsilon$, ensuring numerical stability.

Numerical Evaluation

The paper evaluates the AIDAL method against established benchmarks like iALM and QP-AIPP across three problem classes:

  • Linearly-Constrained Quadratic Programming (LCQP): Testing the handling of nonconvex quadratic objectives.
  • Sparse Principal Component Analysis (Sparse PCA): A machine learning benchmark where sparsity constraints add non-smoothness and complexity.
  • Linearly-Constrained Quadratic Matrix (LCQM) Problems: High-dimensional problems involving spectraplex constraints.

In these experiments, an adaptive version of the algorithm (rADL0) consistently outperformed competitors. In Sparse PCA tasks, AIDAL was often orders of magnitude faster in terms of total runtime and required significantly fewer inner iterations to reach the desired accuracy.

Conclusion and Limitations

AIDAL represents a significant step forward in nonconvex optimization, offering a faster, more stable alternative to traditional AL methods. While the results are promising, the current analysis relies on a compact domain for the nonsmooth part of the objective and a "Slater-like" condition for the constraints. Future research may focus on relaxing these assumptions and developing fully self-tuning versions of the algorithm's hyperparameters.

Summary updated

Abstract

This paper proposes and analyzes an accelerated inexact dampened augmented Lagrangian (AIDAL) method for solving linearly-constrained nonconvex composite optimization problems. Each iteration of the AIDAL method consists of: (i) inexactly solving a dampened proximal augmented Lagrangian (AL) subproblem by calling an accelerated composite gradient (ACG) subroutine; (ii) applying a dampened and under-relaxed Lagrange multiplier update; and (iii) using a novel test to check whether the penalty parameter of the AL function should be increased. Under several mild assumptions involving the dampening factor and the under-relaxation constant, it is shown that the AIDAL method generates an approximate stationary point of the constrained problem in ${\cal O}(\varepsilon^{-5/2}\log\varepsilon^{-1})$ iterations of the ACG subroutine, for a given tolerance $\varepsilon>0$. Numerical experiments are also given to show the computational efficiency of the proposed method.
BibTeX
@article{kong2021accelerated,
  author = {Weiwei Kong and Renato D. C. Monteiro},
  title = {{An Accelerated Inexact Dampened Augmented Lagrangian Method for Linearly-Constrained Nonconvex Composite Optimization Problems}},
  journal = {Comput. Optim. Appl},
  year = {2021},
}
Figure