Complexity estimates of some cutting plane methods based on the analytic barrier

This paper establishes the efficiency estimates for two cutting plane methods based on the analytic barrier. It proves that the rate of convergence of the second method is optimal uniformly in the number of variables. The paper presents a modification of the second method. In this modified version each test point satisfies an approximate centering condition. It also uses the standard strategy for updating approximate Hessians of the logarithmic barrier function. The paper proves that the rate of convergence of the modified scheme remains optimal and demonstrate that the number of Newton steps in the auxiliary minimization processes is bounded by an absolute constant. It also shows that the approximate Hessian strategy significantly improves the total arithmetical complexity of the method.