Theorem 1 (Reduced Relaxation) — the interval relaxation of the perspective formulation is equivalent to (5)
ProvedL0BnB.Reduced.theorem_1Let , and . Consider the interval relaxation of the perspective formulation (3),
and the reduced problem (5),
where if and if , with the reverse Huber penalty (4). Let be the optimal value of (5). The two problems are equivalent in the following sense:
- a vector can be completed to a feasible point of the relaxation if and only if ;
- for every with , the minimum of the relaxation's objective over all with feasible exists and equals ;
- both problems attain their minimum, and both optimal values equal .
Theorem 1 eliminates the indicator variables and the conic auxiliary variables : the relaxation is a box-constrained least squares problem with a separable penalty, which is either the reverse Huber penalty or an penalty depending on how compares with . 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 is never evaluated on an empty or unbounded set. Norms are explicit coordinate sums and is for all . No normalization of or is assumed (the unit-norm assumption of the paper begins in Section 3).
import Mathlib import Definitions.Def_L0BnB_Reduced_ReverseHuber import Definitions.Def_L0BnB_Reduced_Setup
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.