康托洛维奇不等式是数值优化中收敛性分析的一个常用工具：
康托洛维奇不等式:设\(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\),
于是：
\[\begin{align*} \frac{(x^Tx)^2}{(x^TQx)(x^TQ^{-1}x)} & =\frac{(y^TD^TDy)^2}{(y^TD^TQDy)((y^TD^TQ^{-1}Dy)}\\ & =\frac{(\sum_{i=1}^n y_i^2)^2}{(\sum_{i=1}^n (\lambda_iy_i^2))(\sum_{i=1}^n (y_i^2/\lambda_i))}\\ & = \frac{1/(\sum_{i=1}^n \xi_i \lambda_i)}{\sum_{i=1}^n (\xi_i/\lambda_i)} \equiv \frac{\phi(\xi)}{\psi(\xi)}\end{align*}\]
其中\(\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\)
于是问题就变成了
\[\begin{align*} \mathop{min}\limits_{\xi} & \quad \frac{1/(\Lambda^T\xi)}{(\mathop{\Lambda}\limits^{-})^T\xi}\\ s.t. & \quad \xi_1+\xi_2+\dots+\xi_n=1\end{align*}\]
再设\(\forall \lambda \in [\lambda_1,\lambda_n],\Gamma(\lambda)=\{\xi : \Lambda^T\xi=\lambda,\xi_1+\xi_2+\dots+\xi_n=1\}\)
于是问题可以表示为:
\[\mathop{min}\limits_{\lambda \in [\lambda_1,\lambda_n]} \mathop{min}\limits_{\xi \in \Gamma(\lambda)} \frac{1/(\Lambda^T\xi)}{(\mathop{\Lambda}\limits^{-})^T\xi}\]
如果先固定\(\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\)”即可.
于是原问题相当于
\[\mathop{min}\limits_{\lambda \in [\lambda_1,\lambda_n],\xi_1+\xi_n=1} \quad \frac{1/\lambda}{\xi_1/\lambda_1+\xi_n/\lambda_n}\]
而
\[\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\),所以得到康托洛维奇不等式
\[\frac{(x^Tx)^2}{(x^TQx)(x^TQ^{-1}x)}\geq\frac{4aA}{(a+A)^2}\]
同时本文也是对叶荫宇老师的《线性与非线性规划》一书8.2节对康托洛维奇不等式证明的补充：
本文来自博客园，作者：来者可追2019，转载请注明原文链接：https://www.cnblogs.com/wjma2719/p/17251945.html