Proof of Theorem 34, p. 43 — eˣ ≤ 1 + x + (x²/2)e^{|x|}, hence e^{αx+αδ} ≤ e^{αx} + αδe^{αx} + ½α²δ²e^{αx+|α|c} for |δ| ≤ c
ProvedLSWCuttingPlane.ChasingZero.exp_taylor_boundexponential-inequalityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1potential-functiontaylor-bound
For every real number ,
and consequently, for all real , , , with ,
This second-order bound on the exponential is the first step of the proof of Theorem 34: applied coordinatewise, it controls the expected growth of the exponential potential under a random mean-zero move.
Formalization Note The two parts are stated as a conjunction; the second quantifies over all real (the hypothesis forces ).
Preamble
import Mathlib import Definitions.Def_LSWCuttingPlane_ChasingZero_Setting
Formal statement
namespace LSWCuttingPlane.ChasingZero
/-- Proof of Theorem 34, p. 43, first display: `e^x ≤ 1 + x + (x²/2) e^{|x|}` for all real `x`,
and therefore `e^{αx+αδ} ≤ e^{αx} + αδ e^{αx} + ½ α² δ² e^{αx + |α| c}` whenever `|δ| ≤ c`. -/
theorem exp_taylor_bound :
(∀ x : ℝ, Real.exp x ≤ 1 + x + x ^ 2 / 2 * Real.exp |x|) ∧
(∀ c δ x α : ℝ, |δ| ≤ c →
Real.exp (α * x + α * δ) ≤
Real.exp (α * x) + α * δ * Real.exp (α * x)
+ 1 / 2 * α ^ 2 * δ ^ 2 * Real.exp (α * x + |α| * c)) := by sorry
end LSWCuttingPlane.ChasingZero
Source
Lee, Sidford, Wong, A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization, arXiv:1508.04874v2, p. 43, proof of Theorem 34, first display
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.