Groupe d’études et de recherche en analyse des décisions

G-2003-26

An Interior Point Cutting Plane Method for Convex Feasibility Problem with Second-Order Cone Inequalities

et

Convex feasibility problem in general is a problem of finding a point in a convex set 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 one Newton step, and that the ACCPM with SOCC is a fully polynomial approximation scheme.

, 31 pages