Group for Research in Decision Analysis

The Eigenvalue Complementarity Problem

Joaquim J. Júdice Instituto de Telecomunicações, Portugal

The Eigenvalue Complementarity Problem (EiCP) finds important applications in different areas of science and engineering and differs from the traditional Eigenvalue Problem on the existence of nonnegative variables and complementarity constraints between pairs of variables. In this talk the EiCP is first introduced together with some of its extensions and important applications.

The symmetric case is next considered and assumes that the two matrices involved in the definition of the EiCP are symmetric. This EICP is shown to be reduced to the problem of finding a Stationary Point of an appropriate fractional quadratic function on the simplex. A Variational Inequality on the simplex and a Nonlinear Programming Problem are introduced as two interesting equivalent problems to the EiCP in the asymmetric case. These formulations guarantee the existence of a solution to the EiCP in the symmetric and asymmetric cases and suggest a number of local algorithms for the EiCP that are discussed in this talk.

Local algorithms may not be able to solve all the instances of the asymmetric EiCP. An enumerative method is introduced to deal with this type of EiCP and is shown to always converge to one of its solutions. The algorithm can be combined with a local semi-smooth Newton method to enhance its efficiency. Numerical experience is reported to highlight the interest of this methodology in practice.

Bounds for the maximum number of complementary eigenvalues for the symmetric and asymmetric cases are also discussed. Finally some conclusions and topics of our current and future research are presented in the last part of the talk.