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, volume 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.