On the asymmetric eigenvalue complementarity problem

Abstract

In this paper, we discuss the eigenvalue complementarity problem (EiCP) where at least one of its defining matrices is asymmetric. A sufficient condition for the existence of a solution to the EiCP is established. The EiCP is shown to be equivalent to finding a global minimum of an appropriate merit function on a convex set Ω defined by linear constraints. A sufficient condition for a stationary point of this function on Ω to be a solution of the EiCP is presented. A branch-and-bound procedure is developed for finding a global minimum of this merit function on Ω. In addition, a sequential enumerative algorithm for the computation of the minimum and the maximum eigenvalues is also discussed. Computational experience is included to highlight the efficiency and efficacy of the proposed methodologies to solve the asymmetric EiCP.

Keywords:

• eigenvalue complementarity
• extreme eigenvalues
• branch-and-bound
• global optimization
• nonlinear programming

AMS Subject Classification :

• 90C26
• 90C30
• 90C33

Acknowledgement

H.D. Sherali was supported in part by the National Science Foundation under grant CMMI-0552676.