Conic simplex methods: Implementation and computational study.

摘要

It is only recently that simplex-like methods have been developed to solve secondorder cone programming ("SOCP") problems, though none entirely are able to mimic the actions of the simplex method on linear programs until now. In this thesis, primal and dual methods are described, with convergence proved for the primal case. A number of familiar concepts from linear programming are found to have analogs in the SOCP setting, including basic solutions, anti-degeneracy techniques, "Big M" and Two-Phase start methods, as well as Dantzig and Steepest Edge pivot rules. It is shown how the Steepest Edge pivot rule for the primal simplex-like method can be applied via a safeguarded Newton's Method similar to that found in trust-region methods. A method for approximating SOCP problems by linear programs is developed, upon which the behavior of linear program solvers is compared to the simplex-like methods applied directly to the underlying SOCP. A flexible suite of test problems is created to complement existing SOCP problem libraries. An extensive implementation is described and numerical results exploring various aspects of the simplex-like methods are presented.