Lemma 2.1, p. 6 — solutions of the homogeneous model (7) are complementary, and give an optimal pair (τ* > 0) or an infeasibility certificate (κ* > 0)
ProvedConicQuadIPM.Homogeneous.lemma_2_1Let , , , let be a pointed closed convex cone with dual cone , and consider the conic pair : and : . Let be any solution of the homogeneous model (7):
Then:
- (i) .
- (ii) If , then is an optimal solution of and is an optimal solution of .
- (iii) If , then at least one of the strict inequalities (8) and (9) holds; if then is infeasible, and if then is infeasible.
The homogeneous model always has the trivial solution, so the lemma is about what a solution with delivers: either a scaled optimal primal–dual pair or a certificate of infeasibility. This is what makes an interior-point method applied to (7) a complete solution method for and .
Formalization Note is Fin n → ℝ, is the dot product u ⬝ᵥ v, is A *ᵥ x and is Aᵀ *ᵥ y; the paper's first coordinate is index 0. The standing assumption that is a pointed closed convex cone is carried as the hypothesis IsPointedClosedConvexCone K. The paper's additional assumption that has full row rank ("for convenience and without loss of generality", p. 4) is not imposed, so the statement is a (harmless) generalization. Division by is written as scalar multiplication by and is only used under . Optimality and infeasibility are order and non-existence predicates over all feasible points.
import Mathlib import Definitions.Def_ConicQuadIPM_Homogeneous_Setting
namespace ConicQuadIPM.Homogeneous
open Matrix
/-- Lemma 2.1 (p. 6). Let `(x*, τ*, y*, s*, κ*)` be any solution of the homogeneous model (7).
Then i) `(x*)ᵀs* + τ*κ* = 0`; ii) if `τ* > 0`, `x*/τ*` is optimal for (P) and `(y*, s*)/τ*` is
optimal for (D); iii) if `κ* > 0`, then `bᵀy* > 0` or `cᵀx* < 0`; if `bᵀy* > 0` then (P) is
infeasible, and if `cᵀx* < 0` then (D) is infeasible. -/
theorem lemma_2_1 {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ) (c : Fin n → ℝ)
(K : Set (Fin n → ℝ)) (hK : IsPointedClosedConvexCone K)
(x : Fin n → ℝ) (τ : ℝ) (y : Fin m → ℝ) (s : Fin n → ℝ) (κ : ℝ)
(h : HomFeasible A b c K x τ y s κ) :
x ⬝ᵥ s + τ * κ = 0 ∧
(0 < τ → PrimalOptimal A b c K (τ⁻¹ • x) ∧ DualOptimal A b c K (τ⁻¹ • y) (τ⁻¹ • s)) ∧
(0 < κ → (0 < b ⬝ᵥ y ∨ c ⬝ᵥ x < 0) ∧ (0 < b ⬝ᵥ y → PrimalInfeasible A b K) ∧
(c ⬝ᵥ x < 0 → DualInfeasible A c K)) := by sorry
end ConicQuadIPM.Homogeneous
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.