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

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

SCOPUSTM   
Citations

13
checked on Aug 21, 2018

WEB OF SCIENCETM
Citations

11
checked on Aug 21, 2018

Page view(s)

89
checked on Jun 30, 2018

Download(s)

15
checked on Jun 30, 2018

Google ScholarTM

Check

Altmetric


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