Lemma 3 — the pure corrector direction (17) is orthogonal and leaves the complementarity gap unchanged to first order
ProvedExpConeIPM.Corrector.lemma_3Work in the setting of Lemma 2: the homogeneous model with and barrier , an iterate with , , a nonsingular scaling satisfying (8), and a solution of the affine system (11). Let
be the corrector term. Then every solution of the pure corrector system (17),
satisfies
The corrector therefore changes neither the residual nor the complementarity gap; adding it to the affine and centering directions in (18) does not disturb the uniform decrease established in Lemma 4.
Formalization Note is the published hess, is fderiv ℝ (hess F) x u w, and is ContinuousLinearMap.inverse (the true inverse: the augmented barrier has a positive definite Hessian at interior points). The barrier in (16) is the augmented , so has a -coordinate; inner products include the terms. Generalizations as in Lemma 2 (one cone , not assumed block diagonal).
import Mathlib import Definitions.Def_SelfScaledIPM_ShortStep_Setting import Definitions.Def_ExpConeIPM_Corrector_HomogeneousModel import Definitions.Def_ExpConeIPM_Corrector_SearchDirections open scoped InnerProductSpace
namespace ExpConeIPM.Corrector
/-- **Lemma 3** (Dahl–Andersen, Math. Program. 194 (2022), p. 352). In the setting of Lemma 2, let
`Δzᵃ` solve the affine system (11), let `η := −½ F'''(x)[Δxᵃ, (F''(x))⁻¹Δsᵃ]` be the corrector (16) of
the augmented barrier `F = F̂ − log τ`, and let `Δzᶜ` solve the pure corrector system (17). Then
`⟨s, Δxᶜ⟩ + ⟨x, Δsᶜ⟩ = 0` and `⟨Δxᶜ, Δsᶜ⟩ = 0`. -/
theorem lemma_3 {n m : ℕ}
(A : EuclideanSpace ℝ (Fin n) →L[ℝ] EuclideanSpace ℝ (Fin m))
(b : EuclideanSpace ℝ (Fin m)) (c : EuclideanSpace ℝ (Fin n))
(hA : Function.Surjective A)
(Khat : Set (EuclideanSpace ℝ (Fin n))) (Fhat : EuclideanSpace ℝ (Fin n) → ℝ) (ϑhat : ℝ)
(hK : SelfScaledIPM.ShortStep.IsProperCone Khat)
(hF : SelfScaledIPM.ShortStep.IsLogHomBarrier Khat Fhat ϑhat)
(x s : EuclideanSpace ℝ (Fin (n + 1))) (y : EuclideanSpace ℝ (Fin m))
(hz : IsInteriorIterate Khat x s)
(W : EuclideanSpace ℝ (Fin (n + 1)) ≃L[ℝ] EuclideanSpace ℝ (Fin (n + 1)))
(hW : IsDoubleSecantScaling (augCone Khat) (augBarrier Fhat) x s W)
(dxa dsa : EuclideanSpace ℝ (Fin (n + 1))) (dya : EuclideanSpace ℝ (Fin m))
(ha : IsAffineDirection A b c x s y W dxa dsa dya)
(dxc dsc : EuclideanSpace ℝ (Fin (n + 1))) (dyc : EuclideanSpace ℝ (Fin m))
(hc : IsPureCorrectorDirection A b c W (corrector (augBarrier Fhat) x dxa dsa) dxc dsc dyc) :
⟪s, dxc⟫_ℝ + ⟪x, dsc⟫_ℝ = 0 ∧ ⟪dxc, dsc⟫_ℝ = 0 := by sorry
end ExpConeIPM.Corrector
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.