Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1 (Reduced Relaxation) — the interval relaxation of the perspective formulation is equivalent to (5)

Proved
L0BnB.Reduced.theorem_1

by mikedeng1 · Oct 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

mixed-integer-programmingp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1perspective-relaxationreverse-hubersparse-regression

Let X∈Rn×pX\in\mathbb R^{n\times p}X∈Rn×p, y∈Rny\in\mathbb R^ny∈Rn and λ0,λ2,M>0\lambda_0,\lambda_2,M>0λ0​,λ2​,M>0. Consider the interval relaxation of the perspective formulation (3),

min⁡β,z,s 12∥y−Xβ∥22+λ0∑i∈[p]zi+λ2∑i∈[p]sis.t.βi2≤sizi,  −Mzi≤βi≤Mzi,  zi∈[0,1],  si≥0,i∈[p],\min_{\beta,z,s}\ \tfrac12\|y-X\beta\|_2^2+\lambda_0\sum_{i\in[p]}z_i+\lambda_2\sum_{i\in[p]}s_i \quad\text{s.t.}\quad \beta_i^2\le s_iz_i,\ \ -Mz_i\le\beta_i\le Mz_i,\ \ z_i\in[0,1],\ \ s_i\ge0,\quad i\in[p],β,z,smin​ 21​∥y−Xβ∥22​+λ0​i∈[p]∑​zi​+λ2​i∈[p]∑​si​s.t.βi2​≤si​zi​,  −Mzi​≤βi​≤Mzi​,  zi​∈[0,1],  si​≥0,i∈[p],

and the reduced problem (5),

min⁡β∈Rp F(β):=12∥y−Xβ∥22+∑i∈[p]ψ(βi;λ0,λ2,M)s.t.∥β∥∞≤M,\min_{\beta\in\mathbb R^p}\ F(\beta):=\tfrac12\|y-X\beta\|_2^2+\sum_{i\in[p]}\psi(\beta_i;\lambda_0,\lambda_2,M)\quad\text{s.t.}\quad\|\beta\|_\infty\le M,β∈Rpmin​ F(β):=21​∥y−Xβ∥22​+i∈[p]∑​ψ(βi​;λ0​,λ2​,M)s.t.∥β∥∞​≤M,

where ψ=ψ1(⋅;λ0,λ2)=2λ0B(⋅ λ2/λ0)\psi=\psi_1(\cdot;\lambda_0,\lambda_2)=2\lambda_0\mathcal B(\cdot\,\sqrt{\lambda_2/\lambda_0})ψ=ψ1​(⋅;λ0​,λ2​)=2λ0​B(⋅λ2​/λ0​​) if λ0/λ2≤M\sqrt{\lambda_0/\lambda_2}\le Mλ0​/λ2​​≤M and ψ=ψ2(⋅;λ0,λ2,M)=(λ0/M+λ2M)∣⋅∣\psi=\psi_2(\cdot;\lambda_0,\lambda_2,M)=(\lambda_0/M+\lambda_2M)|\cdot|ψ=ψ2​(⋅;λ0​,λ2​,M)=(λ0​/M+λ2​M)∣⋅∣ if λ0/λ2>M\sqrt{\lambda_0/\lambda_2}>Mλ0​/λ2​​>M, with B\mathcal BB the reverse Huber penalty (4). Let VPR(M)V_{\mathrm{PR}(M)}VPR(M)​ be the optimal value of (5). The two problems are equivalent in the following sense:

  1. a vector β\betaβ can be completed to a feasible point (β,z,s)(\beta,z,s)(β,z,s) of the relaxation if and only if ∥β∥∞≤M\|\beta\|_\infty\le M∥β∥∞​≤M;
  2. for every β\betaβ with ∥β∥∞≤M\|\beta\|_\infty\le M∥β∥∞​≤M, the minimum of the relaxation's objective over all (z,s)(z,s)(z,s) with (β,z,s)(\beta,z,s)(β,z,s) feasible exists and equals F(β)F(\beta)F(β);
  3. both problems attain their minimum, and both optimal values equal VPR(M)V_{\mathrm{PR}(M)}VPR(M)​.

Theorem 1 eliminates the indicator variables zzz and the conic auxiliary variables sss: the relaxation is a box-constrained least squares problem with a separable penalty, which is either the reverse Huber penalty or an ℓ1\ell_1ℓ1​ penalty depending on how λ0/λ2\sqrt{\lambda_0/\lambda_2}λ0​/λ2​​ compares with MMM. This reduced form underlies the paper's first-order solver for node relaxations and its dual bounds.

Formalization Note The paper's "equivalent" is formalized as the three clauses above; "minimum" is IsLeast (membership plus lower bound), so attainment is asserted and the real sInf defining VPR(M)V_{\mathrm{PR}(M)}VPR(M)​ is never evaluated on an empty or unbounded set. Norms are explicit coordinate sums and ∥β∥∞≤M\|\beta\|_\infty\le M∥β∥∞​≤M is ∣βi∣≤M|\beta_i|\le M∣βi​∣≤M for all iii. No normalization of XXX or yyy is assumed (the unit-norm assumption of the paper begins in Section 3).

Preamble
import Mathlib
import Definitions.Def_L0BnB_Reduced_ReverseHuber
import Definitions.Def_L0BnB_Reduced_Setup
Formal statement
namespace L0BnB.Reduced

/-- Theorem 1 (Reduced Relaxation), p. 6: the interval relaxation of the perspective formulation (3)
is equivalent to (5), `min F(β)` subject to `‖β‖_∞ ≤ M`. Precisely:
1. `β` extends to a feasible `(β, z, s)` of the relaxation iff `‖β‖_∞ ≤ M`;
2. for every `β` with `‖β‖_∞ ≤ M`, the minimum of the relaxation's objective over `(z, s)` is `F(β)`;
3. both problems attain their minimum, and the common optimal value is `V_{PR(M)}`. -/
theorem theorem_1 {n p : ℕ} (X : Matrix (Fin n) (Fin p) ℝ) (y : Fin n → ℝ) (lam0 lam2 M : ℝ)
    (h0 : 0 < lam0) (h2 : 0 < lam2) (hM : 0 < M) :
    (∀ β : Fin p → ℝ, (∃ z s : Fin p → ℝ, PRFeas M β z s) ↔ β ∈ box p M) ∧
    (∀ β ∈ box p M, IsLeast (PRValuesAt X y lam0 lam2 M β) (F X y lam0 lam2 M β)) ∧
    (IsLeast (PRValues X y lam0 lam2 M) (VPR X y lam0 lam2 M) ∧
      IsLeast (F X y lam0 lam2 M '' box p M) (VPR X y lam0 lam2 M)) := 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. 6, Theorem 1 (with (3), p. 5, and (4)–(5), p. 6); proof p. 28
Human review
  • Endorsed by Shuze Chen · Oct 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 8, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me