A linear program is a convex optimization problem where the objective and constraints are all affine.
$$ \begin{align*} \min_{x \in \R^n} \quad & a_0^T x \\ \text{subject to} \quad & a_i^Tx - b_i = 0, \quad i \in [m] \\ & c_j^Tx -d_j \leq 0, \quad j \in [k] \end{align*} \hspace{15pt} \equiv \hspace{15pt} \begin{align*} \min_{x \in \R^n} \quad & a_0^T x \\ \text{subject to} \quad & Ax = b \\ & Cx \leq d \end{align*} $$
The feasible set $\mathcal{X}$ of a linear program is a polyhedron, as it is the intersection of $m$ hyperplanes and $k$ halfplanes. In the context of linear programs, it is common to call the extreme points of $\mathcal{X}$ vertices.
<aside> <img src="/icons/castle_yellow.svg" alt="/icons/castle_yellow.svg" width="40px" />
Vertex Solutions. If a linear program has a solution, at least one solution is a vertex.
<aside> <img src="/icons/castle_yellow.svg" alt="/icons/castle_yellow.svg" width="40px" />
Simplex Algorithm. Finds the optimal solution $x^*$ to a linear program.
$$ \textbf{Simplex Algorithm} \\ 1. \text{ Select an arbitrary vertex $x$.} \hspace{85pt} \\
\text{ For each adjacent vertex $\tilde{x}_i$, compute $s_i = a_0^T \tilde{x}_i$.} \\
\text{ If $s_i < a_0^T x$, then repeat the algorithm on $\tilde{x}_i$. } \hspace{14pt} \\
\text{ Otherwise, $x$ is an optimal solution.} \hspace{54pt} $$
Geometrically, this algorithm works by starting at a vertex and iteratively comparing the objective values of vertices by moving along the boundary $\partial \mathcal{X}$ of $\mathcal{X}$.
</aside>
Any linear program can be written in standard form, where the inequality constraints are turned into equality constraints and all variable coefficients are made nonnegative.
$$ \textbf{Convert Inequalities to Equalities } \hspace{15pt} c_j ^T x \leq d_j \space \xrightarrow{\hspace{5pt}} \space c_j ^Tx +s_j = d_j , \space s_j \geq 0 \\
\textbf{Make Variable Coefficients Nonnegative } \hspace{15pt} x_i \xrightarrow{\hspace{5pt}} x_i ^+ - x_i ^- , \hspace{5pt} x_i ^+, x_i ^- \geq 0 \hspace{2pt} $$
$$ \begin{align*} \min_{x \in \R^n} \quad & a_0^T x \\ \text{subject to} \quad & Ax = b \\ & Cx \leq d \end{align*} \hspace{10pt} \xrightarrow{\hspace{15pt}} \hspace{10pt} \begin{align*} \min_{x \in \R^\ell} \quad & a_0^T x \\ \text{subject to} \quad & A'x = b' \\ & x \geq 0 \end{align*} $$
Geometrically, this shifts the feasible region to be within the nonnegative orthant of some higher-dimensional space. Moreover, we say that a standard linear program is non-degenerate if each vertex has exactly $m$ non-zero entries.
<aside> <img src="/icons/castle_yellow.svg" alt="/icons/castle_yellow.svg" width="40px" />
Vertex Finding Procedure. The vertices of a standard linear program can be found with the following procedure:
$$ \textbf{Vertex Finding Procedure} \\ 1. \text{ Arbitrarily select a set of indices $B \sube \{1, \dots, n\} $ s.t. $|B| = m$.} \\
\text{ If $A_B$ is invertible, proceed. Otherwise, choose another $B$.} \hspace{16pt} \\
\text{ Compute $y = A^{-1}_B b$ and extend $y$ s.t. $y_i = 0$ for any $i \notin B$.} \hspace{15pt} \\
\text{ If $y \geq 0$, then $y$ is a vertex.}\hspace{147pt} \\
\text{ Repeat for all $\begin{pmatrix} n \\ m \end{pmatrix}$ choices of $B$.} \hspace{117pt} $$
The reason why this works is because each candidate $y$ is exactly a point where the $m$ hyperplanes intersect. Because $A_B$ is invertible, the intersection is trivial, so the point $y$ is guaranteed to be an extreme point because there is no line segment in the intersection that $y$ can lie on. Then, $y \geq 0$ simply ensures that $y$ belongs to the feasible set.
</aside>
<aside> <img src="/icons/castle_yellow.svg" alt="/icons/castle_yellow.svg" width="40px" />
Adjacent Vertices Match Entries. Given a non-degenerate, standard linear program with vertices $v_1, \dots, v_p \in \mathcal{X}$, we say that two vertices $v_i$ and $v_j$ are adjacent if and only if $v_i$ and $v_j$ are zero at the same $n - m - 1$ indices in $\{1, \dots, m\}$.
Geometric Intuition. Two vertices are adjacent if you can go from one vertex to another along a line segment in $\partial \mathcal{X}$.
</aside>
Technique for converting a non-affine objective to an affine objective by forcing the objective below an affine slack variable $t$.
$$ \begin{align*} \min_{x \in \R^n} \quad & f_0(x) \\ \text{subject to} \quad & x \in \mathcal{X} \\ \space \end{align*}\hspace{15pt} \equiv \hspace{15pt} \begin{align*} \min_{x \in \R^n, \space t \in \R} \quad & t \\ \text{subject to} \quad & x \in \mathcal{X} \\ & f_0(x) \leq t \end{align*} $$