# Karmarkar algorithm

### From Glossary

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 , for , i.e. x is an element of the n-dim. simplex, and assumes (so 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 , and .

- Form and
*Project:*Project to null space of :*Normalize*Normalize the ascent direction: If c*=0, terminate since the solution is optimal.)*Move*Move in projected space to , where is a fixed step size (= 1/4).*Project*Project back into x-space: .