Lemma 4 — along the combined corrector direction (18) the residuals and the complementarity gap both scale by
ProvedExpConeIPM.Corrector.lemma_4Work in the homogeneous model of a conic pair: has full row rank, , , is a proper cone with a -logarithmically homogeneous self-concordant barrier , , , , and is the residual of the homogeneous self-dual embedding. Let be an iterate with , , let , let , be the shadow iterates, and let be a nonsingular scaling with and . Let solve the affine system (11), let be the corrector (16), and let be a centering parameter.
Then every solution of the combined system (18),
satisfies
and for all ,
So a step of length along the combined direction reduces the infeasibility residuals and the complementarity gap by the same factor. Iterating, and when : the algorithm needs no merit function to balance feasibility against optimality.
Formalization Note The first identity is printed on p. 353 as . That is a misprint: the proof on the same page derives , and together with the printed version would give , contradicting the last identity whenever . The repaired identity is stated (compare (12) of Lemma 2, the case , ). Inner products include the homogenizing coordinates, . A single proper cone stands for the paper's product of cones, and is any nonsingular linear map satisfying (8), not necessarily block diagonal; both are generalizations. The identities hold for every real ; the hypothesis is the paper's.
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 4** (Dahl–Andersen, Math. Program. 194 (2022), p. 353), with the misprinted first
identity repaired. 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 τ`,
let `γ > 0`, and let `Δz` solve the combined system (18) with `μ = ⟨x, s⟩/ϑ`, `ϑ = ϑ̂ + 1`. Then
`⟨s, Δx⟩ + ⟨x, Δs⟩ = −(1 − γ)⟨x, s⟩` (printed as `= 0` on p. 353; the proof on the same page derives
`−(1 − γ)⟨x, s⟩`, and `= 0` contradicts the last identity), `⟨Δx, Δs⟩ = 0`, and for all `α ∈ ℝ`
`G(z + αΔz) = (1 − α(1 − γ)) G(z)` and `⟨x + αΔx, s + αΔs⟩ = (1 − α(1 − γ))⟨x, s⟩`. -/
theorem lemma_4 {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)
(γ : ℝ) (hγ : 0 < γ)
(dx ds : EuclideanSpace ℝ (Fin (n + 1))) (dy : EuclideanSpace ℝ (Fin m))
(hd : IsCombinedDirection A b c Khat Fhat ϑhat x s y W
(corrector (augBarrier Fhat) x dxa dsa) γ dx ds dy) :
⟪s, dx⟫_ℝ + ⟪x, ds⟫_ℝ = -(1 - γ) * ⟪x, s⟫_ℝ ∧ ⟪dx, ds⟫_ℝ = 0 ∧
∀ α : ℝ,
residual A b c (x + α • dx) (s + α • ds) (y + α • dy) =
(1 - α * (1 - γ)) • residual A b c x s y ∧
⟪x + α • dx, s + α • ds⟫_ℝ = (1 - α * (1 - γ)) * ⟪x, s⟫_ℝ := by sorry
end ExpConeIPM.Corrector
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.