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.

Via its interface, VSDP 2012 provides an easy access to the conic solvers CSDP, SeDuMi, SDPA, SDPT3, as well as LPSOLVE and MATLAB's LINPROG.

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.

- Further reading:
- C. Jansson. Rigorous Error Bounds for the Optimal Value of Linear Programming Problems. International Workshop on Global Constrained Optimization and Constraint Satisfaction, Springer, 2002.
- C. Jansson. A rigorous lower bound for the optimal value of convex optimization problems. J. Global Optimization, 28:121-137, 2004.
- C. Jansson. Rigorous Lower and Upper Bounds in Linear Programming. SIAM J. Optimization (SIOPT), 14(3):914-935, 2004.
- C. Jansson. Termination and Verification for Ill-posed Semidefinite Programming Problems, 2005. http://www.optimization-online.org/DB_HTML/2005/06/1150.html.
- C. Jansson. Rigorous Results in Combinatorial Optimization. In Bruno Buchberger, Shin'ichi Oishi, Michael Plum, and Siegfried M. Rump, editors, Algebraic and Numerical Algorithms and Computer-assisted Proofs, number 05391 in Dagstuhl Seminar Proceedings. Internationales Begegnungs- und Forschungszentrum (IBFI), Schloss Dagstuhl, Germany, 2006. http://drops.dagstuhl.de/opus/volltexte/2006/446.
- C.Jansson. VSDP: Verified SemiDefinite Programming, User's Guide, 2006. http://www.optimization-online.org/DB_HTML/2006/12/1547.html.
- C. Keil and C. Jansson. Computational Experience with Rigorous Error Bounds for the Netlib Linear Programming Library. Reliable Computing, 12, issue 4:303-321, 2006. http://www.optimization-online.org/DB_HTML/2004/12/1018.html. (PDF, 227525 bytes)
- C. Jansson. Guaranteed Accuracy for Conic Programming Problems in Vector Lattices, 2007. arXiv:0707.4366v1, http://arxiv.org/abs/0707.4366v1.
- C. Jansson, D. Chaykin, and C. Keil. Rigorous Error Bounds for the Optimal Value in Semidefinite Programming. SIAM Journal on Numerical Analysis, 46(1):180-200, 2007. http://link.aip.org/link/?SNA/46/180/1. (PDF, 261230 bytes) (doi:10.1137/050622870)
- D. Chaykin. Verification of semidefinite optimization problems with application to variational electronic structure calculation, 2009. https://doi.org/10.15480/882.849.
- C. Jansson. On Verified Numerical Computations in Convex Programming. Japan J. Indust. Appl. Math., 26:337-363, 2009. (PDF, 270770 bytes)
- C. Keil. Verified Linear Programming – a Comparison. http://www.optimization-online.org/DB_HTML/2008/06/2007.html.
- D. Chaykin, C. Jansson, F. Keil, M. Lange, K.T. Ohlhus, and S.M. Rump. Rigorous results in electronic structure calculations. Optimization online, 2016. http://www.optimization-online.org/DB_FILE/2016/11/5730.pdf.

Institute for Reliable Computing

Hamburg University of Technology

Am Schwarzenberg-Campus 3

21073 Hamburg

Germany