I am reading simplex algorithm in text book 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
max c transpose * x Ax <= b x >= 0
where x is the vector of variables, x = (x1; : : : ; xn). Suppose the origin is feasible. Then it is certainly a vertex, since it is the unique point at which the n inequalities {x1>=0, ..., xn>=0 } are tight.
Now let's solve our two tasks. Task 1:
The origin is optimal if and only if all ci <= 0
If all ci <= 0, then considering the constraints x>=0, we can't hope for a better objective value. Conversely, if some ci > 0, then the origin is not optimal, since we can increase the objective function by raising xi.
Thus, for task 2, we can move by increasing some xi for which ci > 0. How much can we increase it? Until we hit some other constraint. That is, we release the tight constraint xi >= 0 and increase xi 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.
> max 2x1 + 5x2 2x1 - x2 <= 4 ----> Eq 1
x1 + 2x2 <= 9 ----> Eq 2
> -x1 + x2 <= 3 -----> Eq 3
x1 >= 0 -----------> Eq 4
x2 >= 0 -----------> Eq 5
Simplex can be started at the origin, which is specied by constraints 4 and 5 . To move, we release the tight constraint x2 >= 0. As x2 is gradually increased, the first constraint it runs into is -x1 + x2 <= 3, and thus it has to stop at x2 = 3, at which point this new inequality is tight. The new vertex is thus given by Eq 3 and Eq 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 (x1, ..., xn) to the local view from u. These local coordinates consist of (appropriately scaled) distances y1, ..., yn to the n hyperplanes (inequalities) that define and enclose u:
u / \ / \ / /\ / /y1\ /----x \ y2Specifically, if one of these enclosing inequalities is ai * x <= bi, then the distance from a point x to that particular "wall" is yi = bi - ai * x
The n equations of this type, one per wall, define the yi's as linear functions of the xi's, and this relationship can be inverted to express the xi's as a linear function of the yi'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:
The revised local LP has the following three properties: 1. It includes the inequalities y >= 0, which are simply the transformed versions of the inequalities defining u. 2. u itself is the origin in y-space. 3. The cost function becomes max cu + ~cT * y, where cu 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 (x1, ..., xn) to the local view from u. These local coordinates consist of (appropriately scaled) distances y1, ..., yn to the n hyperplanes (inequalities) that define and enclose u:
What does author mean by shifting coordinate system to local view from "u" in above statement?
What does local coordinates consist of distances to the n hyper planes mean?
Kindly explain
Thanks in advance for your time and help
This is a geometric interpretation of multiplying with the inverse of the basis matrix.