how does method of multipliers solve the problem of unboundedness of lagrangian and non differentiability of dual problem

Question

$L_ρ(x,z,y) = f(x) + y^T (Ax − b)+\frac{\rho}{2}||Ax - b||2$

$g(y) = \text{min}_x\{L_ρ(x,y)\} $

Method of multipliers claims to have good convergence properties but I wonder how it solves the problems of dual ascent algorithm.

1. How does it tackle the problem of unboundedness of augmented lagrangian in this step since it the min value can go to negative infinity
   $x^{k+1} = \text{argmin}_xL_ρ(x,y^k)$
2. How does it tackle non-differentiability of dual-function(g(y)) since using subgradient ascent causes slow convergence in this step $y^{k+1} = y^k + grad(g(y))$

Answer 1

Note that ADMM uses alternating updates, which means that in each iteration you fix $y$ then update $x$ and vice versa. Similar extensions are possible if you have multiple blocks.

In this paragraph, I assume that $y$ is fixed. The unboundedness is a potential scenario for the $x$ update. But, typically the function $L_{\rho}$ is assumed to be lower bounded. For example, you can achieve this by assuming $f$ is coercive (which implies that level sets are bounded, thus infimum can be potentially attained). You can also achieve lower boundedness of $L_{\rho}$ even when $f$ is not coercive, for example, when $f$ is linear. This is due to the penalty term, which is coercive.

Regarding dual update, after $x$ is fixed, the function is continuous with respect to $y$. Thus, the subdifferential coincides with the singleton which is $\{\nabla g(y)\}$. So, you can directly use gradient.