Theorem 1, PDF pp. 5β6 β if π° is a simplex in β^m_+, some affine policy is optimal for Ξ _Adapt(π°)
ProvedAffinePolicies.Simplex.theorem_1Consider the two-stage adaptive problem of model (1),
with , , , . Suppose the uncertainty set is a simplex,
where are affinely independent, and that the problem is feasible. Then there is an optimal two-stage solution whose second stage is an affine function of : there are and with
and is optimal among all (not only affine) two-stage solutions. In particular .
The result marks the boundary of exactness for affine policies: Sections 3 and 4 of the paper show that already for sets with extreme points affine policies can be suboptimal, and that the gap can grow like .
Formalization Note "Optimal" means: is feasible, and every worst-case cost bound achieved by some feasible two-stage solution is also achieved by ; this asserts that the minimum in (1) is attained (the paper's proof presupposes an optimal solution). The page writes " for all "; all vertices are required nonnegative, as 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 : is v (j-1).
import Mathlib import Definitions.Def_AffinePolicies_Simplex_Setting
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.