Claim 1, p. 7 (restated with its context) — a negative linear objective on P + F^I_i is attained at a point of small complexity
ProvedMIQPInNP.SmallSol.claim_1computational-complexitymixed-integer-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1polyhedraquadratic-programming
This is Claim 1 of the proof of Theorem 1, restated with the objects of its context as hypotheses.
Let be a rational polytope, let be linearly independent (the rays of a simple cone), let and , and let be an index with (that is, ). Put and
There is a single polynomial , fixed before , the number of rows of , , and the data, such that: if takes a negative value somewhere on , then there is a rational point with and
In the proof of Theorem 1 the point is then pushed along the direction , on which is linear, to produce a feasible point of small complexity.
Formalization Note The objective is kept as printed, , without symmetrizing .
Differences from the source:
- generalization: the context of p. 7 ( from Proposition 4, the rays of a cone from Lemma 7, "-small complexity") → any rational polytope, any linearly independent rational , bound polynomial in the sizes of these local data; reason: in the source's context , the , and are themselves -small, so composing the polynomials gives the source's -small bound.
- reading: "the optimum of this problem is negative" → the objective takes a negative value somewhere on ; reason: the infimum is negative exactly when some point has a negative value.
Preamble
import Mathlib import Definitions.Def_MIQPInNP_SmallSol_Setting
Formal statement
namespace MIQPInNP.SmallSol
open scoped Pointwise
/-- Claim 1, p. 7, restated with its context (Del Pia, Dey & Molinaro, arXiv:1407.4798v1). -/
theorem claim_1 :
∃ g : Polynomial ℕ, ∀ (n mP k : ℕ) (A' : Matrix (Fin mP) (Fin n) ℚ) (b' : Fin mP → ℚ)
(r : Fin k → Fin n → ℚ) (H : Matrix (Fin n) (Fin n) ℚ) (c : Fin n → ℚ) (i : Fin k),
Bornology.IsBounded (polyhedron A' b') →
LinearIndependent ℝ (fun j => toReal (r j)) →
quadForm H (toReal (r i)) = 0 →
(∃ x ∈ polyhedron A' b' + intCone ((fun j => toReal (r j)) '' {j | j ≠ i}),
2 * (∑ u, ∑ v, x u * (H u v : ℝ) * toReal (r i) v) + ∑ u, (c u : ℝ) * toReal (r i) u
< 0) →
∃ xt : Fin n → ℚ,
toReal xt ∈ polyhedron A' b' + intCone ((fun j => toReal (r j)) '' {j | j ≠ i}) ∧
2 * (∑ u, ∑ v, toReal xt u * (H u v : ℝ) * toReal (r i) v)
+ ∑ u, (c u : ℝ) * toReal (r i) u < 0 ∧
vecSize xt ≤ g.eval (matSize A' + vecSize b' + ∑ j, vecSize (r j) + matSize H + vecSize c) := by sorry
end MIQPInNP.SmallSol
Source
Del Pia, Dey & Molinaro, Mixed-integer quadratic programming is in NP, arXiv:1407.4798v1, p. 7, Claim 1 (context pp. 6–7)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.