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