On Semidefinite Programming and Applications in Combinatorial Optimization

Gerald Gruber

In the 1990s striking advances have been achieved in Semidefinite Programming. It is an extension of Linear Programming and belongs to the class of conic convex programming, which means optimizing a linear function subject to the constraint set given by the intersection of an affine space with a closed cone. This dissertation covers Semidefinite Programming in conjunction with Combinatorial Optimization. This presentation is subdivided into three parts. Part One consisting of two chapters serves as the introductory part. Chapter 1 deals with the semidefinite programming problem in standard form and provides a review of the essential aspects concerning duality and interior-point methods. In chapter 2 we survey recent convergence results and propose a global convergence proof based on the concept of closed mappings. Part Two presents algorithmic aspects. In chapter 3 we consider linear-quadratic functionals in Semidefinite Programming. We propose a primal-dual path-following algorithm, show that it generates iterates which remain in a compact set and establish the global convergence of the algorithm. In chapter 4 we consider classes of ill-posed semidefinite problems. This chapter provides a numerically stable interior-point approach on how to handle semidefinite problems with zero duality gap for which Slater's condition fails for at least one of the primal and dual problem. Most of the motivation in Semidefinite Programming comes from the fact that it has found many applications in various fields, including control theory and Combinatorial Optimization. Part Three is devoted to two classical problems in Combinatorial Optimization. In chapter 5 we consider the maximum stable set problem. We investigate various improvements of the well known $\vartheta-$function and present computational results. The last chapter deals with the maximum cut problem. We present an approach to approximate semidefinite relaxations through purely Linear Programming based techniques. First computational results on chordal graphs are very promising and make this an attractive alternative for large scale problems.

G. Gruber, On Semidefinite Programming and Applications in Combinatorial Optimization, PhD thesis, University of Technology, Graz, Austria, 2000. Shaker Verlag, Aachen - Maastricht, ISBN 3-8265-7541-5

Contact: gerald.gruber@uni-klu.ac.at