(7) — for ,
ProvedL0BnB.Strength.ineq_7mixed-integer-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1perspective-relaxationrelaxation-strengthsparse-regression
Let , , and with . Let be the optimal value of the reduced perspective relaxation (5), that of the interval relaxation of the Big-M formulation (2), and let be an optimal solution of (5): and for every with . Then
Since , the added term is nonnegative, and it is positive as soon as some coordinate satisfies : in this regime the perspective relaxation is at least as strong as the Big-M relaxation, with a quantified gap.
Formalization Note and are explicit sums. The optimal solution is a hypothesis-carrying binder, not a chosen minimizer.
Preamble
import Mathlib import Definitions.Def_L0BnB_Strength_Penalties import Definitions.Def_L0BnB_Strength_Relaxations
Formal statement
namespace L0BnB.Strength
/-- (7), Proposition 1, p. 7 (proof p. 28): for `√(λ₀/λ₂) > M` and `β*` an optimal solution of (5),
`V_{PR(M)} ≥ V_{B(M)} + λ₂ (M ‖β*‖₁ − ‖β*‖₂²)`. -/
theorem ineq_7 {n p : ℕ} (X : Matrix (Fin n) (Fin p) ℝ) (y : Fin n → ℝ) (lam0 lam2 M : ℝ)
(hlam0 : 0 < lam0) (hlam2 : 0 < lam2) (hM : 0 < M)
(hregime : M < Real.sqrt (lam0 / lam2))
(βs : Fin p → ℝ) (hβs_feas : ∀ i, |βs i| ≤ M)
(hβs_opt : ∀ β : Fin p → ℝ, (∀ i, |β i| ≤ M) → L0BnB.Reduced.F X y lam0 lam2 M βs ≤ L0BnB.Reduced.F X y lam0 lam2 M β) :
L0BnB.Reduced.VPR X y lam0 lam2 M ≥
VB X y lam0 lam2 M + lam2 * (M * ∑ i, |βs i| - ∑ i, βs i ^ 2) := 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. 7, Proposition 1, (7); proof p. 28
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.