An interior point cutting plane method for the convex feasibility problem with second-order cone inequalities

• 成果类型: Article
• 署名作者: Oskoorouchi, MR; Goffin, JL
• 署名单位: California State University System; California State University San Marcos; McGill University; Universite de Montreal
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1040.0116
• 发表日期: 2005
• 页码: 127-149
• 关键词: quadratic cut method; complexity analysis; multiple cuts; algorithm; optimization

摘要

The convex feasibility problem in general is a problem of finding a point in a convex set that contains a full dimensional ball and is contained in a compact convex set. We assume that the outer set is described by second-order cone inequalities and propose an analytic center cutting plane technique to solve this problem. We discuss primal and dual settings simultaneously. Two complexity results are reported: the complexity of restoration procedure and complexity of the overall algorithm. We prove that an approximate analytic center is updated after adding a second-order cone cut (SOCC) in O(1) Newton step, and that the analytic center cutting plane method (ACCPM) with SOCC is a fully polynomial algorithm.