@misc{Helmberg2000, author = {Helmberg, Christoph}, title = {SBmethod --- A C++ Implementation of the Spectral Bundle Method. Manual to Version 1.1}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6039}, number = {00-35}, year = {2000}, abstract = {\texttt{SBmethod}, Version 1.1, is an implementation of the spectral bundle method for eigenvalue optimization problems of the form \begin{displaymath} \min_{y\in \mathbf{R}^m}\;\; a\;\lambda_{\max}(C-\sum_{i=1}^{m} A_i y_i)+b^Ty. \end{displaymath} The design variables \$y_i\$ may be sign constrained, \$C\$ and and \$A_i\$ are given real symmetric matrices, \$b\in\mathbf{R}^m\$ allows to specify a linear cost term, and \$a>0\$ is a constant multiplier for the maximum eigenvalue function \$\lambda_{\max}(\cdot)\$. The code is intended for large scale problems and allows to exploit structural properties of the matrices such as sparsity and low rank structure. The manual contains instructions for installation and use of the program. It describes in detail input format, options, and output. The meaning of the variables and parameters is made precise by relating them to a mathematical description of the algorithm in pseudocode.}, language = {en} } @misc{Helmberg2001, author = {Helmberg, Christoph}, title = {Numerical Evaluation of SBmethod}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6637}, number = {01-37}, year = {2001}, abstract = {We report numerical results for SBmethod --- a publically available implementation of the spectral bundle method --- applied to the 7\$^{th}\$ DIMACS challenge test sets that are semidefinite relaxations of combinatorial optimization problems. The performance of the code is heavily influenced by parameters that control bundle update and eigenvalue computation. Unfortunately, no mathematically sound guidelines for setting them are known. Based on our experience with SBmethod, we propose heuristics for dynamically updating the parameters as well as a heuristc for improving the starting point. These are now the default settings of SBmethod Version 1.1. We compare their performance on the DIMACS instances to our previous best choices for Version 1.0. SBmethod Version 1.1 is also part of the independent DIMACS benchmark by H.~Mittelmann. Based on these results we try to analyze strengths and weaknesses of our approach in comparison to other codes for large scale semidefinite programming.}, language = {en} } @misc{Helmberg2001, author = {Helmberg, Christoph}, title = {A Cutting Plane Algorithm for Large Scale Semidefinite Relaxations}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6527}, number = {01-26}, year = {2001}, abstract = {The recent spectral bundle method allows to compute, within reasonable time, approximate dual solutions of large scale semidefinite quadratic 0-1 programming relaxations. We show that it also generates a sequence of primal approximations that converge to a primal optimal solution. Separating with respect to these approximations gives rise to a cutting plane algorithm that converges to the optimal solution under reasonable assumptions on the separation oracle and the feasible set. We have implemented a practical variant of the cutting plane algorithm for improving semidefinite relaxations of constrained quadratic 0-1 programming problems by odd-cycle inequalities. We also consider separating odd-cycle inequalities with respect to a larger support than given by the cost matrix and present a heuristic for selecting this support. Our preliminary computational results for max-cut instances on toroidal grid graphs and balanced bisection instances indicate that warm start is highly efficient and that enlarging the support may sometimes improve the quality of relaxations considerably.}, language = {en} } @phdthesis{Helmberg2000, author = {Helmberg, Christoph}, title = {Semidefinite Programming for Combinatorial Optimization}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6022}, number = {00-34}, year = {2000}, abstract = {This book offers a self-contained introduction to the field of semidefinite programming, its applications in combinatorial optimization, and its computational methods. We equip the reader with the basic results from linear algebra on positive semidefinite matrices and the cone spanned by them. Starting from linear programming, we introduce semidefinite programs and discuss the associated duality theory. We then turn to semidefinite relaxations of combinatorial optimization and illustrate their interrelation. In the second half we deal with computational methods for solving semidefinite programs. First, the interior point approach, its iteration complexity, and implementational issues are discussed. Next, we explain in great detail the spectral bundle method, which is particularly suited for large scale semidefinite programming. One of the most successful techniques in integer linear programming is the cutting plane approach which improves an initial relaxation by adding violated inequalities. We explore possibilities to combine the two solution methods with the cutting plane approach in order to strengthen semidefinite relaxations of combinatorial optimization problems.}, language = {en} } @misc{DuarteSagnolOliveira2015, author = {Duarte, Belmiro P.M. and Sagnol, Guillaume and Oliveira, Nuno M.C.}, title = {A robust minimax Semidefinite Programming formulation for optimal design of experiments for model parametrization}, issn = {1438-0064}, doi = {10.1016/B978-0-444-63578-5.50146-8}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-54626}, year = {2015}, abstract = {Model-based optimal design of experiments (M-bODE) is a crucial step in model parametrization since it encloses a framework that maximizes the amount of information extracted from a battery of lab experiments. We address the design of M-bODE for dynamic models considering a continuous representation of the design. We use Semidefinite Programming (SDP) to derive robust minmax formulations for nonlinear models, and extend the formulations to other criteria. The approaches are demonstrated for a CSTR where a two-step reaction occurs.}, language = {en} }