An analytic center cutting plane method for semidefinite feasibility problems

An analytic center cutting plane method for semidefinite feasibility problems

0.00 Avg rating0 Votes
Article ID: iaor2004391
Country: United States
Volume: 27
Issue: 2
Start Page Number: 332
End Page Number: 346
Publication Date: May 2002
Journal: Mathematics of Operations Research
Authors: , ,
Keywords: semidefinite programming, cutting plane algorithms
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 Γ.

Reviews

Required fields are marked *. Your email address will not be published.