zbMATH — the first resource for mathematics

An analytic center cutting plane method for semidefinite feasibility problems. (English) Zbl 1082.90555
Summary: 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 \times m$$ symmetric positive semidefinite matrix $$\widehat Y$$ either confirms that $$\widehat Y \in \Gamma$$ or returns a cut, i.e., a symmetric matrix $$A$$ such that $$\Gamma$$ is in the half-space $$\{Y : A \cdot Y \leq A \cdot \widehat Y\}$$. 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^*(m^3 /\varepsilon^2 )$$ on the total number of cuts to be used, where $$\varepsilon$$ is the maximum radius of a ball contained by $$\Gamma$$.

MSC:
 90C22 Semidefinite programming
Full Text: