A Polynomial Barrier Algorithm for Linearly Constrained Convex Programming Problems

We consider the standard linearly constrained convex program min{f(x) ∣ x ∈ ℝⁿ, Ax = b, x ≥ 0} where f(x) satisfies a certain scaled Lipschitz condition. Using the classical logarithmic barrier method our algorithm obtains an ε-solution within O(√n|ln ε|) or O(n|ln ε|) total iterations depending on the updating of the barrier parameter.