of 9

Polytopes inside polytopes

Criteria for polytopes being subsets of other polytopes using
Published on: Mar 4, 2016
Published in: Technology      Education

Transcripts - Polytopes inside polytopes

• 1. Polytopes Inside Polytopes Pantelis Sopasakis IMT Lucca October 13, 2013 Pantelis Sopasakis Polytopes Inside Polytopes
• 2. Deﬁnitions (1) We call a half-space any set of the form H = {x ∈ Rn ; p, x ≤ q}. A set C ⊆ R is called a polytope if it is the intersection of a ﬁnite number of subspaces. Compact polytopes can be written as the convex hull of a ﬁnite number of points in Rn , C = conv{ci }M . i=1 Any polytope can be written as C = {x ∈ Rn ; Hx ≤ K}, where H ∈ Rs×n and K ∈ Rs and ≤ stands for the component-wise comparison relation. Pantelis Sopasakis Polytopes Inside Polytopes
• 3. Deﬁnitions (2) Let C ⊆ Rn be a polytope, A ∈ Rm×n and b ∈ Rm . We introduce the following notation: AC + b {z = Ac + b; c ∈ C}. A special polytope is the closed ball of the inﬁnity norm, x ∞ maxi=1,...,n |xi |; it is B∞ {z; z ∞ ≤ 1}. We use the notation [k] to denote the ﬁrst k rows of a matrix A ∈ Rm×n , with A 1 ≤ k ≤ m. Pantelis Sopasakis Polytopes Inside Polytopes
• 4. Criterion 1 Theorem (Extreme points) Let C1 , C2 be two polytopes and C1 be compact. Then C1 ⊆ C2 if and only if the extreme points of C1 are in C2 . The proof is trivial. In practice, the use of this criterion implies the enumeration of the extreme points of the polytope C1 and is computationally prohibitive in high-dimensional spaces; for instance the inﬁnity ball in Rn has 2n extreme points. Pantelis Sopasakis Polytopes Inside Polytopes
• 5. Criterion 2 Theorem (Linear Transformations of B∞ ) Let A, B ∈ Rm×n . It is AB∞ ⊆ BB∞ if and only if Ax 1 ≤ Bx 1 for all x ∈ Rn . The condition proposed by this criterion cannot always be reduced to a simpler expression. If m = n it can be equivalently written in the form AB † 1 ≤ 1, where B † is the Moore-Penrose pseudoinverse of B. Pantelis Sopasakis Polytopes Inside Polytopes
• 6. Proof of Criterion 2 Let δ (x | C) be the support function of a set C, i.e., δ (x | C) = supy∈C x, y 1 . Since AB∞ and BB∞ are both closed and convex sets, it holds that for all x ∈ Rn AB∞ ⊆ BB∞ ⇔ δ (x | AB∞ ) ≤ δ (x | BB∞ ) ⇔ sup{ x, As , s ∈ B∞ } ≤ sup{ x, Bp , p ∈ B∞ } ⇔ sup s A x, s ≤ sup ∞ ≤1 ⇔ Ax 1 p B x, p ∞ ≤1 ≤ Bx 1 , which proves the assertion. 1 R. T. Rockafellar, ”Convex Analysis,” Princeton University Press, New Jersey, 1972, ISBN: 0-691-08069-0. Pantelis Sopasakis Polytopes Inside Polytopes
• 7. Criterion 3 Theorem (Dual Norms) Let · be a norm in Rn and let · be its dual norm (Deﬁned as x sup x ≤1 x, x ). Let B = {z ∈ Rn ; z ≤ 1}. Then AB ⊆ BB if and only if Ax ≤ Bx for all x ∈ Rn . Pantelis Sopasakis Polytopes Inside Polytopes
• 8. Criterion 3 - Implications We may use Criterion 3 with · = · 1 (and · = · ∞ ). Also, if C is a nonempty balanced absorbing compact polytope containing the origin in its interior, then its Minkowski functional pC (x) inf λ>0 {x ∈ λC} is a norm and again Criterion 3 applies. In this case, if x pC (x), then for x ∈ Rn : x = sup{ x, x , pC (x) ≤ 1} x But, the set {x : pC (x) ≤ 1} in this case is the topological closure of C, i.e., C since it is assumed to be closed. Hence x = δ (x | C). Pantelis Sopasakis Polytopes Inside Polytopes
• 9. Criterion 4 Theorem (Equal number of extreme points) Let HP , HQ ∈ Rm×n have full row rank and deﬁne P = {x ∈ Rn : HP x ≤ KP } and Q = {x ∈ Rn : HQ x ≤ KQ }. The following are equivalent: 1 2 P ⊆Q One of the following holds true: There is a matrix M , lower triangular and with positive diagonal elements so that HP = M HQ and KP = M KQ , There is an l, with 1 ≤ l ≤ m and a matrix M ∈ Rl×l so [l] [l] [l] [l] that HP = M HQ and qP < M qQ . For a proof see Lemma 4.5.1. in: L. Q. Thuan, ”Piecewise Aﬃne Dynamical Systems: Well-posedness, controllability and stabilizability,” PhD. Dissertation, University of Groningen, 2013. Pantelis Sopasakis Polytopes Inside Polytopes