The symmetric eigenvalue complementarity problem
Authors:
Marcelo Queiroz, Joaquim Júdice and Carlos Humes, Jr.
Journal:
Math. Comp. 73 (2004), 18491863
MSC (2000):
Primary 90C33, 47A75; Secondary 90C30, 82B05
Published electronically:
August 20, 2003
MathSciNet review:
2059739
Fulltext PDF Free Access
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 gradientascent 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.
Giles
Auchmuty, Unconstrained variational principles for eigenvalues of
real symmetric matrices, SIAM J. Math. Anal. 20
(1989), no. 5, 1186–1207. MR 1009353
(91b:49055), http://dx.doi.org/10.1137/0520078
 2.
Giles
Auchmuty, Globally and rapidly convergent algorithms for symmetric
eigenproblems, SIAM J. Matrix Anal. Appl. 12 (1991),
no. 4, 690–706. MR 1121702
(92h:65062), http://dx.doi.org/10.1137/0612053
 3.
Mokhtar
S. Bazaraa and C.
M. Shetty, Nonlinear programming, John Wiley & Sons, New
YorkChichesterBrisbane, 1979. Theory and algorithms. MR 533477
(80f:90110)
 4.
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 (94d:65002)
 5.
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
(2002a:74094), http://dx.doi.org/10.1007/9781475732795_4
 6.
S. Dirkse and M. Ferris, The PATH solver: a nonmonotone stabilization scheme for mixed complementarity problems, Optimization and Software, 5:123156, 1995.
 7.
Patrick
T. Harker and JongShi
Pang, Finitedimensional 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
(91g:90166), http://dx.doi.org/10.1007/BF01582255
 8.
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
(95m:90133)
 9.
M. Mongeau and M. Torki, Computing eigenelements of real symmetric matrices via optimization, Technical Report MIP 9954, Université Paul Sabatier, Toulouse, 1999.
 10.
B. A. Murtagh and M. A. Saunders, MINOS 5.1 user's guide, Report SOL 8320R, Department of Operations Research, Stanford University, 1987.
 11.
K.
G. Murty, Linear complementarity, linear and nonlinear
programming, Sigma Series in Applied Mathematics, vol. 3,
Heldermann Verlag, Berlin, 1988. MR 949214
(89h:90240)
 12.
James
M. Ortega, Matrix theory, The University Series in
Mathematics, Plenum Press, New York, 1987. A second course. MR 878977
(88a:15002)
 13.
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 (99c:65072)
 14.
Alberto
Seeger, Eigenvalue analysis of equilibrium processes defined by
linear complementarity conditions, Linear Algebra Appl.
292 (1999), no. 13, 1–14. MR 1689301
(2000c:90098), http://dx.doi.org/10.1016/S00243795(99)00004X
 1.
 G. Auchmuty, Unconstrained variational principles for eigenvalues of real symmetric matrices, SIAM J. Math. Anal., 20(5):11861207, 1989. MR 91b:49055
 2.
 G. Auchmuty, Globally and rapidly convergent algorithms for symmetric eigenproblems, SIAM J. Matrix Anal. Appl., 12(4):690706, 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. 6783, 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:123156, 1995.
 7.
 P. T. Harker and J.S. Pang, Finitedimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications, Math. Program.  Series B  Variational inequality problems, 48(2):161220, 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. 435474, 1994.MR 95m:90133
 9.
 M. Mongeau and M. Torki, Computing eigenelements of real symmetric matrices via optimization, Technical Report MIP 9954, Université Paul Sabatier, Toulouse, 1999.
 10.
 B. A. Murtagh and M. A. Saunders, MINOS 5.1 user's guide, Report SOL 8320R, 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:114, 1999.MR 2000c:90098
Similar Articles
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, 05508090 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, 05508090 São Paulo, SP, Brazil
Email:
chumes@usp.br
DOI:
http://dx.doi.org/10.1090/S0025571803016144
PII:
S 00255718(03)016144
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/062272 and 02/013517.
The second author was supported by FCT project POCTI/35059/MAT/2000.
Article copyright:
© Copyright 2003
American Mathematical Society
