##
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