10.11. Linear Programming

10.11.1. Linear Optimization Problem

10.11.1.1. General Form

Definition 10.38 (Linear optimization problem)

A convex optimization problem where the objective and constraint functions are all affine is known as a linear optimization problem or a linear program.

A general linear program has the following form:

(10.27)$$\begin{array}{rlrl}& \text{minimize }& & {\mathbf{c}}^T\mathbf{x}+d\\ & \text{subject to }& & \mathbf{G}\mathbf{x}⪯\mathbf{h}\\ & & & \mathbf{A}\mathbf{x}=\mathbf{b}\end{array}$$

where

1. $\mathbf{x}\in {\mathbb{R}}^n$ is the optimization variable.

2. $f(\mathbf{x})={\mathbf{c}}^T\mathbf{x}+d$ is an affine objective function.

3. $\mathbf{G}\in {\mathbb{R}}^{m\times n}$ and $\mathbf{h}\in {\mathbb{R}}^m$ describe the $m$ affine inequality constraints.

4. $\mathbf{A}\in {\mathbb{R}}^{p\times n}$ and $\mathbf{b}\in {\mathbb{R}}^p$ describe the $p$ affine equality constraints.

Note

1. Minimizing ${\mathbf{c}}^T\mathbf{x}+d$ is same as minimizing ${\mathbf{c}}^T\mathbf{x}$ with the scalar $d$ only being an offset for the optimal value. Thus, the affine objective can be replaced as a linear objective.

2. The problem of maximizing ${\mathbf{c}}^T\mathbf{x}+d$ is same as the problem of minimizing $-{\mathbf{c}}^T\mathbf{x}-d$ which is also an affine functional. Thus, an affine maximization problem with affine constraints is also a linear program.

3. The feasible set of a linear program is a polyhedron. Recall from Definition 9.18 that a polyhedron is the solution set of a finite number of linear inequalities and linear equations. In this case, we have $m$ linear inequalities and $p$ linear equations.

10.11.1.2. Standard Form

Definition 10.39 (Linear programming standard form)

The standard form for linear programming is given by

(10.28)$$\begin{array}{rlrl}& \text{minimize }& & {\mathbf{c}}^T\mathbf{x}\\ & \text{subject to }& & \mathbf{A}\mathbf{x}=\mathbf{b}\\ & & & \mathbf{x}⪰\mathbf{0}.\end{array}$$

Note

This form has

1. A linear objective function.

2. A system of linear equations as equality constraints.

3. Component wise nonnegativity constraints on the optimization variable $\mathbf{x}$.

Observation 10.12 (Converting general form into standard form)

We show how the general form (10.27) can be converted to an equivalent standard form (10.28) linear programming problem.

1. We first introduce slack variables to the linear inequalities $\mathbf{s}\in {\mathbb{R}}^m$. We get the form

   $$\begin{array}{rlrl}& \text{minimize }& & {\mathbf{c}}^T\mathbf{x}+d\\ & \text{subject to }& & \mathbf{G}\mathbf{x}+\mathbf{s}=\mathbf{h}\\ & & & \mathbf{A}\mathbf{x}=\mathbf{b}\\ & & & \mathbf{s}⪰\mathbf{0}.\end{array}$$

2. We next split the optimization variable $\mathbf{x}\in {\mathbb{R}}^n$ as the difference between two nonnegative variables ${\mathbf{x}}^{+}$ and ${\mathbf{x}}^{-}$. $\mathbf{x}={\mathbf{x}}^{+}-{\mathbf{x}}^{-}$ where both ${\mathbf{x}}^{+},{\mathbf{x}}^{-}\in {\mathbb{R}}_{+}^n$. The optimization problem becomes:

   $$\begin{array}{rlrl}& \text{minimize }& & {\mathbf{c}}^T{\mathbf{x}}^{+}-{\mathbf{c}}^T{\mathbf{x}}^{-}+d\\ & \text{subject to }& & \mathbf{G}{\mathbf{x}}^{+}-\mathbf{G}{\mathbf{x}}^{-}+\mathbf{s}=\mathbf{h}\\ & & & \mathbf{A}{\mathbf{x}}^{+}-\mathbf{A}{\mathbf{x}}^{-}=\mathbf{b}\\ & & & {\mathbf{x}}^{+}⪰\mathbf{0},{\mathbf{x}}^{-}⪰\mathbf{0},\mathbf{s}⪰\mathbf{0}.\end{array}$$

3. This is an LP in standard form with the optimization variables being ${\mathbf{x}}^{+}$, ${\mathbf{x}}^{-}$, and $\mathbf{s}$.

   1. We can drop the scalar $d$ to get a linear objective function.

   2. We can introduce an optimization variable $\mathbf{y}\in {\mathbb{R}}^{2n+m}$ as the concatenation of ${\mathbf{x}}^{+}$, ${\mathbf{x}}^{-}$, and $\mathbf{s}$ and require that $\mathbf{y}⪰\mathbf{0}$ be the unified inequality constraint.

   3. We can then write $\mathbf{G}{\mathbf{x}}^{+}-\mathbf{G}{\mathbf{x}}^{-}+\mathbf{s}=\mathbf{h}$ as

      $$\left[\begin{array}{ccc}\mathbf{G}& -\mathbf{G}& {\mathbf{I}}_m\end{array}\right]\mathbf{y}=\mathbf{h}.$$

   4. Similarly, the objective function can be written as

      $$\begin{array}{r}{\left[\begin{array}{c}\mathbf{c}\\ -\mathbf{c}\\ {\mathbf{0}}_m\end{array}\right]}^T\mathbf{y}.\end{array}$$

10.11.1.3. Inequality Form

Definition 10.40 (Linear programming inequality form)

The standard form for linear programming is given by

(10.29)$$\begin{array}{rlrl}& \text{minimize }& & {\mathbf{c}}^T\mathbf{x}\\ & \text{subject to }& & \mathbf{A}\mathbf{x}⪯\mathbf{b}.\end{array}$$

Note

This form has

1. A linear objective function.

2. A system of linear inequalities as inequality constraints.

3. No equality constraints.