Theorem 3 โ in multistage programs, ๐๐ฎ๐ซ^u and ๐๐ฎ๐ซ^l are equivalent to the linear programs (4.2) and (4.6)
ProvedPrimalDualLDR.Multistage.theorem_3Consider a linear multistage stochastic program (p. 18): over stages, minimize over non-anticipative rules subject to -a.s., with deterministic constraint matrices , and .
Assume that has a polyhedral support of the type (2.1) โ nonempty, bounded, spanning , with of the form (2.1b) and โ while
If is strictly feasible, then and are equivalent to the linear programs (4.2) and (4.6), respectively; the second equivalence is stated under the condition : , or some row of is nonzero (see the Formalization Note):
Since is a conservative and a progressive approximation of , the two linear programs bracket the optimal value of the multistage program, and both are of size polynomial in the problem dimensions.
Formalization Note "Equivalent" is formalized as equality of optimal values, each the infimum of the objective over the feasible set in the extended reals ( when infeasible, when unbounded). The matrices are data of the setting and the hypothesis states that they give the conditional mean; this is equivalent to the paper's "for some ", since the problems depend on only through on . Strict feasibility of , which ยง4 does not define, is the analogue of (2.9) for the standard form (4.1): slacks bounded below by some . The equality constraint of is in the corrected reading in which covers only . The final sentence of the printed theorem (the linear programs have polynomial size and are efficiently solvable) is informal and not formalized. The hypothesis on the second equality is a repair and is not in the paper (the first equality is stated without it, as printed): for the support is , and if has no nonzero row besides the two rows of (2.1b), the cone of Proposition 3 is all of while , so Proposition 3 and the second equality fail. For instance , , , , is strictly feasible, has value , and (4.6) is unbounded below. For the spanning support has at least two points and the omitted constraint is implied by , as the paper's argument (p. 8) needs; for with a nonzero row of (then , as is nonempty), as well. So excludes exactly the case in which the printed statement fails.
import Mathlib import Definitions.Def_PrimalDualLDR_Multistage_Basic import Definitions.Def_PrimalDualLDR_Multistage_Setting import Definitions.Def_PrimalDualLDR_Multistage_Problems open MeasureTheory Matrix
namespace PrimalDualLDR.Multistage
/-- Theorem 3 (p. 22): assume that `P` has a polyhedral support of the type (2.1), while
`๐ผ_t(ฮพ) = M_t P_t ฮพ` almost surely for the matrices `M_t โ โ^{k ร k^t}`, `t โ ๐`. If `๐๐ฎ๐ซ` (which has
deterministic constraint matrices `A_ts` by construction) is strictly feasible, then `๐๐ฎ๐ซ^u` and
`๐๐ฎ๐ซ^l` are equivalent to the linear programs (4.2) and (4.6), respectively: their optimal values
coincide. The hypothesis on the second equality (`2 โค k`, or some row of `ลด` below (2.1b) is nonzero)
is not in the paper: for `k = 1` (so `ฮ = {1}`) and `W` with zero rows below (2.1b), the cone `๐ฆ` of
Proposition 3 is all of `โ` while `๐ฆ_โ = [0, โ)`, and the second equality fails (e.g. `T = 1`, `A = 1`,
`B = 0`, `C = -1`: `๐๐ฎ๐ซ^l` has value `0`, (4.6) is unbounded below). The hypothesis excludes exactly
that case. The first equality is stated without it, as printed. -/
theorem theorem_3 (ฯ : Setting) (hฯ : ฯ.Standing) (hM : ฯ.LinearCondMean)
(hsf : ฯ.StrictlyFeasible) :
ฯ.valMSPu = ฯ.valLP42 โง
((2 โค ฯ.k โจ โ i : Fin ฯ.l, 2 โค i.val โง ฯ.W i โ 0) โ ฯ.valMSPl = ฯ.valLP46) := by sorry
end PrimalDualLDR.Multistage
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.