$H=\{x∈ℝ^n:a^Tx=β\}$ is a hyperplane

$F=\{x∈ℝ^n:a^Tx≤β\}$ is a halfspace

Each of these basically represents a single constraint

Dimension of $H$ is $cols - 1$

Polyhedron

• A polyhedron consists of multiple halfspaces
• Think of it as the AND (intersection) of all of the halfspaces
• $P=\{x∈ℝ^n:Ax≤β\}$ is a set of linear constraints
• So a polyhedra is literally just a linear program

A line through $x_1, x_2$ is formally defined as the set of points

$\{λx_1 + (1 - λ)x_2: λ∈ℝ\}$

Convexity

We define convex to mean all lines in the shape stay in the shape.

All halfspaces are convex.

All intersections of convex sets are convex. Therefore, polyhedra are also convex.

Green is convex, blue is not.

Extreme Points

A point is properly contained in a line if it’s different from its endpoints.

Points in a convex set that are properly contained in no lines are extreme points.

Basically, if the tangent line to a point is outside of the shape, it’s extreme.

For a typical LP $P = \{x:Ax=b,x≥0\}$

$\overline{x}$ is an extreme point iff $\overline{x}$ is a BFS.

Extreme points in red. Infinite amount of extreme points for curved edges. Otherwise, they’re just the vertices of straight edges.

Corners are extreme bcuz they can only form endpoints and are thus improperly contained.

Basically if the set of tight constraints (rows for which $a\overline x=b$) has a rank of $n$ (the number of columns) then $\overline x$ is an extreme point. Note that as a consequence of the definition of rank, the rows have to be linearly independent.