DIMACS TR: 93-75
Interior-Point Methods for Max-Min Eigenvalue Problems
Authors: Franz Rendl, Robert J. Vanderbei, and Henry Wolkowicz
ABSTRACT
The problem of
maximizing the smallest eigenvalue of a symmetric matrix subject to
modifications on the main diagonal that sum to zero is important since,
for example, it yields the best bounds for graph-partitioning.
Current algorithms for this problem work well when the
multiplicity of the minimum eigenvalue at optimality is one.
However, real-world applications have
multiplicity at optimality that is greater than one. For such
problems, current algorithms break down quickly as the
multiplicity increases.
We present a primal-dual interior-point method for this problem.
The method proves to be simple, robust and efficient.
And most importantly, it is not adversely affected by high
multiplicities.
Key words:
max-min eigenvalue problems,
semidefinite programming,
interior-point methods.
Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-75.ps
DIMACS Home Page