This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Oskoorouchi, M. R. Articles by Goffin, J.-L. Search for Related Content

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

College of Business Administration, California State University, San Marcos, San Marcos, California 92096-0001, USA
GERAD/Faculty of Management, McGill University, 1001 Sherbrooke West, Montreal, QC, H3A 1G5, Canada
moskooro{at}csusm.edu
jlg{at}crt.umontreal.ca

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.

Key Words: cutting plane algorithm; nondifferentiable optimization; analytic center; second-order cone
History: Received: April 22, 2003; revision received: May 11, 2004;

This article has been cited by other articles:

				V. L. Basescu and J. E. Mitchell An Analytic Center Cutting Plane Approach for Conic Programming Mathematics of Operations Research, August 1, 2008; 33(3): 529 - 551. [Abstract] [PDF]