A matrix generation approach for eigenvalue optimization |
| |
Authors: | Mohammad R Oskoorouchi Jean-Louis Goffin |
| |
Institution: | (1) College of Business Administration, California State University San Marcos, San Marcos, California 92096, USA;(2) GERAD/Faculty of Management, McGill University, 1001 SherbrookeWest, Montreal, QC, H3A 1G5, Canada |
| |
Abstract: | We study the extension of a column generation technique to nonpolyhedral models. In particular, we study the problem of minimizing
the maximum eigenvalue of an affine combination of symmetric matrices. At each step of the algorithm a restricted master problem
in the primal space, corresponding to the relaxed dual (original) problem, is formed. A query point is obtained as an approximate
analytic center of a bounded set that contains the optimal solution of the dual problem. The original objective function is
evaluated at the query point, and depending on its differentiability a column or a matrix is added to the restricted master
problem. We discuss the issues of recovering feasibility after the restricted master problem is updated by a column or a matrix.
The computational experience of implementing the algorithm on randomly generated problems are reported and the cpu time of
the matrix generation algorithm is compared with that of the primal-dual interior point methods on dense and sparse problems
using the software SDPT3. Our numerical results illustrate that the matrix generation algorithm outperforms primal-dual interior
point methods on dense problems with no structure and also on a class of sparse problems.
This work has been completed with the partial support of a summer grant from the College of Business Administration, California
State University San Marcos, and the University Professional Development/Research and Creative Activity Grant |
| |
Keywords: | Column generation Cutting plane technique Eigenvalue optimization Analytic center Semidefinite inequality |
本文献已被 SpringerLink 等数据库收录! |
|