§3.1, p.7 — : Rockafellian relaxation is a relaxation
ProvedRockafellianRelax.neg_conj_minValue_eq_inf_tiltoptimizationp2o-gran-per-chapterp2o-plan-paperp2o-v1stochastic-optimizationvariational-analysis
Let with min-value function , and let . Then
So the relaxed problem (3.2) has optimal value at most that of the actual problem, for every : it is a relaxation.
Differences from the source:
- encoding: f a Rockafellian for (3.1) (the context of the statement) → f : ℝᵐ × ℝⁿ → R̄ arbitrary; reason: every f is a Rockafellian for φ := f(0, ·), and φ does not occur in the statement, so no instance changes
- encoding: ℝᵐ × ℝⁿ, values in R̄ = [−∞, ∞], ⟨y, u⟩ → (Fin m → ℝ) × (Fin n → ℝ) with the product topology, EReal, y ⬝ᵥ u; reason: Lean convention; same instances (the product topology has the same convergent sequences as the Euclidean norm)
Preamble
import Mathlib import Definitions.Def_RockafellianRelax_conj import Definitions.Def_RockafellianRelax_minValue import Definitions.Def_RockafellianRelax_tilt
Formal statement
namespace RockafellianRelax
/-- **Rockafellian relaxation is a relaxation.** Royset, Chen & Eckstrand, arXiv:2204.04762v4, §3.1,
p.7: "Since −𝒱*(ȳ) = inf_{u,x} f(u, x) − ⟨ȳ, u⟩ and the right-hand side involves joint optimization
over u and x, one has 𝒱(0) ≥ −𝒱*(ȳ) always and the relaxed problem (3.2) is indeed a relaxation of
the actual problem (3.1)."
For every `f : ℝᵐ × ℝⁿ → R̄` and `ȳ ∈ ℝᵐ`: `−𝒱*(ȳ) = inf_{u,x} f(u, x) − ⟨ȳ, u⟩` and
`𝒱(0) ≥ −𝒱*(ȳ)`.
**Formalization Note.** `𝒱*` is the conjugate (`conj`, p.7) of the min-value function
`𝒱 = minValue f`; infima and suprema in `EReal`. -/
theorem neg_conj_minValue_eq_inf_tilt {m n : ℕ} (f : (Fin m → ℝ) × (Fin n → ℝ) → EReal)
(ybar : Fin m → ℝ) :
-(conj (minValue f) ybar) = (⨅ p : (Fin m → ℝ) × (Fin n → ℝ), tilt f ybar p) ∧
-(conj (minValue f) ybar) ≤ minValue f 0 := by sorry
end RockafellianRelax
Source
Royset, Chen & Eckstrand, Rockafellian Relaxation and Stochastic Optimization under Perturbations, arXiv:2204.04762v4, §3.1, p.7 ("Since −𝒱∗(ȳ) = inf_{u,x} f(u, x) − ⟨ȳ, u⟩ … one has 𝒱(0) ≥ −𝒱∗(ȳ) always")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.