Theorem 4.5 — an ε-relaxed decision procedure for Ax ≤ b, x ∈ P with O(ρ²ε⁻²log(mρ/ε)) oracle calls
ProvedFracPackCover.General.theorem_4_5Let be an arbitrary real matrix, arbitrary, with , and convex. Let bound the width, for all and all , and let be any exact minimizing oracle for and (subroutine (10)). For every with and every starting point , the driver that calls IMPROVE-GENERAL repeatedly:
- stops;
- if it outputs a point , then and ( is an -approximate solution);
- if it reports infeasibility, then there is no exact solution: no satisfies ;
- it makes at most
calls to subroutine (10).
This is the paper's main result for the GENERAL problem: an -relaxed decision procedure whose number of optimization-oracle calls depends on the width , the accuracy and only logarithmically on the number of constraints.
Formalization Note. The paper writes ; its proof yields above: each call made with costs at most calls (Theorem 4.4), more than halves between calls, so and there are at most calls. The equals whenever any call is made (it only keeps nonnegative when , a case in which every point of is already -approximate); is the floor truncated at . IMPROVE-GENERAL uses in place of in Figure 4's and (see the procedure's definition). The driver is run with a fuel bound, and the theorem asserts it stops for every fuel . The "time to compute " part of the paper's statement is not formalized.
Retired 2026-10-27: a Lean-vs-paper fidelity audit found this statement weaker than, or narrower than, the cited result. A corrected statement will be resubmitted.
import Mathlib import Definitions.Def_FracPackCover_General_Driver
namespace FracPackCover.General
/-- Theorem 4.5 (p. 27), for the driver over IMPROVE-GENERAL with the corrected parameters.
For every `ε ∈ (0,1)`, every start `x₀ ∈ P` and every exact minimizing oracle, the driver run with
any fuel `≥ N` stops; if it outputs `x` then `x ∈ P` and `Ax ≤ b + εd`; if it reports
infeasibility then no `x ∈ P` has `Ax ≤ b`; and it makes at most
`N = 2(⌊log₂(ρ/ε)⌋ + 1) + 11520 ρ² ε⁻² ln(12 m max(ρ,ε)/ε)` oracle calls (the paper writes
`O(ρ²ε⁻² log(mρε⁻¹))`). -/
theorem theorem_4_5 {m n : ℕ} [NeZero m] (A : Matrix (Fin m) (Fin n) ℝ) (b d : Fin m → ℝ)
(P : Set (Fin n → ℝ)) (hP : Convex ℝ P) (hd : ∀ i, 0 < d i)
(ρ : ℝ) (hρ : 0 < ρ) (hW : WidthBound A b d P ρ)
(orc : (Fin m → ℝ) → (Fin n → ℝ)) (horc : IsMinOracle P A orc)
(x0 : Fin n → ℝ) (hx0 : x0 ∈ P) (ε : ℝ) (hε0 : 0 < ε) (hε1 : ε < 1) (fuel : ℕ)
(hfuel : 2 * ((⌊Real.logb 2 (ρ / ε)⌋₊ : ℝ) + 1)
+ 11520 * ρ ^ 2 / ε ^ 2 * Real.log (12 * m * max ρ ε / ε) ≤ (fuel : ℝ)) :
(generalDriver A b d ρ ε orc fuel x0).outcome ≠ DriverOutcome.outOfFuel ∧
(∀ x, (generalDriver A b d ρ ε orc fuel x0).outcome = DriverOutcome.approx x →
x ∈ P ∧ ∀ i, FracPackCover.Covering.rowVal A x i ≤ b i + ε * d i) ∧
((generalDriver A b d ρ ε orc fuel x0).outcome = DriverOutcome.infeasible →
¬ ∃ x ∈ P, ∀ i, FracPackCover.Covering.rowVal A x i ≤ b i) ∧
((generalDriver A b d ρ ε orc fuel x0).calls : ℝ) ≤
2 * ((⌊Real.logb 2 (ρ / ε)⌋₊ : ℝ) + 1)
+ 11520 * ρ ^ 2 / ε ^ 2 * Real.log (12 * m * max ρ ε / ε) := by sorry
end FracPackCover.General
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.