📂Optimization

Initialization and Auxiliary Problem in Simplex Method

Buildup

$$ \begin{matrix} \text{Maximize} & \mathbf{c}^{T} \mathbf{x} \\ \text{subject to} & A \mathbf{x} = \mathbf{b} \\ & \mathbf{x} \ge \mathbf{0} \end{matrix} $$

Let’s say the linear programming problem is represented in the equation form as above with respect to matrices $A \in \mathbb{R}^{m \times n}$, $\mathbf{b} \in \mathbb{R}^{m \times 1}$, and $\mathbf{c} \in \mathbb{R}^{n}$. And for all $j = 1 , \cdots , n+m$, $x_{k} \ge 0$ holds, and for $i = 1 , \cdots , m$, $$ \begin{align*} \zeta &=& & & \sum_{j=1}^{n} c_{j} x_{j} \\ x_{n+i} &=& b_{i} &-& \sum_{j=1}^{n} a_{ij} x_{j} \end{align*} $$

Let’s assume the first dictionary of the linear programming problem is given as above. The simplex method basically optimizes by changing the solutions of these given systems of equations. But if there are no solutions to change from the beginning, what should we do? ¹ At first glance, one might think that since optimization has to be done in any way, one could just start with any value, e.g., if we start with $x_{1} , \cdots , x_{n} = 0$, then $x_{n+i} = b_{i}$ occurs $$ \left( x_{1}, \cdots , x_{n} , x_{n+1} , \cdots , x_{n+m} \right) = \left( 0, \cdots , 0 , b_{1} , \cdots , b_{m} \right) $$ It seems like it certainly satisfies the constraints, but if immediately $b_{i} < 0$ happens, it violates $\mathbf{x} \ge \mathbf{0}$. Meanwhile, the simplex method, by exploring every vertex of the simplex, can definitely succeed in optimization, however, under this strategy, finding any feasible solution is as difficult as finding an optimal solution. ² Of course, this is when there are no measures, and naturally, mathematicians have prepared measures for this.

Glossary

Auxiliary Problem

In the initialization of the simplex method, the difficulty mentioned above is called infeasibility, and the dictionary that resolves infeasibility by introducing a new variable is simply called an auxiliary problem.

Phase

The process of creating an auxiliary problem and finding its first feasible solution is called Phase 1, and the process of applying the actual simplex method to optimize is called Phase 2.

Example

Let’s look at what an auxiliary problem is through a simple problem. Let’s assume the following linear programming problem is given for $x_{1} , x_{2} , x_{3} \ge 0$. $$ \begin{matrix} \text{Maximize} & & x_{1} & + & 2x_{2} \\ \text{subject to} & & x_{1} & + & 3x_{2} & + & x_{3} & = & 4 \\ & & & & 2x_{2} & + & x_{3} & = & 2 \end{matrix} $$

This problem shows that initialization does not go well by just choosing any vertex of the simplex. For example, consider the most basic point $\left( x_{1} , x_{2} , x_{3} \right) = (0,0,0)$, which does not satisfy the constraints. Of course, someone might quickly find $(1,1,0)$ intuitively, but keep in mind that this problem is a very simple problem made just for illustration. If something like $A \in \mathbb{R}^{100 \times 30}$ was given in a real problem, neither mental arithmetic nor intuition would be of any help.

The idea to solve this is simple. Just as slack variables were introduced to create the equation form of the inequality form linear programming problem, we introduce an auxiliary variable as a buffer. By introducing a new $x_{4} , x_{5} \ge 0$ as in $$ \begin{matrix} \text{Maximize} & & & & & & & - & x_{4} & - & x_{5} & \\ \text{subject to} & & x_{1} & + & 3x_{2} & + & x_{3} & + & x_{4} & & & = & 4 \\ & & x_{1} & & 2x_{2} & + & x_{3} & & & + & x_{5} & = & 2 \end{matrix} $$ we can very simply find the initial value $(0,0,0,4,2)$. We can start the simplex method from this point, and we have decided to call this up to Phase 1.