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

Mohammad R. Oskoorouchi (moskoorocsusm.edu)
Jean-Louis Goffin (Jean-Louis.GoffinMcGill.CA)

Abstract: 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.

Keywords: Analytic center, cutting plane algorithm, second-order cone, nondifferentiable optimization

Category 1: Convex and Nonsmooth Optimization

Citation: GERAD, Technical report, April 2003 http://public.csusm.edu/oskoorouchi/

Download: [Postscript]

Entry Submitted: 04/19/2003
Entry Accepted: 04/21/2003
Entry Last Modified: 04/19/2003

Modify/Update this entry