Theorem 22.2 — orthogonality of the step directions and the effect of a step on ρ, μ and XZe − μe
ProvedVanderbeiLP.SelfDual.step_direction_relationsinterior-pointlinear-programmingp2o-batch-b23ap2o-gran-per-chapterp2o-plan-bookp2o-v1self-dual
Let and let be a real skew-symmetric matrix. Let , let , and let be any solution of the step equations
where and . For a step length put , , , . Then
- ;
- ;
- ;
Here are the diagonal matrices of the corresponding vectors and is the vector of ones, so is the vector with components . These identities drive the whole convergence analysis: infeasibility and noncomplementarity are reduced by the same factor, and the deviation from centrality changes by a controlled quadratic term.
Formalization Note No positivity of or is assumed; the book's proof does not use it. The step length is an arbitrary real number.
Preamble
import Mathlib import Definitions.Def_VanderbeiLP_SelfDual_HomogeneousSelfDual open Matrix
Formal statement
namespace VanderbeiLP.SelfDual
/-- Theorem 22.2 (Vanderbei, p. 326). Let `A` be skew symmetric (`n ≥ 2`), `0 ≤ δ ≤ 1`, let
`(Δx, Δz)` solve (22.5)–(22.6) at `(x, z)`, let `θ` be a step length, and put
`x̄ = x + θΔx`, `z̄ = z + θΔz`. Then
(1) `Δzᵀ Δx = 0`;
(2) `ρ̄ = (1 - θ + θδ) ρ`;
(3) `μ̄ = (1 - θ + θδ) μ`;
(4) `X̄Z̄e - μ̄e = (1 - θ)(XZe - μe) + θ² ΔXΔZe`. -/
theorem step_direction_relations {n : ℕ} (hn : 2 ≤ n)
(A : Matrix (Fin n) (Fin n) ℝ) (hA : IsSkewSymmetric A)
(δ : ℝ) (hδ0 : 0 ≤ δ) (hδ1 : δ ≤ 1)
(x z dx dz : Fin n → ℝ) (hstep : IsStepDirection A δ x z dx dz) (θ : ℝ) :
dz ⬝ᵥ dx = 0 ∧
rho A (x + θ • dx) (z + θ • dz) = (1 - θ + θ * δ) • rho A x z ∧
mu (x + θ • dx) (z + θ • dz) = (1 - θ + θ * δ) * mu x z ∧
centralityResidual (x + θ • dx) (z + θ • dz) =
(1 - θ) • centralityResidual x z + θ ^ 2 • (fun j => dx j * dz j) := by sorry
end VanderbeiLP.SelfDual
Source
Vanderbei, Linear Programming: Foundations and Extensions, 4th ed., Springer 2014, p. 326, Theorem 22.2 (PDF p. 332), with Eqs. (22.5)–(22.6)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.