(19) ⇒ (64), p.27 — the update (19) satisfies (64) and the bounds on
ProvedHomotopyProxVM.eq_64convex-optimizationhomotopyp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1proximal-methods
Let , , , , let be given by (18), let , and let be given by (19). Then for every ,
This is the condition Algorithm 1 asks of the update together with the budget (64) that closes the induction in the proof of Theorem 4.
Differences from the source:
- generalization: a = ‖∇f(x⁰)+ξ⁰‖₂, b = L_g+‖ξ⁰‖₂, and "0 ≤ 1 − τ_k" on p.27 → arbitrary positive reals a, b, and 0 < 1 − τ_k; reason: pure algebra; the strict inequality is the one Theorem 4 claims and it implies the page's
- reading: C₁ > 0 and σ ∈ (ω,1), as used on p.27 → the hypotheses 0 < a, 0 < ω, 0 < b; reason: (18) is undefined at ω = 0 or b = 0; at a = 0 one has σ = 1 and τ_k is constant, the case handled in theorem_4
Preamble
import Mathlib import Definitions.Def_HomotopyProxVM_sigmaConst import Definitions.Def_HomotopyProxVM_tauSeq
Formal statement
namespace HomotopyProxVM
/-- Tran-Dinh, Liang & Toh, arXiv:1812.05243v1, Appendix B.1, (64) and the lines after (65), p.27: with
`C₁ := (σ − ω) a / (ω b)`, the update (19) satisfies `0 < τ_k < τ_{k+1} ≤ 1`, the condition (64)
`τ_{k+1} ≤ τ_k + C₁ σᵏ τ_k τ_{k+1}`, and `0 < 1 − τ_k ≤ (1 − τ₀) σᵏ / τ₀`.
**Formalization Note.** A statement about real numbers, with `a = ‖∇f(x⁰) + ξ⁰‖₂ > 0` and
`b = L_g + ‖ξ⁰‖₂ > 0`. The page prints `0 ≤ 1 − τ_k` here and `0 < 1 − τ_k` in Theorem 4; the strict
form is stated. -/
theorem eq_64 {τ₀ ω a b : ℝ} (hτ₀ : τ₀ ∈ Set.Ioo (0 : ℝ) 1) (hω : ω ∈ Set.Ioo (0 : ℝ) 1)
(ha : 0 < a) (hb : 0 < b) :
let σ := sigmaConst τ₀ ω a b
let C₁ := (σ - ω) * a / (ω * b)
let τ := tauSeq τ₀ σ
∀ k : ℕ, 0 < τ k ∧ τ k < τ (k + 1) ∧ τ (k + 1) ≤ 1 ∧
τ (k + 1) ≤ τ k + C₁ * σ ^ k * τ k * τ (k + 1) ∧
0 < 1 - τ k ∧ 1 - τ k ≤ (1 - τ₀) * σ ^ k / τ₀ := by sorry
end HomotopyProxVM
Source
Tran-Dinh, Liang & Toh, A New Homotopy Proximal Variable-Metric Framework for Composite Convex Minimization, arXiv:1812.05243v1, Appendix B.1, (64) and the following lines, p.27
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.