A Pivotting Procedure for a Class of Second-Order Cone Programming

Masakazu Muramatsu (muramatucs.uec.ac.jp)

Abstract: We propose a pivotting procedure for a class of Second-Order Cone Programming (SOCP) having one second-order cone. We introduce a dictionary, basic variables, nonbasic variables, and other necessary notions to define a pivot for the class of SOCP. In a pivot, two-dimensional SOCP subproblems are solved to decide which variables should be entering to or leaving from the basis. Under a nondegeneracy assumption, we prove that the objective function value is strictly decreasing by a pivot unless the current basic solution is optimal. We also propose an algorithm using the pivotting procedure which has global convergence property.

Keywords: Second-Order Cone Programming, Pivot, The Simplex Method, Quadratic Programming,

Category 1: Linear, Cone and Semidefinite Programming (Second-Order Cone Programming )

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: Technical Report CS-03-02, Dept. of Computer Science, The University of Electro-Communications 1-5-1 Chofugaoka, Chofu-shi, Tokyo 182-8585 JAPAN. September 2003.

Download: [Postscript][Compressed Postscript][PDF]

Entry Submitted: 09/22/2003
Entry Accepted: 09/22/2003
Entry Last Modified: 06/07/2004

Modify/Update this entry