ON SOME EFFICIENT INTERIOR POINT METHODS FOR NONLINEAR CONVEX-PROGRAMMING

We introduce two interior point algorithms for minimizing a convex function subject to linear constraints. Our algorithms require the solution of a nonlinear system of equations at each step. We show that if sufficiently good approximations to the solutions of the nonlinear systems can be found, then the primal-dual gap becomes less that epsilon in O(square-root n\ln epsilon\) steps, where n is the number of variables.