The symmetric eigenvalue complementarity problem

Authors:
Marcelo Queiroz, Joaquim Júdice and Carlos Humes, Jr.

Journal:
Math. Comp. **73** (2004), 1849-1863

MSC (2000):
Primary 90C33, 47A75; Secondary 90C30, 82B05

DOI:
https://doi.org/10.1090/S0025-5718-03-01614-4

Published electronically:
August 20, 2003

MathSciNet review:
2059739

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper the Eigenvalue Complementarity Problem (EiCP) with real symmetric matrices is addressed. It is shown that the symmetric (EiCP) is equivalent to finding an equilibrium solution of a differentiable optimization problem in a compact set. A necessary and sufficient condition for solvability is obtained which, when verified, gives a convenient starting point for any gradient-ascent local optimization method to converge to a solution of the (EiCP). It is further shown that similar results apply to the Symmetric Generalized Eigenvalue Complementarity Problem (GEiCP). Computational tests show that these reformulations improve the speed and robustness of the solution methods.

**1.**G. Auchmuty, Unconstrained variational principles for eigenvalues of real symmetric matrices,*SIAM J. Math. Anal.*, 20(5):1186-1207, 1989. MR**91b:49055****2.**G. Auchmuty, Globally and rapidly convergent algorithms for symmetric eigenproblems,*SIAM J. Matrix Anal. Appl.*, 12(4):690-706, 1991.MR**92h:65062****3.**M. S. Bazaraa, H. D. Sherali and C. M. Shetty, Nonlinear programming: theory and algorithms, 2nd Edition. John Wiley and Sons, New York, 1993.MR**80f:90110****4.**F. Chatelin, Eigenvalues of matrices. John Wiley & Sons, 1993.MR**94d:65002****5.**A. P. Costa, I. N. Figueiredo, J. Júdice and J. A. C. Martins, A complementarity eigenproblem in the stability analysis of finite dimensional elastic systems with frictional contact, In.: Complementarity: applications, algorithms and extensions, edited by M. Ferris, J. S. Pang and O. Mangasarian, Kluwer, New York, pp. 67-83, 2001.MR**2002a:74094****6.**S. Dirkse and M. Ferris, The PATH solver: a nonmonotone stabilization scheme for mixed complementarity problems,*Optimization and Software*, 5:123-156, 1995.**7.**P. T. Harker and J.-S. Pang, Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications,*Math. Program. - Series B - Variational inequality problems*, 48(2):161-220, 1990.MR**91g:90166****8.**J. Júdice, Algorithms for Linear Complementarity Problems, In.: Algorithms for Continuous Optimization, edited by E. Spedicato, Kluwer, Amsterdam, pp. 435-474, 1994.MR**95m:90133****9.**M. Mongeau and M. Torki, Computing eigenelements of real symmetric matrices via optimization,*Technical Report MIP 99-54*, Université Paul Sabatier, Toulouse, 1999.**10.**B. A. Murtagh and M. A. Saunders, MINOS 5.1 user's guide,*Report SOL 83-20R*, Department of Operations Research, Stanford University, 1987.**11.**K. G. Murty, Linear complementarity, linear and nonlinear programming, Heldermann Verlag, Berlin, 1988.MR**89h:90240****12.**J. M. Ortega, Matrix analysis: a second course, Plenum Press, New York, 1987. MR**88a:15002****13.**B. N. Parlett, The symmetric eigenvalue problem, Classics in Applied Mathematics 20, SIAM, 1997.MR**99c:65072****14.**A. Seeger, Eigenvalue analysis of equilibrium processes defined by linear complementarity conditions,*Linear Algebra and its Applications*, 292:1-14, 1999.MR**2000c:90098**

Retrieve articles in *Mathematics of Computation*
with MSC (2000):
90C33,
47A75,
90C30,
82B05

Retrieve articles in all journals with MSC (2000): 90C33, 47A75, 90C30, 82B05

Additional Information

**Marcelo Queiroz**

Affiliation:
Computer Science Department, University of São Paulo, Rua do Matão 1010, 05508-090 São Paulo, SP, Brazil

Email:
mqz@ime.usp.br

**Joaquim Júdice**

Affiliation:
Mathematics Department, University of Coimbra, 3000 Coimbra, Portugal

Email:
Joaquim.Judice@co.it.pt

**Carlos Humes, Jr.**

Affiliation:
Computer Science Department, University of São Paulo, Rua do Matão 1010, 05508-090 São Paulo, SP, Brazil

Email:
chumes@usp.br

DOI:
https://doi.org/10.1090/S0025-5718-03-01614-4

Received by editor(s):
March 26, 2002

Received by editor(s) in revised form:
January 23, 2003

Published electronically:
August 20, 2003

Additional Notes:
The first author was supported by FAPESP Grant Nos. 97/06227-2 and 02/01351-7.

The second author was supported by FCT project POCTI/35059/MAT/2000.

Article copyright:
© Copyright 2003
American Mathematical Society