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.

Google ScholarTM

Check

Altmetric


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