Theorem 1 — with fixed recourse and strict feasibility, and equal the LPs (2.3) and (2.8)
ProvedPrimalDualLDR.FixedRecourse.theorem_1Consider the one-stage stochastic program with fixed recourse
with , , and assume that has a polyhedral support of the type (2.1): nonempty, bounded, with of the form (2.1b), spanning . Assume further that is strictly feasible (2.9). Let . Then
- the primal linear-decision-rule problem ( s.t. , -a.s.) has the same optimal value as the linear program (2.3),
- the dual linear-decision-rule problem ( over , s.t. , -a.s.) has the same optimal value as the linear program (2.8),
The formal statement adds one hypothesis the paper does not state: , i.e. some row of below the first two is nonzero (see the Formalization Note).
Since is an upper and a lower bound on , the theorem brackets the optimal value of the (generally #P-hard) stochastic program between two explicit linear programs whose size is polynomial in .
Formalization Note "Equivalent" is formalized as equality of optimal values, each the infimum of the objective over the feasible set in ( if infeasible, if unbounded). Strict feasibility is a hypothesis of both equalities, as printed, although the first holds without it. The paper's last sentence (the LP sizes are polynomial, so they are efficiently solvable) is informal and is not part of the statement. Repaired statement: the hypothesis is added because the printed theorem is false without it: for , , , , , , , , every assumption of the theorem holds, has value , but , so (2.8) has no sign constraint on and value . The paper's proof of Proposition 3 drops the constraint as redundant, which fails exactly when . Under the standing assumptions holds automatically when (a bounded forces it), so the repair only excludes this degenerate one-point case.
import Mathlib import Definitions.Def_PrimalDualLDR_FixedRecourse_Basic import Definitions.Def_PrimalDualLDR_FixedRecourse_Setting import Definitions.Def_PrimalDualLDR_FixedRecourse_Problems open MeasureTheory Matrix
namespace PrimalDualLDR.FixedRecourse
/-- Theorem 1 (p. 10): if `P` has a polyhedral support of the type (2.1) while `SP` has fixed recourse
and is strictly feasible, then `SP^u` and `SP^l` are equivalent to the linear programs (2.3) and
(2.8), respectively: their optimal values coincide.
Repair (trap 30): the hypothesis `hW` says `Ŵ ≠ 0` (some row `i ≥ 2` of `W` is nonzero; rows
`0`, `1` are `±e_1ᵀ`). The page omits it, and the printed statement is false without it: for
`k = 1`, `l = 2`, `W = (1, −1)ᵀ`, `h = (1, −1)`, `P = δ_1`, the matrix `W − h e_1ᵀ` is `0`, so
`𝒦 = ℝ` while `𝒦_P = [0, ∞)`; with `n = m = 1`, `A = B = 1`, `C = −1` (strictly feasible with
`x̄ = 0`, `s̄(ξ) = ξ`) the program (2.8) loses `S ≥ 0` and has value `−∞`, while (2.6) and `SP^l`
have value `−1`. Under the standing assumptions `Ŵ ≠ 0` is automatic when `k ≥ 2`. -/
theorem theorem_1 (σ : Setting) (hσ : σ.Standing)
(hW : ∃ i : Fin σ.l, 2 ≤ i.val ∧ σ.W i ≠ 0) (hsf : σ.StrictlyFeasible) :
σ.valSPu = σ.valLP23 ∧ σ.valSPl = σ.valLP28 := by sorry
end PrimalDualLDR.FixedRecourse
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.