Large-Scale Optimization of Eigenvalues

Abstract

Optimization problems involving eigenvalues arise in many applications. Let x be a vector of real parameters and let $A(x)$ be a continuously differentiable symmetric matrix function of x. We consider a particular problem that occurs frequently: the minimization of the maximum eigenvalue of , subject to linear constraints and bounds on x. The eigenvalues of $A(x)$ are not differentiable at points x where they coalesce, so the optimization problem is said to be nonsmooth. Furthermore, it is typically the case that the optimization objective tends to make eigenvalues coalesce at a solution point. There are three main purposes of the paper. The first is to present a clear and self-contained derivation of the Clarke generalized gradient of the max eigenvalue function in terms of a “dual matrix.” The second purpose is to describe a new algorithm, based on the ideas of a previous paper by the author [SIAM J. Matrix Anal. Appl., 9 (1988), pp. 256–268], which is suitable for solving large-scale eigenvalue optimization problems. The algorithm uses a “successive partial linear programming” formulation that should be useful for other large-scale structured nonsmooth optimization problems as well as large-scale nonlinear programming with a relatively small number of nonlinear constraints. The third purpose is to report on our extensive numerical experience with the new algorithm, solving problems that arise in the following application areas: the optimal design of columns against buckling; the construction of optimal preconditioners for numerical linear equation solvers; the bounding of the Shannon capacity of a graph. We emphasize the role of the dual matrix, whose dimension is equal to the multiplicity of the minimal max eigenvalue. The dual matrix is computed by the optimization algorithm and used for verification of optimality and sensitivity analysis.