1
$\begingroup$

In Section 7.6.2 of the textbook "Algorithms" by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani, the authors provide a geometric interpretation of the two main tasks of each iteration of the simplex algorithm for linear programming:

  1. Check whether the current vertex is optimal;
  2. Determine where to move next. In particular, it says

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!

Later, it explains how to transform a vertex $\vec{u}$ into the origin, by shifting the coordinate system from the usual $(x_1, \cdots, x_n)$ to the "local view" from $\vec{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 closing inequalities is $\vec{a_i} \cdot \vec{x} \le b_i$, then the distance from a point $\vec{x}$ to that particular "wall" is $$y_i = b_i - \vec{a_i} \cdot \vec{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 linear functions of the $y_i's$.


I am able to understand the linear algebra computation (e.g., row operations) behind this coordination system transformation. However, it does not quite fit what I learn in undergraduate linear algebra textbooks about basis change.

In particular, in my knowledge, a basis is given as a set of vectors and the coordinates of a vertex under a basis $\mathcal{B}$ are the coefficients of the linear combination representation of the vectors in $\mathcal{B}$. However, the description above considers hyperplanes and the distances from a point $\vec{x}$ to them. What is the theory behind this kind of coordinate systems and its transformation?

$\endgroup$
  • $\begingroup$ Can you help me understand what you mean by "the theory behind this kind of coordinate systems and its transformation"? What kind of answer are you expecting? Are you familiar with linear transformations? With change of basis? With how you can represent a hyperplane with a linear equation? $\endgroup$ – D.W. Feb 17 at 21:01
  • $\begingroup$ @D.W. Yes, I know linear transformation, change of basis, and representation of a hyperplane with a linear equation. But I am not able to relate the description of coordinate system transformation in terms of hyperplanes and distances here to the change of basis in terms of vectors and linear combinations which I know about. Maybe it is obvious, but I think I need some clarification. Thanks. $\endgroup$ – hengxin Feb 18 at 2:08
  • 1
    $\begingroup$ These are affine transformations, not linear transformations. $\endgroup$ – Yuval Filmus Feb 18 at 4:08
  • $\begingroup$ @YuvalFilmus Thanks. Could you please write your comment as an answer with more details? $\endgroup$ – hengxin Feb 23 at 13:30
  • $\begingroup$ An affine transformation is one of the form $x \mapsto Ax+b$. Wikipedia has an article about these. Beyond that, you'll have to work it out. $\endgroup$ – Yuval Filmus Feb 23 at 17:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.