Lemma 6, p. 5 — normalizing hyperplane of small complexity for a pointed cone
ProvedMIQPInNP.SmallSol.lemma_6computational-complexitymixed-integer-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1polyhedraquadratic-programming
Let be a pointed cone generated by rational vectors , . There is a single polynomial , fixed before , and the generators, such that there is a hyperplane with and
- ;
- for every with (Euclidean norm),
- is bounded.
Such a hyperplane meets every ray of exactly once, and it is used to compactify cones in Lemma 7 and in the proof of Theorem 1.
Formalization Note If all are zero then , and item 2 is vacuous.
Differences from the source:
- encoding: the generators and the maximum over → rational generators; reason: the index range and the maximum presuppose , and complexity is defined for rational data only.
- encoding: "polynomially bounded", →
Polynomial ℕquantified before the data, Schrijver's bit-size, Euclidean norm; reason: Lean conventions for the paper's notions.
Preamble
import Mathlib import Definitions.Def_MIQPInNP_SmallSol_Setting
Formal statement
namespace MIQPInNP.SmallSol
/-- Lemma 6 (normalizing hyperplane), p. 5 (Del Pia, Dey & Molinaro, arXiv:1407.4798v1). -/
theorem lemma_6 :
∃ g : Polynomial ℕ, ∀ (n s : ℕ) (r : Fin s → Fin n → ℚ) (hs : 0 < s),
IsPointedCone (cone (Set.range fun i => toReal (r i))) →
∃ f : Fin n → ℚ,
vecSize f ≤ g.eval (Finset.univ.sup fun i => vecSize (r i)) ∧
(∀ x ∈ cone (Set.range fun i => toReal (r i)), euclidNorm x = 1 →
1 / (Finset.univ.sup' ⟨⟨0, hs⟩, Finset.mem_univ _⟩
fun i => euclidNorm (toReal (r i))) ≤ ∑ j, (f j : ℝ) * x j) ∧
Bornology.IsBounded (cone (Set.range fun i => toReal (r i)) ∩ hyperplane f) := by sorry
end MIQPInNP.SmallSol
Source
Del Pia, Dey & Molinaro, Mixed-integer quadratic programming is in NP, arXiv:1407.4798v1, p. 5, Lemma 6
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.