Tutte colloquium-R. Tyrell Rockafellar

Title: Problem Decomposition in Optimization:  Algorithmic Advances Beyond ADMM

Abstract:

Decomposition schemes like those coming from ADMM typically start by posing a separable-type problem in the Fenchel duality format.  They then pass to an augmented Lagrangian, which however can interfere with the separability and cause a slow-down.  Progressive decoupling offers a more flexible approach which can utilize augmented Lagrangians while maintaining decomposability.  Based on a variable metric extension of the proximal point algorithm that's applied in a twisted sort of way, progressive decoupling benefits from stopping criteria which can guarantee convergence despite inexact minimization in each iteration.   The convergence is generically at a linear rate, and for convex problems, is global. But the method also works for nonconvex problems when initiated close enough to a point that satisfies a natural extension of the strong sufficient condition for local optimality known from nonlinear programming.

This talk is held as part of the 26^th Annual Midwest Optimization Meeting (“MOM26”).