Proposition 3.1 — a polyhedral -approximation of needs inequalities ()
ProvedPolyhedralSOC.LowerBound.polyhedral_approx_lower_boundThere is a positive absolute constant such that the following holds. Let be an integer, , and let
be a polyhedral -approximation of the Lorentz cone . Then the number of linear inequalities satisfies
Together with Theorem 1.1 of the same paper, which constructs polyhedral -approximations with , this shows that the order of the number of inequalities cannot be improved.
Formalization Note The paper's " with positive absolute constant " is stated as quantified before , , , and . The paper states the proposition for every positive integer ; for it is false, since is polyhedral and (, ) is a polyhedral -approximation for every . The statement is therefore made for . The bound concerns alone.
import Mathlib import Definitions.Def_PolyhedralSOC_Shared_LorentzCone import Definitions.Def_PolyhedralSOC_Shared_IsPolyhedralApprox
namespace PolyhedralSOC.LowerBound
/-- Ben-Tal & Nemirovski, *On Polyhedral Approximations of the Second-Order Cone*,
Math. Oper. Res. 26(2):193–205 (2001), Proposition 3.1, Eq. (13), p. 202 (PDF p. 10):
there is a positive absolute constant `c` such that, for every `k ≥ 2`, every `ε ∈ (0, 0.5]` and
every polyhedral `ε`-approximation `Π(y, t, u) : ℝ^k × ℝ × ℝ^p → ℝ^q` of the Lorentz cone `L^k`,
`q ≥ c k ln(1/ε)`.
**Correction:** the paper states this for every positive integer `k`; for `k = 1` it is false,
because `L^1 = {(y, t) | |y| ≤ t}` is polyhedral and `Π(y, t) = (t − y, t + y)` (`p = 0`, `q = 2`)
is a polyhedral `ε`-approximation for every `ε > 0`. The result is stated for `k ≥ 2`. -/
theorem polyhedral_approx_lower_bound :
∃ c : ℝ, 0 < c ∧ ∀ k : ℕ, 2 ≤ k → ∀ ε : ℝ, 0 < ε → ε ≤ 1 / 2 →
∀ (p q : ℕ) (P : (Fin k → ℝ) × ℝ × (Fin p → ℝ) →ₗ[ℝ] (Fin q → ℝ)),
Shared.IsPolyhedralApprox k p q ε P → c * k * Real.log (1 / ε) ≤ q := by sorry
end PolyhedralSOC.LowerBound
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.