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. 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. 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.
A large variety of problems and applications, from optimization to nonlinear systems, can be modelled as convex or conic problems. There are simple symbolic manipulations and transformations with so-called conic representable sets and functions that allow to implement a convex or conic arithmetic. This aritmetic is favorable compared to other ones, such as affine or interval aritmetic, because (i) it is much better suited to algorithmic processing with interior point methods, and because (ii) the computed results can be verified efficiently with VSDP without much overestimation or wrapping effects, the latter being very likely in interval arithmetic.
There are three versions of VSDP. Detailed instructions on how to install VSDP are given in the corresponding User's Guide.
The VSDP 2006 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 constraints, rigorously.
The VSDP 2012 source files and the User's Guide of the older version can be downloaded from:
Additionally, the 2012 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.
The VSDP 2018 source files and the User's Guide of the older version can be downloaded from:
Like the previous version, the 2018 version supports conic programming problems including free variables and linear, second-order, and semidefinite cones. This version supports more approximate solvers (see below) and for a more intuitive usage the interface was redesigned object oriented. Especially, the code readability has been improved a lot, without sacrificing the performance gain of the previous version.
Via its interface, the latest version of VSDP provides an easy access to the conic solvers CSDP, MOSEK, SDPA, SeDuMi, SDPT3, LPSOLVE, GLPK, and MATLAB's LINPROG.
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 in all versions has rigorously solved many real world applications among them Truss topology design, Stochastic forestry problems, Oil refinery 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
21073 Hamburg
Germany