Please use this identifier to cite or link to this item:
https://doi.org/10.1007/s10957-004-5150-4
Title: | Analytic center cutting-plane method with deep cuts for semidefinite feasibility problems | Authors: | Chua, S.K. Toh, K.C. Zhao, G.Y. |
Keywords: | Analytic centers cutting-plane methods deep cuts semidefinite feasibility problems |
Issue Date: | Nov-2004 | Citation: | Chua, S.K., Toh, K.C., Zhao, G.Y. (2004-11). Analytic center cutting-plane method with deep cuts for semidefinite feasibility problems. Journal of Optimization Theory and Applications 123 (2) : 291-318. ScholarBank@NUS Repository. https://doi.org/10.1007/s10957-004-5150-4 | Abstract: | An analytic center cutting-plane method with deep cuts for semidefinite feasibility problems is presented. Our objective in these problems is to find a point in a nonempty bounded convex set Γ in the cone of symmetric positive-semidefinite matrices. The cutting plane method achieves this by the following iterative scheme. At each iteration, a query point Ŷ that is an approximate analytic center of the current working set is chosen. We assume that there exists an oracle which either confirms that Ŷ ∈ Γ or returns a cut A ∈ S m such that {Y ∈ S m: A• Y ≤ A• Ŷ - ξ} ⊃Γ, where ξ ≥ 0. Ŷ ∉ Γ, an approximate analytic center of the new working set, defined by adding the new cut to the preceding working set, is then computed via a primal Newton procedure. Assuming that Γ contains a ball with radius ε > 0, the algorithm obtains eventually a point in Γ, with a worst-case complexity of O*(m 3/ε 2) on the total number of cuts generated. | Source Title: | Journal of Optimization Theory and Applications | URI: | http://scholarbank.nus.edu.sg/handle/10635/102860 | ISSN: | 00223239 | DOI: | 10.1007/s10957-004-5150-4 |
Appears in Collections: | Staff Publications |
Show full item record
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.