Konrad-Zuse-Zentrum
|
ZIB PaperWeb
|
|
|
| 00-34 | Christoph Helmberg
Semidefinite Programming for Combinatorial Optimization |   |
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.
Keywords: positive semidefinite matrices,
semidefinite cone,
semidefinite Programming,
semidefinite duality,
combinatorial optimization,
max-cut,
quadratic 0-1 programming,
graph partitioning,
semidefinite relaxations,
interior point methods,
spectral bundle method,
eigenvalue optimization,
cutting plane algorithms
MSC: 90C22, 90C27, 90-02