An analytic center cutting plane approach for conic programming
Download the paper,
in pdf.
Authors:
Vasile L. Basescu
vbasescu at comcast.net
John E. Mitchell
Department of Mathematical Sciences
Rensselaer Polytechnic Institute
Troy, NY 12180 USA
mitchj@rpi.edu
June 22, 2005.
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
Accepted for publication in
Mathematics of Operations Research.
Download the paper,
in pdf.
Also of interest:
Basescu's thesis
Optimization Online listing
Return to my list of papers.