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.
Citation
College of Business Administration, California State University San Marcos, San Marcos, California, USA 92096-0001