Karmarkar algorithm

From Glossary

Jump to: navigation, search

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
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.

Personal tools