An analytic center cutting plane approach for conic programming

Vasile L. Basescu (vbasescucomcast.net)
John E. Mitchell (mitchjrpi.edu)

Abstract: We analyze the problem of finding a point strictly interior to a bounded, fully dimensional set from a finite dimensional Hilbert space. We generalize the results obtained for the LP, SDP and 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.

Keywords: cutting plane, cutting surface, analytic center, conic programming, feasibility problem

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: June 2005. Department of Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, NY 12180 USA. http://www.rpi.edu/~mitchj/papers/coniccuts.html

Download: [PDF]

Entry Submitted: 06/22/2005
Entry Accepted: 06/22/2005
Entry Last Modified: 06/22/2005

Modify/Update this entry