Proof of Theorem 1, p. 496 — at every binary point
ProvedSDDiP.Envelope.g_eq_f_binarybinary-optimizationconvex-envelopep2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a real function on and as in the proof of Theorem 1. For every binary point the maximum defining is attained and
This is the exactness half of Theorem 1 for the proof's function ; it fails for general finite sets in place of .
Formalization Note The attained maximum is stated as IsGreatest (primalValues f x) (f x).
Preamble
import Mathlib import Definitions.Def_SDDiP_Envelope_ProofLP
Formal statement
namespace SDDiP.Envelope
/-- Proof of Theorem 1, p. 496: `g(x) = f(x)` at every binary point `x ∈ {0,1}ⁿ`, where
`g(x) = max_{(α,β) ∈ Π} {αᵀx + β}`; the maximum is attained and equals `f(x)`. -/
theorem g_eq_f_binary {n : ℕ} (f : (Fin n → ℝ) → ℝ) (x : Fin n → ℝ) (hx : x ∈ binaryPoints n) :
IsGreatest (primalValues f x) (f x) ∧ g f x = f x := by sorry
end SDDiP.Envelope
Source
Zou, Ahmed, Sun, Stochastic dual dynamic integer programming, Math. Program. 175 (2019), p. 496, proof of Theorem 1 ('Therefore, g(x) = f(x) for all x ∈ {0, 1}^n')
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.