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

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. In the implementation part, we apply the algorithm to the eigenvalue optimization problem by relaxing the semidefinite inequalities into multiple second-order cone inequalities. Computational results on randomly generated problems are reported.

Citation

College of Business Administration, California State University San Marcos San Marcos, CA 92096

Article

Download

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