Lemma 2.1 — a rank and feasibility test for complete recourse
ProvedKallMayerSLP.Recourse.lemma_2_1kall-mayer-slplinear-programmingp2o-gran-per-chapterp2o-plan-bookp2o-v1stochastic-programmingtwo-stage-recourse
Let . The following are equivalent:
- satisfies the complete recourse condition (2.6), ;
- , and for every set of linearly independent columns of the linear system (2.7)
is feasible; 3. , and for some set of linearly independent columns of the system (2.7) is feasible.
So complete recourse, a condition on infinitely many right-hand sides, reduces to a rank computation and one LP feasibility test.
Formalization Note A selection of columns is a map whose columns are linearly independent. The statement is the conjunction of the two equivalences 1 ⇔ 2 and 1 ⇔ 3. Complete recourse is the published KallMayer.Recourse.CompleteRecourse.
Differences from the source:
- reading: 'for an arbitrary set {W_{i1}, …, W_{im2}} of linearly independent columns of W, the constraints (2.7) are feasible' → both readings: for every such selection (1 ⇔ 2) and for some selection (1 ⇔ 3); reason: the proof of ⇒ works for any selection and the proof of ⇐ uses one; stating both covers the stronger reading of each direction
- encoding: a set of m₂ linearly independent columns {W_{i1}, …, W_{im2}} →
s : Fin m₂ → Fin n₂withLinearIndependent ℝ (fun k => Wᵀ (s k)); reason: linear independence forces s injective; same selections
Preamble
import Mathlib import Definitions.Def_KallMayer_Recourse_CompleteRecourse open KallMayer.Recourse (CompleteRecourse) open Matrix
Formal statement
namespace KallMayerSLP.Recourse
/-- Lemma 2.1 (Kall & Mayer, Stochastic Linear Programming (2005), Chapter 3, Lemma 2.1,
pp.201–202, PDF 210–211): a matrix `W ∈ ℝ^{m₂×n₂}` satisfies the complete recourse condition (2.6),
`{z | z = W y, y ≥ 0} = ℝ^{m₂}`, if and only if `rank(W) = m₂` and, for a set
`{W_{i₁}, …, W_{i_{m₂}}}` of linearly independent columns of `W`, the system (2.7)
`W y = 0, y_{i_k} ≥ 1 (k = 1, …, m₂), y ≥ 0` is feasible.
**Formalization Note.** "For an arbitrary set of linearly independent columns" is stated in both
readings: the first conjunct quantifies over every selection, the second asks for one selection.
A selection is `s : Fin m₂ → Fin n₂` whose columns `k ↦ Wᵀ (s k)` (the column `W_{s k}`) are linearly
independent (which forces `s` injective). The complete recourse condition is the published
`KallMayer.Recourse.CompleteRecourse`. -/
theorem lemma_2_1 {m₂ n₂ : ℕ} (W : Matrix (Fin m₂) (Fin n₂) ℝ) :
(CompleteRecourse W ↔
W.rank = m₂ ∧
∀ s : Fin m₂ → Fin n₂, LinearIndependent ℝ (fun k => W.transpose (s k)) →
∃ y : Fin n₂ → ℝ, W *ᵥ y = 0 ∧ (∀ k, 1 ≤ y (s k)) ∧ 0 ≤ y) ∧
(CompleteRecourse W ↔
W.rank = m₂ ∧
∃ s : Fin m₂ → Fin n₂, LinearIndependent ℝ (fun k => W.transpose (s k)) ∧
∃ y : Fin n₂ → ℝ, W *ᵥ y = 0 ∧ (∀ k, 1 ≤ y (s k)) ∧ 0 ≤ y) := by sorry
end KallMayerSLP.Recourse
Source
Kall & Mayer, Stochastic Linear Programming (2005), Chapter 3, Lemma 2.1, pp.201–202 (PDF 210–211)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.