Linear programming

Exercise 1

Consider a linear program in its standard form:

define formally the linear program using its general minimization expression, and
derive the KKT conditions for such a program.

What is a Linear Program or LP?

def: Linear program is an optimization problems with a linear objective function $J$ and linear constraints $\mathbf{c}(\mathbf{x})$, which may include both equalities and inequalities. Linear programs are usually stated and analyzed in the following standard form [i]:

$$ \min_{\mathbf{x}\in\mathbb{R}^n}{J(\mathbf{x})=\mathbf{c}^T\mathbf{x}\,\,\,\text{s.t.}\,\,\,A\mathbf{x}=\mathbf{b},\,\mathbf{x}\geq 0}, $$

where $\mathbf{c}\in\,\mathbb{R}^n,\,b\in\,\mathbb{R}^m$ and $A\in\,\mathbb{R}^{m\times n}$.

The Lagrangian of the linear program in it's standard form can be expressed:

$$ \mathcal{L}(\mathbf{x},\mathbf{\lambda})=\mathbf{c}^T\mathbf{x}-\mathbf{\lambda}_1^T(\mathbf{A}\mathbf{x}-\mathbf{b})-\mathbf{\lambda}_2^T\mathbf{x} $$

where $\mathbf{\lambda}_1\,\in\,\mathbb{R}^m$ and $\mathbf{\lambda}_2\,\in\,\mathbb{R}^n$ are the Lagrange multipliers (or better, vectors of lagrange multipliers as we are speaking in general terms) for the equality and the inequality constraint. The gradient of such a Lagrangian yields to:

$$ \nabla_\mathbf{x}\mathcal{L}(\mathbf{x}^*,\mathbf{\lambda}^*)=\mathbf{c}-(\mathbf{\lambda}_1^{*T}\mathbf{A})^T-\mathbf{\lambda}_2^*, $$

note that this is possible because both cost function and constraints are linear. The KKT conditions can be expressed [ii]:

$\mathbf{A}^T\mathbf{\lambda}_1^*+\mathbf{\lambda}_2^*-\mathbf{c}=0$,
$\mathbf{A}\mathbf{x}^*-\mathbf{b}=0$,
$\mathbf{x}^*\geq 0$,
$\mathbf{\lambda}_2\geq 0 $, and
$\mathbf{\lambda}_2^*\mathbf{x}_i^*=0$.

Exercise 2

Consider the standard form of a linear program (this is the exercise on page 390 n. 13.5 in the textbook):

$$\min_{\mathbf{x}\in\mathbb{R}^n}{J(\mathbf{x})=\mathbf{c}^T\mathbf{x}\,\,\,\text{s.t.}\,\,\,A\mathbf{x}\geq\mathbf{b},\,\mathbf{x}\geq 0},$$

with $\mathbf{c}\in\,\mathbb{R}^n,\,b\in\,\mathbb{R}^m$ and $A\in\,\mathbb{R}^{m\times n}$:

show that its dual is expressed (with $\mathbf{\lambda}\in\,\mathbb{R}^m$):

$$\max_{\mathbf{\lambda}\in\mathbb{R}^m}{J(\mathbf{\lambda})=\mathbf{b}^T\mathbf{\lambda}\,\,\,\text{s.t.}\,\,\,A^T\mathbf{\lambda}\leq \mathbf{c},\,\mathbf{\lambda}\geq 0}.$$

Exercise 3

Two process stages are involved in the production of gold of different carats (kt). Let's suppose a gold production factory in Denmark profits 40 dollars per gram of 18 kt gold, 30 dollars for 14 kt gold, and 20 dollars for 10 kt gold.

To make a gold ingot of 1 kg, the following times in each process stage are required:

1 kg of 18 kt gold requires 3 hours in the first, 2 hours in the second stage,
1 kg of 14 kt gold requires 2 hours in the first, 2 hours in the second stage, and
1 kg of 10 kt gold requires 1 hour in the first, 3 hours in the second stage.

During 1 year, the first stage has 7 200 hours and the second stage has 6 000 hours production time available. The rest is needed due to the maintenance of the production line. The available time should be fully utilized.

We wish to maximize the yearly profit.

define the LP,
use some of the KKT conditions to identify the points of the optimization problem that might be optimal, and
show which of the points found at the previous step respect all the KKT conditions.

Wishing to maximize the profit, means minimizing its negative; so let's impose as the decision variable $\mathbf{x}=(x_1\,\,\,x_2\,\,\,x_3)^T$ the kg of gold manufactured, and as $\mathbf{c}$ the negative of the profits per kg of different ingots, i.e., $\mathbf{c}=-10^4(4\,\,\,3\,\,\,2)^T$. Decision variables are the unknowns of a mathematical programming model - e.g., the amount of gold manufactured. In this exercise we are determining their optimum values with an optimization method. To be exact, here we are expressing KKT conditions so we are doing it analytically. You can later use an optimization method to establish them numerically (i.e., Matlab script that uses the Simplex method).

The profit can be written:

$$ -\mathbf{c}^T\mathbf{x}=-c_1x_1-c_2x_2-c_3x_3=4\cdot 10^4x_1+3\cdot 10^4x_2+2\cdot 10^4x_3 $$

For the two stages and their per-year time constraint, the objective function can be expressed in the following form:

$$ 3x_1+2x_2+1x_3=7.2\cdot 10^3, $$$$ 2x_1+2x_2+3x_3=6\cdot 10^3, $$

which can be clearly expressed in the form $\mathbf{A}\mathbf{x}=\mathbf{b}$ given:

