Robust feasibility of an uncertain linear inequality, and conically represented perturbation sets
DefinitionRobustOptimization_LOconvex-optimizationlinear-optimizationoptimization
Retired 2026-09-21. This declaration belongs to the first draft of the Ben-Tal, El Ghaoui and Nemirovski, Robust Optimization (2009) mission series, which was withdrawn in full. The series is being redrafted from the source under the namespace RobustOpt; build on those declarations, not on this one. The original statement and prose are preserved in the Prove2OR repository, branch textbook-sequential, under papers/ben-tal-2009-robust-optimization/retired/.
Definition code
import Mathlib
namespace RobustOptimization
open Matrix Finset
/-- A vector `x` is robust feasible for the uncertain linear inequality
`aᵀx ≤ b` whose data is affinely perturbed,
`[a; b] = [a⁰; b⁰] + ∑_ℓ ζ_ℓ [a^ℓ; b^ℓ]` with `ζ` ranging over the perturbation set `Z`. -/
def RobustFeasible {n L : ℕ} (a0 : Fin n → ℝ) (a : Fin L → Fin n → ℝ) (b0 : ℝ) (b : Fin L → ℝ)
(Z : Set (Fin L → ℝ)) (x : Fin n → ℝ) : Prop :=
∀ ζ ∈ Z, (a0 + ∑ l, ζ l • a l) ⬝ᵥ x ≤ b0 + ∑ l, ζ l * b l
/-- The unit box perturbation set `Box₁ = {ζ : ‖ζ‖_∞ ≤ 1}`. -/
def Box1 (L : ℕ) : Set (Fin L → ℝ) := {ζ | ∀ l, |ζ l| ≤ 1}
/-- The ball perturbation set `Ball_Ω = {ζ : ‖ζ‖₂ ≤ Ω}`. -/
def BallRadius (L : ℕ) (Ω : ℝ) : Set (Fin L → ℝ) :=
{ζ | Real.sqrt (∑ l, (ζ l) ^ 2) ≤ Ω}
/-- A conically represented perturbation set `Z = {ζ : ∃u, Pζ + Qu + p ∈ K}`. -/
def ConicRepresented {L K' N : ℕ} (P : Matrix (Fin N) (Fin L) ℝ)
(Qm : Matrix (Fin N) (Fin K') ℝ) (p : Fin N → ℝ) (K : Set (Fin N → ℝ)) :
Set (Fin L → ℝ) :=
{ζ | ∃ u : Fin K' → ℝ, P.mulVec ζ + Qm.mulVec u + p ∈ K}
/-- The dual cone `K_* = {y : yᵀz ≥ 0 for all z ∈ K}`. -/
def DualCone {N : ℕ} (K : Set (Fin N → ℝ)) : Set (Fin N → ℝ) :=
{y | ∀ z ∈ K, 0 ≤ y ⬝ᵥ z}
/-- `K` is a closed convex pointed cone with a nonempty interior — the standing assumption on
the cone of a conic representation. -/
def IsProperCone {N : ℕ} (K : Set (Fin N → ℝ)) : Prop :=
IsClosed K ∧ Convex ℝ K ∧ (∀ c : ℝ, 0 ≤ c → ∀ z ∈ K, c • z ∈ K) ∧
(∀ z ∈ K, -z ∈ K → z = 0) ∧ (interior K).Nonempty
end RobustOptimizationSource
Aharon Ben-Tal, Laurent El Ghaoui and Arkadi Nemirovski, Robust Optimization, Princeton Series in Applied Mathematics, Princeton University Press, 2009, https://doi.org/10.1515/9781400831050, pp. 18-20: the uncertain inequality (1.3.4), the uncertainty set (1.3.5), the semi-infinite constraint (1.3.6), the box and ball perturbation sets of Examples 1.3.2 and 1.3.3, and the conic representation (1.3.10) with its cone assumptions. Source PDF sha256 b4aba60d1c863237fe4ee6ce4b62051d945cddbcb78523d03b06d6eff13a7c91.