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

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

0.00 Avg rating0 Votes
Article ID: iaor20061396
Country: United States
Volume: 30
Issue: 1
Start Page Number: 127
End Page Number: 149
Publication Date: Feb 2005
Journal: Mathematics of Operations Research
Authors: ,
Abstract:

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 the analytic center cutting plane method with SOCC is a fully polynomial algorithm.

Reviews

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