Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1, PDF pp. 5–6 β€” if 𝒰 is a simplex in ℝ^m_+, some affine policy is optimal for Ξ _Adapt(𝒰)

Proved
AffinePolicies.Simplex.theorem_1

by mikedeng1 Β· Oct 5, 2026 Β· Mathlib 0df444a (Lean v4.33.1)

adaptive-optimizationaffine-policieslinear-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1robust-optimization

Consider the two-stage adaptive problem Ξ Adapt(U)\Pi_{Adapt}(\mathcal U)Ξ Adapt​(U) of model (1),

zAdapt(U)=min⁑x, y(β‹…)Β cTx+max⁑b∈UdTy(b)s.t.Β Ax+By(b)β‰₯b,Β xβ‰₯0,Β y(b)β‰₯0Β Β βˆ€b∈U,z_{Adapt}(\mathcal U)=\min_{x,\,y(\cdot)}\ c^Tx+\max_{b\in\mathcal U}d^Ty(b)\quad\text{s.t. } Ax+By(b)\ge b,\ x\ge 0,\ y(b)\ge 0\ \ \forall b\in\mathcal U,zAdapt​(U)=x,y(β‹…)min​ cTx+b∈Umax​dTy(b)s.t.Β Ax+By(b)β‰₯b,Β xβ‰₯0,Β y(b)β‰₯0Β Β βˆ€b∈U,

with A∈RmΓ—n1A\in\mathbb R^{m\times n_1}A∈RmΓ—n1​, B∈RmΓ—n2B\in\mathbb R^{m\times n_2}B∈RmΓ—n2​, c∈R+n1c\in\mathbb R^{n_1}_+c∈R+n1​​, d∈R+n2d\in\mathbb R^{n_2}_+d∈R+n2​​. Suppose the uncertainty set is a simplex,

U=conv⁑(b1,…,bm+1),\mathcal U=\operatorname{conv}(b^1,\dots,b^{m+1}),U=conv(b1,…,bm+1),

where b1,…,bm+1∈R+mb^1,\dots,b^{m+1}\in\mathbb R^m_+b1,…,bm+1∈R+m​ are affinely independent, and that the problem is feasible. Then there is an optimal two-stage solution (x^,y^)(\hat x,\hat y)(x^,y^​) whose second stage is an affine function of bbb: there are P∈Rn2Γ—mP\in\mathbb R^{n_2\times m}P∈Rn2​×m and q∈Rn2q\in\mathbb R^{n_2}q∈Rn2​ with

y^(b)=Pb+qforΒ allΒ b∈U,\hat y(b)=Pb+q\qquad\text{for all } b\in\mathcal U,y^​(b)=Pb+qforΒ allΒ b∈U,

and (x^,y^)(\hat x,\hat y)(x^,y^​) is optimal among all (not only affine) two-stage solutions. In particular zAff(U)=zAdapt(U)z_{Aff}(\mathcal U)=z_{Adapt}(\mathcal U)zAff​(U)=zAdapt​(U).

The result marks the boundary of exactness for affine policies: Sections 3 and 4 of the paper show that already for sets with m+3m+3m+3 extreme points affine policies can be suboptimal, and that the gap can grow like m1/2βˆ’Ξ΄m^{1/2-\delta}m1/2βˆ’Ξ΄.

Formalization Note "Optimal" means: (x^,y^)(\hat x,\hat y)(x^,y^​) is feasible, and every worst-case cost bound achieved by some feasible two-stage solution is also achieved by (x^,y^)(\hat x,\hat y)(x^,y^​); this asserts that the minimum in (1) is attained (the paper's proof presupposes an optimal solution). The page writes "bj∈R+mb^j\in\mathbb R^m_+bj∈R+m​ for all j=1,…,mj=1,\dots,mj=1,…,m"; all m+1m+1m+1 vertices are required nonnegative, as UβŠ†R+m\mathcal U\subseteq\mathbb R^m_+UβŠ†R+m​ in (1) demands. The simplex is automatically compact, convex and (by affine independence) full-dimensional, so these standing assumptions of (1) are not stated separately. Feasibility is the paper's standing assumption on (1). Vertices are indexed from 000: bjb^jbj is v (j-1).

Preamble
import Mathlib
import Definitions.Def_AffinePolicies_Simplex_Setting
Formal statement
namespace AffinePolicies.Simplex

theorem theorem_1 {m n₁ nβ‚‚ : β„•} (A : Matrix (Fin m) (Fin n₁) ℝ) (B : Matrix (Fin m) (Fin nβ‚‚) ℝ)
    (c : Fin n₁ β†’ ℝ) (d : Fin nβ‚‚ β†’ ℝ) (hc : 0 ≀ c) (hd : 0 ≀ d)
    (v : Fin (m + 1) β†’ Fin m β†’ ℝ) (hv : AffineIndependent ℝ v) (hvnn : βˆ€ j, 0 ≀ v j)
    (hfeas : βˆƒ (x : Fin n₁ β†’ ℝ) (y : (Fin m β†’ ℝ) β†’ Fin nβ‚‚ β†’ ℝ),
      Feasible A B (simplexSet v) x y) :
    βˆƒ (x : Fin n₁ β†’ ℝ) (P : Matrix (Fin nβ‚‚) (Fin m) ℝ) (q : Fin nβ‚‚ β†’ ℝ),
      IsOptimalAdapt A B c d (simplexSet v) x (affinePolicy P q) := by sorry

end AffinePolicies.Simplex
Source
Bertsimas & Goyal, On the power and limitations of affine policies in two-stage adaptive optimization, Math. Program. Ser. A, DOI 10.1007/s10107-011-0444-4, Theorem 1, PDF pp. 5–6
Human review
  • Endorsed by Shuze Chen Β· Oct 5, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 Β· Oct 5, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
Β© 2026 Prove2Me