A Smoothed Augmented Lagrangian Framework for Convex Optimization with Nonsmooth Constraints

Abstract Augmented Lagrangian (AL) methods have proven remarkably useful in solving optimization problems with complicated constraints. The last decade has seen the development of overall complexity guarantees for inexact AL variants. Yet, a crucial gap persists in addressing nonsmooth convex constraints. To this end, we present a smoothed augmented Lagrangian (AL) framework where nonsmooth terms are progressively smoothed with a smoothing parameter $$\eta _k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>η</mml:mi> <mml:mi>k</mml:mi> </mml:msub> </mml:math> . The resulting AL subproblems are $$\eta _k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>η</mml:mi> <mml:mi>k</mml:mi> </mml:msub> </mml:math> -smooth, allowing for leveraging accelerated schemes. By a careful selection of the inexactness level $$\epsilon _k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>ϵ</mml:mi> <mml:mi>k</mml:mi> </mml:msub> </mml:math> (for inexact subproblem resolution), the penalty parameter $$\rho _k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>ρ</mml:mi> <mml:mi>k</mml:mi> </mml:msub> </mml:math> , and smoothing parameter $$\eta _k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>η</mml:mi> <mml:mi>k</mml:mi> </mml:msub> </mml:math> at epoch k , we derive rate and complexity guarantees of $$\tilde{\mathcal {O}}(1/\varvec{\varepsilon }^{3/2})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mover> <mml:mi>O</mml:mi> <mml:mo>~</mml:mo> </mml:mover> <mml:mrow> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:msup> <mml:mrow> <mml:mi>ε</mml:mi> </mml:mrow> <mml:mrow> <mml:mn>3</mml:mn> <mml:mo>/</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:msup> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> and $$\tilde{\mathcal {O}}(1/\varvec{\varepsilon })$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mover> <mml:mi>O</mml:mi> <mml:mo>~</mml:mo> </mml:mover> <mml:mrow> <mml:mo>(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>/</mml:mo> <mml:mrow> <mml:mi>ε</mml:mi> </mml:mrow> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> in convex and strongly convex regimes for computing an $$\varvec{\varepsilon }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ε</mml:mi> </mml:mrow> </mml:math> -optimal solution, when $$\rho _k$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>ρ</mml:mi> <mml:mi>k</mml:mi> </mml:msub> </mml:math> increases at a geometric rate, a significant improvement over the best available guarantees for AL schemes for convex programs with nonsmooth constraints. Analogous guarantees are developed for settings with $$\rho _k = \rho $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>ρ</mml:mi> <mml:mi>k</mml:mi> </mml:msub> <mml:mo>=</mml:mo> <mml:mi>ρ</mml:mi> </mml:mrow> </mml:math> as well as $$\eta _k = \eta $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>η</mml:mi> <mml:mi>k</mml:mi> </mml:msub> <mml:mo>=</mml:mo> <mml:mi>η</mml:mi> </mml:mrow> </mml:math> . Preliminary numerics on a fused Lasso problem display promise.