A second-order cone cutting surface method: complexity and application

Download the paper, pdf

Authors:

M. Oskoorouchi
College of Business Administration
Cal State San Marcos
Troy, NY 12180 USA
moskooro@csusm.edu

J. E. Mitchell
Department of Mathematical Sciences
Rensselaer Polytechnic Institute
Troy, NY 12180 USA
mitchj@rpi.edu

Citation details:

Computational Optimization and Applications 43(3), pages 379-409, 2009.

Abstract:

We present an analytic center cutting surface algorithm that uses mixed linear and multiple second-order cone cuts. Theoretical issues and applications of this technique are discussed. From the theoretical viewpoint, we derive two complexity results. We show that an approximate analytic center can be recovered after simultaneously adding $p$ second-order cone cuts in $O(p\log(p+1))$ Newton steps, and that the overall algorithm is polynomial. From the application viewpoint, we implement our algorithm on mixed linear-quadratic-semidefinite programming problems with bounded feasible region and report some computational results on randomly generated fully dense problems. We compare our cpu time with that of SDPLR, SDPT3, and SeDuMi and show that our algorithm outperforms these software packages on fully dense problems. We also show the performance of our algorithm on semidefinite relaxation of the maxcut and Lovasz theta problems.

Download the paper, pdf

Optimization Online link.

Return to my list of papers.