document: An analytic center cutting plane method for semidefinite feasibility problems Semidefinite feasibility problems arise in many areas of operations research . The abstract form of these problems can be described as finding a point in a nonempty bounded convex body Gamma in the cone of symmetric positive semidefinite matrices . Assume that Gamma is defined by an oracle , which for any given m * m symmetric positive semidefinite matrix Gamma either confirms that Y epsilon Gamma or returns a cut , i.e. , a symmetric matrix A such that Gamma is in the half-space -LCB- Y : A . Y < or = A . Y -RCB- . We study an analytic center cutting plane algorithm for this problem . At each iteration , the algorithm computes an approximate analytic center of a working set defined by the cutting plane system generated in the previous iterations . If this approximate analytic center is a solution , then the algorithm terminates ; otherwise the new cutting plane returned by the oracle is added into the system . As the number of iterations increases , the working set shrinks and the algorithm eventually finds a solution to the problem . All iterates generated by the algorithm are positive definite matrices . The algorithm has a worst-case complexity of O * -LRB- m/sup 3 / / epsilon / sup 2 / -RRB- on the total number of cuts to be used , where epsilon is the maximum radius of a ball contained by Gamma
doc_bio_tags: O B I I I I O B I I B I I O O O O O B I O O O O O O O O O O O O O O O O B I I I O O O O O B I I I O O O O O O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B O O O O O B I I O O B I O O O O O O O O O O O O O O B I I O O O O O O O O O O O O O O O O O B O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O
extractive_keyphrases: semidefinite feasibility problems analytic center cutting plane method operations research nonempty bounded convex body symmetric positive semidefinite matrices oracle iteration approximate analytic center working set
abstractive_keyphrases: worst-case complexity maximum ball radius