I am working through Karmarkar's seminal paper [0] and came across something I didn't quite understand. In section 2.3, Description of the Algorithm, he explains how to calculate the next point. The point $\mathbf{x^{(k)}} \in \mathbb{R}^n$ that is put into $\phi$ has to be a feasible point, i.e., A$\mathbf{x}^{(k)}=0$. The matrix $D$ is a diagonal matrix with the $\mathbf{x_i}^{(k)}$ on the diagonal. Now,

\begin{align*}AD=\begin{pmatrix}A_1 \mathbf{x}_1^{(k)}\dots A_n \mathbf{x}_n^{(k)} \end{pmatrix}\end{align*}

where $A_i$ is the $i$th column of $A$. We know that the sum of these components is $0$.

The matrix $B$ is the matrix $AD$ with a row of $1$'s at the bottom. Now, in the algorithm it says that

$$\mbox{Ker} B \subseteq \Sigma = \left\{ \mathbf{x} \mid \sum_i x_i=1 \right\}$$

But $\mbox{Ker} B = \vec{0}$, because the last row of $B$ consists of ones. Am I not seeing something here?

[0] Narendra Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, Volume 4, Issue 4, December 1984.


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.