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 |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.