Eq. (13) — the worst case over is
ProvedRobustRegLasso.Coupled.eq_13_coupled_worst_caseLet be an arbitrary norm on with , let , and let be convex functions. Consider the coupled uncertainty set and the budget set
Then for every ,
where and both suprema are taken in the extended reals.
This identity reduces the robust problem over a coupled set to a convex maximization over the budgets ; Corollaries 1 and 2 evaluate its last term for specific sets .
Formalization Note. The paper writes "max" on both sides; neither maximum need exist (e.g. empty or unbounded), so both are extended-real suprema: when both sides are , and when is unbounded on both sides are . The paper's first line, , holds as a set identity only when is downward closed in ; the identity (13) itself holds without that, and it is stated here for as defined on p. 6. The convexity of the is the paper's standing assumption and is not needed for (13). The norm space is nontrivial ().
import Mathlib import Definitions.Def_RobustRegLasso_Coupled_Basic
namespace RobustRegLasso.Coupled
/-- Eq. (13), proof of Theorem 4, Appendix B of arXiv:0811.1790v1, p. 19. For the coupled
uncertainty set `U′ = {(δ₁, …, δₘ) | f_j(‖δ₁‖ₐ, …, ‖δₘ‖ₐ) ≤ 0, j = 1, …, k}` with convex
`f_j : ℝᵐ → ℝ`, and `Z = {z ∈ ℝᵐ | f_j(z) ≤ 0, j = 1, …, k; z ≥ 0}`, for every `x`
`sup_{ΔA ∈ U′} ‖b − (A + ΔA)x‖ₐ = ‖b − Ax‖ₐ + sup_{c ∈ Z} |x|ᵀc`, both suprema taken in the extended
reals (so the identity also covers `Z = ∅`, both sides `⊥`, and an unbounded right-hand side, both
sides `⊤`). Requires `E ≠ 0` (`n ≥ 1`); the convexity of the `f_j` is the paper's standing
assumption. -/
theorem eq_13_coupled_worst_case {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E]
[Nontrivial E] {m k : ℕ} (a : Fin m → E) (b : E) (f : Fin k → (Fin m → ℝ) → ℝ)
(hf : ∀ j, ConvexOn ℝ Set.univ (f j)) (x : Fin m → ℝ) :
robustObjective a b (coupledSet f) x =
((‖b - matVec a x‖ : ℝ) : EReal) +
⨆ c ∈ budgetSet f, ((∑ i, |x i| * c i : ℝ) : EReal) := by sorry
end RobustRegLasso.Coupled
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.