Abstract
We propose a new first-order augmented Lagrangian algorithm ALCC for solving convex conic programs of the form min{rho(x)+gamma(x): Ax-b in K, x in chi}, where rho and gamma are closed convex functions, and gamma has a Lipschitz continuous gradient, A is mxn real matrix, K is a closed convex cone, and chi is a "simple" convex compact set such that optimization problems of the form min{rho(x)+|x-x0|_2^2: x in chi} can be efficiently solved for any given x0. We show that any limit point of the primal ALCC iterates is an optimal solution of the conic convex problem, and the dual ALCC iterates have a unique limit point that is a Karush-Kuhn-Tucker (KKT) point of the conic program. We also show that for any epsilon>0, the primal ALCC iterates are epsilon-feasible and epsilon optimal after O(log(1/epsilon)) iterations which require solving O(1/epsilon log(1/epsilon)) problems of the form min{rho(x)+|x-x0|_2^2: x in chi}.
Introduction
Conic convex programming is a versatile framework that encompasses linear, quadratic, and semidefinite programming, making it a cornerstone of modern machine learning, signal processing, and engineering design. As datasets and problem dimensions grow, traditional solvers—specifically Interior Point Methods (IPMs)—face significant scalability hurdles. While IPMs are robust and converge in few iterations, each iteration requires a computationally expensive matrix factorization (e.g., Cholesky decomposition). For high-dimensional problems where the decision variable $x$ reaches millions of dimensions, these factorizations become prohibitive in terms of both memory and time.
To address this, researchers have pivoted toward first-order methods that rely solely on gradient information. However, many existing first-order approaches for conic programming require the constraint matrix $A$ to satisfy strict regularity conditions, such as being surjective or full rank. In practical applications, constraints are frequently redundant or poorly conditioned, leading to failure or slow convergence in standard algorithms. This paper introduces the Augmented Lagrangian for Conic Convex (ALCC) algorithm to overcome these limitations.
The ALCC Algorithm
The ALCC algorithm is designed to solve large-scale conic programs by decomposing the primary problem into a sequence of simpler, inexact subproblems. The approach centers on four key components:
- The Penalty Lagrangian: Instead of enforcing hard constraints ($Ax - b \in K$), the algorithm incorporates the constraint into the objective function using a penalty based on the distance to the cone $K$.
- Inexact Subproblem Solvers: Unlike traditional methods that require exact solutions for subproblems, ALCC utilizes an Accelerated Proximal Gradient (APG) method (a variant of FISTA) to solve subproblems inexactly. This significantly reduces the computational burden per iteration.
- Dynamic Parameter Control: The algorithm carefully manages the growth of the penalty parameter ($\mu_k$) and the tightening of the sub-optimality tolerance ($\alpha_k$). This balance ensures that the sequence of inexact solutions eventually converges to the global optimum.
- Projection onto Simple Sets: ALCC assumes that the variable $x$ is constrained to a "simple" compact convex set $\chi$ (such as a box or simplex). This ensures that the proximal steps—the core computational unit of the algorithm—can be performed efficiently.
Theoretical Convergence and Complexity
A primary contribution of this work is the rigorous proof of convergence without requiring the surjectivity of the constraint matrix $A$. This makes ALCC significantly more robust than previous state-of-the-art methods like FALC.
Primal and Dual Convergence
The authors demonstrate a two-tier convergence guarantee. First, every limit point of the primal iterates generated by ALCC is an optimal solution to the conic convex problem. Second, the sequence of dual iterates (the multipliers) is shown to converge to a unique Karush-Kuhn-Tucker (KKT) point. This dual convergence is critical for applications where the "shadow prices" or sensitivity of the constraints are as important as the solution itself.
Iteration Complexity
The paper establishes an optimal complexity bound for first-order methods. To achieve $\epsilon$-feasibility and $\epsilon$-optimality, the algorithm requires $O(\log(1/\epsilon))$ outer iterations. The total operation complexity is $O(\epsilon^{-1} \log(\epsilon^{-1}))$. This near-linear scaling with respect to accuracy requirements makes the algorithm highly suitable for large-scale "Big Data" applications where moderate precision is sufficient.
Discussion and Limitations
While ALCC offers a powerful alternative to IPMs, its performance is contingent on the nature of the set $\chi$ and the cone $K$. The algorithm's efficiency is derived from the ability to compute projections onto these sets quickly. If the projection steps themselves require solving complex optimization problems, the first-order advantage is diminished.
Furthermore, the current theoretical framework assumes that the set $\chi$ is compact (bounded). While many real-world problems satisfy this, extending the proofs to unbounded sets remains an area for future research. Finally, while the paper provides theoretical sequences for penalty parameters, practical implementation often requires heuristic tuning to optimize performance for specific hardware architectures or problem instances.
Conclusion
ALCC provides a robust, scalable framework for conic convex programming that bypasses the memory bottlenecks of second-order methods and the regularity requirements of previous first-order methods. By combining the Augmented Lagrangian framework with accelerated proximal gradients, it offers a mathematically sound and practically viable path for solving the next generation of large-scale optimization challenges.
Summary updated