Please use this identifier to cite or link to this item: https://doi.org/10.1137/S1052623400370503
Title: A multiple-cut analytic center cutting plane method for semidefinite feasibility problems
Authors: Toh, K.-C. 
Zhao, G. 
Sun, J. 
Keywords: Analytic center
Cutting plane methods
Multiple cuts
Semidefinite programming
Issue Date: 2002
Citation: Toh, K.-C., Zhao, G., Sun, J. (2002). A multiple-cut analytic center cutting plane method for semidefinite feasibility problems. SIAM Journal on Optimization 12 (4) : 1126-1146. ScholarBank@NUS Repository. https://doi.org/10.1137/S1052623400370503
Abstract: We consider the problem of finding a point in a nonempty bounded convex body F in the cone of symmetric positive semidefinite matrices S+ m. Assume that Γ is defined by a separating oracle, which, for any given m × m symmetric matrix Ŷ, either confirms that Ŷ ∈ Γ or returns several selected cuts, i.e., a number of symmetric matrices Ai, i = 1,...,p, p ≤ pmax, such that Γ is in the polyhedron {Y ∈ S+ m | Ai • Y ≤ Ai • Ŷ, i = 1, ⋯,p}. We present a multiple-cut analytic center cutting plane algorithm. Starting from a trivial initial point, the algorithm generates a sequence of positive definite matrices which are approximate analytic centers of a shrinking polytope in S+ m. The algorithm terminates with a point in F within O(m3pmax/ε2) Newton steps (to leading order), where e is the maximum radius of a ball contained in Γ.
Source Title: SIAM Journal on Optimization
URI: http://scholarbank.nus.edu.sg/handle/10635/44200
ISSN: 10526234
DOI: 10.1137/S1052623400370503
Appears in Collections:Staff Publications
Elements

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
2002-multiple_cut_analytic_center_cutting-published.pdf230.7 kBAdobe PDF

OPEN

PublishedView/Download

Google ScholarTM

Check

Altmetric


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