The symmetric eigenvalue complementarity problem
HTML articles powered by AMS MathViewer
- by Marcelo Queiroz, Joaquim Júdice and Carlos Humes Jr. PDF
- Math. Comp. 73 (2004), 1849-1863 Request permission
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.References
- Giles Auchmuty, Unconstrained variational principles for eigenvalues of real symmetric matrices, SIAM J. Math. Anal. 20 (1989), no. 5, 1186–1207. MR 1009353, DOI 10.1137/0520078
- Giles Auchmuty, Globally and rapidly convergent algorithms for symmetric eigenproblems, SIAM J. Matrix Anal. Appl. 12 (1991), no. 4, 690–706. MR 1121702, DOI 10.1137/0612053
- Mokhtar S. Bazaraa and C. M. Shetty, Nonlinear programming, John Wiley & Sons, New York-Chichester-Brisbane, 1979. Theory and algorithms. MR 533477
- Françoise Chatelin, Eigenvalues of matrices, John Wiley & Sons, Ltd., Chichester, 1993. With exercises by Mario Ahués and the author; Translated from the French and with additional material by Walter Ledermann. MR 1232655
- A. Pinto da Costa, I. N. Figueiredo, J. J. Júdice, and J. A. C. Martins, A complementarity eigenproblem in the stability analysis of finite dimensional elastic systems with frictional contact, Complementarity: applications, algorithms and extensions (Madison, WI, 1999) Appl. Optim., vol. 50, Kluwer Acad. Publ., Dordrecht, 2001, pp. 67–83. MR 1818617, DOI 10.1007/978-1-4757-3279-5_{4}
- S. Dirkse and M. Ferris, The PATH solver: a nonmonotone stabilization scheme for mixed complementarity problems, Optimization and Software, 5:123-156, 1995.
- Patrick T. Harker and Jong-Shi Pang, Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications, Math. Programming 48 (1990), no. 2, (Ser. B), 161–220. MR 1073707, DOI 10.1007/BF01582255
- Joaquím J. Júdice, Algorithms for linear complementarity problems, Algorithms for continuous optimization (Il Ciocco, 1993) NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., vol. 434, Kluwer Acad. Publ., Dordrecht, 1994, pp. 435–474. MR 1314218
- M. Mongeau and M. Torki, Computing eigenelements of real symmetric matrices via optimization, Technical Report MIP 99-54, Université Paul Sabatier, Toulouse, 1999.
- B. A. Murtagh and M. A. Saunders, MINOS 5.1 user’s guide, Report SOL 83-20R, Department of Operations Research, Stanford University, 1987.
- K. G. Murty, Linear complementarity, linear and nonlinear programming, Sigma Series in Applied Mathematics, vol. 3, Heldermann Verlag, Berlin, 1988. MR 949214
- James M. Ortega, Matrix theory, The University Series in Mathematics, Plenum Press, New York, 1987. A second course. MR 878977, DOI 10.1007/978-1-4899-0471-3
- Beresford N. Parlett, The symmetric eigenvalue problem, Classics in Applied Mathematics, vol. 20, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1998. Corrected reprint of the 1980 original. MR 1490034, DOI 10.1137/1.9781611971163
- Alberto Seeger, Eigenvalue analysis of equilibrium processes defined by linear complementarity conditions, Linear Algebra Appl. 292 (1999), no. 1-3, 1–14. MR 1689301, DOI 10.1016/S0024-3795(99)00004-X
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
- 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. - © Copyright 2003 American Mathematical Society
- 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
- MathSciNet review: 2059739