An analytic center cutting plane approach for conic programming

• 成果类型: Article
• 署名作者: Basescu, Vasile L.; Mitchell, John E.
• 署名单位: Rensselaer Polytechnic Institute
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1080.0319
• 发表日期: 2008
• 页码: 529-551
• 关键词: semidefinite feasibility problems; interior-point algorithms; quadratic cut method; Barrier functions; symmetric cones; jordan algebras; multiple cuts; optimization

摘要

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), semide finite 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.