$$ \mathbf{A}=\begin{pmatrix}\,3&2&1\,\\2&2&3 \end{pmatrix},\,\,\,\,\,\,\mathbf{b}=10^3\begin{pmatrix}\,7.2\,\\6\end{pmatrix}, $$

we cannot produce a negative amount of ingots, thus $\mathbf{x}\geq 0$ holds, and the problem can be stated as follows [i]:

$$ \min_{\mathbf{x}\in\mathbb{R}^3}{J(\mathbf{x})=-10^4(4\,\,\,3\,\,\,2)\mathbf{x}\,\,\,\text{s.t.}\,\,\,\begin{pmatrix}\,3&2&1\,\\2&2&3 \end{pmatrix}\mathbf{x}=10^3\begin{pmatrix}\,7.2\,\\6\end{pmatrix},\,\mathbf{x}\geq 0}. $$

Note that now you can use what you wrote previously in Exercise [1].The Lagrangian can be expressed with the following equation, where $\mathbf{\lambda}_1\in\mathbb{R}^2$ and $\mathbf{\lambda}_2\in\mathbb{R}^3$:

$$ \mathcal{L}(\mathbf{x},\mathbf{\lambda})=J(\mathbf{x})-\mathbf{\lambda}_1\left( \begin{pmatrix}\,3&2&1\,\\2&2&3\end{pmatrix} \mathbf{x}-10^3 \begin{pmatrix}\,7.2\,\\6\end{pmatrix} \right)-\mathbf{\lambda}_2(\mathbf{x}), $$

the stationary KKT condition $\nabla_{\mathbf{x}}\mathcal{L}(\mathbf{x}^*,\mathbf{\lambda}^*)=0$ can be written:

$$ \nabla_{\mathbf{x}}\mathcal{L}(\mathbf{x}^*,\mathbf{\lambda}^*)= -10^4\begin{pmatrix}\,4\,\\3\\2\end{pmatrix}-\left( (\lambda_{1,1}\,\,\,\lambda_{1,2})\begin{pmatrix}\,3&2&1\,\\2&2&3\end{pmatrix} \right)^T-\begin{pmatrix}\,\lambda_{2,1}\,\\\lambda_{2,2}\\\lambda_{2,3}\end{pmatrix}= \begin{pmatrix} -4\cdot 10^4-3\lambda_{1,1}-2\lambda_{1,2}-\lambda_{2,1}\\ -3\cdot 10^4-2\lambda_{1,1}-2\lambda_{1,2}-\lambda_{2,2}\\ -2\cdot 10^4-\lambda_{1,1}-3\lambda_{1,2}-\lambda_{2,3} \end{pmatrix}=0, $$

which gives us the values of $\mathbf{\lambda}^*$ such that the above equation is satisfied. Now let's use the second KKT condition $c_i(\mathbf{x})=0$ to find the optimal decision variable (amount of gold manufactured) $\mathbf{x}^*$

$$ c(\mathbf{x}^*)=\mathbf{A}\mathbf{x}-\mathbf{b}=\begin{pmatrix} 3x_1+2x_2+x_3-7.2\cdot 10^3\\ 2x_1+2x_2+3x_3-6\cdot 10^3 \end{pmatrix}=0, $$

as you can see, we have just two equation in a system of three variables. We need thus to differentiate the problem in three sub-classes, by eliminating variables one-by-one [ii]:

when $x_1=0,\,\mathbf{x}^*=(0\,\,\,3900\,\,\,-600)$, note that this point is infeasible, so it cannot be an optimal point (you cannot have a negative product, as you don't respect the equality constraint),
when $x_2=0,\,\mathbf{x}^*=\frac{1}{7}(15600\,\,\,0\,\,\,3600)$, and
when $x_3=0,\,\mathbf{x}^*=(1200\,\,\,1800\,\,\,0)$.

which gives us the values of the possible candidates for optimal points (due to the convexity of linear programs, KKT conditions are both necessary and sufficient).

Let's check if KKT holds for these points. The point $\mathbf{x}^*=(0\,\,\,3900\,\,\,-600)$ clearly does not satisfy KKT conditions, as it is not feasible.

So let's check the point $\mathbf{x}^*=\frac{1}{7}(15600\,\,\,0\,\,\,3600)$. From the last KKT condition $\mathbf{\lambda}_2^*\mathbf{x}_i^*=0,$ we know that either $\lambda_{2,i}$ is zero, or the decision variable is zero:

$$ \nabla_{\mathbf{x}}\mathcal{L}(\mathbf{x}^*,\mathbf{\lambda}^*)= \begin{pmatrix} -40 000-3\lambda_{1,1}-2\lambda_{1,2}\\ -30 000-2\lambda_{1,1}-2\lambda_{1,2}-\lambda_{2,2}\\ -20 000-\lambda_{1,1}-3\lambda_{1,2} \end{pmatrix}=0, $$

this results in $\lambda_{2,2}=-\frac{10000}{7}$. Now remember the KKT condition $\mathbf{\lambda}_2\geq 0 $, which is not respected. Thus this is not the optimal point.

Finally let's check the point $\mathbf{x}^*=(1200\,\,\,1800\,\,\,0)$:

$$ \nabla_{\mathbf{x}}\mathcal{L}(\mathbf{x}^*,\mathbf{\lambda}^*)= \begin{pmatrix} -40 000-3\lambda_{1,1}-2\lambda_{1,2}\\ -30 000-2\lambda_{1,1}-2\lambda_{1,2}\\ -20 000-\lambda_{1,1}-3\lambda_{1,2}-\lambda_{2,3} \end{pmatrix}=0, $$

this result in $\lambda_{2,3}=5000$. Which respect all the KKT conditions. This is henceforth the optimal point [iii].