(37) — the Big-M interval relaxation equals
ProvedL0BnB.BigMvsPR.eq_37mixed-integer-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1sparse-regression
Let , and . The optimal value of the interval relaxation of the Big-M formulation (2) equals the minimum of
over the box :
and the minimum is attained.
This eliminates the relaxed indicator variables from the Big-M relaxation and expresses it in alone, which is the form compared with in Proposition 2.
Formalization Note "min, attained, equal to " is IsLeast (H '' box) VB: is a value of on the box and is at most every such value.
Preamble
import Mathlib import Definitions.Def_L0BnB_BigMvsPR_Penalties import Definitions.Def_L0BnB_BigMvsPR_Relaxations
Formal statement
namespace L0BnB.BigMvsPR
/-- (37), Proof of Proposition 1, p. 28: the interval relaxation of B(M) has optimal value
`min_{‖β‖_∞ ≤ M} L0BnB.Strength.H(β)`; the minimum over the L0BnB.Reduced.box is attained and equals `V_{B(M)}`. -/
theorem eq_37 {n p : ℕ} (X : Matrix (Fin n) (Fin p) ℝ) (y : Fin n → ℝ) (lam0 lam2 M : ℝ)
(hlam0 : 0 < lam0) (hlam2 : 0 < lam2) (hM : 0 < M) :
IsLeast (L0BnB.Strength.H X y lam0 lam2 M '' L0BnB.Reduced.box p M) (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. 28, App. A, Proof of Proposition 1, (37)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.