Proof of Theorem 1 — reduction of the coordinate problem ω to the one-variable problem (36)
ProvedL0BnB.Reduced.reduction_36p2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1perspective-relaxationsparse-regression
Fix and with . Consider the one-coordinate constraints of the interval relaxation of the perspective formulation,
and let , with when . Then:
- every feasible pair satisfies and ;
- for every , the pair is feasible;
- consequently, a real number is the minimum of over the feasible pairs if and only if it is the minimum of problem (36),
This eliminates the indicator variable and turns the computation of into a one-dimensional minimization over , which the two cases of the proof of Theorem 1 then solve.
Formalization Note "Is the minimum" is IsLeast: the value belongs to the set and bounds it from below. The paper's side condition of (36) is the hypothesis on .
Preamble
import Mathlib import Definitions.Def_L0BnB_Reduced_ReverseHuber import Definitions.Def_L0BnB_Reduced_Setup
Formal statement
namespace L0BnB.Reduced
/-- Proof of Theorem 1, p. 28: for one coordinate `b` with `|b| ≤ M`, every feasible `(z, s)` of
(35b)–(35d) has `s ≥ b²` and `z ≥ ẑ = max{b²/s, |b|/M}`; for every `s ≥ b²` the pair `(ẑ, s)` is
feasible; hence `ω(b; λ₀, λ₂, M)` is the minimum of (36). -/
theorem reduction_36 (lam0 lam2 M b : ℝ) (h0 : 0 < lam0) (h2 : 0 < lam2) (hM : 0 < M)
(hb : |b| ≤ M) :
(∀ z s : ℝ, CoordFeas M b z s → b ^ 2 ≤ s ∧ zhat M b s ≤ z) ∧
(∀ s : ℝ, b ^ 2 ≤ s → CoordFeas M b (zhat M b s) s) ∧
(∀ v : ℝ, IsLeast (omegaValues lam0 lam2 M b) v ↔ IsLeast (values36 lam0 lam2 M b) v) := 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, reduction to (36)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.