On the convergence properties of a majorized ADMM for linearly constrained convex optimization problems with coupled objective functions

Ying Cui, Xudong Li, Defeng Sun, Kim-Chuan ToharXiv 2015 · DOI · arXiv

Introduction

The Alternating Direction Method of Multipliers (ADMM) has long been a staple in large-scale optimization, particularly for problems that can be decomposed into independent, separable components (e.g., $f(x) + g(y)$). However, many contemporary problems in quadratic programming and regularized regression involve "coupled" objective functions where a smooth term $\phi(x, y)$ links the variables together.

In such cases, the standard ADMM convergence proofs often fail. Historically, practitioners were forced to either use very small step sizes—sacrificing efficiency—or rely on heuristics without theoretical guarantees. This paper provides a rigorous theoretical foundation for a Majorized ADMM designed specifically to handle these coupled objectives while maintaining the high performance associated with large step lengths.

The Problem: Beyond Separability

Standard ADMM is designed for problems of the form: $$\min \{ f(x) + g(y) \mid Ax + By = c \}$$

When a coupling term $\phi(x, y)$ is introduced, the objective becomes $f(x) + g(y) + \phi(x, y)$. The presence of $\phi(x, y)$ creates "interference" between the $x$ and $y$ updates. Previous research suggested that to ensure convergence in this scenario, the dual update step size (often denoted as $\tau$) had to be significantly restricted. This paper addresses the fundamental question: How can we maintain the efficiency of ADMM using large step sizes while guaranteeing global convergence for coupled problems?

Methodology: Majorization and Proximal Terms

The authors propose a Majorized ADMM framework. Instead of attempting to minimize the complex coupled objective directly in each iteration, the algorithm minimizes a "majorant" function—an upper bound that is easier to solve but remains locally faithful to the original function.

Key Technical Components

  1. Majorization of the Smooth Term: The algorithm applies a second-order Taylor-like expansion to the smooth coupled function $\phi(u, v)$. By incorporating proximal terms (positive semidefinite operators $S$ and $T$), the authors ensure that the resulting subproblems are well-behaved and computationally tractable.
  2. Generalized Mean-Value Theorem: A significant hurdle in coupled optimization is controlling the "cross terms" that arise during variable updates. The authors utilize Clarke’s generalized Hessian and nonsmooth analysis to bound the errors introduced by the coupling. This mathematical framework allows for a much finer control over the algorithm's trajectory than previous methods.
  3. Large Step Lengths: One of the paper's most impactful findings is that the dual step length $\tau$ can be as large as the golden ratio $(\approx 1.618)$. This matches the efficiency of standard 2-block ADMM for separable problems, proving that coupling does not inherently necessitate slower step sizes if majorization is applied correctly.

Theoretical Insights and Results

The paper establishes several critical convergence properties for the proposed algorithm:

  • Global Convergence: Under mild conditions regarding the majorization operators and the Lipschitz continuity of the gradient of $\phi$, the algorithm is guaranteed to converge to a global optimal solution.
  • Iteration Complexity ($O(1/k)$): The authors provide complexity bounds for both ergodic and non-ergodic cases.
  • Non-Ergodic Rate: The Karush-Kuhn-Tucker (KKT) residual—a measure of how close the current iterate is to optimality—improves at a rate of $O(1/k)$.
  • Ergodic Rate: The average of the iterates (the ergodic mean) also converges at a rate of $O(1/k)$ with respect to primal feasibility and the objective function value.
  • Quadratic Simplification: For problems where the coupling is purely quadratic, the conditions for convergence simplify significantly, essentially aligning with the requirements for standard semi-proximal ADMM.

Limitations and Future Directions

While the paper provides a robust foundation for 2-block problems, it primarily focuses on the dual-variable update and primal convergence. The authors note that while Schur complement techniques might extend these results to multi-block problems, the explicit analysis for more than two blocks remains outside the scope of this work. Additionally, while the theory supports a large step length, the optimal selection of proximal operators $S$ and $T$ for specific practical applications remains an open area for empirical study.

Conclusion

By bridging the gap between majorization techniques and ADMM, this paper demonstrates that coupled convex optimization problems do not require a compromise on algorithmic efficiency. The use of the generalized Mean-Value Theorem provides a powerful tool for handling non-separable objectives, ensuring that the "golden ratio" step size remains a viable and theoretically sound choice for complex optimization tasks.

Summary updated

Abstract

In this paper, we establish the convergence properties for a majorized alternating direction method of multipliers (ADMM) for linearly constrained convex optimization problems whose objectives contain coupled functions. Our convergence analysis relies on the generalized Mean-Value Theorem which plays an important role to properly control the cross terms due to the presence of coupled objective functions. Our results in particular show that directly applying 2-block ADMM with a large step length to the linearly constrained convex optimization problem with a quadratically coupled objective function is convergent under mild conditions. We also provide several iteration complexity results for the algorithm.
BibTeX
@misc{cui2015convergence,
  author = {Ying Cui and Xudong Li and Defeng Sun and Kim-Chuan Toh},
  title = {{On the convergence properties of a majorized ADMM for linearly constrained convex optimization problems with coupled objective functions}},
  year = {2015},
  eprint = {1502.00098},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1502.00098},
}
Figure