Lemma 6.3 (dual estimate), p. 28 — if η = ϵ₊/(1 − δ) < 1 then the dual step satisfies ‖q_s‖_s ≤ η
OpenSelfScaledIPM.ShortStep.lemma_6_3_qs_boundinterior-pointpath-followingself-scaled-coneshort-step
Let be a self-scaled cone with -self-scaled barrier and conjugate barrier , and let be surjective. Let with . Fix , put (6.4), let be the scaling point of (so ), and let solve the short-step system (6.7):
With and , suppose (6.11). Then the dual component of the step satisfies
This is the second inequality of Lemma 6.3. The paper proves the first one, , using Lemma 3.13 and the orthogonality , and then says "similarly ". The dual argument uses the second half of (3.22), with , the symmetric form of (6.7), and (3.3).
Formalization note. is identified with , and is lnorm (conj K F) s, the local norm at the dual point of the dual vector . The hypotheses are exactly those of the platform statement of Lemma 6.3.
Preamble
import Mathlib import Definitions.Def_dualCone import Definitions.Def_SelfScaledIPM_ShortStep_Setting import Definitions.Def_SelfScaledIPM_ShortStep_Measures open scoped InnerProductSpace
Formal statement
namespace SelfScaledIPM.ShortStep
/-- **Lemma 6.3, dual estimate** (p. 28): under the hypotheses of Lemma 6.3 —
`(x, y, s) ∈ N(β)`, `β, κ ∈ (0, 1)`, `µ₊ = (1 − κ/√ν)µ(x, s)` (6.4), `w` the scaling point of
`(x, s)`, `(q_x, q_y, q_s)` a solution of (6.7), and `η = ϵ₊/(1 − δ) < 1` (6.11) — the dual
step satisfies `‖q_s‖_s ≤ η`, the norm being the local norm of `q_s ∈ E*` at the dual point
`s ∈ int K*`, i.e. `⟨F*''(s) q_s, q_s⟩^{1/2}` (`lnorm (conj K F) s q_s`). -/
theorem lemma_6_3_qs_bound {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))
(β κ : ℝ) (hβ0 : 0 < β) (hβ1 : β < 1) (hκ0 : 0 < κ) (hκ1 : κ < 1)
(x : EuclideanSpace ℝ (Fin n)) (y : EuclideanSpace ℝ (Fin m)) (s : EuclideanSpace ℝ (Fin n))
(hN : InN K F A b c ν β x y s)
(w : EuclideanSpace ℝ (Fin n)) (hw : IsScalingPoint K F x s w)
(qx : EuclideanSpace ℝ (Fin n)) (qy : EuclideanSpace ℝ (Fin m)) (qs : EuclideanSpace ℝ (Fin n))
(hq : IsShortStepDir F A x s w (muPlus ν κ x s) qx qy qs)
(hη : eta K F ν κ x s < 1) :
lnorm (conj K F) s qs ≤ eta K F ν κ x s := by sorry
end SelfScaledIPM.ShortStep
Source
Nesterov & Todd, Primal-dual interior-point methods for self-scaled cones, SIAM J. Optim. 8 (1998) 324–364 (authors' copy, Cornell eCommons), p. 28, Lemma 6.3, second inequality ‖q_s‖_s ≤ η ("and similarly ‖q_s‖_s ≤ η" in the proof)