康托洛维奇不等式是数值优化中收敛性分析的一个常用工具：
康托洛维奇不等式:设\(Q\)为正定对称阵，\(x \in \mathbb{R}^n\),则有
\[\frac{(x^Tx)^2}{(x^TQx)(x^TQ^{-1}x)}\geq\frac{4aA}{(a+A)^2} \]其中\(a,A\)分别为\(Q\)的最小和最大特征值。
证明：设\(Q\)的特征值位\(\lambda_1,\lambda_2,\dots,\lambda_n\),且$$0<a\leq \lambda_1\leq \lambda_2 \leq \dots \leq \lambda_n=A$$
设\(D^TQD=diag\{\lambda_1,\lambda_2,\dots,\lambda_n\},D^TD=I_n,x=Dy,y=(y_1,y_2,\dots,y_n)^T\),
于是：
其中\(\xi_i=y_i^2 / \sum_{i=1}^n y_i^2\)
已知\(0<a\leq \lambda_1\leq \lambda_2 \leq \dots \leq \lambda_n=A\),
令\(\xi=(\xi_1,\xi_2,\dots,\xi_n)^T\),\(\Lambda=(\lambda_1,\lambda_2,\dots,\lambda_n)^T,\mathop{\Lambda}\limits^{-}=(\frac{1}{\lambda_1},\frac{1}{\lambda_2},\dots,\frac{1}{\lambda_n})^T\)
于是问题就变成了
再设\(\forall \lambda \in [\lambda_1,\lambda_n],\Gamma(\lambda)=\{\xi : \Lambda^T\xi=\lambda,\xi_1+\xi_2+\dots+\xi_n=1\}\)
于是问题可以表示为:
如果先固定\(\lambda \in [\lambda_1,\lambda_n]\)，则
\(\mathop{min}\limits_{\xi \in \Gamma(\lambda)} \frac{1/(\Lambda^T\xi)}{(\mathop{\Lambda}\limits^{-})^T\xi} = \frac{1}{(\mathop{\Lambda}\limits^{-})^T\xi}\iff \mathop{max}\limits_{\xi \in \Gamma(\lambda)}(\mathop{\Lambda}\limits^{-})^T\xi=\xi_1\frac{1}{\lambda_2}+\xi_2\frac{1}{\lambda_2}+\dots+\xi_n\frac{1}{\lambda_n}\)
进一步发现：\(\xi_1\frac{1}{\lambda_2}+\xi_2\frac{1}{\lambda_2}+\dots+\xi_n\frac{1}{\lambda_n} \leq \frac{\xi_1+\xi_2+\dots+\xi_{n-1}}{\lambda_1}+\frac{\xi_n}{\lambda_n}=\frac{1-\xi_n}{\lambda_1}+\frac{\xi_n}{\lambda_n}\)
而上述不等式的等号可以取到，事实上，只需要使得:"\(\xi_1=\xi_n=1,\xi_2=\xi_3=\dots=\xi_{n-1}=0,\xi_1\lambda_1+\xi_n\lambda_n=\lambda\)"即可.
于是原问题相当于
而
\[\frac{1/\lambda}{\xi_1/\lambda_1+\xi_n/\lambda_n}=\frac{1/\lambda}{(\lambda_1+\lambda_n-\lambda)/(\lambda_1\lambda_n)}=\frac{\lambda_1\lambda_n}{\lambda(\lambda_1+\lambda_n-\lambda) }\geq \frac{4\lambda_1\lambda_n}{(\lambda_1+\lambda_n)^2} \]上述等号在\(\lambda=\frac{1}{2}(\lambda_1+\lambda_n)\)时成立.
由于\(\lambda_1=a,\lambda_n=A\),所以得到康托洛维奇不等式
同时本文也是对叶荫宇老师的《线性与非线性规划》一书8.2节对康托洛维奇不等式证明的补充：
