(8) — for ,
ProvedL0BnB.Strength.ineq_8mixed-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), the value (6), and an optimal solution of (5). With ,
For the factor is strictly positive, so the perspective relaxation with a finite bound is strictly stronger than whenever .
Formalization Note is (6) as printed (the infimum of over ); see the definition item.
Preamble
import Mathlib import Definitions.Def_L0BnB_Strength_Penalties import Definitions.Def_L0BnB_Strength_Relaxations
Formal statement
namespace L0BnB.Strength
/-- (8), Proposition 1, p. 7 (proof (38), p. 29): for `√(λ₀/λ₂) > M` and `β*` an optimal solution
of (5), `V_{PR(M)} ≥ V_{PR(∞)} + h(λ₀, λ₂, M) ‖β*‖₁`. -/
theorem ineq_8 {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 ≥ 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, (8); proof p. 29, (38)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.