Volume 2, Issue 2
Linear Constrained Rayleigh Quotient Optimization: Theory and Algorithms

Yunshen Zhou, Zhaojun Bai & Ren-Cang Li

CSIAM Trans. Appl. Math., 2 (2021), pp. 195-262.

Published online: 2021-05

Preview Full PDF 199 4323
Export citation
  • Abstract

We consider the following constrained Rayleigh quotient optimization problem (CRQopt):

image.png

where $A$ is an $n×n$ real symmetric matrix and $C$ is an $n×m$ real matrix. Usually, $m$ « $n$. The problem is also known as the constrained eigenvalue problem in literature since it becomes an eigenvalue problem if the linear constraint $C$T$v=b$ is removed. We start by transforming CRQopt into an equivalent optimization problem (LGopt) of minimizing the Lagrangian multiplier of CRQopt, and then into another equivalent problem (QEPmin) of finding the smallest eigenvalue of a quadratic eigenvalue problem. Although these equivalences have been discussed in literature, it appears to be the first time that they are rigorously justified in this paper. In the second part, we present numerical algorithms for solving LGopt and QEPmin based on Krylov subspace projection. The basic idea is to first project LGopt and QEPmin onto Krylov subspaces to yield problems of the same types but of much smaller sizes, and then solve the reduced problems by direct methods, which is either a secular equation solver (in the case of LGopt) or an eigensolver (in the case of QEPmin). We provide convergence analysis for the proposed algorithms and present error bounds. The sharpness of the error bounds is demonstrated by examples, although in applications the algorithms often converge much faster than the bounds suggest. Finally, we apply the new algorithms to semi-supervised learning in the context of constrained clustering.

  • Keywords

Quadratic programming, quadratic eigenvalue problems, Lanczos algorithms, constrained clustering.

  • AMS Subject Headings

65F15, 65F50, 90C20

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@Article{CSIAM-AM-2-195, author = {Yunshen Zhou , and Zhaojun Bai , and Ren-Cang Li , }, title = {Linear Constrained Rayleigh Quotient Optimization: Theory and Algorithms}, journal = {CSIAM Transactions on Applied Mathematics}, year = {2021}, volume = {2}, number = {2}, pages = {195--262}, abstract = {

We consider the following constrained Rayleigh quotient optimization problem (CRQopt):

image.png

where $A$ is an $n×n$ real symmetric matrix and $C$ is an $n×m$ real matrix. Usually, $m$ « $n$. The problem is also known as the constrained eigenvalue problem in literature since it becomes an eigenvalue problem if the linear constraint $C$T$v=b$ is removed. We start by transforming CRQopt into an equivalent optimization problem (LGopt) of minimizing the Lagrangian multiplier of CRQopt, and then into another equivalent problem (QEPmin) of finding the smallest eigenvalue of a quadratic eigenvalue problem. Although these equivalences have been discussed in literature, it appears to be the first time that they are rigorously justified in this paper. In the second part, we present numerical algorithms for solving LGopt and QEPmin based on Krylov subspace projection. The basic idea is to first project LGopt and QEPmin onto Krylov subspaces to yield problems of the same types but of much smaller sizes, and then solve the reduced problems by direct methods, which is either a secular equation solver (in the case of LGopt) or an eigensolver (in the case of QEPmin). We provide convergence analysis for the proposed algorithms and present error bounds. The sharpness of the error bounds is demonstrated by examples, although in applications the algorithms often converge much faster than the bounds suggest. Finally, we apply the new algorithms to semi-supervised learning in the context of constrained clustering.

}, issn = {2708-0579}, doi = {https://doi.org/10.4208/csiam-am.2021.nla.01}, url = {http://global-sci.org/intro/article_detail/csiam-am/18884.html} }
TY - JOUR T1 - Linear Constrained Rayleigh Quotient Optimization: Theory and Algorithms AU - Yunshen Zhou , AU - Zhaojun Bai , AU - Ren-Cang Li , JO - CSIAM Transactions on Applied Mathematics VL - 2 SP - 195 EP - 262 PY - 2021 DA - 2021/05 SN - 2 DO - http://doi.org/10.4208/csiam-am.2021.nla.01 UR - https://global-sci.org/intro/article_detail/csiam-am/18884.html KW - Quadratic programming, quadratic eigenvalue problems, Lanczos algorithms, constrained clustering. AB -

We consider the following constrained Rayleigh quotient optimization problem (CRQopt):

image.png

where $A$ is an $n×n$ real symmetric matrix and $C$ is an $n×m$ real matrix. Usually, $m$ « $n$. The problem is also known as the constrained eigenvalue problem in literature since it becomes an eigenvalue problem if the linear constraint $C$T$v=b$ is removed. We start by transforming CRQopt into an equivalent optimization problem (LGopt) of minimizing the Lagrangian multiplier of CRQopt, and then into another equivalent problem (QEPmin) of finding the smallest eigenvalue of a quadratic eigenvalue problem. Although these equivalences have been discussed in literature, it appears to be the first time that they are rigorously justified in this paper. In the second part, we present numerical algorithms for solving LGopt and QEPmin based on Krylov subspace projection. The basic idea is to first project LGopt and QEPmin onto Krylov subspaces to yield problems of the same types but of much smaller sizes, and then solve the reduced problems by direct methods, which is either a secular equation solver (in the case of LGopt) or an eigensolver (in the case of QEPmin). We provide convergence analysis for the proposed algorithms and present error bounds. The sharpness of the error bounds is demonstrated by examples, although in applications the algorithms often converge much faster than the bounds suggest. Finally, we apply the new algorithms to semi-supervised learning in the context of constrained clustering.

Yunshen Zhou, Zhaojun Bai & Ren-Cang Li. (2021). Linear Constrained Rayleigh Quotient Optimization: Theory and Algorithms. CSIAM Transactions on Applied Mathematics. 2 (2). 195-262. doi:10.4208/csiam-am.2021.nla.01
Copy to clipboard
The citation has been copied to your clipboard