zbMATH — the first resource for mathematics

Nonlinear eigenvector methods for convex minimization over the numerical range. (English) Zbl 07301509
Summary: We consider the optimization problem in which a continuous convex function is to be minimized over the joint numerical range of two Hermitian matrices. When those matrices are of large size, solving such problems by convex optimization can be computationally expensive. The goal of this paper is to present a novel nonlinear eigenvector method to accelerate the computation. We will show that the global minimizer of the optimization problem corresponds to a solution of a nonlinear eigenvalue problem with eigenvector nonlinearity (NEPv). The special structure of this NEPv allows for an efficient sequential subspace search algorithm, which is a nonlinear analogue to the NEPv of the commonly applied locally optimal conjugate gradient descent methods for Hermitian linear eigenvalue problems. Our new algorithm can be proven globally convergent to an eigenvector of the NEPv. Implementation details such as block iteration and preconditioning will be discussed. Numerical examples, with applications in computing the coercivity constant of boundary integral operators and solving multicast beamforming problems, show the effectiveness of our approach.
Reviewer: Reviewer (Berlin)
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
15A60 Norms of matrices, numerical range, applications of functional analysis to matrix theory
BEM++; JDQR; JDQZ; lobpcg.m; PRIMME
Full Text: DOI
[1] P.-A. Absil and K. A. Gallivan, Accelerated line-search and trust-region methods, SIAM J. Numer. Anal., 47 (2009), pp. 997-1018, https://doi.org/10.1137/08072019X. · Zbl 1191.65067
[2] Z. Bai, J. Demmel, J. Dongarra, A. Ruhe, and H. van der Vorst, Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide, Software Environ. Tools 11, SIAM, Philadelphia, 2000, https://doi.org/10.1137/1.9780898719581. · Zbl 0965.65058
[3] Z. Bai, D. Lu, and B. Vandereycken, Robust Rayleigh quotient minimization and nonlinear eigenvalue problems, SIAM J. Sci. Comput., 40 (2018), pp. A3495-A3522, https://doi.org/10.1137/18M1167681. · Zbl 1416.65148
[4] M. Bengtsson and B. Ottersten, Optimal downlink beamforming using semidefinite optimization, in Proceedings of the 37th Annual Allerton Conference on Communication, Control, and Computing, Monticello, IL, 1999, pp. 987-996.
[5] T. Betcke and E. A. Spence, Numerical estimation of coercivity constants for boundary integral operators in acoustic scattering, SIAM J. Numer. Anal., 49 (2011), pp. 1572-1601, https://doi.org/10.1137/100788483. · Zbl 1232.65097
[6] S. Boyd and V. Balakrishnan, A regularity result for the singular values of a transfer matrix and a quadratically convergent algorithm for computing its \(L_\infty \)-norm, Systems Control Lett., 15 (1990), pp. 1-7. · Zbl 0704.93014
[7] S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, Cambridge, UK, 2004. · Zbl 1058.90049
[8] D. Brandwood, A complex gradient operator and its application in adaptive array theory, Proc. IEE-H, 130 (1983), pp. 11-16.
[9] J. V. Burke, Second order necessary and sufficient conditions for convex composite NDO, Math. Program., 38 (1987), pp. 287-302. · Zbl 0641.49013
[10] E. Cancès, R. Chakir, and Y. Maday, Numerical analysis of nonlinear eigenvalue problems, J. Sci. Comput., 45 (2010), pp. 90-117. · Zbl 1203.65237
[11] S. H. Cheng and N. J. Higham, The nearest definite pair for the Hermitian generalized eigenvalue problem, Linear Algebra Appl., 302 (1999), pp. 63-76. · Zbl 0947.65042
[12] F. H. Clarke, Optimization and Nonsmooth Analysis, Classics Appl. Math. 5, SIAM, Philadelphia, 1990, https://doi.org/10.1137/1.9781611971309. · Zbl 0696.49002
[13] C. R. Crawford, A stable generalized eigenvalue problem, SIAM J. Numer. Anal., 13 (1976), pp. 854-860, https://doi.org/10.1137/0713067. · Zbl 0348.15005
[14] M. K. H. Fan and A. L. Tits, On the generalized numerical range, Linear Multilinear Algebra, 21 (1987), pp. 313-320. · Zbl 0648.15017
[15] D. D. Gaurav and K. V. S. Hari, A fast eigen solution for homogeneous quadratic minimization with at most three constraints, IEEE Signal Process. Lett., 20 (2013), pp. 968-971.
[16] E. Gutkin, E. A. Jonckheere, and M. Karow, Convexity of the joint numerical range: Topological and differential geometric viewpoints, Linear Algebra Appl., 376 (2004), pp. 143-171. · Zbl 1050.15026
[17] W. Hackbusch, Hierarchical Matrices: Algorithms and Analysis, Springer Ser. Comput. Math. 49, Springer, Heidelberg, 2015. · Zbl 1336.65041
[18] W. W. Hager, Minimizing a quadratic over a sphere, SIAM J. Optim., 12 (2001), pp. 188-208, https://doi.org/10.1137/S1052623499356071. · Zbl 1058.90045
[19] N. J. Higham, F. Tisseur, and P. M. Van Dooren, Detecting a definite Hermitian pair and a hyperbolic or elliptic quadratic eigenvalue problem, and associated nearness problems, Linear Algebra Appl., 351/352 (2002), pp. 455-474. · Zbl 1004.65045
[20] J.-B. Hiriart-Urruty and C. Lemaréchal, Convex Analysis and Minimization Algorithms I: Fundamentals, Grundlehren Math. Wiss. 305, Springer-Verlag, Berlin, 1993.
[21] Y. Huang and D. P. Palomar, Randomized algorithms for optimal solutions of double-sided QCQP with applications in signal processing, IEEE Trans. Signal Process., 62 (2014), pp. 1093-1108. · Zbl 1394.94245
[22] C. R. Johnson, Numerical determination of the field of values of a general complex matrix, SIAM J. Numer. Anal., 15 (1978), pp. 595-602, https://doi.org/10.1137/0715039. · Zbl 0389.65018
[23] F. Kangal, K. Meerbergen, E. Mengi, and W. Michiels, A subspace method for large-scale eigenvalue optimization, SIAM J. Matrix Anal. Appl., 39 (2018), pp. 48-82, https://doi.org/10.1137/16M1070025. · Zbl 1378.65090
[24] A. V. Knyazev, A preconditioned conjugate gradient method for eigenvalue problems and its implementation in a subspace, in Numerical Treatment of Eigenvalue Problems, Vol. 5 (Oberwolfach, 1990), Internat. Ser. Numer. Math. 96, Birkhäuser, Basel, 1991, pp. 143-154.
[25] A. V. Knyazev, Toward the optimal preconditioned eigensolver: Locally optimal block preconditioned conjugate gradient method, SIAM J. Sci. Comput., 23 (2001), pp. 517-541, https://doi.org/10.1137/S1064827500366124. · Zbl 0992.65028
[26] D. Kressner, D. Lu, and B. Vandereycken, Subspace acceleration for the Crawford number and related eigenvalue optimization problems, SIAM J. Matrix Anal. Appl., 39 (2018), pp. 961-982, https://doi.org/10.1137/17M1127545. · Zbl 1394.65031
[27] K. Kreutz-Delgado, The Complex Gradient Operator and the CR-Calculus, Tech. report, Course Lecture Suppl. ECE275A., Dept. Elect. Comput. Eng., University of California San Diego, San Diego, CA, 2005; available at http://dsp.ucsd.edu/ kreutz/.
[28] C. Le Bris, Computational chemistry from the perspective of numerical analysis, Acta Numer., 14 (2005), pp. 363-444. · Zbl 1119.65390
[29] C.-K. Li and Y.-T. Poon, Convexity of the joint numerical range, SIAM J. Matrix Anal. Appl., 21 (2000), pp. 668-678, https://doi.org/10.1137/S0895479898343516. · Zbl 0945.15019
[30] R.-C. Li, Rayleigh quotient based optimization methods for eigenvalue problems, in Matrix Functions and Matrix Equations, World Scientific, Singapore, 2015, pp. 76-108. · Zbl 1332.65053
[31] E. Mengi, E. A. Yildirim, and M. Kiliç, Numerical optimization of eigenvalues of Hermitian matrix functions, SIAM J. Matrix Anal. Appl., 35 (2014), pp. 699-724, https://doi.org/10.1137/130933472. · Zbl 1307.65043
[32] R. Meyer, Nonlinear eigenvector algorithms for local optimization in multivariate data analysis, Linear Algebra Appl., 264 (1997), pp. 225-246. · Zbl 0909.62060
[33] G. Narkiss and M. Zibulevsky, Sequential Subspace Optimization Method for Large-Scale Unconstrained Problems, Tech. report CCIT 559, EE Dept., Technion, Haifa, Israel, 2005.
[34] J. Nocedal and S. J. Wright, Numerical Optimization, 2nd ed., Springer, New York, 2006. · Zbl 1104.65059
[35] M. L. Overton, On minimizing the maximum eigenvalue of a symmetric matrix, SIAM J. Matrix Anal. Appl., 9 (1988), pp. 256-268, https://doi.org/10.1137/0609021. · Zbl 0647.65044
[36] B. N. Parlett, The Symmetric Eigenvalue Problem, Classics Appl. Math. 20, SIAM, Philadelphia, 1998, https://doi.org/10.1137/1.9781611971163. · Zbl 0885.65039
[37] P. Pulay, Convergence acceleration of iterative sequences. The case of SCF iteration, Chem. Phys. Lett., 73 (1980), pp. 393-398.
[38] V. R. Saunders and I. H. Hillier, A “level-shifting” method for converging closed shell Hartree-Fock wave functions, Int. J. Quantum Chem., 7 (1973), pp. 699-705.
[39] N. D. Sidiropoulos, T. N. Davidson, and Z.-Q. Luo, Transmit beamforming for physical-layer multicasting, IEEE Trans. Signal Process., 54 (2006), pp. 2239-2251. · Zbl 1374.94600
[40] W. Śmigaj, T. Betcke, S. Arridge, J. Phillips, and M. Schweiger, Solving boundary integral problems with BEM++, ACM Trans. Math. Softw., 41 (2015), 6. · Zbl 1371.65127
[41] A. Stathopoulos and J. R. McCombs, PRIMME: Preconditioned iterative multimethod eigensolver-methods and software description, ACM Trans. Math. Softw., 37 (2010), 21. · Zbl 1364.65087
[42] G. W. Stewart, Perturbation bounds for the definite generalized eigenvalue problem, Linear Algebra Appl., 23 (1979), pp. 69-85. · Zbl 0407.15012
[43] L. Thøgersen, J. Olsen, D. Yeager, P. Jørgensen, P. Sałek, and T. Helgaker, The trust-region self-consistent field method: Towards a black-box optimization in Hartree-Fock and Kohn-Sham theories, J. Chem. Phys., 121 (2004), pp. 16-27.
[44] F. Uhlig, On computing the generalized Crawford number of a matrix, Linear Algebra Appl., 438 (2013), pp. 1923-1935. · Zbl 1261.65044
[45] C. Yang, J. C. Meza, and L.-W. Wang, A trust region direct constrained minimization algorithm for the Kohn-Sham equation, SIAM J. Sci. Comput., 29 (2007), pp. 1854-1875, https://doi.org/10.1137/060661442. · Zbl 1154.65340
[46] L.-H. Zhang, On optimizing the sum of the Rayleigh quotient and the generalized Rayleigh quotient on the unit sphere, Comput. Optim. Appl., 54 (2013), pp. 111-139. · Zbl 1285.90042
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.