Augmented Lagrangian and Proximal Point Algorithm¶
Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming (1976 R.T. Rockafellar)
From method of multipliers to proximal method of multipliers.
For solving a inequalities constrained convex optimization problem (P, for ‘primal’):
\[\begin{split}\begin{align*}
&minimize \quad f_{0}(x) \\
&subject\ to \quad f_{i}(x) \le 0, \ i = 1,...,m
\end{align*}\end{split}\]
1. Proximal point algorithm for P : primal¶
Proximal operator:
\[f_{0}^{k}(x) = f_{0}(x) + (1/2c_{k})\| x- x^{k}\|_{2}^{2}\]
For this modification, we have a stronger convexity, as we have :
\[f_{0}^{k}((1-\lambda)x + \lambda x') \le (1-\lambda)f_{0}^{k}(x) + \lambda f_{0}^{k}(x') - (\lambda(1-\lambda)/2c_{k})\| x- x'\|_{2}^{2}\]
- In many algorithms, strong convexity is a boon to good convergence and makes possible more convenient stopping criteria, including estimates of how far one is from a minimum point.
- Can reduce trouble when solving the problem : as the infimum may not be attained at all or not attained uniquely, this make is harder to generate simultaneously an asymptotically minimizing sequence for (P) itself.
- The separability of the kind essential to decomposition methods is perserved.
2. Proximal point algorithm for D : dual¶
Method of multipliers, Augmented lagrangian
