Groupe d’études et de recherche en analyse des décisions

G-2000-32

The Analytic Center Cutting Plane Method with Semidefinite Cuts

et

We analyze an analytic center cutting plane algorithm for the convex feasibility problems with semidefinite cuts. At each iteration the oracle returns a p-dimensional semidefinite cut at an approximate analytic center of the set of localization. The set of localization, which contains the solution set, is a compact set consists of piecewise algebraic surfaces. We prove that the analytic center is recovered after adding a p-dimensional cut in O(p log (p+1)) damped Newton's iteration. We also prove that the algorithm stops when the dimension of the accumulated block diagonal matrix cut reaches to the bound of O*(p2m3 / 2), where p is the maximum dimension cut and is radius of the largest ball contained in the solution set.

, 25 pages