An Analytic Center Cutting Plane Approach for Conic Programming

An Analytic Center Cutting Plane Approach for Conic Programming

0.00 Avg rating0 Votes
Article ID: iaor200954173
Country: United States
Volume: 33
Issue: 3
Start Page Number: 529
End Page Number: 551
Publication Date: Aug 2008
Journal: Mathematics of Operations Research
Authors: ,
Keywords: programming: convex, programming: linear
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.