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.

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.

Priv.-Doz. Dr. Christian Jansson
Institute for Reliable Computing
Hamburg University of Technology
Am Schwarzenberg-Campus 3
21073 Hamburg