13. Simplex method

Algorithmic Idea

• The optimum is an extreme point (aka vertex)

  → Of course, we have to be sure that it is bounded.

• Extreme point = a basic feasible solution (BFS)

• A BFS corresponds to a basis matrix

• Consider a method that moves to an adjacent vertex

💡

즉, extreme point를 찾고 optimality condition을 check하고 아닌 경우 adjacent vertex로 이동한다는 것. 이때 convex이기 때문에 optimality condition을 만족하면 global minimum임을 보장할 수 있다.

• Basic variable : $\ge 0$ ($0$ is possible because of degeneracy)

• Non-basic variable : $= 0$

Basis matrix update:

• Entering variable: non-basic → basic

• Leaving variable: basic → non-basic

Algorithm

$$\min c^Tx$$

$\text{subject to}$

$$Ax = b \\ x_i \ge 0,\forall i$$

Normally, the number of column is larger than the number of row.

W.L.O.G. $A\in \mathcal L(\R^n, \R^m) \quad (n \ge m)$

1. Assume that we already know the initial starting point

   💡

   We can get the initial point of this algorithm by Phase-1 which is similar but a slightly different linear programming. This algorithm will be discussed later.

2. We only consider the columns in the basic.

   W.L.O.G

   $$A = [B| N] \\ x= \begin{bmatrix}x_B \\x_N\end{bmatrix}$$

2. Find the solution for

   $$Bx_B = b$$

   or equivalently

   $$x_B = B^{-1}b$$

What can we do when given point is not a optimal point?

Revisit our objective function

$$\min c^Tx = c_B^Tx_B + c_N^Tx_N$$

$\text{subject to}$

$$Ax = b \\ x_i \ge 0,\forall i$$

Our given point $x_B = B^{-1}b - B^{-1}Nx_N$

Therefore our objective function is

$$\min c^Tx = c_B^TB^{-1}b + (c_N^T - c_B^TB^{-1}N)x_N$$

we call $c_N^T - c_B^TB^{-1}N$ to reduced cost and $c_B^TB^{-1}b$ is a current objective function value.

Note that if a non-basic variable increases it s value from zero, it reduced cost indicates the change per unit in the objective function.

💡

Entering variable : variable that have most negative reduced cost. However, we can’t guarantee that it is always optimal since there are other constraints also. Other more sophisticated ways of choosing the entering variable are possible, but they may require additional computations.

💡

추가적으로 $B$가 invertible하기 위해서는 적어도 정방행렬이어야 한다. 즉, basic variable의 개수는 주어진 constraint의 개수와 동일하게 잡아야 한다.

Basically, the steps of the simplex algorithm are given below

1. The optimality test : Computer the reduced cost

   $$(c_N^T - c_B^TB^{-1}N)$$

   1. If for all coefficient are all non-negative, the current basis is optimal
   2. If not, select a variable that has a negative reduced cost value and make it as a entering variable. For simplicity, let say the entering variable is $i$’th component of $x_N$

2. Select leaving variable : Increase the value of

   $$x_B = B^{-1}b - B^{-1}N_ix_{N_i}$$

   until there are no violating constraints, where $N_i$ is the $i$’th column of $N$.

3. Update : Update the basis matrix $B$ and the vector of basic variables $x_B$

4. Repeat 1 ~ 3 until current basis is optimal.

Example 1

$$\min -x_1 -2x_2$$

$\text{subject to}$

$$-2x_1 + x_2 + s_1 = 2 \\ -x_1 + x_2 + s_2 = 3 \\ x_1 + s_3 = 3 \\ x_1, x_2, s_1, s_2, s_3 \ge 0$$

which is equivalent to

$$\min c^T\begin{bmatrix}x \\s\end{bmatrix}$$

$\text{subject to}$

$$A\begin{bmatrix}x\\ s\end{bmatrix} = b$$

where

$$c^T = \begin{bmatrix}-1 & -2 & 0 & 0& 0\end{bmatrix} \\ A= \begin{bmatrix}-2 & 1 & 1 & 0 & 0 \\ -1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1\end{bmatrix} \\ b = \begin{bmatrix}2 \\ 3\\3\end{bmatrix}$$

Take

