AUGMENTED LAGRANGIAN AND PROXIMAL ALTERNATING DIRECTION METHODS OF MULTIPLIERS IN HILBERT SPACES. APPLICATIONS TO GAMES, PDE'S AND CONTROL

We consider alternating minimization algorithms based on an augmented Lagrangian approach in order to solve convex structured minimization problems. Our approach, which stems from the seminal work of Glowinski and allied, relies on an alternate proximal minimization/maximization procedure applied to the augmented Lagrangian formulation of the problem. We consider a splitting algorithm in which proximal minimization steps are performed alternatively on the primal variables x and y and then a proximal maximization step is performed on the dual variable z. The proximal regularization terms which asymptotically vanish, induce dissipative effects which are similar to friction in mechanics, anchoring and inertia in decision sciences. They play a crucial role in the convergence of the process. Just assuming that the set of equilibria is non empty, it is proved that, for each initial data, the proximal-like algorithm generates a sequence which weakly converges to a saddle point of the augmented Lagrangian, or equivalently of the Lagrangian function. So doing, one obtains both a solution of the problem and a corresponding Lagrange multiplier of the constraint. Applications are given in best response dynamics for potential games, domain decomposition for PDE's, and optimal control of variational inequalities.