Optimization Online


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

Masakazu Muramatsu (muramatu***at***cs.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

  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