A matrix generation approach for eigenvalue optimization

Mohammad R Oskoorouchi (moskoorocsusm.edu)
Jean-Louis Goffin (Jean-Louis.GoffinMcGill.Ca)

Abstract: We study the extension of a column generation technique to eigenvalue optimization. In our approach we utilize the method of analytic center to obtain the query points at each iteration. A restricted master problem in the primal space is formed corresponding to the relaxed dual problem. At each step of the algorithm, an oracle is called to return the necessary columns to update the restricted master. Since eigenvalue optimization yields to a nonpolyhedral model, at some query points the oracle generates matrices, rather than traditional columns. In this case, we update the restricted master problem by enlarging the matrix variable by a block-diagonal element. We discuss the issues of recovering feasibility after the restricted master is updated by a column or a matrix. The numerical result of implementing the algorithm on randomly generated problems is reported.

Keywords: Column generation, cutting plane technique, eigenvalue optimization, analytic center, semidefinite inequality

Category 1: Convex and Nonsmooth Optimization

Category 2: Linear, Cone and Semidefinite Programming

Citation: College of Business Administration, California State University San Marcos, San Marcos, California, USA 92096-0001

Download: [Postscript]

Entry Submitted: 04/05/2004
Entry Accepted: 04/07/2004
Entry Last Modified: 04/05/2004

Modify/Update this entry