Please use this identifier to cite or link to this item:
Title: An analytic center cutting plane method for semidefinite feasibility problems
Authors: Sun, J. 
Toh, K.-C. 
Zhao, G. 
Keywords: Analytic center
Cutting plane methods
Semidefinite programming
Issue Date: 2002
Source: Sun, J.,Toh, K.-C.,Zhao, G. (2002). An analytic center cutting plane method for semidefinite feasibility problems. Mathematics of Operations Research 27 (2) : 332-346. ScholarBank@NUS Repository.
Abstract: 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 Γ in the cone of symmetric positive semidefinite matrices. Assume that Γ is defined by an oracle, which for any given m × m symmetric positive semidefinite matrix Ŷ either confirms that Ŷ ε Γ or returns a cut, i.e., a symmetric matrix A such that Γ is in the half-space {Y : A · Y ≤ A · Ŷ}. 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* (m3/ε2) on the total number of cuts to be used, where ε is the maximum radius of a ball contained by Γ.
Source Title: Mathematics of Operations Research
ISSN: 0364765X
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

checked on Dec 8, 2017

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.