Optimization Online


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

Mohammad R. Oskoorouchi (moskooro***at***csusm.edu)
John E. Mitchell (mitchj***at***rpi.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society