Source-linked AI summary
An inertial alternating direction method of multipliers
Radu Ioan Bot, Ernö Robert Csetnek
TL;DR
Classical ADMM is not a fully splitting method because its x-update contains Ax. This paper derives inertial ADMM from inertial Douglas–Rachford splitting and studies its convergence for primal–dual convex problems in Hilbert spaces, extending the approach to finite sums of convex functions.
Problem
Classical ADMM’s x-update contains Ax, so the scheme is not a fully splitting algorithm.
Source: §1 · p. 2Method
Results
The analysis establishes convergence properties for generated iterates and objective values, and extends the approach to finite-sum convex minimization and its Fenchel-type dual.
Source: §1 · p. 2, §4 · pp. 12, 14Takeaways & Limitations
The paper provides inertial ADMM schemes for primal–dual convex optimization, including problems whose objective is a finite sum of convex functions.
Source: §1 · p. 2Classical ADMM’s x-update contains Ax, which means the scheme is not a fully splitting algorithm.
Source: §1 · p. 2
Abstract
from arXiv · showhide
In the context of convex optimization problems in Hilbert spaces, we induce inertial effects into the classical ADMM numerical scheme and obtain in this way so-called inertial ADMM algorithms, the convergence properties of which we investigate into detail. To this aim we make use of the inertial version of the Douglas-Rachford splitting method for monotone inclusion problems recently introduced in [12], in the context of concomitantly solving a convex minimization problem and its Fenchel dual. The convergence of both sequences of the generated iterates and of the objective function values is addressed. We also show how the obtained results can be extended to the treating of convex minimization problems having as objective a finite sum of convex functions.
1 Introduction
The introduction presents inertial ADMM as an extension of classical ADMM, drawing on inertial proximal-point and Douglas–Rachford methods. It previews convergence analysis for primal–dual problems in Hilbert spaces and an extension to finite sums of convex functions.
1 Introduction
- Classical ADMM’s x-update contains Ax, so the scheme is not a fully splitting algorithm like the cited primal–dual methods.The introduction also notes applications including location problems, lasso image processing, statistics, and support-vector-machine classification.Source: §1 · p. 2
- Inertial effects use the previous two iterates, following the paper’s inertial proximal-point approach.The authors connect these schemes to time discretizations of second-order differential inclusions.Source: §1 · p. 2
- The method combines inertial Douglas–Rachford splitting with ADMM techniques to solve a convex problem and its Fenchel dual in Hilbert spaces.The paper addresses convergence of both generated iterates and objective-function values, and recovers classical ADMM as a special case.Source: §1 · p. 2
- The paper also develops inertial ADMM algorithms and convergence statements for minimizing finite sums of convex functions and their Fenchel-type duals.The stated aim is to evaluate each function in the objective separately in the algorithmic scheme.Source: §1 · p. 2
2 Preliminaries
The preliminaries establish the operator and convex-analysis notation used in the convergence arguments. They also recall an inertial Douglas–Rachford method as the basis for the later ADMM construction.
2 Preliminaries
- The section defines monotone operators, their resolvents, and weak versus strong convergence notation used in the analysis.For a maximally monotone operator, the resolvent is single-valued; the adjoint notation is also specified for continuous linear operators.Source: §2 · p. 3
- Convex-analysis preliminaries connect subdifferentials with conjugate functions and identify proximal points with resolvents of subdifferentials.For an indicator of a nonempty closed convex set, the proximal point operator is the orthogonal projection onto that set.Source: §2 · p. 3
- The recalled inertial Douglas–Rachford scheme uses two prior iterates and resolvent updates, with strong convergence of y and v when either operator is uniformly monotone.Its assumptions bound the inertial parameters and constrain the relaxation parameters; the theorem also states convergence properties for the generated sequences.Source: §2 · p. 4
3 Inertial ADMM
The section formulates an inertial ADMM algorithm for a convex optimization problem and its Fenchel-type dual in Hilbert spaces. Under stated existence, regularity, and operator conditions, it establishes convergence properties for the primal–dual iterates and objective values.
3 Inertial ADMM
- The main result formulates inertial ADMM for a primal–dual convex optimization pair in Hilbert spaces.The primal problem minimizes a proper, convex, lower semicontinuous function plus another such function composed with a continuous linear operator.Source: §3 · p. 5
- Algorithm 5 uses inertial and relaxation parameters, and assumes an optimal primal solution, a regularity condition, and hypothesis (H) on the operator.Hypothesis (H) ensures the x-iterates are well defined; in finite dimensions it is equivalent to full column rank when the operator’s range condition in the passage holds.Source: §3 · pp. 6–7
- Setting all inertial parameters to zero recovers the error-free classical ADMM, and setting each relaxation parameter to one gives classical ADMM.Source: §3 · p. 7
- Under the theorem’s assumptions, the generated pair includes a primal optimizer and a dual optimizer, with equal optimal values and convergence of the primal and dual objective values.The theorem states v(P) = v(D) and gives the limiting dual-objective expression.Source: §3 · p. 7
- If g* is uniformly convex, the dual iterates y converge strongly to the unique dual optimizer.The section also states strong convergence conditions involving strong convexity of f* and a condition on L.Source: §3 · pp. 7, 11
- In infinite-dimensional spaces, the proof needs an additional construction because weak convergence alone does not justify the required limit passage for the operator graph.The passage contrasts this with finite dimensions, where direct limits suffice.Source: §3 · p. 11
4 The minimization of a finite sum of convex functions
This section extends inertial ADMM to finite-sum convex minimization by reformulating the problem in a product space, yielding two algorithm variants and corresponding convergence statements for primal-dual solutions.
4 The minimization of a finite sum of convex functions
- The section derives two inertial ADMM algorithms for minimizing a finite sum, with each component function evaluated separately.The second variant is obtained by interchanging the roles of f and g.Source: §4 · pp. 11, 12, 15
- A coercive component function and remaining functions bounded from below are one stated sufficient condition for the primal problem to have an optimal solution.The passage states that under these conditions the objective is coercive.Source: §4 · p. 12
- The algorithms follow by reformulating the finite-sum problem in a product space and applying the earlier inertial ADMM scheme.The reformulation identifies the corresponding Fenchel dual and translates its optimality conditions to the finite-sum setting.Source: §4 · pp. 12–13
- Under existence of a primal optimum and regularity condition (60), the convergence theorems provide primal and dual solutions satisfying the optimality conditions.The conditions identify the primal solution as optimal for (P) and the dual solution as optimal for (D).Source: §4 · pp. 12, 14
- When every f_i is strongly convex, the generated dual sequences converge strongly to the unique dual optimum.The convergence theorems also state that the primal and dual solutions satisfy the finite-sum optimality conditions.Source: §4 · p. 14