Proof of Theorem 1, Case II — when
ProvedL0BnB.Reduced.case_IIp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1perspective-relaxationsparse-regression
Fix with , and with . Let be the minimum of over the pairs with
Then this minimum is attained and equals
In this regime the Big-M constraint is active at the optimum, and the ridge term of the perspective formulation turns into a pure penalty in the relaxation.
Formalization Note The statement is IsLeast of the set of values over the feasible pairs, so it asserts both attainment and the lower bound.
Preamble
import Mathlib import Definitions.Def_L0BnB_Reduced_ReverseHuber import Definitions.Def_L0BnB_Reduced_Setup
Formal statement
namespace L0BnB.Reduced
/-- Proof of Theorem 1, Case II, p. 28: if `√(λ₀/λ₂) > M` and `|b| ≤ M`, then
`ω(b; λ₀, λ₂, M) = (λ₀/M + λ₂M)|b| = ψ₂(b; λ₀, λ₂, M)`. -/
theorem case_II (lam0 lam2 M b : ℝ) (h0 : 0 < lam0) (h2 : 0 < lam2) (hM : 0 < M)
(hreg : M < Real.sqrt (lam0 / lam2)) (hb : |b| ≤ M) :
IsLeast (omegaValues lam0 lam2 M b) (psi2 lam0 lam2 M b) := by sorry
end L0BnB.Reduced
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 Theorem 1, Case II
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.