Proposition 2 — if ; if and
ProvedL0BnB.BigMvsPR.proposition_2Let , and . Let be the optimal value of the interval relaxation of the Big-M formulation (2) of -regularized least squares, and
the value (6) of the interval relaxation of the perspective formulation , where is the reverse Huber penalty (4). Let be the set of minimizers in (6) and as in (9). Then:
- if , then
- if and , then
Neither relaxation dominates the other in general: a tight Big-M bound makes the Big-M relaxation the stronger one, while a loose one makes it the weaker one, provided some optimal solution of lies in the box.
Formalization Note Optimal values are real infima (sInf), well defined because the objectives are nonnegative and the feasible sets nonempty. The paper remarks (p. 8) that the proposition applies for any ; the statement here assumes , since the function and the reformulation (37) divide by ; at the hypothesis of (11) cannot hold.
import Mathlib import Definitions.Def_L0BnB_BigMvsPR_Penalties import Definitions.Def_L0BnB_BigMvsPR_Relaxations
namespace L0BnB.BigMvsPR
/-- Proposition 2, p. 7: with `L(M)` as in (9),
(10) `V_{B(M)} ≥ V_{PR(∞)}` if `M ≤ ½ √(λ₀/λ₂)`, and
(11) `V_{B(M)} ≤ V_{PR(∞)}` if `M ≥ √(λ₀/λ₂)` and `λ₂ ∈ L(M)`. -/
theorem proposition_2 {n p : ℕ} (X : Matrix (Fin n) (Fin p) ℝ) (y : Fin n → ℝ) (lam0 lam2 M : ℝ)
(hlam0 : 0 < lam0) (hlam2 : 0 < lam2) (hM : 0 < M) :
(M ≤ (1 / 2) * Real.sqrt (lam0 / lam2) → L0BnB.Strength.VPRinf X y lam0 lam2 ≤ L0BnB.Strength.VB X y lam0 lam2 M) ∧
(Real.sqrt (lam0 / lam2) ≤ M → lam2 ∈ L X y lam0 M →
L0BnB.Strength.VB X y lam0 lam2 M ≤ L0BnB.Strength.VPRinf X y lam0 lam2) := by sorry
end L0BnB.BigMvsPR
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.