polyhedra

Question 1

polyhedron:

Answer 1

P={x in Rn: Ax<=b} where A in R^(mxn), b in Rm (each row forms an inequality, gives a set of linear equations

Question 2

supporting hyperplane:

Answer 2

of a polyhedron, where P within H- (a halfspace of the hyperplane)

Question 3

face:

Answer 3

if H is a supporting hyperplane, a set of the form F=H∩P is a face of P, made up of several rows in the original polyhedron set

Question 4

dimension:

Answer 4

dimF, smallest dimension of an affine space containing F

Question 5

facet:

Answer 5

a face with dimF=dimP-1

Question 6

vertex:

Answer 6

a face of dimF=0
also a point that can’t be made of a convex combo of two other points

Question 7

edge:

Answer 7

a face of dimF=1

Question 8

polytope:

Answer 8

convex hull of finitely many points, P=conv({x1,…,xk})

Question 9

bounded polyhedron:

Answer 9

the convex hull of its vertices so a polytope is a bounded polyhedron

Question 10

hyperplane separation for cones:

Answer 10

let C!=Rn be a closed convex cone and z not in C, then there exists a linear hyperplane H={x in Rn: ⟨a,x⟩=0} such that C within H- and z in intH+

Question 11

farkas’ lemma:

Answer 11

given a matrix A in R(mxn) and b in Rm, there exists a vector x such that Ax=b with x>=0 iff there is No y such that A^(T)y>=0 with ⟨y,b⟩<0