Multiple cuts in the analytic center cutting plane method

We analyze the multiple cut generation scheme in the analytic center cuttin g plane method. We propose an optimal primal and dual updating direction wh en the cuts are central. The direction is optimal in the sense that it maxi mizes the product of the new dual slacks and of the new primal variables wi thin the trust regions defined by Dikin's primal and dual ellipsoids. The n ew primal and dual directions use the variance-covariance matrix of the nor mals to the new cuts in the metric given by Dikin's ellipsoid. We prove that the recovery of a new analytic center from the optimal restor ation direction can be done in O(p log(p + 1)) damped Newton steps, where p is the number of new cuts added by the oracle, which may vary with the ite ration. The results and the proofs are independent of the specific scaling matrix primal, dual, or primal-dual that is used in the computations. The computation of the optimal direction uses Newtons method applied to a s elf-concordant function of p variables. The convergence result of [Ye, Math. Programming, 78 (1997), pp. 85-104] ho lds here also: the algorithm stops after O*((p) over bar(2)n(2)/epsilon(2)) cutting planes have been generated, where (p) over bar is the maximum numb er of cuts generated at any given iteration.