(37) — the interval relaxation of the Big-M formulation is
ProvedL0BnB.Strength.eq_37big-mmixed-integer-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1sparse-regression
Let , , and . Let be the optimal value of the interval relaxation of the Big-M formulation (2), in which the indicator variables range over , and let
Then attains its minimum over the box , and
This eliminates the variables from the Big-M relaxation and expresses it purely in -space, which is the form in which it is compared with the perspective relaxation (5).
Formalization Note The statement is IsLeast (H '' box) V_B(M): is a value of on the box and a lower bound for all of them, which is the paper's "min".
Preamble
import Mathlib import Definitions.Def_L0BnB_Strength_Penalties import Definitions.Def_L0BnB_Strength_Relaxations
Formal statement
namespace L0BnB.Strength
/-- (37), Proof of Proposition 1, p. 28: the interval relaxation of B(M) has optimal value
`min_{‖β‖_∞ ≤ M} 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 (H X y lam0 lam2 M '' L0BnB.Reduced.box p M) (VB X y lam0 lam2 M) := by sorry
end L0BnB.Strength
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.