An Analytic Center Cutting Plane Method
For Semidefinite Feasibility Problems
Jie Sun, Kim-Chuan Toh, and Gongyun Zhao
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 matrix $\hat{Y}$, either confirms
that $\hat Y \in \Gamma$ or returns a cut, i.e.,
a symmetric matrix $A$ such that $\Gamma$ is in the
half-space
$ \{ Y \mid A \bullet Y \le A \bullet \hat{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 of the problem. All iterates
generated by the algorithm are positive definite
matrices due to log-determinant barrier terms
in the potential function. The algorithm has a worst
case complexity of $O^*(m^3/{\epsilon}^2)$
on the total number of cuts to be used, where
$\epsilon$ is the maximum radius of a ball
contained by $\Gamma$.
Research Report No 766, Department of Mathematics,
National University of Singapore, January 2000
Contact: [email protected]
![[DVI]](../gif/DVI.gif)
![[PS]](../gif/PS.gif)
![[IP PAGE]](../gif/HOME.gif)
![[SEARCH AGAIN]](../gif/SEARCH.gif)