A multiple-cut analytic center cutting plane method for semidefinite feasibility problems

Abstract

We consider the problem of finding a point in a nonempty bounded convex body F in the cone of symmetric positive semidefinite matrices S+ m. Assume that Γ is defined by a separating oracle, which, for any given m × m symmetric matrix Ŷ, either confirms that Ŷ ∈ Γ or returns several selected cuts, i.e., a number of symmetric matrices Ai, i = 1,...,p, p ≤ pmax, such that Γ is in the polyhedron {Y ∈ S+ m | Ai • Y ≤ Ai • Ŷ, i = 1, ⋯,p}. We present a multiple-cut analytic center cutting plane algorithm. Starting from a trivial initial point, the algorithm generates a sequence of positive definite matrices which are approximate analytic centers of a shrinking polytope in S+ m. The algorithm terminates with a point in F within O(m3pmax/ε2) Newton steps (to leading order), where e is the maximum radius of a ball contained in Γ.