Primal-dual-infeasible Newton approach for the analytic center deep-cutting plane method

The convergence and complexity of a primal-dual column generation and cutti ng plane algorithm from approximate analytic centers for solving convex fea sibility problems defined by a deep cut separation oracle is studied. The p rimal-dual-infeasible Newton method is used to generate a primal-dual updat ing direction. The number of recentering steps is O(1) for cuts as deep as half way to the deepest cut, where the deepest cut is tangent to the primal -dual variant of Dikin's ellipsoid.