Proposition 1 — for the perspective relaxation dominates the Big-M and PR(∞) relaxations
ProvedL0BnB.Strength.proposition_1mixed-integer-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1perspective-relaxationrelaxation-strengthsparse-regression
Let , , and . Let be the optimal value of the reduced perspective relaxation (5),
let be the optimal value of the interval relaxation of the Big-M formulation (2), and let with as in (6). Let be an optimal solution to (5), and . If , then
Both added terms are nonnegative in this regime, so the perspective relaxation is at least as tight as both the Big-M relaxation and , with explicit gaps that depend on the relaxation's own optimal solution. This is the theoretical basis for using with a tight, valid in branch-and-bound.
Formalization Note is a binder with the hypotheses and for all feasible . The regime is written .
Preamble
import Mathlib import Definitions.Def_L0BnB_Strength_Penalties import Definitions.Def_L0BnB_Strength_Relaxations
Formal statement
namespace L0BnB.Strength
/-- Proposition 1, p. 7: for `√(λ₀/λ₂) > M` and `β*` an optimal solution of (5),
`V_{PR(M)} ≥ V_{B(M)} + λ₂ (M ‖β*‖₁ − ‖β*‖₂²)` (7) and
`V_{PR(M)} ≥ V_{PR(∞)} + h(λ₀, λ₂, M) ‖β*‖₁` (8). -/
theorem proposition_1 {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) ∧
L0BnB.Reduced.VPR X y lam0 lam2 M ≥ VPRinf X y lam0 lam2 + hGap lam0 lam2 M * ∑ i, |βs i| := 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; App. A, Proof of Proposition 1, pp. 28–29
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.