Theorem 2.1, Primal infeasibility (5), p. 4 — s ∈ K_*, Aᵀy + s = 0, bᵀy > 0 certifies that (P) is infeasible
ProvedConicQuadIPM.Homogeneous.primal_infeasibilityLet be a pointed closed convex cone with dual cone , and let be the problem . If there is a pair with
then has no feasible point.
Such a is a Farkas-type certificate of primal infeasibility; Lemma 2.1 iii) shows that a solution of the homogeneous model with and produces one.
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. The display (5) prints ; the star is a typographical slip for the bound variable , and the Lean states . The objective plays no role and is not a parameter.
import Mathlib import Definitions.Def_ConicQuadIPM_Homogeneous_Setting
namespace ConicQuadIPM.Homogeneous
open Matrix
/-- Theorem 2.1, Primal infeasibility (5) (p. 4): if some `(y, s)` has `s ∈ K_*`,
`Aᵀy + s = 0` and `bᵀy > 0`, then (P) is infeasible. -/
theorem primal_infeasibility {m n : ℕ} (A : Matrix (Fin m) (Fin n) ℝ) (b : Fin m → ℝ)
(K : Set (Fin n → ℝ)) (hK : IsPointedClosedConvexCone K)
(hcert : ∃ (y : Fin m → ℝ) (s : Fin n → ℝ),
s ∈ dualCone K ∧ Aᵀ *ᵥ y + s = 0 ∧ 0 < b ⬝ᵥ y) :
PrimalInfeasible A b K := by sorry
end ConicQuadIPM.Homogeneous
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.