Equations (18)–(19) — componentwise projection bound
ProvedAdaptiveStepIPM.Probabilistic.equations_18_19interior-point-methodsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1probabilityrandom-subspaces
Let , , and . Put and . In every coordinate ,
Consequently . For this is the deterministic step connecting Lemma 6 to Theorem 5.
Formalization Note Here . The equivalent hypothesis gives the real square root its intended domain.
Preamble
import Definitions.Def_AdaptiveStepIPM_Probabilistic_Model open MeasureTheory ProbabilityTheory Filter
Formal statement
namespace AdaptiveStepIPM.Probabilistic
/-- The componentwise identity (18) and lower bound (19). -/
theorem equations_18_19 {n : ℕ} (g w : EuclideanSpace ℝ (Fin n))
(ζ : ℝ) (hζ : ζ ^ 2 ≤ 1) :
let η := Real.sqrt (1 - ζ ^ 2)
let p₀ : Fin n → ℝ := fun j => (1 + ζ) * g j + η * w j
let q₀ : Fin n → ℝ := fun j => (1 - ζ) * g j - η * w j
(∀ j : Fin n,
p₀ j * q₀ j = η ^ 2 * (g j) ^ 2 - 2 * ζ * η * g j * w j - η ^ 2 * (w j) ^ 2 ∧
p₀ j * q₀ j = -(w j) ^ 2 + (η * g j - ζ * w j) ^ 2 ∧
-(supNorm w) ^ 2 ≤ p₀ j * q₀ j) ∧
negSupNorm (fun j => p₀ j * q₀ j) ≤ (supNorm w) ^ 2 := by sorry
end AdaptiveStepIPM.Probabilistic
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. 15, Eqs. (18)–(19); https://doi.org/10.1287/moor.18.4.964
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.