Using Subproblem Objective Gaps in Inexact Augmented Lagrangian and ADMM Algorithms, with Applications to Stochastic Mixed Integer Programming

2026/07/27 by Jonathan Eckstein
Mathematics · #math.OC

paper · pdf

Abstract

Through a "partial strong convexity" lemma, this paper shows how bounds on subproblem objective value suboptimality can be used in inexact augmented Lagrangian methods and ADMM algorithms. The ADMM result uses a small but important refinement on a long-standing criterion for approximately solving subproblems. The results enable two new approaches to computing Lagrangian bounds on the optimal values of stochastic mixed-integer programming problems, with simpler convergence analysis than the prior state of the art. In each case, the subproblems are solved by variants of the classical Frank-Wolfe algorithm. However, as compared to prior methods of the same type, there is much more freedom in the choice of Frank-Wolfe variant.

Related

• Two Innovations in Inexact Augmented Lagrangian Methods for Convex Optimization
• Combining Progressive Hedging with a Frank-Wolfe Method to Compute Lagrangian Dual Bounds in Stochastic Mixed-Integer Programming
• The Augmented Lagrangian Methods: Overview and Recent Advances
• Solving Stochastic Optimization with Expectation Constraints Efficiently by a Stochastic Augmented Lagrangian-Type Algorithm
• SI-ADMM: A Stochastic Inexact ADMM Framework for Stochastic Convex Programs