Analytic Center Cutting-Plane Method with Deep Cuts for Semidefinite Feasibility Problems |
| |
Authors: | S K Chua K C Toh G Y Zhao |
| |
Institution: | (1) Department of Mathematics, National University of Singapore, Singapore |
| |
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
{YS
m
: AY AY - } , where 0. If , 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. |
| |
Keywords: | Analytic centers cutting-plane methods semidefinite feasibility problems deep cuts |
本文献已被 SpringerLink 等数据库收录! |
|