Optimization

Results in Optimization

• Selected result:

  The exact last-gradient bound for constant-step gradient descent in the strongly convex case

  ProvedTaylor–Hendrickx–Glineur Conjecture 3: last-iterate gradient norm of gradient descent

  Mathematics · Convex optimization · standalone Lean package

  Gradient descent with step h/L, 0 ≤ h ≤ 2, on L-smooth μ-strongly convex f on any real Hilbert space satisfies ‖∇f(x_N)‖ ≤ L‖x₀ − x*‖ max{p_N(μ/L, h), |1 − h|^N} for every N, with equality attained in one dimension.

  Manuscript: The exact last-gradient bound for constant-step gradient descent in the strongly convex case · Lean proof: The exact last-gradient bound for constant-step gradient descent in the strongly convex case · Verification: The exact last-gradient bound for constant-step gradient descent in the strongly convex case

• Selected result:

  A narrow interval for the universal multiplier step of two-block ADMM

  Partially resolvedGlowinski's open question on the ADMM dual step size beyond the golden ratio

  Mathematics · Optimization · standalone Lean package

  Two-block ADMM with multiplier step τ converges for every 0 < τ ≤ 1.886795 on finite-dimensional convex problems with attained proximal steps and a saddle point; fixed polytopes in R^128 cycle for every τ ≥ 1.8868840…; scalar problems converge exactly for 0 < τ < 2

  Manuscript: A narrow interval for the universal multiplier step of two-block ADMM · Lean proof: A narrow interval for the universal multiplier step of two-block ADMM · Verification: A narrow interval for the universal multiplier step of two-block ADMM

• Selected result:

  Escaping Nesterov flows and iterates below critical damping

  Partially resolvedBoundedness of Nesterov ODE trajectories and iterates below critical damping r < 3

  Mathematics · Convex optimization · standalone Lean package

  On ℓ²(ℕ;ℝ²), Nesterov flows from rest and iterates with momentum k/(k+r) stay bounded for all convex objectives with 1-Lipschitz gradient and attained minimum exactly when r ≥ 3; a planar potential escapes for 0 < r ≤ 2.

  Manuscript: Escaping Nesterov flows and iterates below critical damping · Lean proof: Escaping Nesterov flows and iterates below critical damping · Verification: Escaping Nesterov flows and iterates below critical damping

• Periodic obstructions to small-extrapolation Chambolle–Pock

  CounterexampleSmall-extrapolation convergence region of the Chambolle–Pock (PDHG) method

  Mathematics · Optimization · standalone Lean package

  For unmodified Chambolle–Pock, every step product κ = τσ‖L‖² > 2 admits polytopes in ℝ⁴ with periodic nonconvergent iterates for all small θ ≥ 0, so any universal condition κ < c(θ) has limsup c(θ) ≤ 2 as θ ↓ 0.

  Manuscript: Periodic obstructions to small-extrapolation Chambolle–Pock · Lean proof: Periodic obstructions to small-extrapolation Chambolle–Pock · Verification: Periodic obstructions to small-extrapolation Chambolle–Pock

• The multi-marginal converse of Minty's theorem fails in the plane

  Answered negativelyMulti-marginal converse of Minty's theorem (Bartz–Bauschke–Phan–Wang, Remark 2.6)

  Mathematics · Optimization · standalone Lean package

  For three marginals on ℝ² with cost Σ⟨xᵢ, xⱼ⟩, an explicit three-point c-monotone set admits no compatible zero-sum tuple, so every maximally c-monotone set containing it has a nonconvex sum image omitting 0.

  Manuscript: The multi-marginal converse of Minty's theorem fails in the plane · Lean proof: The multi-marginal converse of Minty's theorem fails in the plane · Verification: The multi-marginal converse of Minty's theorem fails in the plane

• A rational five-cycle for two-block ADMM with multiplier step below two

  CounterexampleConvergence of two-block ADMM with multiplier (dual) step size τ in (0, 2)

  Mathematics · Optimization · standalone Lean package

  For two-block ADMM with penalty one and multiplier-only step τ = 199/100, two explicit compact convex polytopes in ℝ⁴ give a nonconstant period-five orbit with squared primal residual at least 500000, so ADMM fails to converge.

  Manuscript: A rational five-cycle for two-block ADMM with multiplier step below two · Lean proof: A rational five-cycle for two-block ADMM with multiplier step below two · Verification: A rational five-cycle for two-block ADMM with multiplier step below two