COMPLEXITY ESTIMATES OF SOME CUTTING PLANE METHODS BASED ON THE ANALYTIC BARRIER

In this paper we establish the efficiency estimates for two cutting pl ane methods based on the analytic barrier, We prove that the rate of c onvergence of the second method is optimal uniformly in the number of variables, We present a modification of the second method. In this mod ified version each test point satisfies an approximate centering condi tion. We also use the standard strategy for updating approximate Hessi ans of the logarithmic barrier function. We prove that the rate of con vergence of the modified scheme remains optimal and demonstrate that t he number of Newton steps in the auxiliary minimization processes is b ounded by an absolute constant. We also show that the approximate Hess ian strategy significantly improves the total arithmetical complexity of the method.