A second-order cone cutting surface method: complexity and application |
| |
Authors: | Mohammad R Oskoorouchi John E Mitchell |
| |
Institution: | (1) College of Business Administration, California State University San Marcos, San Marcos, CA 92096, USA;(2) Department of Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, NY 12180, USA |
| |
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(plog (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 problems with fully dense coefficient matrices. We also show the performance
of our algorithm on semidefinite relaxations of the maxcut and Lovasz theta problems.
M.R. Oskoorouchi’s work has been completed with the support of the partial research grant from the College of Business Administration,
California State University San Marcos, and the University Professional Development Grant.
J.E. Mitchell’s material is based upon work supported by the National Science Foundation under Grant No. 0317323. Any opinions,
findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily
reflect the views of the National Science Foundation. |
| |
Keywords: | Second-order cone Semidefinite inequality Cutting plane techniques Semidefinite programming |
本文献已被 SpringerLink 等数据库收录! |
|