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

Mohammad R. Oskoorouchi (moskoorocsusm.edu)
John E. Mitchell (mitchjrpi.edu)

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

Keywords: Second-order cone, semidefinite inequality, cutting plane techniques, eigenvalue optimization

Category 1: Convex and Nonsmooth Optimization

Category 2: Linear, Cone and Semidefinite Programming

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

Download: [Postscript]

Entry Submitted: 05/11/2005
Entry Accepted: 05/12/2005
Entry Last Modified: 05/11/2005

Modify/Update this entry