§5 —
ProvedAdaptiveStepIPM.Potential.psi_rewrite_lower_boundinterior-point-methodslinear-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1potential-reduction
Let , , and with , . Let be the primal–dual potential (1). Then:
- the potential can be rewritten as
- the sum is nonpositive (arithmetic–geometric mean inequality), so
- consequently, if , and , then .
The lower bound turns a decrease of the potential into a decrease of the duality gap: once has been driven down to , precision has been reached.
Formalization Note is the published LinearOptimization.interiorPointPotential ρ x s, which agrees with (1) for . All logarithms are natural; the third item uses for .
Preamble
import Mathlib import Definitions.Def_LinearOptimization_InteriorPointPotential import Definitions.Def_AdaptiveStepIPM_Potential_Neighborhood open Matrix
Formal statement
namespace AdaptiveStepIPM.Potential
/-- **§5, p. 11.** For `x, s > 0` the potential (1) can be written as
`ψ(x, s) = (ρ − n) log(xᵀs) − Σⱼ log(x_j s_j/(xᵀs/n)) + n log n`; the sum is nonpositive
(arithmetic–geometric mean inequality), so `ψ(x, s) ≥ (ρ − n) log(xᵀs) + n log n`; hence,
for `ρ > n` and `t ≥ 0`, `ψ(x, s) ≤ −(ρ − n)t + n log n` implies `xᵀs ≤ 2^{−t}`. -/
theorem psi_rewrite_lower_bound {n : ℕ} (hn : 1 ≤ n) (ρ : ℝ) (x s : Fin n → ℝ)
(hx : ∀ j, 0 < x j) (hs : ∀ j, 0 < s j) :
LinearOptimization.interiorPointPotential ρ x s =
(ρ - n) * Real.log (x ⬝ᵥ s) -
∑ j, Real.log (x j * s j / ((x ⬝ᵥ s) / n)) + n * Real.log n ∧
(ρ - n) * Real.log (x ⬝ᵥ s) + n * Real.log n ≤
LinearOptimization.interiorPointPotential ρ x s ∧
∀ t : ℝ, (n : ℝ) < ρ → 0 ≤ t →
LinearOptimization.interiorPointPotential ρ x s ≤ -((ρ - n) * t) + n * Real.log n →
x ⬝ᵥ s ≤ (2 : ℝ) ^ (-t) := by sorry
end AdaptiveStepIPM.Potential
Source
Mizuno, Todd, Ye, On adaptive-step primal-dual interior-point algorithms for linear programming, Cornell ORIE Technical Report No. 944 (1990, rev. 1991), p. 11, §5 (displays before Algorithm 3)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.