Review pending

Lemma 11.12.1 · Simultaneous escape

Lemma 11.12.1. (Simultaneous escape). Let P⊂Rs×RdP\subset\mathbf R^s\times\mathbf R^d be a nonempty closed polyhedron, where s>0s>0, and suppose that its projection to the second factor is bounded. Exactly one of the following alternatives holds:

  1. There is (w,0)∈rec⁡(P)(w,0)\in\operatorname{rec}(P) with wi>0w_i>0 for every ii.

  2. There is M∈RM\in\mathbf R such that min⁡iti≤M\min_i t_i\leq M for every (t,y)∈P(t,y)\in P.

Argument in the manuscript

Proof. We use the elementary finite-dimensional Farkas alternative in the following form: if a linear functional cc is nonpositive on {w:Aw≤0}\{w:Aw\leq 0\}, then c=λtAc=\lambda^tA for some column vector λ≥0\lambda\geq 0. Here is a brief justification. The cone generated by the rows of AA is closed: in each nonnegative representation, a linear dependence can eliminate one positive coefficient, until its support is linearly independent. There are finitely many such supports; on a fixed independent support convergence of the represented vectors forces convergence of the coefficients. If cc were outside this closed convex cone, separation would give ww with Aw≤0<c(w)Aw\leq 0<c(w), a contradiction.

It follows that a linear functional unbounded above on a nonempty polyhedron Q={v:Av≤b}Q=\{v:Av\leq b\} is positive on some recession vector: otherwise c=λtAc=\lambda^tA gives c(v)≤λtbc(v)\leq\lambda^tb on QQ. Apply this observation to Q={(t,y,z):(t,y)∈P, z≤ti for all i}.Q=\{(t,y,z):(t,y)\in P,\ z\leq t_i\text{ for all }i\}. If alternative (2) fails, zz is unbounded above on QQ. Hence QQ has a recession vector (w,v,a)(w,v,a) with a>0a>0. The inequalities give wi≥aw_i\geq a. Boundedness of the yy-projection forces v=0v=0, proving (1). Conversely, a ray with every wi>0w_i>0 makes min⁡iti\min_i t_i unbounded. ◻

Citation

Non-Archimedean Geometry Foundations, Tag NAG-900164.

Proof in chapter