DIMACS TR: 93-75
Interior-Point Methods for Max-Min Eigenvalue Problems
Authors: Franz Rendl, Robert J. Vanderbei, and Henry Wolkowicz
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
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
max-min eigenvalue problems,
Paper available at:
DIMACS Home Page