Chapter 15 — ADMM
Proofs omitted. Hover over highlighted terms to see their Lean types.
Algorithm 15.1
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Algorithm 15.1: given a positive parameter ρ and the current dual iterate yᵏ, the next iterate yᵏ⁺¹ is chosen from the arg min set of the ADMM dual objective h₁^*(-Aᵀ y) + h₂^*(-Bᵀ y) + ⟪c, y⟫ + (1 / (2ρ)) ‖y - yᵏ‖², realized through the canonical Chapter 15 dual owner admm_dual_objective and the canonical whole-space argmin-set owner unconstrained_problem_solutions.
universe u v w
variable {X : Type u} {Z : Type v} {Y : Type w}
variable [AddCommGroup X] [Module ℝ X]
variable [AddCommGroup Z] [Module ℝ Z]
variable [NormedAddCommGroup Y] [InnerProductSpace ℝ Y]
abbrev admm_dual_update
(ρ : PosReal)
(h₁ : X → EReal) (h₂ : Z → EReal)
(A : X →ₗ[ℝ] Y) (B : Z →ₗ[ℝ] Y) (c yk : Y) : Set Y :=
unconstrained_problem_solutions (admm_dual_update_objective ρ h₁ h₂ A B c yk)Definition 15.1
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 15.1: the ADMM primal problem H_opt = min { H(x, z) ≡ h₁(x) + h₂(z) : A x + B z = c }, where h₁ and h₂ are proper closed convex functions, is represented by the infimum of the canonical constrained objective on X × Z built from H[h₁, h₂] and the affine feasible set A x + B z = c.
universe u v w
variable {X : Type u} {Z : Type v} {Y : Type w}
variable {𝕜 : Type*} [Semiring 𝕜]
variable [AddCommMonoid X] [Module 𝕜 X]
variable [AddCommMonoid Z] [Module 𝕜 Z]
variable [AddCommMonoid Y] [Module 𝕜 Y]
def admm_problem_value
(h₁ : X → EReal) (h₂ : Z → EReal)
(A : X →ₗ[𝕜] Y) (B : Z →ₗ[𝕜] Y) (c : Y) : EReal :=
sInf (Set.range (constrained_problem_objective
(H[h₁, h₂]) (admm_feasible_set A B c)))Proposition 15.1
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Proposition 15.1: for the canonical ADMM dual-update objective from equation (15.4), if that objective is evaluated at points whose two conjugate-affine terms lie in the interior of their finite domains, then the textbook arg min condition (15.4) is equivalent to the split subdifferential inclusion (15.5).
open InnerProductSpace (toDual toDualMap)
open scoped Pointwise
universe u v w
variable {X : Type u} {Z : Type v} {Y : Type w}
variable [NormedAddCommGroup X] [InnerProductSpace ℝ X] [FiniteDimensional ℝ X]
variable [NormedAddCommGroup Z] [InnerProductSpace ℝ Z] [FiniteDimensional ℝ Z]
variable [NormedAddCommGroup Y] [InnerProductSpace ℝ Y] [FiniteDimensional ℝ Y]
theorem mem_admm_dual_update_iff_zero_mem_split_subdifferential_sum
(ρ : PosReal)
(h₁ : X → EReal) (h₂ : Z → EReal)
(A : X →ₗ[ℝ] Y) (B : Z →ₗ[ℝ] Y) (c yk yNext : Y)
(hy₁ : -A.adjoint yNext ∈ interior (finite_domain (h₁∗)))
(hy₂ : -B.adjoint yNext ∈ interior (finite_domain (h₂∗))) :
yNext ∈ admm_dual_update ρ h₁ h₂ A B c yk ↔
0 ∈ (-A) '' euclideanSubdifferential (h₁∗) (-A.adjoint yNext) +
(-B) '' euclideanSubdifferential (h₂∗) (-B.adjoint yNext) +
{c + (1 / (ρ : ℝ)) • (yNext - yk)}Theorem 15.1
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 15.1 (1): if Assumption 15.2 holds for the AD-PMM problem, then the optimal values of the primal problem (15.1) and dual problem (15.2) coincide.
universe u v w
open scoped Pointwise
variable {X : Type u} {Z : Type v} {Y : Type w}
variable [NormedAddCommGroup X] [InnerProductSpace ℝ X] [FiniteDimensional ℝ X]
variable [NormedAddCommGroup Z] [InnerProductSpace ℝ Z] [FiniteDimensional ℝ Z]
variable [NormedAddCommGroup Y] [NormedSpace ℝ Y]
variable {h₁ : X → EReal} {h₂ : Z → EReal}
variable {A : X →ₗ[ℝ] Y} {B : Z →ₗ[ℝ] Y} {c : Y}
variable {ρ : PosReal} {G : X →ₗ[ℝ] X} {Q : Z →ₗ[ℝ] Z}
variable (h₁_proper : IsProperExtendedRealFunction h₁)
variable (h₂_proper : IsProperExtendedRealFunction h₂)
variable (h₁_convex : is_convex_function h₁)
variable (h₂_convex : is_convex_function h₂)
variable (hqual :
∃ xHat ∈ intrinsicInterior ℝ (effective_domain h₁),
∃ zHat ∈ intrinsicInterior ℝ (effective_domain h₂),
A xHat + B zHat = c)
include h₁_proper h₂_proper h₁_convex h₂_convex hqual
omit h₁_proper h₂_proper h₁_convex h₂_convex hqual
theorem admm_problem_value_eq_admm_dual_problem_value
(hAssump : IsADPMMProblem ρ h₁ h₂ A B G Q c) :
H_opt[h₁, h₂; A, B, c] = admm_dual_problem_value h₁ h₂ A B cAlgorithm 15.2
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Algorithm 15.2: given an initialization y^0 = y0 and a positive penalty parameter ρ, the sequences x, z, and y form an ADMM trajectory when, for every iteration k, the pair (x^(k+1), z^(k+1)) lies in the joint arg min set of h₁(x) + h₂(z) + (ρ / 2) ‖A x + B z - c + (1 / ρ) y^k‖² and the multiplier update satisfies y^(k+1) = y^k + ρ (A x^(k+1) + B z^(k+1) - c).
universe u v w
variable {X : Type u} {Z : Type v} {Y : Type w}
variable [AddCommMonoid X] [Module ℝ X]
variable [AddCommMonoid Z] [Module ℝ Z]
variable [NormedAddCommGroup Y] [NormedSpace ℝ Y]
class IsADMMTrajectory
(ρ : PosReal)
(h₁ : X → EReal) (h₂ : Z → EReal)
(A : X →ₗ[ℝ] Y) (B : Z →ₗ[ℝ] Y) (c : Y)
(x : ℕ → X) (z : ℕ → Z) (y : ℕ → Y) (y0 : Y) : Prop where
y_zero : y 0 = y0
primal_step (k : ℕ) :
(x (k + 1), z (k + 1)) ∈ admm_primal_update_argmin ρ h₁ h₂ A B c (y k)
multiplier_step (k : ℕ) :
y (k + 1) =
admm_multiplier_update ρ A B c (y k) (x (k + 1)) (z (k + 1))Definition 15.2
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 15.2 (1): the ADMM Lagrangian associated with the affine constraint A x + B z = c.
universe u v w
open InnerProductSpace (toDualMap)
variable {X : Type u} {Z : Type v} {Y : Type w}
variable [AddCommMonoid X] [Module ℝ X]
variable [AddCommMonoid Z] [Module ℝ Z]
variable [AddCommGroup Y] [Module ℝ Y]
def admm_lagrangian
(h₁ : X → EReal) (h₂ : Z → EReal)
(A : X →ₗ[ℝ] Y) (B : Z →ₗ[ℝ] Y) (c : Y)
(x : X) (z : Z) (y : Module.Dual ℝ Y) : EReal :=
H[h₁, h₂] (x, z) + (y (A x + B z - c) : EReal)Proposition 15.2
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Proposition 15.2: by the conjugate subgradient theorem, equation (15.5) holds exactly when there are points x^{k+1} and z^{k+1} minimizing the two affine subproblems x ↦ ⟪Aᵀ y^{k+1}, x⟫ + h₁(x) and z ↦ ⟪Bᵀ y^{k+1}, z⟫ + h₂(z) such that y^{k+1} = y^k + ρ (A x^{k+1} + B z^{k+1} - c).
universe u v w
open InnerProductSpace (toDualMap)
variable {X : Type u} {Z : Type v} {Y : Type w}
variable [NormedAddCommGroup X] [InnerProductSpace ℝ X] [FiniteDimensional ℝ X]
variable [NormedAddCommGroup Z] [InnerProductSpace ℝ Z] [FiniteDimensional ℝ Z]
variable [NormedAddCommGroup Y] [InnerProductSpace ℝ Y] [FiniteDimensional ℝ Y]
theorem admm_dual_optimality_condition_iff_exists_primal_argmin_and_affine_update
(ρ : ℝ)
(h₁ : X → EReal) (h₂ : Z → EReal)
(A : X →ₗ[ℝ] Y) (B : Z →ₗ[ℝ] Y) (c yk yNext : Y)
(hPair : IsADMMConvexObjectivePair h₁ h₂) :
admm_dual_optimality_condition ρ h₁ h₂ A B c yk yNext ↔
∃ xNext ∈ unconstrained_problem_solutions (admm_x_subproblem h₁ A yNext),
∃ zNext ∈ unconstrained_problem_solutions (admm_z_subproblem h₂ B yNext),
yNext = yk + ρ • (A xNext + B zNext - c)Theorem 15.2
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Theorem 15.2 (1): the ergodic average objective value satisfies `H(x^(n), z^(n)) - H_opt ≤ (‖x^* - x^0‖_G^2 + (ρ * ‖B (z^* - z^0)‖^2 + ⟪z^* - z^0, Q (z^* - z^0)⟫) + (1 / ρ) (γ + ‖y^0‖)^2) / (2 (n + 1))`, which is the source bound with ‖z^* - z^0‖_C^2 expanded along C = ρ Bᵀ B + Q.
universe u v w uE
open InnerProductSpace (toDual)
open scoped BigOperators
open scoped Gradient
variable {X : Type u} {Z : Type v} {Y : Type w}
variable [NormedAddCommGroup X] [InnerProductSpace ℝ X]
variable [NormedAddCommGroup Z] [InnerProductSpace ℝ Z]
variable [NormedAddCommGroup Y] [InnerProductSpace ℝ Y]
variable [FiniteDimensional ℝ X] [FiniteDimensional ℝ Z] [FiniteDimensional ℝ Y]
variable {h₁ : X → EReal} {h₂ : Z → EReal}
variable {A : X →ₗ[ℝ] Y} {B : Z →ₗ[ℝ] Y} {c : Y}
variable {ρ : PosReal}
variable {G : X →ₗ[ℝ] X} {Q : Z →ₗ[ℝ] Z}
variable {x0 : X} {z0 : Z} {y0 : Y}
variable {x : ℕ → X} {z : ℕ → Z} {y : ℕ → Y}
theorem ad_pmm_ergodic_objective_gap_le
(hAssump : IsADPMMProblem ρ h₁ h₂ A B G Q c)
(hTrajectory : IsADPMMLinearTrajectory ρ h₁ h₂ A B c G Q x0 z0 y0 x z y)
{xStar : X} {zStar : Z}
(hPrimalOpt : IsADPMMPrimalOptimal h₁ h₂ A B c xStar zStar)
{yStar : Y}
(hDualOpt : IsADPMMDualOptimal h₁ h₂ A B c yStar)
{γ : PosReal} (hγ : 2 * ‖yStar‖ ≤ (γ : ℝ))
(n : ℕ) :
(H[h₁, h₂] (ergodicAverage x n, ergodicAverage z n)).toReal -
(H[h₁, h₂] (xStar, zStar)).toReal ≤
(quadraticPenaltyOfLinearMap G (xStar - x0) +
((ρ : ℝ) * ‖B (zStar - z0)‖ ^ (2 : ℕ) +
quadraticPenaltyOfLinearMap Q (zStar - z0)) +
(1 / (ρ : ℝ)) * ((γ : ℝ) + ‖y0‖) ^ (2 : ℕ)) /
(2 * ((n : ℝ) + 1))Algorithm 15.3
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Algorithm 15.3: given initial iterates x^0 = x0, z^0 = z0, y^0 = y0 and a positive penalty parameter ρ, the sequences x, z, and y form an ADMM trajectory when, for every iteration k, x^(k+1) lies in the arg min set from (a), z^(k+1) lies in the arg min set from (b), and y^(k+1) = y^k + ρ (A x^(k+1) + B z^(k+1) - c) as in (c).
universe u v w
variable {X : Type u} {Z : Type v} {Y : Type w}
variable [AddCommMonoid X] [Module ℝ X]
variable [AddCommMonoid Z] [Module ℝ Z]
variable [NormedAddCommGroup Y] [NormedSpace ℝ Y]
class IsADMMAlternatingTrajectory
(ρ : PosReal)
(h₁ : X → EReal) (h₂ : Z → EReal)
(A : X →ₗ[ℝ] Y) (B : Z →ₗ[ℝ] Y) (c : Y)
(x : ℕ → X) (z : ℕ → Z) (y : ℕ → Y)
(x0 : X) (z0 : Z) (y0 : Y) : Prop where
x_zero : x 0 = x0
z_zero : z 0 = z0
y_zero : y 0 = y0
x_step (k : ℕ) :
x (k + 1) ∈ admm_x_update_argmin ρ h₁ A B c (z k) (y k)
z_step (k : ℕ) :
z (k + 1) ∈ admm_z_update_argmin ρ h₂ A B c (x (k + 1)) (y k)
y_step (k : ℕ) :
y (k + 1) =
admm_multiplier_update ρ A B c (y k) (x (k + 1)) (z (k + 1))Definition 15.3
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 15.3: the augmented Lagrangian associated with the ADMM problem is L_ρ(x, z; y) = h₁(x) + h₂(z) + ⟪y, A x + B z - c⟫ + (ρ / 2) ‖A x + B z - c‖².
universe u v w
open InnerProductSpace (toDualMap)
variable {X : Type u} {Z : Type v} {Y : Type w}
variable [AddCommMonoid X] [Module ℝ X]
variable [AddCommMonoid Z] [Module ℝ Z]
variable [NormedAddCommGroup Y] [InnerProductSpace ℝ Y]
def admm_augmented_lagrangian
(h₁ : X → EReal) (h₂ : Z → EReal)
(A : X →ₗ[ℝ] Y) (B : Z →ₗ[ℝ] Y) (c : Y) (ρ : ℝ)
(x : X) (z : Z) (y : Y) : EReal :=
admm_lagrangian h₁ h₂ A B c x z (toDualMap ℝ Y y) +
(((ρ / 2) * ‖A x + B z - c‖ ^ (2 : ℕ) : ℝ) : EReal)Proposition 15.3
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Proposition 15.3: equation (15.5) is equivalent to the existence of primal witnesses x^(k+1) and z^(k+1) satisfying the affine update (15.6) together with the Euclidean subdifferential conditions corresponding to (15.7) and (15.8).
universe u v w
variable {X : Type u} {Z : Type v} {Y : Type w}
variable [NormedAddCommGroup X] [InnerProductSpace ℝ X] [FiniteDimensional ℝ X]
variable [NormedAddCommGroup Z] [InnerProductSpace ℝ Z] [FiniteDimensional ℝ Z]
variable [NormedAddCommGroup Y] [InnerProductSpace ℝ Y] [FiniteDimensional ℝ Y]
theorem admm_dual_optimality_condition_iff_exists_primal_subgradient_and_affine_update
(ρ : ℝ)
(h₁ : X → EReal) (h₂ : Z → EReal)
(A : X →ₗ[ℝ] Y) (B : Z →ₗ[ℝ] Y) (c yk yNext : Y)
(hPair : IsADMMConvexObjectivePair h₁ h₂) :
admm_dual_optimality_condition ρ h₁ h₂ A B c yk yNext ↔
∃ xNext,
-A.adjoint yNext ∈ euclideanSubdifferential h₁ xNext ∧
∃ zNext,
-B.adjoint yNext ∈ euclideanSubdifferential h₂ zNext ∧
yNext = yk + ρ • (A xNext + B zNext - c)Algorithm 15.4
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Algorithm 15.4: given initial iterates x^0 = x0, z^0 = z0, y^0 = y0, a positive penalty parameter ρ, and quadratic proximal penalties G and Q, the sequences x, z, and y form an AD-PMM trajectory when, for every iteration k, x^(k+1) minimizes h₁(x) + (ρ / 2) ‖A x + B z^k - c + (1 / ρ) y^k‖² + (1 / 2) G(x - x^k), z^(k+1) minimizes h₂(z) + (ρ / 2) ‖A x^(k+1) + B z - c + (1 / ρ) y^k‖² + (1 / 2) Q(z - z^k), and y^(k+1) = y^k + ρ (A x^(k+1) + B z^(k+1) - c).
universe u v w
variable {X : Type u} {Z : Type v} {Y : Type w}
variable [AddCommGroup X] [Module ℝ X]
variable [AddCommGroup Z] [Module ℝ Z]
variable [NormedAddCommGroup Y] [NormedSpace ℝ Y]
class IsADPMMTrajectory
(ρ : PosReal)
(h₁ : X → EReal) (h₂ : Z → EReal)
(A : X →ₗ[ℝ] Y) (B : Z →ₗ[ℝ] Y) (c : Y)
(G : QuadraticForm ℝ X) (Q : QuadraticForm ℝ Z)
(x0 : X) (z0 : Z) (y0 : Y)
(x : ℕ → X) (z : ℕ → Z) (y : ℕ → Y) : Prop where
/-- The `x`-sequence starts from the prescribed initial point `x0`. -/
x_zero : x 0 = x0
/-- The `z`-sequence starts from the prescribed initial point `z0`. -/
z_zero : z 0 = z0
/-- The multiplier sequence starts from the prescribed initial point `y0`. -/
y_zero : y 0 = y0
/-- At each iteration `k`, the next primal block `x^(k+1)` is chosen from the step-(a) `arg min`
set. -/
x_step (k : ℕ) :
x (k + 1) ∈ ad_pmm_x_update_argmin ρ h₁ A B c (z k) (y k) G (x k)
/-- At each iteration `k`, the next primal block `z^(k+1)` is chosen from the step-(b) `arg min`
set. -/
z_step (k : ℕ) :
z (k + 1) ∈ ad_pmm_z_update_argmin ρ h₂ A B c (x (k + 1)) (y k) Q (z k)
/-- At each iteration `k`, the multiplier satisfies the affine step-(c) update. -/
y_step (k : ℕ) :
y (k + 1) = admm_multiplier_update ρ A B c (y k) (x (k + 1)) (z (k + 1))Definition 15.4
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 15.4: Assumption 15.2 for the AD-PMM problem means that h₁ and h₂ form an ADMM convex objective pair, the proximal operators G and Q are symmetric positive semidefinite, every proximal one-block subproblem from clause (D) attains a minimizer, there exist x̂ ∈ ri(dom h₁) and ẑ ∈ ri(dom h₂) with A x̂ + B ẑ = c, and the canonical primal optimal set constrained_problem_solutions (H[h₁, h₂]) (admm_feasible_set A B c) is nonempty. The primal optimal value remains the canonical owner H_opt[h₁, h₂; A, B, c].
universe u v w
variable {X : Type u} {Z : Type v} {Y : Type w}
variable [NormedAddCommGroup X] [InnerProductSpace ℝ X]
variable [NormedAddCommGroup Z] [InnerProductSpace ℝ Z]
variable [NormedAddCommGroup Y] [NormedSpace ℝ Y]
class IsADPMMProblem
(ρ : PosReal)
(h₁ : X → EReal) (h₂ : Z → EReal)
(A : X →ₗ[ℝ] Y) (B : Z →ₗ[ℝ] Y)
(G : X →ₗ[ℝ] X) (Q : Z →ₗ[ℝ] Z)
(c : Y) : Prop
extends IsADMMConvexObjectivePair h₁ h₂ where
G_positive : LinearMap.IsPositive G
Q_positive : LinearMap.IsPositive Q
x_subproblem_argmin_nonempty (a : X) :
(unconstrained_problem_solutions (adpmm_proximal_objective ρ h₁ A G a)).Nonempty
z_subproblem_argmin_nonempty (b : Z) :
(unconstrained_problem_solutions (adpmm_proximal_objective ρ h₂ B Q b)).Nonempty
ri_qualification :
∃ xHat ∈ intrinsicInterior ℝ (effective_domain h₁),
∃ zHat ∈ intrinsicInterior ℝ (effective_domain h₂),
A xHat + B zHat = c
optimal_set_nonempty :
(constrained_problem_solutions (H[h₁, h₂]) (admm_feasible_set A B c)).Nonempty
-- `lean_leansearch` was unavailable in this agent environment; the companion-instance choice
-- follows the local `Fact`-exposure pattern used in Chapter 10 assumption/problem owners.Algorithm 15.5
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Algorithm 15.5: given initial points x^0 = x0, z^0 = z0, y^0 = y0, a positive penalty parameter ρ, and admissible linearization parameters α and β satisfying the operator-norm forms of ρ λ_max(Aᵀ A) ≤ α and ρ λ_max(Bᵀ B) ≤ β, the sequences x, z, and y form an AD-LPMM trajectory when, for every iteration k, x^(k+1) satisfies the proximal update in (a), z^(k+1) satisfies the proximal update in (b), and y^(k+1) satisfies the affine update in (c).
universe u v w
variable {X : Type u} {Z : Type v} {Y : Type w}
variable [NormedAddCommGroup X] [InnerProductSpace ℝ X] [FiniteDimensional ℝ X]
variable [NormedAddCommGroup Z] [InnerProductSpace ℝ Z] [FiniteDimensional ℝ Z]
variable [NormedAddCommGroup Y] [InnerProductSpace ℝ Y] [FiniteDimensional ℝ Y]
class IsADLPMMTrajectory
(ρ : PosReal)
(A : X →ₗ[ℝ] Y) (B : Z →ₗ[ℝ] Y) (c : Y)
(α : ADLPMMLinearizationParameter ρ A)
(β : ADLPMMLinearizationParameter ρ B)
(h₁ : X → EReal) (h₂ : Z → EReal)
(x : ℕ → X) (z : ℕ → Z) (y : ℕ → Y)
(x0 : X) (z0 : Z) (y0 : Y) : Prop where
x_zero : x 0 = x0
z_zero : z 0 = z0
y_zero : y 0 = y0
x_step (k : ℕ) :
x (k + 1) ∈ adlpmm_x_step h₁ ρ α A B c (x k) (z k) (y k)
z_step (k : ℕ) :
z (k + 1) ∈ adlpmm_z_step h₂ ρ β A B c (x (k + 1)) (z k) (y k)
y_step (k : ℕ) :
y (k + 1) = admm_multiplier_update ρ A B c (y k) (x (k + 1)) (z (k + 1))Algorithm 15.6
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Algorithm 15.6 trajectories are the alternating ADMM trajectories specialized to B = -LinearMap.id and c = 0.
universe u v
variable {X : Type u} {Y : Type v}
variable [AddCommMonoid X] [Module ℝ X]
variable [NormedAddCommGroup Y] [InnerProductSpace ℝ Y]
recall IsADMMAlternatingTrajectoryDefinition 15.6
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 15.6: the linear-composite objective x ↦ f₁(x) + f₂(Ax) is the Chapter 10 composite objective specialized to g := f₂ ∘ A.
universe u v
variable {X : Type u} {Y : Type v}
variable [AddCommMonoid X] [Module ℝ X]
variable [AddCommMonoid Y] [Module ℝ Y]
recall composite_model_objectiveAlgorithm 15.7
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Algorithm 15.7: given initial iterates x^0, w^0, y₂^0 in X, z^0, y₁^0 in Y, and a positive parameter ρ, the sequences x, z, w, y₁, and y₂ follow ADMM version 2 for minimizing f₁(x) + f₂(A x) when each iteration satisfies the displayed linear x-solve, the proximal updates z^(k+1) ∈ prox[((1 / ρ) f₂)] (A x^(k+1) + (1 / ρ) y₁^k) and w^(k+1) ∈ prox[((1 / ρ) f₁)] (x^(k+1) + (1 / ρ) y₂^k), and the two affine multiplier recursions y₁^(k+1) = y₁^k + ρ (A x^(k+1) - z^(k+1)) and y₂^(k+1) = y₂^k + ρ (x^(k+1) - w^(k+1)).
universe u v
open ContinuousLinearMap
open scoped InnerProduct
variable {X : Type u} {Y : Type v}
variable [NormedAddCommGroup X] [InnerProductSpace ℝ X] [CompleteSpace X]
variable [NormedAddCommGroup Y] [InnerProductSpace ℝ Y] [CompleteSpace Y]
class IsADMMSumCompositionTrajectoryV2
(ρ : PosReal) (f₁ : X → EReal) (f₂ : Y → EReal) (A : X →L[ℝ] Y)
(x w y2 : ℕ → X) (z y1 : ℕ → Y)
(x0 w0 y20 : X) (z0 y10 : Y) : Prop where
x_zero : x 0 = x0
w_zero : w 0 = w0
y2_zero : y2 0 = y20
z_zero : z 0 = z0
y1_zero : y1 0 = y10
x_step (k : ℕ) :
x (k + 1) = admm_sum_composition_v2_x_update ρ A (z k) (y1 k) (w k) (y2 k)
z_step (k : ℕ) :
z (k + 1) ∈ prox[((((1 / ρ : PosReal) : EReal) • f₂))]
(A (x (k + 1)) + (1 / (ρ : ℝ)) • y1 k)
w_step (k : ℕ) :
w (k + 1) ∈ prox[((((1 / ρ : PosReal) : EReal) • f₁))]
(x (k + 1) + (1 / (ρ : ℝ)) • y2 k)
y1_step (k : ℕ) :
y1 (k + 1) = y1 k + (ρ : ℝ) • (A (x (k + 1)) - z (k + 1))
y2_step (k : ℕ) :
y2 (k + 1) = y2 k + (ρ : ℝ) • (x (k + 1) - w (k + 1))Definition 15.7
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 15.7: the problem min_x (f₁ x + f₂ (A x)) is equivalently written as minimizing the ADMM objective H[f₁, f₂] over the graph-feasible pairs satisfying A x = z, equivalently A x - z = 0 when subtraction is available.
open Set
universe u v
variable {X : Type u} {Z : Type v}
-- Proof sketch: identify the graph-feasible set with `univ.graphOn A`; every feasible pair has
-- the form `(x, A x)`, and on that graph `H[f₁, f₂]` agrees with the linear-composite
-- objective, so the two sets of attainable values have the same infimum.
theorem admm_linear_composite_primal_infimum_eq_split_infimum
(f₁ : X → EReal) (f₂ : Z → EReal) (A : X → Z) :
sInf (Set.range (composite_model_objective f₁ (f₂ ∘ A))) =
sInf (Set.image (H[f₁, f₂]) (univ.graphOn A))Algorithm 15.8
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Algorithm 15.8 trajectories are the generic AD-LPMM trajectories specialized to B = -I and c = 0.
universe u v
variable {X : Type u} {Y : Type v}
variable [NormedAddCommGroup X] [InnerProductSpace ℝ X] [FiniteDimensional ℝ X]
variable [NormedAddCommGroup Y] [InnerProductSpace ℝ Y] [FiniteDimensional ℝ Y]
recall IsADLPMMTrajectory
-- Proof sketch: specialize `mem_adlpmm_x_step_iff` from Algorithm 15.5 at `B = -LinearMap.id`
-- and `c = 0`, then simplify the residual `A x^k + (-id) z^k - 0`.Definition 15.8
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 15.8: the basis-pursuit problem (15.28) is the constrained objective with ℓ¹ objective and affine feasible set A x = b.
universe u v
variable {ι : Type u} [Fintype ι]
variable {Y : Type v} [AddCommMonoid Y] [Module ℝ Y]
local notation "X" => EuclideanSpace ℝ ι
def basis_pursuit_problem
(A : X →ₗ[ℝ] Y) (b : Y) : X → EReal :=
constrained_problem_objective (fun x ↦ ((‖x‖₁ : ℝ) : EReal))
(A ⁻¹' ({b} : Set Y))Algorithm 15.9
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Algorithm 15.9 (1) x-iterate sequence for the ℓ¹-regularized least-squares split problem.
universe u v
open scoped RealInnerProductSpace
open scoped SoftThreshold
variable {ι : Type u} {κ : Type v}
variable [Fintype ι] [Fintype κ]
local notation "X" => EuclideanSpace ℝ ι
local notation "Y" => EuclideanSpace ℝ κ
def l1_regularized_least_squares_admm_v2_x
(A : X →ₗ[ℝ] Y) (b : Y) (lam : ℝ) (ρ : PosReal)
(x0 : X) (z0 : Y) (w0 : X) (y10 : Y) (y20 : X) :
ℕ → X :=
fun k ↦ (iterateState A b lam ρ x0 z0 w0 y10 y20 k).xDefinition 15.9
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Definition 15.9: the finite-sum linear-composite objective x ↦ ∑ i, g_i (A_i x) is the Chapter 8 finite-sum owner specialized to the family fun i x ↦ g_i (A_i x).
recall finite_sum_objectiveAlgorithm 15.10
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Algorithm 15.10: the explicit AD-LPMM iterates form the canonical linear-composite trajectory with α = ρ L and β = ρ.
open scoped RealInnerProductSpace
open scoped SoftThreshold
universe u v
variable {ι : Type u} {κ : Type v}
variable [Fintype ι] [Fintype κ]
local notation "X" => EuclideanSpace ℝ ι
local notation "Y" => EuclideanSpace ℝ κ
theorem ad_lpmm_trajectory
(A : X →ₗ[ℝ] Y) (ρ : PosReal) (lam : NNReal)
(hL : 0 < adlpmm_linearization_bound (1 : PosReal) A)
(b : Y) (x0 : X) (z0 y0 : Y) :
IsADLPMMTrajectory
ρ
A
(-LinearMap.id)
0
(ad_lpmm_alpha_parameter A ρ hL)
(ad_lpmm_beta_parameter ρ)
(ad_lpmm_l1_regularizer lam)
(denoising_data_fidelity b)
(ad_lpmm_x A ρ lam hL b x0 z0 y0)
(ad_lpmm_z A ρ lam hL b x0 z0 y0)
(ad_lpmm_y A ρ lam hL b x0 z0 y0)
x0
z0
y0Algorithm 15.11
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Algorithm 15.11: given initial iterates z^0 = z0 and y^0 = y0 and a positive penalty parameter ρ, the sequences x, z, and y form the version-1 ADMM trajectory when, for every iteration k, x^(k+1) belongs to the canonical linear-composite ADMM x-argmin set, z^(k+1) is the canonical shifted soft-threshold update from part (b), and y^(k+1) is the canonical affine multiplier update specialized to A x - z = 0. This is the source-facing view of alternating ADMM specialized to h₁ = 0, h₂(z) = ‖z - b‖₁, B = -I, and c = 0; the source-specific content here is only the trajectory packaging by z⁰ and y⁰.
universe u v
variable {X : Type u} {ι : Type v}
variable [AddCommMonoid X] [Module ℝ X]
variable [Fintype ι]
local notation "Y" => EuclideanSpace ℝ ι
class IsADMMSoftThresholdTrajectoryV1
(ρ : PosReal)
(A : X →ₗ[ℝ] Y)
(b : Y)
(x : ℕ → X)
(z y : ℕ → Y)
(z0 y0 : Y) : Prop where
z_zero : z 0 = z0
y_zero : y 0 = y0
x_step (k : ℕ) :
x (k + 1) ∈
admm_x_update_argmin
ρ
(fun _ : X ↦ (0 : EReal))
A
(-LinearMap.id)
0
(z k)
(y k)
z_step (k : ℕ) :
z (k + 1) = admm_linear_composite_shifted_l1_z_update ρ A b (x (k + 1)) (y k)
y_step (k : ℕ) :
y (k + 1) =
admm_multiplier_update ρ A (-LinearMap.id) 0 (y k) (x (k + 1)) (z (k + 1))Algorithm 15.12
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Algorithm 15.12: the specialized x-solve is exactly the displayed linear-composite ADMM minimizer with the quadratic proximal tether centered at x^k.
open scoped SoftThreshold
open scoped InnerProduct
open ContinuousLinearMap
universe u v
variable {X : Type u} {ι : Type v}
variable [NormedAddCommGroup X] [InnerProductSpace ℝ X] [CompleteSpace X]
variable [Fintype ι]
local notation "E" => EuclideanSpace ℝ ι
theorem admm_linear_composite_v2_x_update_isMinOn_zero
(ρ : PosReal) (A : X →L[ℝ] E) (zk y1k : E) (xk : X) :
IsMinOn
(fun x : X ↦
((((1 / 2 : ℝ) * ‖x - xk‖ ^ (2 : ℕ) : ℝ) : EReal)) +
((((1 / 2 : ℝ) * ‖A x - zk + (1 / (ρ : ℝ)) • y1k‖ ^ (2 : ℕ) : ℝ) : EReal)))
Set.univ
(admm_linear_composite_v2_x_update ρ A zk y1k xk)Algorithm 15.13
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Algorithm 15.13: the explicit iterates form the canonical linear-composite AD-LPMM trajectory for h₁ = 0 and h₂(z) = ‖z - b‖₁, under the source specialization α = ρ L and β = ρ.
open scoped SoftThreshold
universe u v
variable {X : Type u} {ι : Type v}
variable [NormedAddCommGroup X] [InnerProductSpace ℝ X] [FiniteDimensional ℝ X]
variable [Fintype ι]
local notation "E" => EuclideanSpace ℝ ι
theorem ad_lpmm_l1_residual_trajectory
(A : X →ₗ[ℝ] E) (ρ : PosReal)
(hL : 0 < adlpmm_linearization_bound (1 : PosReal) A)
(b : E) (x0 : X) (z0 y0 : E) :
IsADLPMMTrajectory ρ A (-LinearMap.id) 0
(ad_lpmm_l1_residual_alpha_parameter A ρ hL) (ad_lpmm_l1_residual_beta_parameter ρ)
(0 : X → EReal) (admm_linear_composite_shifted_l1_regularizer b)
(ad_lpmm_l1_residual_x A ρ b x0 z0 y0)
(ad_lpmm_l1_residual_z A ρ b x0 z0 y0)
(ad_lpmm_l1_residual_y A ρ b x0 z0 y0)
x0 z0 y0Algorithm 15.14
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Algorithm 15.14: the explicit basis-pursuit iterates form the canonical linear-composite AD-LPMM trajectory with h₁ x = ‖x‖₁, h₂ = δ_ ({b} : Set Y), α = ρ L, β = ρ, and the fixed z^k = b.
open scoped SoftThreshold
universe u v
variable {Y : Type u} {ι : Type v}
variable [NormedAddCommGroup Y] [InnerProductSpace ℝ Y] [FiniteDimensional ℝ Y]
variable [Fintype ι]
local notation "E" => EuclideanSpace ℝ ι
theorem ad_lpmm_basis_pursuit_trajectory
(ρ : PosReal) (A : E →ₗ[ℝ] Y) (b : Y)
(hL : 0 < adlpmm_linearization_bound (1 : PosReal) A)
(x0 : E) (y0 : Y) :
IsADLPMMTrajectory ρ A (-LinearMap.id) 0
(ad_lpmm_basis_pursuit_alpha_parameter A ρ hL) (ad_lpmm_basis_pursuit_beta_parameter ρ)
(ad_lpmm_l1_regularizer (1 : NNReal)) (δ_ ({b} : Set Y))
(ad_lpmm_basis_pursuit_x ρ A hL b x0 y0) (fun _ ↦ b)
(ad_lpmm_basis_pursuit_y ρ A hL b x0 y0) x0 b y0Algorithm 15.15
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Algorithm 15.15: for the finite-sum linear-composite problem min_x ∑ i, g_i(A_i x), assume the canonical stacked operator x ↦ (A_i x)_i on PiLp 2 Y has full column rank. The underlying ADMM trajectory is the canonical alternating trajectory for the split objective 0 + PiLp.separableSum g and constraint A x - z = 0; the source-facing content retained here is the explicit full-column-rank formula for the x-update.
open scoped BigOperators
universe u v w
variable {ι : Type v} {X : Type u} {Y : ι → Type w}
variable [Fintype ι]
variable [NormedAddCommGroup X] [InnerProductSpace ℝ X] [FiniteDimensional ℝ X]
variable [∀ i, NormedAddCommGroup (Y i)]
variable [∀ i, InnerProductSpace ℝ (Y i)]
variable [∀ i, FiniteDimensional ℝ (Y i)]
local notation "Z" => PiLp (2 : ENNReal) Y
class IsADMMFiniteSumLinearCompositeTrajectoryV1FullColumnRank
(A : ∀ i, X →ₗ[ℝ] Y i)
(ρ : PosReal)
(g : ∀ i, Y i → EReal)
(x : ℕ → X)
(z y : ℕ → Z)
(x0 : X)
(z0 y0 : Z) : Prop extends
IsADMMAlternatingTrajectory
ρ
(fun _ : X ↦ (0 : EReal))
(PiLp.separableSum g)
(admm_finite_sum_linear_composite_stacked_map A)
(-LinearMap.id)
0
x
z
y
x0
z0
y0 where
fullColumnRank : Function.Injective (admm_finite_sum_linear_composite_stacked_map A)
x_step_eq (k : ℕ) :
x (k + 1) = admm_finite_sum_linear_composite_v1_x_update A fullColumnRank ρ (z k) (y k)Algorithm 15.16
Lean contributors (project-level attribution): Shu Miao, Zhiyan Wang, Suwan Wu, Changyu Zou, Xinyi Guo, Yunxi Duan, Wanli Ma, Zichen Wang.
Algorithm 15.16 uses the canonical stacked IsADLPMMTrajectory specialized to α = ρ L, β = ρ, h₁ = 0, and h₂ = ∑ᵢ gᵢ. The explicit x-, z-, and y-formulas are recovered as derived bridge theorems below.
open scoped BigOperators
universe u v w
variable {ι : Type v} {X : Type u} {Y : ι → Type w}
variable [Fintype ι]
variable [NormedAddCommGroup X] [InnerProductSpace ℝ X] [FiniteDimensional ℝ X]
variable [∀ i, NormedAddCommGroup (Y i)] [∀ i, InnerProductSpace ℝ (Y i)]
variable [∀ i, FiniteDimensional ℝ (Y i)]
local notation "Z" => PiLp (2 : ENNReal) Y
recall IsADLPMMTrajectory