Smoothness of the Augmented Lagrangian Dual in Convex Optimization

This paper focuses on the general linearly constrained optimization problem: ${\min }_{x\in {\mathbb{R}}^d}f(x)\text{ s.t. }Ax=b$, where $f:{\mathbb{R}}^d\to \mathbb{R}\cup \{+\mathrm{\infty }\}$ is a closed proper convex function, $A\in {\mathbb{R}}^{p\times d}$, and $b\in {\mathbb{R}}^p$. We define the standard dual function $\phi (\lambda )={\inf }_x\{f(x)+⟨\lambda ,Ax-b⟩\}$, the augmented Lagrangian ${\mathcal{L}}_{\rho }(x,\lambda )=f(x)+⟨\lambda ,Ax-b⟩+\frac{\rho }{2}\mathrm{\parallel }Ax-b{\mathrm{\parallel }}^2$ ($\rho >0$), and the augmented Lagrangian dual function ${\phi }_{\rho }(\lambda )={\inf }_x{\mathcal{L}}_{\rho }(x,\lambda )$. Under the fundamental condition that $\text{dom }\phi \mathrm{\ne }\mathrm{\varnothing }$, we establish that: (1) ${\phi }_{\rho }$ is $\frac{1}{\rho }$-smooth everywhere; and (2) the solution to ${\min }_{x\in {\mathbb{R}}^d}{\mathcal{L}}_{\rho }(x,\lambda )$ exists for any $\lambda \in {\mathbb{R}}^p$. These theoretical findings substantially weaken the stringent assumptions typically imposed in the literature to ensure such properties.