关于分子和分母都是二次型的分式最值问题

sir_chen

对于形如$y={x^TAx}/{x^TBx}$最优化问题(x为n为列向量, A和B均为$n\timesn$的实矩阵), 我看到有些文献中说可以通过求解特征方程:

$Bx=lambda Ax$来加以解决, 其对应的最小特征值就是以上问题的最小值. 这个是怎样得到的, 谁能帮忙证明一下.

mathe

通常这里我们会将A,B都写成实对称阵，而且要求它们正定（不然问题可能不能转化）
在A,B都是实对称阵的情况下，存在可逆合同变换P使得B变成单位阵，也就是$B=P^TP$
由于${P^T}^-1AP^-1$也是对称阵，存在正交阵S使得$S^T{P^T}^-1AP^-1S$是对角阵D
而且$B=P^TSS^TP$
于是
$y={x^TP^TSS^T{P^T}^-1AP^-1SS^TPx}/{x^TP^TSS^T{P^T}^-1BP^-1SS^TPx}$
其中我们取$z=S^TPx$，得到$y={z^TDz}/{z^Tz}$
于是很显然，D对角线中最小的元素对应函数y的最小值，D对角线中最大元素对应y的最大值。
而它们都正好对应上面特征方程中的解。

sir_chen

上面的问题只需要B是正定对称的即可, A除了对称外无其他要求
对于正定对称矩阵B可以相似对角化为$B=C^TLambdaC$其中C为正交阵.
那么$B^{1/2}=C^TLambda^{1/2}C$
$y={x^TAx}/{x^TBx}$
$={(B^{1/2}x)^T(B^{-1/2})^TAB^{-1/2}(B^{1/2}x)}/{(B^{1/2}x)^T(B^{1/2}x)}$
$=({B^{1/2}x}/sqrt{(B^{1/2}x)^T(B^{1/2}x)})^T(B^{-1/2})^TAB^{-1/2}({B^{1/2}x}/sqrt{(B^{1/2}x)^T(B^{1/2}x)})$
$=z^TMz$
其中$z={B^{1/2}x}/sqrt{(B^{1/2}x)^T(B^{1/2}x)}), M=(B^{-1/2})^TAB^{-1/2}$
由于M是实对称矩阵, 因此有$M=P^TDP$, 其中D为对角矩阵
从而$y=z^TP^TDPz=(Pz)^TD(Pz)=\sum_{k=1}^nlambda_k(Pz)_k^2$
所以$lambda_min\sum_{k=1}^{n}(Pz)_k^2<=\sum_{k=1}^nlambda_k(Pz)_k^2<=lambda_max\sum_{k=1}^{n}(Pz)_k^2$
注意到$\sum_{k=1}^{n}(Pz)_k^2=(Pz)^T(Pz)=z^TP^zPz=z^Tz=1$
所以$lambda_min<=z^TMz<=lambda_max$
当z为M的特征向量时,$Mz=lambdaz, z^TMz=lambdaz^Tz=lambda$
也就是说z为特征向量时, $z^TMz$的值等于对应的特征值. 也就是说最值在特征向量处取得.
考察特征方程$(B^{-1/2})^TAB^{-1/2}z=lambdaz <=>Ax=lambdaBx$
从而此特征方程最小特征值对应的特征向量为最小值点, 最大特征值对应的特征向量为最大值点.