Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 22.2 — orthogonality of the step directions and the effect of a step on ρ, μ and XZe − μe

Proved
VanderbeiLP.SelfDual.step_direction_relations

by mikedeng1 · Oct 2, 2026 · Mathlib 0df444a (Lean v4.33.1)

interior-pointlinear-programmingp2o-batch-b23ap2o-gran-per-chapterp2o-plan-bookp2o-v1self-dual

Let n≥2n \ge 2n≥2 and let AAA be a real skew-symmetric n×nn \times nn×n matrix. Let x,z∈Rnx, z \in \mathbb{R}^nx,z∈Rn, let 0≤δ≤10 \le \delta \le 10≤δ≤1, and let (Δx,Δz)(\Delta x, \Delta z)(Δx,Δz) be any solution of the step equations

AΔx+Δz=−(1−δ)ρ,ZΔx+XΔz=δμe−XZe,(22.5)–(22.6)A\Delta x + \Delta z = -(1 - \delta)\rho, \qquad Z\Delta x + X\Delta z = \delta\mu e - XZe, \qquad (22.5)\text{–}(22.6)AΔx+Δz=−(1−δ)ρ,ZΔx+XΔz=δμe−XZe,(22.5)–(22.6)

where ρ=ρ(x,z)=Ax+z\rho = \rho(x, z) = Ax + zρ=ρ(x,z)=Ax+z and μ=μ(x,z)=1nxTz\mu = \mu(x, z) = \frac1n x^T zμ=μ(x,z)=n1​xTz. For a step length θ∈R\theta \in \mathbb{R}θ∈R put xˉ=x+θΔx\bar x = x + \theta\Delta xxˉ=x+θΔx, zˉ=z+θΔz\bar z = z + \theta\Delta zzˉ=z+θΔz, ρˉ=ρ(xˉ,zˉ)\bar\rho = \rho(\bar x, \bar z)ρˉ​=ρ(xˉ,zˉ), μˉ=μ(xˉ,zˉ)\bar\mu = \mu(\bar x, \bar z)μˉ​=μ(xˉ,zˉ). Then

  1. ΔzTΔx=0\Delta z^T \Delta x = 0ΔzTΔx=0;
  2. ρˉ=(1−θ+θδ)ρ\bar\rho = (1 - \theta + \theta\delta)\rhoρˉ​=(1−θ+θδ)ρ;
  3. μˉ=(1−θ+θδ)μ\bar\mu = (1 - \theta + \theta\delta)\muμˉ​=(1−θ+θδ)μ;
XˉZˉe−μˉe=(1−θ)(XZe−μe)+θ2 ΔXΔZe.\bar X\bar Ze - \bar\mu e = (1 - \theta)(XZe - \mu e) + \theta^2\,\Delta X\Delta Z e.XˉZˉe−μˉ​e=(1−θ)(XZe−μe)+θ2ΔXΔZe.

Here X,Z,Xˉ,Zˉ,ΔX,ΔZX, Z, \bar X, \bar Z, \Delta X, \Delta ZX,Z,Xˉ,Zˉ,ΔX,ΔZ are the diagonal matrices of the corresponding vectors and eee is the vector of ones, so ΔXΔZe\Delta X\Delta ZeΔXΔZe is the vector with components ΔxjΔzj\Delta x_j\Delta z_jΔxj​Δzj​. 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 xxx or zzz is assumed; the book's proof does not use it. The step length θ\thetaθ 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
  • Endorsed by Shuze Chen · Oct 5, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 5, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me