Linear programming is a mathematical method for optimizing a linear objective function subject to linear equality and inequality constraints.
Examples:
These problems are typically modeled with:
Quick detour
Equation of a Plane in 2D: - A line in 2D can be written as:
\[ a x_1+b x_2+c=0 \]
Equation of a Plane in 3D:
\[ a x_1+b x_2+c x_3+d=0 \]
Equation of a Hyperplane in N-D Space:
\[ w_1 x_1+w_2 x_2+\cdots+w_N x_N+b=0 \]
\({ }^{-} w\) is the normal vector, \(b\) is the bias term. - Separates \(N\)-dimensional space into two half-spaces.
The equation of a plane in 3D can be written using the normal vector \(\vec{n}=\langle a, b, c\rangle\) and a point on the plane \(P_0=\left(x_0, y_0, z_0\right)\) as:
\[ a\left(x-x_0\right)+b\left(y-y_0\right)+c\left(z-z_0\right)=0 \]
Alternatively, in expanded form:
\[ a x+b y+c z=d \]
where: - \(a, b, c\) are the components of the normal vector \(\vec{n}\), - \(d=a x_0+b y_0+c z_0\) is a constant determined by the point on the plane.
Finally, using dot product notation, the equation of a plane in 3D can be written as:
\(\vec{n} \cdot (\vec{r} - \vec{r}_0) = 0\)
Where:
This form expresses that the vector from \(\vec{r}_0\) to \(\vec{r}\) is orthogonal to the normal vector \(\vec{n}\), hence lies in the plane.
Introduction and statement of problem
An constrained optimization problem involves finding the values of decision variables that minimize (or maximize) an objective function, subject to a set of constraints:
Minimize: \[ f(x_1, x_2, \ldots, x_n) \] Subject to: \[ \begin{aligned} g_1(x_1, x_2, \ldots, x_n) &\;\; \{=,\; \leq,\; \geq\} \;\; b_1 \\ g_2(x_1, x_2, \ldots, x_n) &\;\; \{=,\; \leq,\; \geq\} \;\; b_2 \\ \vdots \\ g_m(x_1, x_2, \ldots, x_n) &\;\; \{=,\; \leq,\; \geq\} \;\; b_m \end{aligned} \]
\[ f\left(x_1, x_2, \ldots, x_n\right)=c_1 x_1+c_2 x_2+\ldots+c_n x_n \]
\[ \begin{aligned} a_{11} x_1+a_{12} x_2+\ldots+a_{1 n} x_n & \leq b_1 \\ a_{21} x_1+a_{22} x_2+\ldots+a_{2 n} x_n & \geq b_2 \\ \vdots & \\ x_i & \geq 0 \text { (non-negativity) } \end{aligned} \]

We can visualize the objective contours as planes. Using the objective z = x1 + x2 + x3, we can plot the contours z = 1.5, z = 2.5 (solving each equation for x3 and plotting the surface):


Source: https://greenor.wordpress.com/2014/02/09/visualizing-lps-in-mathematica/
A polytope is the bounded region formed by the intersection of a finite number of linear inequalities.
In \(\mathbb{R}^n\), it is a convex, multi-faced geometric object—a polygon in 2D, a polyhedron in 3D, and higher-dimensional analogs beyond.
It is the blue region in the image below
A closed feasible region of a problem with three variables is a convex polyhedron.
The surfaces giving a fixed value of the objective function are planes (not shown).
The linear programming problem is to find a point on the polyhedron that is on the plane with the highest possible value.

If the problem had more independent variables, e.g. 3, the polytope would have higher dimension

