(10) — for
ProvedL0BnB.BigMvsPR.ineq_10mixed-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), and the value (6) of the interval relaxation of . If , then
So for a sufficiently tight Big-M bound, the Big-M relaxation gives a lower bound at least as large as that of the perspective relaxation without box constraint. This is the first half of Proposition 2.
Preamble
import Mathlib import Definitions.Def_L0BnB_BigMvsPR_Penalties import Definitions.Def_L0BnB_BigMvsPR_Relaxations
Formal statement
namespace L0BnB.BigMvsPR
/-- (10) of Proposition 2, p. 7 (proof (40), p. 29): if `M ≤ ½ √(λ₀/λ₂)` then
`V_{B(M)} ≥ V_{PR(∞)}`. -/
theorem ineq_10 {n p : ℕ} (X : Matrix (Fin n) (Fin p) ℝ) (y : Fin n → ℝ) (lam0 lam2 M : ℝ)
(hlam0 : 0 < lam0) (hlam2 : 0 < lam2) (hM : 0 < M)
(hMsmall : M ≤ (1 / 2) * Real.sqrt (lam0 / lam2)) :
L0BnB.Strength.VPRinf X y lam0 lam2 ≤ L0BnB.Strength.VB 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. 7, Proposition 2, (10); proof p. 29, (40)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.