Lemma 7.1, p. 27 — the updated lower bound satisfies ζ⁺ ≤ ζ∗ and ⟨c, x̂⟩ − ζ⁺ ≤ νσ_x̂(−p)
ProvedSelfScaledLongStep.Karmarkar.lemma_7_1Let be a self-scaled cone with a -self-scaled barrier (). Consider the problem
with linear and surjective and , and assume that the dual
has a strictly feasible solution () and that is not constant on the feasible set of (P). Let be the optimal value of (P).
Let be strictly feasible for (P) and let . Let and be the projections of and into with respect to , i.e. , (7.3). Let be the possibly updated lower bound: if , and otherwise (7.6). Let (7.5). Then and
The lemma says that the lower-bound update never overshoots the optimal value, and that the resulting gap is controlled by how far one can move from along before leaving . It generalizes a result of Anstreicher for linear programming, and is the bound used in the third line of the potential estimate (7.10).
Formalization Note is sigma K x p. The vectors , are , (the page prints "", a misprint; see the definitions item). The projections are taken as data , satisfying (7.3); they are unique by Proposition 6.1. is identified with ; the barrier's Hessian is assumed nondegenerate (implied for a pointed cone); the conjugate barrier is a supremum over . Strict feasibility of (P) is implied by ; strict feasibility of (D) is assumption (6.3) of §6 and makes finite. The hypothesis is a consequence of pointedness stated on p. 3, taken as a binder.
import Mathlib import Definitions.Def_dualCone import Definitions.Def_SelfScaledIPM_ShortStep_Setting import Definitions.Def_SelfScaledIPM_ShortStep_Measures import Definitions.Def_SelfScaledLongStep_Karmarkar_Defs open scoped InnerProductSpace open SelfScaledIPM.ShortStep
namespace SelfScaledLongStep.Karmarkar
/-- **Lemma 7.1** (p. 27). Let `x̂ ∈ S⁰(P)` and `ζ̂ ≤ ζ*`, let `p(c)`, `p(d)` solve (7.3) for
`û = ĉ`, `û = d̂`, let `ζ⁺` be the possibly updated lower bound (7.6) and `p = p(c) − ζ⁺p(d)`
(7.5). Then `ζ⁺ ≤ ζ*` and (7.7) `⟨c, x̂⟩ − ζ⁺ ≤ ν σ_x̂(−p)`. -/
theorem lemma_7_1
{n m : ℕ} (K : Set (EuclideanSpace ℝ (Fin n))) (hK : IsProperCone K)
(F : EuclideanSpace ℝ (Fin n) → ℝ) (ν : ℝ) (hν : 1 ≤ ν) (hF : IsSelfScaledBarrier K F ν)
(B : EuclideanSpace ℝ (Fin n) →L[ℝ] EuclideanSpace ℝ (Fin m)) (hB : Function.Surjective B)
(c d : EuclideanSpace ℝ (Fin n)) (hd : d ∈ ConvexOptimization.dualCone K)
(hD : ∃ (y : EuclideanSpace ℝ (Fin m)) (ζ : ℝ) (s : EuclideanSpace ℝ (Fin n)),
s ∈ interior (ConvexOptimization.dualCone K) ∧
ContinuousLinearMap.adjoint B y + ζ • d + s = c)
(hnc : ∃ x₁ x₂ : EuclideanSpace ℝ (Fin n),
KarFeasible K B d x₁ ∧ KarFeasible K B d x₂ ∧ ⟪c, x₁⟫_ℝ ≠ ⟪c, x₂⟫_ℝ)
(xh : EuclideanSpace ℝ (Fin n)) (hxh : KarStrict K B d xh)
(ζh : ℝ) (hζh : ζh ≤ zetaStar K B c d)
(yc : EuclideanSpace ℝ (Fin m)) (pc : EuclideanSpace ℝ (Fin n))
(hpc : SelfScaledLongStep.PrimalDual.IsProjection F B xh (cHat F ν c xh) yc pc)
(yd : EuclideanSpace ℝ (Fin m)) (pd : EuclideanSpace ℝ (Fin n))
(hpd : SelfScaledLongStep.PrimalDual.IsProjection F B xh (dHat F ν d xh) yd pd) :
let ζp := zetaPlus K ν c d xh pc pd ζh
let p := karDir pc pd ζp
ζp ≤ zetaStar K B c d ∧ ⟪c, xh⟫_ℝ - ζp ≤ ν * sigma K xh (-p) := by sorry
end SelfScaledLongStep.Karmarkar
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.