= Karmarkar standard form
{c}
{title2=$\min c^Ty,\quad Ay=0,\quad\mathbf1^Ty=1,\quad y\ge0$}
This form of <linear programming> additionally has the uniform <vector> as a strictly positive <feasible point> and known optimum zero. A <homogeneous self-dual embedding of a linear program>, followed by elimination of unrestricted <Lagrange multipliers> and normalization by the sum of nonnegative coordinates, yields this form without presupposing feasibility of the original program. The known start and optimum support projective <interior-point methods>. Polynomial bit-complexity statements additionally require finite rational input encoding; bounded arbitrary real coefficients alone do not provide it.
Back to article page
