Linear Programming

Linear programming (LP) deals with optimization problems where both the objective function and constraints are linear.

Standard Form

A linear programming problem can be expressed as:

${\min }_{\theta \in {\mathbb{R}}^D}{c}^T\theta \text{ such that }\{\begin{array}{l}{A}_{eq}\theta =b_{eq}{A}_{ineq}\theta \le b_{ineq}\end{array}$

Where:

• $A_{eq}\in {\mathbb{R}}^{m\times D}$ and $A_{ineq}\in {\mathbb{R}}^{n\times D}$ are matrices
• $c\in {\mathbb{R}}^D$, $b_{eq}\in {\mathbb{R}}^m$ and $b_{ineq}\in {\mathbb{R}}^n$ are vectors

Key Characteristics

• Hessian (and higher derivatives) are zero - unlike quadratic/nonlinear problems
• Inequality constraints are necessary - without constraints, linear objectives have no minimum/maximum
• Requires specialized numerical methods - different from those used for nonlinear optimization

Standard Canonical Form

All linear programs can be converted to the standard canonical form:

${\min }_{\theta \in {\mathbb{R}}^D}{c}^T\theta \text{ such that }\{\begin{array}{l}A\theta =b\theta \ge 0\end{array}$

Where $A\in {\mathbb{R}}^{C\times D}$ is a matrix, $c\in {\mathbb{R}}^D$ and $b\in {\mathbb{R}}^C$ are vectors, and $C<D$.

KKT Conditions for Linear Programming

By splitting the Lagrange multiplier into $\lambda$ and $s$:

1. $A^T{\lambda }^{\ast }+s^{\ast }=c$
2. $A{\theta }^{\ast }=b$
3. ${\theta }^{\ast }\ge 0$
4. $s^{\ast }\ge 0$
5. ${\theta }_i^{\ast }{s}_i=0$ for all $i=1,\dots ,n$

Solution Methods

Graphical Method

• For small problems (typically 2 variables)
• Plot the constraints to identify the feasible region
• The optimal solution will be at a vertex of the feasible region

Simplex Algorithm

• Start at a vertex of the feasible region
• Move along edges to adjacent vertices that improve the objective value
• Continue until reaching the optimal vertex
• Efficient for most practical problems