Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2011-015 (September 23, 2011)

Simplex type algorithm for second-order cone programs via semi-infinite programming reformulation
by Yoshihiko Ito and Shunsuke Hayashi

pdf File

The (linear) second-order cone program (SOCP) is to minimize a linear function over the intersection between a polyhedral set and an affine transformation of Cartesian product of second-order cones. For solving such a problem, the primal-dual interior-point method has been studied extensively so far and said to be the most efficient method by many researchers. On the other hand, the simplex type method for SOCP is much less spotlighted, while it still keeps an important position for linear programming (LP) problems. Actually, some researchers have tried to apply such a method to the SOCPs. However, in those existing studies, the proposed algorithms were not implemented practically, or could be applied only to some restricted class of problems. In this paper, we apply the dual-simplex primal-exchange (DSPE) method, which was originally developed for solving linear semi-infinite programs (LSIP), to the SOCP by reformulating the second-order cone constraint as an infinite number of linear inequality constraints. Especially, by means of some numerical experiments, we observe that such a simplex type method can be more efficient than the existing interior-point based method, when we solve multiple SOCPs having similar data structures successively applying the so-called hot start technique.