Globalized robust counterparts of conic constraints: norms, distances, the recessive cone, and the function Psi
DefinitionRobustOptimization_GRCConicconvex-optimizationoperations-researchoptimization
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 Definitions.Def_RobustOptimization_GRC
import Mathlib
namespace RobustOptimization
open Matrix Finset
/-- A norm on `ℝⁿ`, carried as a function together with its defining properties, so that the
arbitrary norms `‖·‖_Q` and `‖·‖_s` of Chapter 11 can be quantified over. -/
def IsNormOn {n : ℕ} (N : (Fin n → ℝ) → ℝ) : Prop :=
(∀ x, N x = 0 ↔ x = 0) ∧ (∀ (c : ℝ) (x : Fin n → ℝ), N (c • x) = |c| * N x) ∧
∀ x y, N (x + y) ≤ N x + N y
/-- The norm conjugate to `N` with respect to the standard inner product:
`N*(f) = sup {fᵀe : N(e) ≤ 1}`, carried as a predicate so that no supremum is taken on faith. -/
def IsDualNorm {n : ℕ} (N Nstar : (Fin n → ℝ) → ℝ) : Prop :=
∀ f : Fin n → ℝ, IsLUB {t : ℝ | ∃ e : Fin n → ℝ, N e ≤ 1 ∧ t = f ⬝ᵥ e} (Nstar f)
/-- The distance from `u` to a set `S`, measured in the norm `N`. -/
noncomputable def distN {n : ℕ} (N : (Fin n → ℝ) → ℝ) (S : Set (Fin n → ℝ))
(u : Fin n → ℝ) : ℝ :=
sInf {t : ℝ | ∃ v ∈ S, t = N (u - v)}
/-- The distance `dist(ζ, Z|L) = min {‖ζ - v‖ : v ∈ Z, ζ - v ∈ L}` of (11.1.5): the distance to
`Z` along the cone `L`. -/
noncomputable def distAlong {n : ℕ} (N : (Fin n → ℝ) → ℝ) (Z L : Set (Fin n → ℝ))
(ζ : Fin n → ℝ) : ℝ :=
sInf {t : ℝ | ∃ v ∈ Z, ζ - v ∈ L ∧ t = N (ζ - v)}
/-- The recessive cone of a nonempty closed convex set `Q`, based at a point `x` of `Q`
(Definition 11.3.1): the directions along which `Q` is unbounded from `x`. -/
def RecConeAt {k : ℕ} (Q : Set (Fin k → ℝ)) (x : Fin k → ℝ) : Set (Fin k → ℝ) :=
{h | ∀ t : ℝ, 0 ≤ t → x + t • h ∈ Q}
/-- The Globalized Robust Counterpart (11.1.6) of the uncertain convex constraint (11.1.4)
`[P⁰ + ∑_ℓ ζ_ℓ P^ℓ]y - [p⁰ + ∑_ℓ ζ_ℓ p^ℓ] ∈ Q`, under a perturbation structure that splits the
perturbation into `S` blocks, each with its own normal range `Zˢ`, cone `Lˢ`, norm `‖·‖ₛ` and
global sensitivity `αₛ`. The perturbation is carried as the family of its blocks. -/
def ConicGRCFeasible {k n S : ℕ} (Ls : Fin S → ℕ)
(P0 : Matrix (Fin k) (Fin n) ℝ)
(P : (s : Fin S) → Fin (Ls s) → Matrix (Fin k) (Fin n) ℝ)
(p0 : Fin k → ℝ) (p : (s : Fin S) → Fin (Ls s) → Fin k → ℝ)
(Q : Set (Fin k → ℝ)) (NQ : (Fin k → ℝ) → ℝ)
(Z : (s : Fin S) → Set (Fin (Ls s) → ℝ)) (L : (s : Fin S) → Set (Fin (Ls s) → ℝ))
(Ns : (s : Fin S) → (Fin (Ls s) → ℝ) → ℝ) (α : Fin S → ℝ) (y : Fin n → ℝ) : Prop :=
∀ ζ : (s : Fin S) → Fin (Ls s) → ℝ, (∀ s, ∃ v ∈ Z s, ζ s - v ∈ L s) →
distN NQ Q ((P0.mulVec y - p0) +
∑ s, ∑ l, ζ s l • ((P s l).mulVec y - p s l))
≤ ∑ s, α s * distAlong (Ns s) (Z s) (L s) (ζ s)
/-- The function `Ψ` of (11.4.1): `Ψ(M) = max {dist_F(Me, K_F) : e ∈ K_E, ‖e‖_E ≤ 1}`, carried
as a predicate asserting that the given real is that least upper bound. -/
def IsPsi {p q : ℕ} (NE : (Fin p → ℝ) → ℝ) (NF : (Fin q → ℝ) → ℝ)
(KE : Set (Fin p → ℝ)) (KF : Set (Fin q → ℝ)) (M : Matrix (Fin q) (Fin p) ℝ)
(ψ : ℝ) : Prop :=
IsLUB {t : ℝ | ∃ e ∈ KE, NE e ≤ 1 ∧ t = distN NF KF (M.mulVec e)} ψ
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, p. 282, Definition 11.1.1 of robust feasibility with global sensitivity and Definition 11.1.2 of its structured version, with the uncertain convex constraint (11.1.4) and the distances of (11.1.5), (11.1.6); p. 284, Definition 11.3.1 of the recessive cone; p. 286, the function Psi of (11.4.1) and the setup preceding it. Source PDF sha256 b4aba60d1c863237fe4ee6ce4b62051d945cddbcb78523d03b06d6eff13a7c91.