(4.9), p. 17 — for p ∈ K: F(x + αp) ≤ F(x) + α⟨F′(x), p⟩ + (α²/2)‖p‖²_x for all α ≥ 0
OpenSelfScaledLongStep.PrimalDual.eq_4_9interior-pointlong-stepself-scaled-barrier
Let be a proper cone with a -self-scaled barrier (). Let and . Then for every ,
where .
This is the form of Theorem 4.2 (4.8) in the degenerate case (i.e. ): the paper notes that the argument of Theorem 4.1 for gives for all , and integrating twice along the ray yields (4.9). The step stays in for every .
Formalization note. Same setting and conventions as SelfScaledLongStep.PrimalDual.theorem_4_2: via the inner product, is gradient F x, is lnorm F x p.
Preamble
import Mathlib import Definitions.Def_dualCone import Definitions.Def_SelfScaledIPM_ShortStep_Setting import Definitions.Def_SelfScaledIPM_ShortStep_Measures open scoped InnerProductSpace open SelfScaledIPM.ShortStep
Formal statement
namespace SelfScaledLongStep.PrimalDual
/-- **(4.9)** (p. 17), the `σ_x(−p) = 0` companion of Theorem 4.2: for `x ∈ int K`, `p ∈ K`
and every `α ≥ 0`,
`F(x + αp) ≤ F(x) + α⟨F'(x), p⟩ + (α²/2)‖p‖²_x`. -/
theorem eq_4_9 {n : ℕ} (K : Set (EuclideanSpace ℝ (Fin n))) (hK : IsProperCone K)
(F : EuclideanSpace ℝ (Fin n) → ℝ) (ν : ℝ) (hν : 1 ≤ ν) (hF : IsSelfScaledBarrier K F ν)
(x p : EuclideanSpace ℝ (Fin n)) (hx : x ∈ interior K) (hp : p ∈ K)
(α : ℝ) (hα0 : 0 ≤ α) :
F (x + α • p) ≤ F x + α * ⟪gradient F x, p⟫_ℝ + α ^ 2 / 2 * (lnorm F x p) ^ 2 := by sorry
end SelfScaledLongStep.PrimalDual
Source
Nesterov & Todd, Self-scaled barriers and interior-point methods for convex programming, Math. Oper. Res. 22(1) (1997) 1–42, p. 17, inequality (4.9) (the case σ_x(p) = 0 of Theorem 4.2)