(28) — closed form of the dual feasible µ̂ of (27)
ProvedL0BnB.DualGap.eq_28dual-boundsdualityp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1sparse-regression
Let , , , and . If maximizes over the with for all (problem (27)), then for every
So the dual feasible solution of the regime is computable in closed form from the residual.
Preamble
import Mathlib import Definitions.Def_L0BnB_DualGap_Setup import Definitions.Def_L0BnB_DualGap_Duals
Formal statement
namespace L0BnB.DualGap
/-- (28), p. 14: the maximizer `µ̂` of (27) is given in closed form by
`µ̂ᵢ = [|ρ̂ᵀXᵢ| − λ₀/M − λ₂M]₊`. -/
theorem eq_28 {n p : ℕ} (X : Matrix (Fin n) (Fin p) ℝ) (y : Fin n → ℝ)
(lam0 lam2 M : ℝ) (hlam0 : 0 < lam0) (hlam2 : 0 < lam2) (hM : 0 < M)
(βhat μhat : Fin p → ℝ) (hμ : IsMuHat X y lam0 lam2 M βhat μhat) :
∀ i, μhat i = max (|colInner X (rhoHat X y βhat) i| - lam0 / M - lam2 * M) 0 := by sorry
end L0BnB.DualGap
Source
Hazimeh, Mazumder, Saab, Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization, arXiv:2004.06152v2, p. 14, (27), (28)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.