Proposition 4.2, p. 1492 — for q ∈ Δ̂ᴺ_sym the Minkowski functional (12) of the shifted q-permutohull is a norm
ProvedRiskUncSets.InnerApprox.proposition_4_2gaugenormp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1permutohullrobust-optimization
Let , let be a centrally symmetric (comonotone) generator, let have sample mean , and let . Assume that has nonempty interior. Then the function
is a norm on :
- if and only if ;
- for every ;
- .
With this is the paper's norm of (12). It is the yardstick in which Theorem 4.5 measures the size of an inner approximation.
Formalization Note The nonempty-interior hypothesis is added: without it (for instance , or all equal, where ) the infimum (12) is off and the function is not a norm; Mathlib's gauge would return there instead. Nonnegativity of holds for every gauge and is not restated. Interior is taken in the product topology of , which is the Euclidean one.
Preamble
import Mathlib import Definitions.Def_RiskUncSets_InnerApprox_Setting noncomputable section
Formal statement
namespace RiskUncSets.InnerApprox
/-- Proposition 4.2: for `q ∈ Δ̂ᴺ_sym` the gauge (12) of `π̃_q(𝒜)` is a norm, provided
`Π_q(𝒜)` has nonempty interior (added: otherwise (12) is `+∞` off `0`). -/
theorem proposition_4_2 {N n : ℕ} (hN : 0 < N) (q : Fin N → ℝ)
(hq : q ∈ symRestrictedSimplex N) (a : Fin N → Fin n → ℝ)
(hint : (interior (permutohull q a)).Nonempty) :
(∀ w : Fin n → ℝ, normQ q a w = 0 ↔ w = 0) ∧
(∀ (β : ℝ) (w : Fin n → ℝ), normQ q a (β • w) = |β| * normQ q a w) ∧
∀ w₁ w₂ : Fin n → ℝ, normQ q a (w₁ + w₂) ≤ normQ q a w₁ + normQ q a w₂ := by sorry
end RiskUncSets.InnerApprox
Source
Bertsimas & Brown, Constructing uncertainty sets for robust linear optimization, Oper. Res. 57(6) (2009), p. 1492, Proposition 4.2, (12)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.