feasible regions
Summary
Extreme points
Concept
Feasible region
- set of all feasible solutions to an LP
Polyhedron
- technically polytropes, for generalizing to
dimensions - region bounded by constraints
polyhedra cannot have “dents” or “holes”
Feasible region of LP is a polyhedron
TODO
Hyperplane
- set of solutions to a linear equation
Dimension of hyperplanes
- the hyperplane passing through 0 is a vector space
one linear constraint removes one degree of freedom
Halfspace
- set of solutions to a linear inequality
a polyhedron is the intersection of a finite set of halfspaces

Translate

translate all the elements of a set
Translate of hyperplanes
Translate of halfspaces
TODO
similar to above
Convexity
- no “dents” and no “holes”
Line through two points
Line segment between two points
- aka convex combination
Convexity of a set
Intersection remains convex
TODO
Linesegment in A and in B so in A
Halfspaces are convex
Polyhedra are convex
TODO
P is intersection of halfspaces
halfspaces are convex
intersection of conves is convex
feasible region of LP is convex, which is what makes it relatively easy to solve
Extreme points
- basically the verticies of the polyhedron
Properly contained
- point on the line segment that is not the endpoints
Non-extreme points
Convex set may have no extreme points (halfspace)
or infinite extreme points (circle/n-sphere)
Tight constraints
- constraint that is satisfied with equality
A point is extreme iff it has
extreme points have
tight constraints
Deficient rank
Extreme points are basic feasible solutions
- simplex algorithm is walking along extreme points
TODO
Problems with slack variables
- are isomorphic
- slack variables do not provide additional information
this allows us to simplify things to “less dimensions” to better visualize the extreme points
Application
SEF to polyhedron form
Extreme points of a LP
Checking for extreme points
Slack variabls and extreme points
Extra
Helpful aside for proving the extreme point theorem
Generalization for line segment form
Generalization to vector
TODO