Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Globalized robust counterparts of conic constraints: norms, distances, the recessive cone, and the function Psi

Definition
RobustOptimization_GRCConic

by naimengye · Sep 18, 2026 · Mathlib 0df444a (Lean v4.33.1)

convex-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 RobustOptimization
Source
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.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me