×

zbMATH — the first resource for mathematics

A new method for solving Pareto eigenvalue complementarity problems. (English) Zbl 1296.90124
Summary: In this paper, we introduce a new method, called the Lattice Projection Method (LPM), for solving eigenvalue complementarity problems. The original problem is reformulated to find the roots of a nonsmooth function. A semismooth Newton type method is then applied to approximate the eigenvalues and eigenvectors of the complementarity problems. The LPM is compared to \(\mathrm{SNM}_{\min}\) and \(\mathrm{SNM}_{\mathrm{FB}}\), two methods widely discussed in the literature for solving nonlinear complementarity problems, by using the performance profiles as a comparing tool [E. D. Dolan and J. J. Moré, Math. Program. 91, No. 2 (A), 201–213 (2002; Zbl 1049.90004)]. The performance measures, used to analyze the three solvers on a set of matrices mostly taken from the Matrix Market [R. F. Boisvert, R. Pozo, K. Remington, K. Barrett and J. J. Dongarra, “Matrix market: a web resource for test matrix collections. In: The Quality of Numerical Software: Assessment and Enhancement, London: Chapman and Hall, 125–137 (1997)], are computing time, number of iterations, number of failures and maximum number of solutions found by each solver. The numerical experiments highlight the efficiency of the LPM and show that it is a promising method for solving eigenvalue complementarity problems. Finally, Pareto bi-eigenvalue complementarity problems were solved numerically as an application to confirm the efficiency of our method.

