Linear programming
In words...
Linear programming concerns the analysis of and the algorithms for one of the most simple class of optimization problems.
Linear programming also forms the basic block of many algorithms for quadratic programming or more complex problems.
In pictures...
In maths...
General form of a linear program
A linear program is an optimization problem of the form
\begin{align*}
\min_{\g x\in\R^d} \ & \g c^T \g x \\
\mbox{s.t. } & \g A\g x \leq \g b \\
& \g A_{eq} \g x = \g b_{eq} \\
&\g l \leq \g x\leq \g u
\end{align*}
Recognizing a linear program
Many problems not written as linear programs can be rewritten as linear programs. A typical example often encountered in machine learning is the minimization of an
$\ell_1$-norm. For instance, consider the problem
\begin{align*}
\min_{\g x\in\R^d} \ & \|\g x\|_1 \\
\mbox{s.t. } & \g A\g x \leq \g b .
\end{align*}
By introducing additional variables, this can be equivalently formulated as
\begin{align*}
\min_{\g x\in\R^d, \g a\in \R^d} \ & \g 1^T \g a \\
\mbox{s.t. } & \g A\g x \leq \g b \\
&-\g a \leq \g x\leq \g a
\end{align*}
which is clearly a linear program.
Standard form of a linear program
The standard form of a linear program is
\begin{align*}
\min_{\g x\in\R^d} \ & \g c^T \g x \\
\mbox{s.t. } & \g A\g x = \g b \\
& \g x\geq \g 0
\end{align*}
We can easily transform a general linear program
\begin{align*}
\min_{\g x\in\R^d} \ & \g c^T \g x \\
\mbox{s.t. } & \g A\g x \leq \g b \\
& \g A_{eq} \g x = \g b_{eq} \\
&\g l \leq \g x\leq \g u
\end{align*}
with $\g A\in\R^{N_I\times d}$ and $\g A_{eq}\in\R^{N_E \times d}$ to the standard form by introducing additional variables as
\begin{align*}
\min_{\g x\in\R^d, \g x_I\in \R^{N_I},\g x_E\in\R^{N_E},\g x_l\in\R^d,\g x_u\in\R^d} \ & \g c^T \g x \\
\mbox{s.t. } & \begin{bmatrix} \g A & \g I & \g 0 & \g 0 & \g 0\\
\g A_{eq} & \g 0 & \g I & \g 0 & \g 0\\
-\g I & \g 0 & \g 0 & \g I & \g 0 \\
\g I & \g 0 & \g 0 & \g 0 & \g I
\end{bmatrix}
\begin{bmatrix}
\g x\\ \g x_I \\ \g x_E \\ \g x_l \\ \g x_u \end{bmatrix}
= \begin{bmatrix}
\g b\\ \g b_{eq} \\ -\g l \\ \g u
\end{bmatrix}
\\
&\g x \geq 0,
\g x_I \geq 0,
\g x_E \geq 0,
\g x_l \geq 0,
\g x_u \geq 0.
\end{align*}