e-companion eq. (5): (corrected: lower semicontinuity added)
ProvedRandAssort.ec_eq_5assortment-optimizationoperations-researchoptimizationp2o-correctedp2o-gran-per-chapterp2o-plan-paperp2o-v1randomizationrobust-optimization
Let be a robust assortment instance satisfying the standing assumptions of §3, with a compact subset of a finite-dimensional real normed space. Suppose that for every the expected revenue is lower semicontinuous on . Let be the set of expected revenue vectors and its convex hull. Then for every randomized assortment ,
and all three minima are attained.
This identity lets the proof of Theorem 1 replace nature's choice of by a choice of in the convex set , where a minimax theorem applies.
Formalization Note is the real infimum of over . Each of the three equalities is stated as IsLeast: belongs to the set of values and bounds it from below. Here .
Differences from the source:
- correction: no continuity of u ↦ R(S,u) (only 𝒰 compact), first min written as attained → u ↦ R(S,u) lower semicontinuous on 𝒰 for every S ∈ 𝒮; reason: without it the first minimum need not exist: n = 1, 𝒮 = {{1}}, r₁ = 2, 𝒰 = [0,1], ℭ(1|{1},s) = s/2 for s ∈ (0,1] and ℭ(1|{1},0) = 1/2 satisfy every assumption, R({1},s) = s for s > 0 and R({1},0) = 1, so at p = e_{1} the infimum 0 is not attained
- encoding: products {1,…,n}, alternatives 𝒩₀ = 𝒩 ∪ {0} with r₀ = 0, a compact subset of a finite-dimensional space → Fin n, Option (Fin n) with none the no-purchase option, revenue summed over offered products, 𝒰 a subset of a finite-dimensional real normed space; reason: Lean convention; same instances
- encoding: min over 𝒰, over ℛ, over conv ℛ; 𝒮, 𝒰 implicitly nonempty → R⋆(p) as the real infimum ⨅, each minimum stated as IsLeast (attained); 𝒮, 𝒰 nonempty in the validity predicate; reason: the minima are undefined over empty sets; the infimum equals the attained minimum
Preamble
import Mathlib import Definitions.Def_RandAssort_Model import Definitions.Def_RandAssort_RevenueVectors
Formal statement
namespace RandAssort
/-- **e-companion eq. (5)**, proof of Theorem 1, e-companion p.ec8 of Z. Wang, H. Peura,
W. Wiesemann, *Randomized Assortment Optimization*, Operations Research (2024),
doi:10.1287/opre.2022.0129 (corrected: lower semicontinuity added):
`R⋆(p) = min_{u ∈ 𝒰} R(p, u) = min_{R ∈ ℛ} p⊤R = min_{R ∈ conv ℛ} p⊤R`.
For a valid instance in which `u ↦ R(S, u)` is lower semicontinuous on `𝒰` for every `S ∈ 𝒮`,
and for every randomized assortment `p ∈ Δ(𝒮)`, the worst-case revenue `R⋆(p)` is the least value
(1) of `u ↦ R(p, u)` over `𝒰`, (2) of `R ↦ p⊤R` over `ℛ`, and (3) of `R ↦ p⊤R` over the convex
hull `conv ℛ`; in particular all three minima are attained.
**Formalization Note** `R⋆(p)` is the real infimum `⨅ u ∈ 𝒰, R(p, u)` (`Instance.RstarP`);
`IsLeast A v` says that `v ∈ A` and `v` is a lower bound of `A`, i.e. `v` is the attained
minimum. `p⊤R = ∑_{S ∈ 𝒮} p_S R_S`. The paper writes `min` without a hypothesis that makes the
first minimum attained; the lower semicontinuity hypothesis is the correction (counterexample:
`n = 1`, `𝒮 = {{1}}`, `r₁ = 2`, `𝒰 = [0,1]`, `ℭ(1|{1},s) = s/2` for `s > 0` and `= 1/2` at
`s = 0`; then `inf_s R({1},s) = 0` is not attained). -/
theorem ec_eq_5 {n : ℕ} {E : Type*} [NormedAddCommGroup E] [NormedSpace ℝ E]
[FiniteDimensional ℝ E] (I : Instance n E) (hI : I.IsValid)
(hlsc : ∀ S ∈ I.S, LowerSemicontinuousOn (fun u => I.R S u) I.U)
(p : I.S → ℝ) (hp : p ∈ stdSimplex ℝ I.S) :
IsLeast (Set.range fun u : I.U => I.Rp p u) (I.RstarP p) ∧
IsLeast ((fun R : I.S → ℝ => ∑ S : I.S, p S * R S) '' I.revSet) (I.RstarP p) ∧
IsLeast ((fun R : I.S → ℝ => ∑ S : I.S, p S * R S) '' convexHull ℝ I.revSet)
(I.RstarP p) := by sorry
end RandAssort
Source
Wang–Peura–Wiesemann, Randomized Assortment Optimization, Oper. Res. (2024), doi:10.1287/opre.2022.0129, proof of Theorem 1, e-companion eq. (5), p.ec8
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.