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

The convergence and complexity of a primal–dual column generation and cutting plane algorithm from approximate analytic centers for solving convex feasibility problems defined by a deep cut separation oracle is studied. The primal–dual-infeasible Newton method is used to generate a primal–dual updating direction. The number of recentering steps is O(1) for cuts as deep as halfway to the deepest cut, where the deepest cut is tangent to the primal–dual variant of Dikin's ellipsoid.