B.8, p. 32 — eliminating β: some β satisfies rν + νΣD·exp((a+β)/ν − 1) ≤ β iff ν log ΣD·exp(a/ν) + rν ≤ 0
ProvedBootRobust.NWDual.beta_eliminationconvex-analysislagrangian-dualitylog-sum-expp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , , and , and write . Consider
Then:
- is minimized at ;
- some satisfies if and only if
With this turns the dual of the strong-duality step into the dual program (33) of Lemma 2.
Formalization Note The paper prints ; the first-order condition gives , which is what is stated here. The paper's final display (the equivalence in item 2) is unaffected by the slip.
Preamble
import Mathlib import Definitions.Def_BootRobust_NWDual_Setting
Formal statement
namespace BootRobust.NWDual
/-- B.8, p. 32 (elimination of `β`): for `D ∈ Dₙ` and `ν > 0`, the map
`β ↦ r ν + ν ∑ᵢ Dᵢ exp((aᵢ + β)/ν − 1) − β` is minimized at `β⋆ = ν − ν log ∑ᵢ Dᵢ exp(aᵢ/ν)`, and
some `β` satisfies `r ν + ν ∑ᵢ Dᵢ exp((aᵢ + β)/ν − 1) ≤ β` if and only if
`ν log (∑ᵢ exp(aᵢ/ν) Dᵢ) + r ν ≤ 0`. -/
theorem beta_elimination {ι : Type*} [Fintype ι] [DecidableEq ι]
(D : ι → ℝ) (hD : D ∈ stdSimplex ℝ ι) (a : ι → ℝ) (ν : ℝ) (hν : 0 < ν) (r : ℝ) :
(∀ β : ℝ,
r * ν + ν * ∑ i, D i * Real.exp
((a i + (ν - ν * Real.log (∑ j, Real.exp (a j / ν) * D j))) / ν - 1) -
(ν - ν * Real.log (∑ j, Real.exp (a j / ν) * D j)) ≤
r * ν + ν * ∑ i, D i * Real.exp ((a i + β) / ν - 1) - β) ∧
((∃ β : ℝ, r * ν + ν * ∑ i, D i * Real.exp ((a i + β) / ν - 1) ≤ β) ↔
ν * Real.log (∑ i, Real.exp (a i / ν) * D i) + r * ν ≤ 0) := by sorry
end BootRobust.NWDual
Source
Bertsimas and Van Parys, Bootstrap robust prescriptive analytics, arXiv:1711.09974v2, B.8 (proof of Lemma 2), p. 32, 'Using first-order optimality conditions, the optimal β⋆ must satisfy …' and the final display
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.