On the implementation of SDPT3 (version 3.1) - A MATLAB software package for semidefinite-quadratic-linear programming

Abstract

This code is designed to solve conic programming problems whose constraint cone is a product of semidefinite cones, second-order cones, nonnegative orthants and Euclidean spaces. It employs a primaldual predictor-corrector path-following method, with either the HKM or the NT search direction. The basic code is written in MATLAB, but key subroutines in Fortran and C are incorporated via a Mex interface. Routines are provided to read in problems in either SDPA or SeDuMi format. Sparsity and block diagonal structure are exploited, but the latter needs to be given explicitly or detected via a subroutine that is provided. Various techniques to improve the efficiency and stablility of the algorithm are incorporated. For example, step-lengths associated with semidefinite cones are calculated via the Lanczos method. Numerical experiments show that this general purpose code can solve 80% of a total of about 300 problems to an accuracy of at least 10 -6 in relative duality gap and infeasibilities. © 2004 IEEE.