Using linear algebra notation, a linear programming (LP) problem can be written compactly as:
\(\begin{aligned} \underset{x}{\text{maximize}} \quad & c^T x \\ \text{subject to} \quad & Gx \leq h \end{aligned}\)
Symbol Definitions
Note on Equality Constraints
Equality constraints can be expressed using two inequalities:
\(g_i^T x = h_i \;\equiv\; \begin{cases} g_i^T x \leq h_i \\ -g_i^T x \leq -h_i \end{cases}\)
This allows all constraints to be handled uniformly in matrix form.
Standard form linear program
\[ \begin{aligned} \underset{x}{\operatorname{minimize }} \, c^T x \\ \text { subject to } & A x=b \\ & x \geq 0 \end{aligned} \]
Although they look different, easy to transform between inequality form and standard form
In standard form we assume \(n>m\), so \(A x=b\) is an underdetermined system of equations (more variables than equations)
We can find solutions by selecting a subset of \(m\) columns of \(A\), solving the linear system, and setting remaining \(n-m\) variables to be 0
Those solutions that also satisfy \(x \geq 0\) are the corners of the polytope
Some set notation will make the resulting systems easier to write
We let \(\mathcal{I} \subseteq\{1, \ldots, n\}\) denote an ordered index set, and let \(\mathcal{I}_i\) the denote the \(i\) th element in set \[ \mathcal{I}=\left\{\mathcal{I}_1, \mathcal{I}_2, \ldots \mathcal{I}_m\right\} \] where \(|\mathcal{I}|=m\) denotes the length of the index set Unlike typical sets order is relevant, so that \(\mathcal{I}=\{1,5\}\) and \(\mathcal{I}=\{5,1\}\) are distinguished between (not important for basic algorithm, but it will be important when we talk about faster versions)
For a vector \(x \in \mathbb{R}^n\) and index set \(\mathcal{I}, x_{\mathcal{I}} \in \mathbb{R}^m\) is a vector of entries selected by indices in \(\mathcal{I}\) \[ x_{\mathcal{I}}=\left[\begin{array}{c} x_{\mathcal{I}_1} \\ x_{\mathcal{I}_2} \\ \vdots \\ x_{\mathcal{I}_m} \end{array}\right] \]
For a matrix \(A \in \mathbb{R}^{m \times n}, A_{\mathcal{I}} \in \mathbb{R}^{m \times m}\) is a matrix where columns are selected by \(\mathcal{I}\) \[ A=\left[\begin{array}{ccc} \mid & \mid & \mid \\ a_{\mathcal{I}_1} & a_{\mathcal{I}_2} \cdots & a_{\mathcal{I}_m} \\ \mid & \mid & \mid \end{array}\right] \]
The simplex method is a way of speeding up this “corner finding” process substantiallyRepeat: 1. Given index set \(\mathcal{I}\) such that \(x_{\mathcal{I}}=A_{\mathcal{I}}^{-1} b \geq 0\) 2. Find \(j\) for which \(\bar{c}_j=c_j-c_{\mathcal{I}}^T A_{\mathcal{I}}^{-1} a_j<0\) (if non exists, return \(\left.x_{\mathcal{I}}^{\star}=A_{\mathcal{I}}^{-1} b\right)\) 3. Compute step direction \(d_{\mathcal{I}}=-A_{\mathcal{I}}^{-1} a_j\) and determine index to remove (or return unbounded if \(d \geq 0\) ) \[ i^{\star}=\underset{i \in \mathcal{I}: d_i<0}{\operatorname{argmin}}-x_i / d_i \] 4. Update index set \[ \mathcal{I} \leftarrow \mathcal{I}-\left\{i^{\star}\right\} \cup\{j\} \]
Note that the above algorithm is described in terms of exact math
When implemented in floating point arithmetic, we’ll often get entries like \(\bar{c}_j, d_i \in\left[-10^{-15}, 10^{-15}\right]\)
When comparing to zero, or comparing “ties” (especially under degeneracy, see next slide), we need to account for this
In practice, set these near-zero elements to zero or compare \(\geq, \leq\) to \(\pm 10^{-12}\)
Simplex will still work fine with zero step sizes, but care must be taken to prevent cycling repeatedly over the same indices
A similar issue can occur when determining which \(i^{\star}\) exits the index set (more than one \(x_i\) becomes zero at the same time)
A simple approach to fix these issues, Bland’s rule: 1. At each step, choose smallest \(j\) such that \(\bar{c}_j<0\) 2. From variables \(x_i\) that could exit index set, choose smallest \(i\)
Alternatively, perturb \(b\) by some small noise and then solve
We assumed a feasible initial point (i.e. \(\mathcal{I}\) such that \(A_{\mathcal{I}} b \geq 0\) )
To find such a point (in cases where it is not easy to construct one), we introduce variables \(y \in \mathbb{R}^m\) and solve auxiliary problem \[ \begin{aligned} \underset{x, y}{\operatorname{minimize}} & 1^T y \\ \text { subject to } & A x+y=b \\ & x, y \geq 0 \end{aligned} \]
A standard form linear program, with feasible solution \(x=0, y=b\), (if \(b_i<0\), replace constraint \(a_i^T x=b_i\) with \(-a_i^T x=-b_i\) )
If solution to this problem has \(y=0\), we know \(A x=b\), so we have found a feasible solution to the original problem (though need to handle possible degeneracy)
Simplex algorithm requires inverting \(A_{\mathcal{I}}\) at each iteration: naive implementation would re-invert this matrix every time \(\Longrightarrow O\left(m^3\right)\) computation at each iteration
Revised simplex algorithm directly maintains and updates this inverse \(\mathcal{A}_I^{-1}\) at each iteration, using \(O\left(m^2\right)\) computation
Key idea is the Sherman-Morrison inversion formula, for an invertible matrix \(C \in \mathbb{R}^{n \times n}\) and vectors \(u, v \in \mathbb{R}^n\) \[ \left(C+u v^T\right)^{-1}=C^{-1}-\frac{C^{-1} u v^T C^{-1}}{1+v^T C^{-1} u} \]
Suppose we update \(\mathcal{I}\) by dropping index \(\mathcal{I}_k\) and adding index \(j\)
Numerically, this is done by overwriting the column \(a_{\mathcal{I}_k}\) in \(A_{\mathcal{I}}\) with \(a_j\) (suppose this occurs at index \(I_k\) ), i.e., \[ A_{\mathcal{I}} \leftarrow A_{\mathcal{I}}+\left(a_j-a_{\mathcal{I}_k}\right) e_k^T \] where \(e_k\) is the \(k\) th basis vector (all zeros except for 1 at element \(k\) )
Using the Sherman-Morrison formula \[ \left(A_{\mathcal{I}}+\left(a_j-a_{\mathcal{I}_k}\right) e_k^T\right)^{-1}=A_{\mathcal{I}}^{-1}-\frac{A_{\mathcal{I}}^{-1}\left(a_j-a_{\mathcal{I}_k}\right) e_k^T A_{\mathcal{I}}^{-1}}{1+e_k^T A_{\mathcal{I}}^{-1}\left(a_j-a_{\mathcal{I}_k}\right)} \]
Right most expression can be written as an outer product matrix \(u v^T\), so forming and adding it to \(A_{\mathcal{I}}^{-1}\) takes \(O\left(m^2\right)\) operations
Review: Matrix math