(47) — the minimum of when
ProvedL0BnB.Duality.eq_47lagrangian-dualityp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1reverse-huber
Let , let (standing for ) and , and let for . If , then the minimum of over is attained and
This is the value of the inner minimization of the Lagrangian in the proof of Theorem 2 when the correlation is large; together with (45) it gives the closed form of the dual function.
Formalization Note "min" is stated as IsLeast of the range of , so attainment is part of the statement. The paper's subsequent combined formula is not stated: it fails when .
Preamble
import Mathlib import Definitions.Def_L0BnB_Duality_Dual
Formal statement
namespace L0BnB.Duality
/-- (47), proof of Theorem 2, p. 31. For `a = αᵀXᵢ` and `η = ηᵢ ≥ 0` with
`|a| − η ≥ 2√(λ₀λ₂)`, the minimum over `βᵢ ∈ ℝ` of `Dᵢ(βᵢ) = ψ₁(βᵢ; λ₀, λ₂) + a βᵢ + η|βᵢ|`
is attained and equals `−(|a| − η)²/(4λ₂) + λ₀`. -/
theorem eq_47 (lam0 lam2 a η : ℝ) (hlam0 : 0 < lam0) (hlam2 : 0 < lam2) (hη : 0 ≤ η)
(hcase : |a| - η ≥ 2 * Real.sqrt (lam0 * lam2)) :
IsLeast (Set.range (D lam0 lam2 a η)) (-(1 / (4 * lam2)) * (|a| - η) ^ 2 + lam0) := by sorry
end L0BnB.Duality
Source
Hazimeh, Mazumder, Saab, Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization, arXiv:2004.06152v2, p. 31, Proof of Theorem 2, Case 2, (47)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.