$$x_B = \begin{bmatrix}s_1 \\ s_2\\s_3\end{bmatrix}, x_N = \begin{bmatrix}x_1\\x_2\end{bmatrix} \\ B = \begin{bmatrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1\end{bmatrix} \\ N = \begin{bmatrix}-2 & 1 \\ -1 & 1 \\ 1 & 0\end{bmatrix}$$

Therefore,

$$x_B = B^{-1}b = \begin{bmatrix}2 \\ 3\\ 3\end{bmatrix}$$

and it reduced cost is

$$\begin{align}c_N^T - c_B^TB^{-1}N &= \begin{bmatrix}-1 & 2\end{bmatrix} - \begin{bmatrix}0 & 0 & 0\end{bmatrix}\begin{bmatrix}-2 & 1 \\ -1 & 1 \\ 1 & 0\end{bmatrix} \\ &= \begin{bmatrix}-1 & -2\end{bmatrix}\end{align}$$

Therefore, we take $x_2$ as a entering variable

$$x_B = \begin{bmatrix}2 \\ 3\\3\end{bmatrix} - B^{-1}N x_N = \begin{bmatrix}2\\3\\3\end{bmatrix} - \begin{bmatrix}1\\1\\0\end{bmatrix}x_2$$

Note that the column that related to $x_2$ is $(1, 1, 0)^T$.

💡

$s_1$ is leaving variable since it is firstly violated when we increase the value of $x_2$

Example 2

$$A = \begin{bmatrix}2 & 1 & 6 \\ 1 & 0 & 2\end{bmatrix} \\ x = \begin{bmatrix}x_1 \\ x_2 \\ x_3\end{bmatrix} \\ b = \begin{bmatrix}4 \\ 1\end{bmatrix}$$

In addition,

$$x_B = \begin{bmatrix}x_1 \\ x_2\end{bmatrix}\\ x_N =\begin{bmatrix}x_3\end{bmatrix}$$

Let the reduced cost of $x_3$ is negative, therefore we can make $x_3$ as an entering variable. But we have to decide how much we could increase $x_3$ without making any problem with constraints. Ideally it is better to increase the value of $x_3$ but it is impossible because other constraints are also depend on $x_3$.

$$\begin{bmatrix}2 & 1 \\ 1 & 0\end{bmatrix} \begin{bmatrix}x_1\\x_2\end{bmatrix} + \begin{bmatrix}6\\2\end{bmatrix}\begin{bmatrix}x_3\end{bmatrix} = \begin{bmatrix}4\\1\end{bmatrix}$$

$$\begin{bmatrix}x_1 \\ x_2\end{bmatrix} = \begin{bmatrix}2 & 1 \\ 1 & 0\end{bmatrix}^{-1}\begin{bmatrix}4 \\ 1\end{bmatrix} - \begin{bmatrix}2 & 1 \\ 1 & 0\end{bmatrix}^{-1}\begin{bmatrix}6 \\ 2\end{bmatrix}x_3$$

$$\begin{bmatrix}x_1 \\ x_2\end{bmatrix} = \begin{bmatrix}1\\ 2\end{bmatrix} - \begin{bmatrix}2 \\ 2\end{bmatrix}x_3$$

For example, since $x_1 = 1 - 2x_3$, if we take $x_3$ greater than $\frac{1}{2}$, $x_1$ goes to negative which makes a problem.

$$x_1 = 1-2x_3 \\ x_2 = 2 - 2x_3$$

Therefore, we can increase $x_3$ until $\frac{1}{2}$. In this scenario, $x_1$ have to change to non-basic variable. We call it leaving variable.

💡

Note that the simplex algorithm is terminated when all variables in reduced cost vector are non-negative.

Simplex Method in Tableau Form

A couple of More Details

Generating an initial point

In general, the origin is not necessarily a feasible BFS. Therefore, we have to find the initial starting point.

Let say our optimization problem is as follows

$$\min c^Tx$$

$\text{subject to}$

$$Ax = b \\ x_i \ge 0,\forall i$$

We can define different linear programming to get a initial point of the original optimization problem

$$\min 1^Ty$$

$\text{subject to}$

$$Ax + Iy = b \\ x\ge 0, y\ge 0$$

This problem is also a linear programming so that we can apply the simplex method. Moreover, we already know the extreme point of this problem

$$x = 0, y = b$$

It is called Phase-1.

But what if we can’t find the $y = 0$? In this case, it implies there is no feasible solution in the original optimization problem.

Unbounded problem

The simplex method there is the possibility that the problem will be unbounded.

For example,

$$x_B = B^{-1}b - B^{-1}N_ix_{N_i}$$

when a any value in $B^{-1}N_i$ is positive, the basic variable will decrease as the entering variable $x_{N_i}$ increases.

However, if there is no positive value in $B^{-1}N_i$, we can increase $x_{N_i}$ whatever we want. That means the feasible region is unbounded. Therefore, we can detect it by using simplex method when our original optimization problem is unbounded.

Example

Consider this optimization problem

$$\min -x_1 -2x_2$$

$\text{subject to}$

$$-x_1 + x_2 + x_3 = 2 \\ -2x_1 + x_2 + x_4 = 1 \\ x_1, x_2, x_3, x_4\ge 0$$

Take

$$x_B = (x_1, x_2)^T \\ x_N = (x_3, x_4)^T$$

At this iterations, $x_B = (1, 3)^T$ and the reduced cost for the non-basic variables are $(5, -3)^T$.

Since it has a negative value $-3$, the current point is not a optimal. Therefore, we take $x_4$ as an entering variable.

Since,

$$\begin{align}B^{-1}N_2 &= \begin{bmatrix}1 & -1 \\ 2 & -1 \end{bmatrix}\begin{bmatrix}0 \\1 \end{bmatrix} \\ &= \begin{bmatrix}-1 \\ -1\end{bmatrix}\end{align}$$

That means we can increase $x_4$ without limit, so the objective function can be decreased without limit. Therefore, there is no finite solution to this linear program.

Degeneracy

The version of the simplex method that we have described can fail, cycling endlessly without any improvement in the objective and without finding a solution. This can only happen on degenerate problems, problems where a basic variable is equal to zero in some basis.

Example

This about this example,

$$\min -x_1 -x_2$$

$\text{subejct to}$

$$x_1 + s_1 = 2 \\ x_1 + x_2 + s_2 = 2 \\ x_1, x_2, s_1, s_2 \ge 0$$

It is equivalent to

$$\min c^Tx$$

$\text{subejct to}$

$$Ax = b \\ x \ge 0$$

where

$$c^T = \begin{bmatrix}-1 & -1 & 0 & 0\end{bmatrix}\\A = \begin{bmatrix}1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1\end{bmatrix} \\ b = \begin{bmatrix}2 \\ 2\end{bmatrix}$$

Suppose we take $x_1, s_4$ as a basis. Then

$$B = \begin{bmatrix}1 & 0 \\ 1 & 1\end{bmatrix} \\ N = \begin{bmatrix}0 & 1 \\ 1 & 0\end{bmatrix}$$

Calculate the reduced cost

$$\begin{align}c_N^T - c_B^{T}B^{-1}N &= \begin{bmatrix}-1 & 0\end{bmatrix} - \begin{bmatrix}-1 & 0\end{bmatrix}\begin{bmatrix}1 & 0 \\ -1 & 1\end{bmatrix}\begin{bmatrix}0 & 1 \\ 1 & 0\end{bmatrix} \\ &= \begin{bmatrix}-1 & 1\end{bmatrix}\end{align}$$

Therefore, we take $x_2$ as a intering variable. Now we have to check the leaving variable

$$\begin{align}x_B &= B^{-1}b - B^{-1}N_1x_2 \\ &= \begin{bmatrix}2 \\ 0\end{bmatrix} - \begin{bmatrix}0 \\ 1\end{bmatrix}x_2 \end{align}$$

Therefore, $s_4$ is a leaving variable and its value set to $0$.

In this case, we have to improvement in objective function. Moreover, it can be fluctuate forever even though there is no improvement in objective function.

💡

이러한 일이 근본적으로 벌어지는 이유는 basic variable 중에 해당 값이 0인 것이 존재할 때 발생한다.

Optimality and the Lagrangian Function

We have discussed optimality condition by using the Lagrangian function before. Actually, this approach is more general. Therefore, we can learn this approach even though our optimization problem is linear program.

We can change our objective function as

$$\min c^Tx$$

$\text{subject to}$

$$Ax = b \quad(\lambda) \\ Ix \ge 0 \quad (\pi)$$

Define

$$\mathcal L(x, \lambda, \pi) = c^Tx - \lambda^T(Ax - b) - \pi^T(Ix -0)$$

Use KKT condition.

1. Stationary condition

   $$\nabla_x\mathcal L(x, \lambda, \pi) = 0 \\ \Rightarrow c - \lambda A^T - \pi = 0$$

2. Primal feasibility

   $$Ax^* = b \\ Ix^* \ge 0$$

3. Dual feasibility

   $$\pi\ge 0$$

4. Complementary slackness

   $$\pi^TIx = 0$$

How can we connect a KKT condition and termination condition of simplex method?

Recall that a simplex method can be terminated when all variables in reduced cost vector is non-negative.

$$c_N^T - c_B^TB^{-1}N$$

Take

$$\begin{align}\pi_N = c_N^T - c_B^TB^{-1}N \\ \pi_B = 0\end{align}$$

Then, it satisfy complementary slackness condition and dual feasibility condition.

$$c - \pi = \lambda A^{T} \\ \Rightarrow \begin{bmatrix}c_B^T \\ c_N^T\end{bmatrix} - \begin{bmatrix}\pi_B^T \\ \pi_N^T\end{bmatrix}=\lambda\begin{bmatrix}B^T \\ N^T\end{bmatrix}$$

Since 12 and 13,

$$\begin{bmatrix}c_B^T \\ c_N^T\end{bmatrix} - \begin{bmatrix}\pi_B^T \\ \pi_N^T\end{bmatrix}=\lambda\begin{bmatrix}B^T \\ N^T\end{bmatrix} \\ \Rightarrow \begin{bmatrix}c_B^T \\ c_N^T\end{bmatrix} - \begin{bmatrix}0 \\ c_N -(c_B^TB^{-1}N)^T\end{bmatrix}=\lambda\begin{bmatrix}B^T \\ N^T\end{bmatrix} \\ \Rightarrow\begin{bmatrix}c_B^T\\N^T(c_B^TB^{-1})^{T}\end{bmatrix} =\lambda\begin{bmatrix}B^T \\ N^T\end{bmatrix}$$

Therefore,

$$\begin{align}\lambda &= (B^{T})^{-1}c_B^T \\ &= (c_B^TB^{-1})^T\end{align}$$

If we take

$$\begin{align}&\pi_N = c_N^T - c_B^TB^{-1}N \\ &\pi_B = 0 \\ &\lambda = (c_B^TB^{-1})^T\end{align}$$

KKT condition and a termination condition for simplex method holds simultaneously.