(41) — for
ProvedL0BnB.BigMvsPR.ineq_41mixed-integer-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1perspective-relaxationsparse-regression
Let , and . Let be the optimal value of the interval relaxation of the Big-M formulation (2), the objective of (6), and
the minimum of over the box. If , then
Combined with the hypothesis , which places a minimizer of inside the box so that , this yields (11).
Formalization Note is the real infimum of over the box (vStar); the paper's is attained since is continuous and the box is compact.
Preamble
import Mathlib import Definitions.Def_L0BnB_BigMvsPR_Penalties import Definitions.Def_L0BnB_BigMvsPR_Relaxations
Formal statement
namespace L0BnB.BigMvsPR
/-- (41), Proof of (11), p. 29: with `v*(M) = min_{‖β‖_∞ ≤ M} L0BnB.Strength.G(β)`, if `M ≥ √(λ₀/λ₂)` then
`v*(M) ≥ V_{B(M)}`. -/
theorem ineq_41 {n p : ℕ} (X : Matrix (Fin n) (Fin p) ℝ) (y : Fin n → ℝ) (lam0 lam2 M : ℝ)
(hlam0 : 0 < lam0) (hlam2 : 0 < lam2) (hM : 0 < M)
(hMlarge : Real.sqrt (lam0 / lam2) ≤ M) :
L0BnB.Strength.VB X y lam0 lam2 M ≤ vStar X y lam0 lam2 M := by sorry
end L0BnB.BigMvsPR
Source
Hazimeh, Mazumder, Saab, Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization, arXiv:2004.06152v2, p. 29, App. A, Proof of (11), (41)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.