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 | Size | Format | Access Settings | Version | |
---|---|---|---|---|---|---|
2002-multiple_cut_analytic_center_cutting-published.pdf | 230.7 kB | Adobe PDF | OPEN | Published | View/Download |
SCOPUSTM
Citations
15
checked on Jan 26, 2023
WEB OF SCIENCETM
Citations
13
checked on Jan 26, 2023
Page view(s)
540
checked on Jan 26, 2023
Download(s)
22
checked on Jan 26, 2023
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.