This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Basescu, V. L. Articles by Mitchell, J. E. Search for Related Content

An Analytic Center Cutting Plane Approach for Conic Programming

Campbell Company, Towson, Maryland 21204
Department of Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, New York 12180
basesv{at}verizon.net
mitchj{at}rpi.edu, http://www.rpi.edu/mitchj

We analyze the problem of finding a point strictly interior to a bounded, convex, and fully dimensional set from a finite dimensional Hilbert space. We generalize the results obtained for the linear programming (LP), semidefinite programming (SDP), and second-order core programming (SOCP) cases. The cuts added by our algorithm are central and conic. In our analysis, we find an upper bound for the number of Newton steps required to compute an approximate analytic center. Also, we provide an upper bound for the total number of cuts added to solve the problem. This bound depends on the quality of the cuts, the dimensionality of the problem and the thickness of the set we are considering.

Key Words: cutting plane; cutting surface; analytic center; conic programming; feasibility problem
History: Received: June 22, 2005; revision received: June 26, 2007;