Institute for Reliable Computing
Priv.-Doz. Dr. Christian Jansson
VSDP (Verified Semidefinte Programming) is a software package for computing verified error bounds in semidefinite programming. In particular, this package provides rigorous lower and upper bounds of the true optimal value, as well as verified certificates of infeasibility. All numerical errors are taken into consideration. It can be used to obtain rigorous error bounds in various areas of optimization, including general convex problems, combinatorial optimization, and global optimization.
There are two versions of VSDP. Detailed instructions on how to install VSDP are given in the corresponding User's Guide.
The VSDP source files and the User's Guide of the older version can be downloaded from:
The code is written in MATLAB and INTLAB, and is rather easy to understand. In particular, this code can be explained in lectures. Nevertheless, it solves many large scale applications up to a million variables and thousands of constaints, rigorously.
The VSDP source files and the User's Guide of the version 2012 can be downloaded from:
Additionally, this version supports linear programming, second order cone programming, and semidefinite programming very efficiently, without transforming the semidefinite problem to the linear or second order cone programming problem.
The code is much more sophisticated, but has rigorously solved problems up to 20 million variables. In many cases, the time for computing rigorous error bounds is neglectable compared with the time for computing approximate solutions. In other words, safety comes almost for free.
If the conic solver produces suitable approximations, then usually the error bounds for the optimal value are quite accurate, while in other cases, lower and upper bounds differ, and the user receives a warning that something went wrong or needs special attention.
VSDP has rigorously solved many real world applications among them Truss topology design, Stochastic forestry problems, Oil renery problems, Flap settings of aircraft, Pilot models, Airline schedule planning, Industrial production and allocation models, Image restoration problems, Multisector economic planning problems, .... Many of them are contained in the NETLIB, a well-known collection of difficult to solve linear programming problems, and in the SDPLIB benchmark problems of Borchers, a library of problems up to thousands of constraints and millions of variables.
There are other software packages for computing rigorous results. These packages don't use relaxation techniques, and can be applied only to problems of small size. Elaborate comparisons with these packages can be found in a paper of Keil, see the reference below.
Electronic structure calculations, in particular the computation of the ground state energy, lead to challenging problems in optimization. These problems are of enormous importance in quantum chemistry for the calculation of properties of solids and molecules. Unfortunately, they are difficult to solve, and numerical solvers sometimes produce erroneous results, as observed by Nakata, Nakatsuji, Ehara, Fukuda, Nakata, and Fujisawa. The smallest problem instance has about one hundred thousand variables and about thousand constraints. The largest problem instance has about 20 million variables and thirty thousand constraints. All these problems are solved with tight and rigorous error bounds.
Institute for Reliable Computing
Hamburg University of Technology
Am Schwarzenberg-Campus 3