§7.2, p. 31 — ⟨s̃(λ), x̂⟩ = ⟨−F′(x̂), p(c)⟩ + λ((‖F′(x̂)‖∗_x̂)² − ‖p(d)‖²_x̂) is increasing in λ
ProvedSelfScaledLongStep.AffinePot.gap_monotoneLet be a self-scaled cone in with -self-scaled barrier , and consider the conic problem : subject to , , with surjective and the dual strictly feasible. Let , i.e. and . Let and be the projections of and of into with respect to , i.e.
and for let . Then for every ,
and this gap is a nondecreasing function of . Here and .
The monotonicity is what makes the lower-bound update (7.17) well defined: the best dual bound obtainable from is attained at the smallest admissible .
Formalization Note through the inner product. is dnorm F x̂ u and is lnorm F x̂ p (the published 1998 setting drops the star). Nondegeneracy of is part of the inherited barrier definition, and the conjugate barrier of the setting is an sSup over ; neither is used in this statement. The paper says "increasing"; the slope can be zero, so the statement is Monotone (nondecreasing), which is the true reading. The standing hypothesis is carried as a binder (the paper derives it from pointedness). The §7 assumption that the objective is not constant on the feasible region is not needed here and is omitted.
import Mathlib import Definitions.Def_dualCone import Definitions.Def_SelfScaledIPM_ShortStep_Setting import Definitions.Def_SelfScaledIPM_ShortStep_Measures import Definitions.Def_SelfScaledLongStep_AffinePot_Defs open scoped InnerProductSpace open SelfScaledIPM.ShortStep
namespace SelfScaledLongStep.AffinePot
/-- **§7.2, p. 31, display before (7.17).** With `pc = p(c)`, `pd = p(d)` the projections (7.12)
of `c` and `d = F'(x̂)`, the gap
`⟨s̃(λ), x̂⟩ = ⟨−F'(x̂), p(c)⟩ + λ((‖F'(x̂)‖*_x̂)² − ⟨F'(x̂), p(d)⟩)
= ⟨−F'(x̂), p(c)⟩ + λ((‖F'(x̂)‖*_x̂)² − ‖p(d)‖²_x̂)`
is a (weakly) increasing function of `λ`. -/
theorem gap_monotone {n m : ℕ} (K : Set (EuclideanSpace ℝ (Fin n))) (hK : IsProperCone K)
(F : EuclideanSpace ℝ (Fin n) → ℝ) (ν : ℝ) (hν : 1 ≤ ν) (hF : IsSelfScaledBarrier K F ν)
(A : EuclideanSpace ℝ (Fin n) →L[ℝ] EuclideanSpace ℝ (Fin m)) (hA : Function.Surjective A)
(b : EuclideanSpace ℝ (Fin m)) (c : EuclideanSpace ℝ (Fin n))
(hD : ∃ y s, IsDualStrict K A c y s)
(xh : EuclideanSpace ℝ (Fin n)) (hxh : IsPrimalStrict K A b xh)
(yc : EuclideanSpace ℝ (Fin m)) (pc : EuclideanSpace ℝ (Fin n))
(hpc : SelfScaledLongStep.PrimalDual.IsProjection F A xh c yc pc)
(yd : EuclideanSpace ℝ (Fin m)) (pd : EuclideanSpace ℝ (Fin n))
(hpd : SelfScaledLongStep.PrimalDual.IsProjection F A xh (gradient F xh) yd pd) :
(∀ t : ℝ, ⟪sTilde F xh pc pd t, xh⟫_ℝ =
⟪-gradient F xh, pc⟫_ℝ + t * ((dnorm F xh (gradient F xh)) ^ 2 - ⟪gradient F xh, pd⟫_ℝ)) ∧
(∀ t : ℝ, ⟪sTilde F xh pc pd t, xh⟫_ℝ =
⟪-gradient F xh, pc⟫_ℝ + t * ((dnorm F xh (gradient F xh)) ^ 2 - (lnorm F xh pd) ^ 2)) ∧
Monotone (fun t : ℝ => ⟪sTilde F xh pc pd t, xh⟫_ℝ) := by sorry
end SelfScaledLongStep.AffinePot
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.