 # Karmarkar algorithm

An interior point method for linear programming, which began a series of variations (e.g., see affine scaling). The original algorithm applies to the system $LaTeX: Ax=0$, for $LaTeX: x \in S_n$, i.e. x is an element of the n-dim. simplex, and assumes $LaTeX: Ae=0$ (so $LaTeX: e/n$ is a feasible solution). It further assumes the optimal objective value is known to be zero. (All of these assumptions have been relaxed in subsequent developments.)

Here are the basic steps of Karmarkar's (original) algorithm, given $LaTeX: x > 0$, $LaTeX: e^T x=1$ and $LaTeX: Ax=0$.

1. Form $LaTeX: D = \mbox{diag}(x_j)$ and $LaTeX: B = \begin{bmatrix} AD \\ e \end{bmatrix}$
(assume $LaTeX: \mbox{rank}(B)=m+1$).
2. Project: Project $LaTeX: Dc$ to null space of $LaTeX: B$: $LaTeX: c* = [I-B^T(BB^T)^{-1}B]Dc.$
3. Normalize Normalize the ascent direction: $LaTeX: d = c* /(\|c*\| \sqrt{n(n-1)}.$ If c*=0, terminate since the solution is optimal.)
4. Move Move in projected space to $LaTeX: y = e/n - sd$, where $LaTeX: s$ is a fixed step size (= 1/4).
5. Project Project back into x-space: $LaTeX: x = Dy /(e^TDy)$.
The time complexity is $LaTeX: O(n^{3.5}L^2 \ln(L)\ln(\ln(L))),$ where $LaTeX: L$ is a measure of data storage for a given precision. The solution obtained is in the relative interior of the set of optimal solutions.