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

# The Analytic Center Cutting Plane Method with Semidefinite Cuts

## Mohammad R. Oskoorouchi et Jean-Louis Goffin

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