标题： 线性约束瑞利商优化：理论与算法 显示英文标题

标题： Linear Constrained Rayleigh Quotient Optimization: Theory and Algorithms

摘要： 我们考虑以下约束瑞利商优化问题 (CRQopt) $$ \min_{x\in \mathbb{R}^n} x^{T}Ax\,\,\mbox{subject to}\,\, x^{T}x=1\,\mbox{and}\,C^{T}x=b, $$ 其中 $A$是一个 $n\times n$实对称矩阵，而 $C$是一个 $n\times m$实矩阵。 通常， $m\ll n$。 在文献中，这个问题也被称为约束特征值问题，因为如果移除线性约束 $C^{T}x=b$，它就变成了一个特征值问题。 我们首先将 CRQopt 等价地转换为一个优化问题，称为 LGopt，即最小化 CRQopt 的拉格朗日乘数，然后是一个称为 QEPmin 的问题，即寻找二次特征值问题的最小特征值。 尽管这些等价性已经在文献中讨论过，但似乎这是首次对这些等价性进行严格的证明。 然后我们提出通过兰佐斯过程使用 Krylov 子空间投影方法来数值求解 LGopt 和 QEPmin。 基本思想类似于对称特征值问题的兰佐斯方法，即首先将 LGopt 和 QEPmin 投影到 Krylov 子空间上，以产生相同类型但规模小得多的问题，然后通过某些直接方法求解这些约简后的问题，这要么是某种超越方程求解器（在 LGopt 的情况下），要么是特征值求解器（在 QEPmin 的情况下）。 所产生的算法称为兰佐斯算法。 我们对所提出的方法进行了收敛性分析并得到了误差界。 虽然在应用中该方法通常比界限所暗示的收敛得更快，但通过人工例子展示了误差界的紧性。 最后，我们将兰佐斯算法应用于约束聚类背景下的半监督学习。 显示英文摘要

摘要： We consider the following constrained Rayleigh quotient optimization problem (CRQopt) $$ \min_{x\in \mathbb{R}^n} x^{T}Ax\,\,\mbox{subject to}\,\, x^{T}x=1\,\mbox{and}\,C^{T}x=b, $$ where $A$ is an $n\times n$ real symmetric matrix and $C$ is an $n\times m$ real matrix. Usually, $m\ll n$. The problem is also known as the constrained eigenvalue problem in the literature because it becomes an eigenvalue problem if the linear constraint $C^{T}x=b$ is removed. We start by equivalently transforming CRQopt into an optimization problem, called LGopt, of minimizing the Lagrangian multiplier of CRQopt, and then an problem, called QEPmin, of finding the smallest eigenvalue of a quadratic eigenvalue problem. Although such equivalences has been discussed in the literature, it appears to be the first time that these equivalences are rigorously justified. Then we propose to numerically solve LGopt and QEPmin by the Krylov subspace projection method via the Lanczos process. The basic idea, as the Lanczos method for the symmetric eigenvalue problem, is to first reduce LGopt and QEPmin by projecting them onto Krylov subspaces to yield problems of the same types but of much smaller sizes, and then solve the reduced problems by some direct methods, which is either a secular equation solver (in the case of LGopt) or an eigensolver (in the case of QEPmin). The resulting algorithm is called the Lanczos algorithm. We perform convergence analysis for the proposed method and obtain error bounds. The sharpness of the error bound is demonstrated by artificial examples, although in applications the method often converges much faster than the bounds suggest. Finally, we apply the Lanczos algorithm to semi-supervised learning in the context of constrained clustering.