MSC:
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Adly, S.; Seeger, A., A nonsmooth algorithm for cone-constrained eigenvalue problems, Comput. Optim. Appl., 49, 299-318, (2011) · Zbl 1220.90128
[2] Amri, A.; Seeger, A., Spectral analysis of coupled linear complementarity problems, Linear Algebra Appl., 432, 2507-2523, (2010) · Zbl 1189.90168
[3] Boisvert, R.F.; Pozo, R.; Remington, K.; Barrett, R.F.; Dongarra, J.J., Matrix market: a web resource for test matrix collections, 125-137, (1997), London
[4] Chu, M.T.; Watterson, J.L., On a multivariate eigenvalue problem: I. algebric theory and a power method, SIAM J. Sci. Comput., 14, 1089-1106, (1993) · Zbl 0789.65023
[5] Clarke, F.H.: Optimization and Nonsmooth Analysis. Wiley, New York (1983). Reprinted by, SIAM, Philadelphia, PA, 1990 · Zbl 0582.49001
[6] Cops: http://mcs.anl.gov/ more/cops/ · Zbl 1014.68640
[7] Luca, T.; Facchinei, F.; Kanzow, C., A semismooth equation approach to the solution of nonlinear complementarity problems, Math. Program., 75, 407-439, (1996) · Zbl 0874.90185
[8] Dirkse, S.P.; Ferris, M.C., A pathsearch damped Newton method for computing general equilibria, Ann. Oper. Res., 68, 211-232, (1996) · Zbl 0868.90012
[9] Dirkse, S.P.; Ferris, M.C., The path solver: a non-monotone stabilization scheme for mixed complementarity problems, Optim. Methods Softw., 5, 123-156, (1995)
[10] Dolan, E.D.; Moré, J.J., Benchmarking optimization software with performance profiles, Math. Program., 91, 201-213, (2002) · Zbl 1049.90004
[11] Ferris, M.C.; Pang, J.S., Engineering and economic applications of complementarity problems, J. Soc. Ind. Appl. Math., 39, 669-713, (1997) · Zbl 0891.90158
[12] Fischer, A., A special Newton-type optimization method, Optimization, 24, 269-284, (1992) · Zbl 0814.65063
[13] Hanafi, M.; Ten Berge, J.M.F., Global optimality of the successive maxbet algorithm, Psychometrika, 68, 97-103, (2003) · Zbl 1306.62422
[14] Harker, P.T.; Pang, J.S., Finite-dimensional variational inequality and nonlinear complementarity problem: a survey of theory, algorithms and applications, Math. Program., 48, 161-220, (1990) · Zbl 0734.90098
[15] Horst, P., Relations among \(m\) sets of measures, Psychometrika, 26, 129-149, (1961) · Zbl 0099.35801
[16] Hotelling, H., The most predictable criterion, J. Educ. Psychol., 26, 139-142, (1935)
[17] Hotelling, H., Relations between two sets of variates, Biometrika, 28, 321-377, (1936) · Zbl 0015.40705
[18] Judice, J.J.; Sherali, H.D.; Ribeiro, I.M., The eigenvalue complementarity problem, Comput. Appl., 37, 139-156, (2007) · Zbl 1181.90261
[19] Júdice, J.J.; Raydan, M.; Rosa, S.S.; Santos, S.A., On the solution of the symmetric eigenvalue complementarity problem by the spectral projected gradient algorithm, Numer. Algorithms, 47, 391-407, (2008) · Zbl 1144.65042
[20] Júdice, J.J.; Sherali, H.D.; Ribeiro, I.M.; Rosa, S.S., On the asymmetric eigenvalue complementarity problem, Optim. Methods Softw., 24, 549-568, (2009) · Zbl 1177.90386
[21] Kanzow, C.; Kleinmichel, H., A new class of semismooth Newton type methods for nonlinear complementarity problems, Comput. Optim. Appl., 11, 227-251, (1998) · Zbl 0913.90250
[22] Kanzow, C.; Yamashita, N.; Fukushima, M., New NCP-functions and their properties, J. Optim. Theory Appl., 94, 115-135, (1997) · Zbl 0886.90146
[23] Kettenring, J.R., Canonical analysis of several sets of variables, Biometrika, 58, 433-451, (1971) · Zbl 0225.62072
[24] Martins, J.A.C.; Barbarin, S.; Raous, M.; Pinto da Costa, A., Dynamic stability of finite dimensional linearly elastic systems with unilateral contact and Coulomb friction, Comput. Methods Appl. Mech. Eng., 177, 289-328, (1999) · Zbl 0943.74023
[25] Martins, J.A.C.; Pinto da Costa, A., Stability of finite-dimensional nonlinear elastic systems with unilateral contact and friction, Int. J. Solids Struct., 37, 2519-2564, (2000) · Zbl 0959.74048
[26] Martins, J.A.C.; Pinto da Costa, A., Bifurcations and instabilities in frictional contact problems: theoretical relations, computational methods and numerical results, (2004)
[27] Martins, J.A.C.; Pinto da Costa, A., Computation of bifurcations and instabilities in some frictional contact problems, (2001)
[28] Martins, J.A.C.; Pinto da Costa, A.; Figueiredo, I.N.; Júdice, J.J., The directional instability problem in systems with frictional contacts, Comput. Methods Appl. Mech. Eng., 193, 357-384, (2004) · Zbl 1075.74596
[29] Mifflin, R., Semismooth and semiconvex functions in constrained optimization, SIAM J. Control Optim., 15, 957-972, (1977) · Zbl 0376.90081
[30] Pang, J.S., Facchinei, F.: Finite-Dimensional Variational Inequalities and Complementarity Problems. Operations Research, vol. 2. Springer, New York (2003) · Zbl 1062.90002
[31] Pang, J.S., Newton’s method for B-differentiable equations, Math. Oper. Res., 15, 311-465, (1990) · Zbl 0716.90090
[32] Pinto da Costa, A.; Seeger, A., Cone-constrained eigenvalue problems: theory and algorithms, Comput. Optim. Appl., 45, 25-57, (2008) · Zbl 1193.65039
[33] Pinto da Costa, A.; Seeger, A., Numerical resolution of cone-constrained eigenvalues problems, J. Comput. Appl. Math., 28, 37-61, (2009) · Zbl 1171.65027
[34] Qi, L., Convergence analysis of some algorithms for solving nonsmooth equations, Math. Oper. Res., 18, 227-244, (1993) · Zbl 0776.65037
[35] Qi, L.: Regular pseudo-smooth NCP and BVIP functions and globally and quadratically convergent generalized Newton methods for complementarity and variational inequality problems. Technical report AMR 97/14, The University of New South Wales, Sydney, Australia (1997) · Zbl 1306.62422
[36] Queiroz, M.; Júdice, J.J.; Humes, C., The symmetric eigenvalue complementarity problem, Math. Comput., 73, 1849-1863, (2003) · Zbl 1119.90059
[37] Qi, L.; Sun, J., A nonsmooth version of newton’s method, Math. Program., 58, 353-367, (1993) · Zbl 0780.90090
[38] Seeger, A., Eigenvalue analysis of equilibrium processes defined by linear complementarity conditions, Linear Algebra Appl., 292, 1-14, (1999) · Zbl 1016.90067
[39] Seeger, A.; Torki, M., On eigenvalues induced by a cone constraint, Linear Algebra Appl., 372, 181-206, (2003) · Zbl 1046.15008
[40] Seeger, A.; Vicente-Pérez, J., On cardinality of Pareto spectra, Electron. J. Linear Algebra, 22, 758-766, (2011) · Zbl 1254.15015
[41] Tanaka, Y., Some generalized methods of optimal scaling and their asymptotic theories: the case of multiple responses-multiple factors, Ann. Inst. Stat. Math., 30, 329-348, (1978) · Zbl 0441.62057
[42] Tisseur, F.; Meerbergen, K., The quadratic eigenvalue problem, J. Soc. Ind. Appl. Math., 43, 235-286, (2001) · Zbl 0985.65028
[43] Ulbrich, M.: In: Semismooth Newton Methods for Variational Inequalities and Constrained Optimization Problems in Function Spaces. MOS-SIAM Series on Optimization (2011) · Zbl 1235.49001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.