0
$\begingroup$

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.

$\endgroup$

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.