Linear programming explanation in Algorithms by Sanjoy Dasgupta

Question

I am reading about simplex algorithms in a textbook titled Algorithms by Dasgupta-Papadimitriou-Vairani.

On each iteration, simplex has two tasks:

1. Check whether the current vertex is optimal (and if so, halt).

2. Determine where to move next.

As we will see, both tasks are easy if the vertex happens to be at the origin. And if the vertex is elsewhere, we will transform the coordinate system to move it to the origin!

First let's see why the origin is so convenient. Suppose we have some generic LP \begin{align}\max&\quad c^\top x\\\text{s.t.}&\quad Ax\le b\\&\quad x\ge0\end{align} where $x$ is the vector of variables, $x = \begin{pmatrix}x_1&\cdots&x_n\end{pmatrix}$. Suppose the origin is feasible. Then it is certainly a vertex, since it is the unique point at which the $n$ inequalities $\{x_1\ge0,\cdots,x_n\ge0\}$ are tight.

Now let's solve our two tasks. For task 1, the origin is optimal if and only if all $c_i\le0$. If all $c_i\le0$, then considering the constraints $x\ge0$, we can't hope for a better objective value. Conversely, if some $c_i > 0$, then the origin is not optimal, since we can increase the objective function by raising $x_i$.

Thus, for task 2, we can move by increasing some $x_i$ for which $c_i > 0$. How much can we increase it? Until we hit some other constraint. That is, we release the tight constraint $x_i\ge0$ and increase $x_i$ until some other inequality, previously loose, now becomes tight.

At that point, we again have exactly $n$ tight inequalities, so we are at a new vertex.

For instance, suppose we're dealing with the following linear program. \begin{alignat}2\max&\quad2x_1+5x_2\\\text{s.t.}&\quad2x_1-x_2\le4\tag1\\&\quad x_1+2x_2\le9\tag2\\&\quad-x_1+x_2\le3\tag3\\&\quad x_1\ge0\tag4\\&\quad x_2\ge0\tag5.\end{alignat} The simplex can be started at the origin, which is specified by constraints $4$ and $5$ . To move, we release the tight constraint $x_2\ge0$. As $x_2$ is gradually increased, the first constraint it runs into is $-x_1 + x_2\le3$, and thus it has to stop at $x_2 = 3$, at which point this new inequality is tight. The new vertex is thus given by $(3)$ and $(4)$.

So we know what to do if we are at the origin. But what if our current vertex $u$ is elsewhere? The trick is to transform $u$ into the origin, by shifting the coordinate system from the usual $(x_1,\cdots,x_n)$ to the local view from $u$. These local coordinates consist of (appropriately scaled) distances $y_1,\cdots,y_n$ to the $n$ hyperplanes (inequalities) that define and enclose $u$:

Specifically, if one of these enclosing inequalities is $a_i\cdot x\le b_i$, then the distance from a point $x$ to that particular "wall" is $y_i = b_i - a_i \cdot x$. The $n$ equations of this type, one per wall, define the $y_i$'s as linear functions of the $x_i$'s, and this relationship can be inverted to express the $x_i$'s as a linear function of the $y_i$'s. Thus we can rewrite the entire LP in terms of the $y$'s. This doesn't fundamentally change it (for instance, the optimal value stays the same), but expresses it in a different coordinate frame. The revised local LP has the following three properties:

1. It includes the inequalities $y\ge0$, which are simply the transformed versions of the inequalities defining $u$.

2. $u$ itself is the origin in the $y$-space.

3. The cost function becomes $\max c_u + c'^\top\cdot y$, where $c_u$ is the value of the objective function at $u$ and $c'$ is a transformed cost vector.

I am having difficulty in understanding trick in above statement mentioned below:

The trick is to transform $u$ into the origin, by shifting the coordinate system from the usual $(x_1,\cdots,x_n)$ to the local view from $u$. These local coordinates consist of (appropriately scaled) distances $y_1,\cdots,y_n$ to the $n$ hyperplanes (inequalities) that define and enclose $u$.

What does the author mean by shifting the coordinate system to the local view from $u$ in the above statement?

What does "local coordinates consist of distances to the $n$ hyperplanes" mean?

Answer 1

For the original problem, we examine the origin, if it is optimal, we halt. Suppose not, from the origin, we know what to do.

Now, suppose we are at vertex $u$, the passage discuss a procedure to make $u$ to be the origin of the new coordinate system, we denote it using $y$ rather than $x$.

The trick is look at those active constraints at $u$, we can use them to define an affine transformation of the coordinate system to a new coordinate system by defining $y_j = b_j-a_j^\top x$. Since the constraints are active at $u$, $b_j-a_j^\top u=0$ in the new coordinate system, the new coordinate at location $u$ corresponds to the new origin since $y_j=b_j-a_j^\top u=0$.

Also, previously, all the feasible points would satisfies $b_j-a_j^\top x \ge 0$, hence in the new coordinate system, $y_j=b_j-a_j^\top x \ge 0$.

As an example, consider the example that you provided:

\begin{alignat}2\max&\quad2x_1+5x_2\\\text{s.t.}&\quad2x_1-x_2\le4\tag1\\&\quad x_1+2x_2\le9\tag2\\&\quad-x_1+x_2\le3\tag3\\&\quad x_1\ge0\tag4\\&\quad x_2\ge0\tag5.\end{alignat}

Now in the first move, we have reached $(0,3)$, we want to convert this vertex to the origin of the new coordinate system. Constraint $(4)$ [Define $y_1=x_1$] are active. Constraint $(3)$ is active too [Define $y_2=3+x_1-x_2$].

We can express $x$ in terms of $y$: $x_1=y_1$ and $x_2=3+y_1-y_2$.

Let's compute the new objective function:

\begin{alignat}2\max&\quad2x_1+5x_2=2y_1+5(3+y_1-y_2)=15+7y_1-5y_2\\\text{s.t.}&\quad2y_1-(3+y_1-y_2) \le 4\tag{6}\\&\quad y_1+2(3+y_1-y_2) \le 9 \tag{7}\\&\quad-y_1+(3+y_1-y_2) \le 3 \tag{8}\\&\quad y_1 \ge 0 \tag{9}\\&\quad 3+y_1-y_2 \ge 0 \tag{10}.\end{alignat}

Now, using the new coordinate system, we are at the origin of the new system in the format that you are familiar with and the procedure can be repeated.

Remark:

• Usually, simplex algorithm is implemented using a tableau.

• Rather than distance, I prefer calling it slack as in slack variable. Strictly speaking $2x\le 6$ and $x\le 3$ are both equivalence inequalities $6-2x$ and $3-x$ gives different values though. When the slack is $0$, the constraint is active, when the slack is negative, the constraint is violated.