 Operations Research and Fuzziolgy 运筹与模糊学, 2013, 3, 35-39 http://dx.doi.org/10.12677/orf.2013.34006 Published Online November 2013 (http://www.hanspub.org/journal/orf.html) An Extension of Kantorovich Inequality with an Application in the Analysis of Steepest Decent Method* Wentao Cao, Yong Xia LMIB of the Ministry of Education, School of Mathematics and System Sciences, Beihang University, Beijing Email: dearyxia@gmail.com Received: Apr. 29th, 2013; revised: Oct. 15th, 2013; accepted: Oct. 20th, 2013 Copyright © 2013 Wentao Cao, Yong Xia. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Abstract: Based on Kuhn-Tucker condition in optimization theory, we extend the canonical Kantorovich inequality. As an application , the analysis on the conv ergence rate of steepest descent for minimizing a posi- tive definite quadratic func tion is extended for the positive semi-definite case. Keywords: Kantorovich Inequality; Kuhn-Tuck er Condition; Steepest Descent; Convergence Rate Kantorovich 不等式的推广及其在最速下降法 分析中的应用* 曹文涛，夏 勇 北京航空航天大学数学与系统科学学院，数学、信息与行为教育部重点试验室，北京 Email: dearyxia@gmail.com 收稿日期：2013 年4月29 日；修回日期：2013 年10 月15 日；录用日期：2013 年10 月20 日 摘 要：本文利用最优化理论中经典的 Kuhn-Tucker 条件证明并推广了 Kantorovich不等式。作为应用， 将极小化正定二次函数的最速下降法的收敛速度分析推广到半正定情形。 关键词：Kantorovich 不等式；Kuhn-Tucker 条件；最速下降法；收敛速度 1. 引言 Kantorovich 不等式以前苏联著名的经济学家、数学家、诺贝尔奖得主 Leonid Kantorovich的名字命名，在 最优化理论、统计分析中有重要应用[1,2]。 定理 1：(Kantorovich)设A为 正定阵， nn1 和n 分别为其最大和最小特征值，则对任意非零向量 x，有 2 TT1 1 2 T1 4 n n xAx xAx xx 有趣的是，Kantorovich 不等式是如下 Cauchy-Schwarz不等式[1,2] 2 TTT1 x xxAxxA x *资助信息：国家自然科学基金 ( 11001006 ) 。 Copyright © 2013 Hanspub 35  曹文涛，夏 勇 Kantorovich不等式的推广及其在最速下降法分析中的应用 的“逆”形式，即对任意 ，Kantorovich不等式与 Cauchy-Schwarz 不等式可以整合成 0x 2 TT1 1 21 14 n Tn xAx xAx xx Kantorovich不等式有很多推广[2,3]，比如将 1n 向量 x 替换成 np 矩阵 x 等。其中一个推广如下： 定理 2：(Greub-Rheinboldt)设 A 和 为两个正定阵，且 B A BBA ，记 1n 和1n 分别为 A 和 的特征值，则对任意非零向量 B x ，有 2 T2 T2 11 2 T11 4 nn nn xAx xBx xABx 需要指出的是，定理 2的估计并不紧。Kantorovich 不等式中令 x为12 12 ABy ，令 A为1 A B，则有 2 11 T2 T211 11 211 1 T11 1 2 4 nn nn AB AB xAx xBxABAB AB ABABAB x ABx 1 (1) 其中 1 1 A B ， 1 n A B 分别为 1 A B的最大和最小特征值。注意到式(1)上界分别是 1 1 A B 和 1 n A B 的递 增函数和递减函数，利用 11 1 1 1 nnn AB AB 放大替换便得到 Greub-Rheinboldt 不等式。 Kantorovich不等式一个著名的应用是刻画了最速下降法的收敛性速度。 本文我们利用最优化中的 Kuhn-Tucker 条件给出了 Kantorovich不等式一个新的证明，该证明方法同时推广 了Kantorovich 不等式，最后，作为推广的 Kantorovich 不等式的应用，我们将目前对极小化正定二次函数的最 速下降法收敛性分析推广到了半正定情形。 2. Kantorovich不等式的推广 本节中我们推广 Kantorovich不等式，得到如下主要结果： 定理 3：设 A和B为n阶半正定阵，且 A BBA ，记和分别为A和B的特征值，则 有 12 ,,, n aa a12 ,,, n bb b 2 TT 2 Tmax, ,0 4 ij ij ijij ijijii ijij xAx xBxba abaa bbbaabab aabb xx 其中且， 证明：我们考虑最优化问题 TT 2 T max x Axx Bx xx 由于分子和分母是 x的齐次函数，所以可以归一化，同时由于 A BBA ，矩阵 A ， 有相同的特征向量， 因此，上述问题等价为 B 22T 11 max s.t. 1 nn ii ji ii axbxx x (2) 其Kuhn-Tucker条件为 22 11 , 1,2,,, 1 nn iijiji iii ii axbxbxaxxin xx T Copyright © 2013 Hanspub 36  曹文涛，夏 勇 Kantorovich不等式的推广及其在最速下降法分析中的应用 据此可得 设 2 . ji 22 11 2nn ii ji ii ax bx *2 11 :0, , nn iii ii I ixyaxzbx 其中 2 恰为最优目标函数值。进一步，Kuhn-Tucker条件可化简为如下必要条件： (3) 记 * 2. ji by azyziI ， * Card I 为I*中元素的个数，下面分别根据 * Card I 进行讨论。 1) *** 00 Card 1. I iI iIii 假设，则任意有 。因此 000 , 1,. iii x ya zb 此时，问题(2)的最优值为 2) * 00 01,2, , max ii in ab ** 12 Card 2.. I iIiI设和 (3)等价为 112 2 2 iiii by azby azyz 下面分如下几种情况讨论。 a) 若 ， ，问题(2)的最优解为 b) 若2 i ，由(3)知道 ，即 121 , iiii bbaa 2 11 则由 22 1 ii xx 知,z ii ya b 12 00 max ii ab 01,2, ,in 121 , iii bbaa 0y112 2 222 10 n iii iii iaxaxax ， 由于，我们有，此时最优值为 2 i优值 2 ** 0. 12 iIiI和12 0 ii aa c) 若，类似可知最为0. 121 , iii bbaa d) 若 且 ii ba 1 i b1 22 i a 121 , iiii bbaa 奇异，此时(3)无解。 2 e) 若 ， 121 , iiii bbaa11 22 ii ii ba ba 非奇异。解 Kuhn-Tucker 条件方程组(3)，得 12 12 ii ii ba ab y 12 12 12 12 2 2 ii ii ii ii bb ba ab zaa 此时，问题(2)的最优解为 12 12 12 1212 2 , max 4 ii ii ii iiii ba ab aabb Copyright © 2013 Hanspub 37  曹文涛，夏 勇 Kantorovich不等式的推广及其在最速下降法分析中的应用 3) 注意到(3)左边的系数矩阵的阶为 * Card 3I * Card 2I ，而右边项均相等。因此该系数矩阵的任何一 行均为其它两行(权和为 1)的加权组合，否则无解。对该系数矩阵分 讨论： a) 该系数矩阵存有两行线性无关。如果满足 2)中情形 d)，那么无解；如果满足 2)中情形e)，那么这两行已 然确定了唯一解。 知(3)的解同于 2) 中情 意两行线性相关，且满足 2)中情形 b)。则系数矩阵的所有行的 列均相等，进一步类比 2)中 阵任意两行线性相关，且满足 2)中情形 c)。此时同上讨论，系数矩阵的所有行的 列均相等且 为0 下列情况 b) 该系数矩阵任意两行线性相关，且满足 2)中情形 a)。则系数矩阵的所有行均相等，易 形a)。 c) 该系数矩阵任i 情形 b)可知所有的列均为 0，同时(3)的最优值为 0. d) 该系数矩 a i a i ，同时(3)的最优值为 0. 综合 1)、2)和3)，问题(2)的目标最优值为 b 2 max, ,0 4ij ij aabb ij ij ijij ijijii ba abaa bbbaabab 其中且， 定理证毕。 作为定理 3的推论，Kantorovich不等式立得证明： 2 2 TT1 2 12 2 T12 11 max ji xAx xAx ,1 max,1 44 11 4 ij ij ij ij j i xx 3. 推广 Kantorovich 不等式的在最速下降法分析中的应用 记对称矩阵 A的Moore-Penrose广义逆为 1,0 0, 0 A A ，对 A的特征值 ， 的相应特征值为 作为定理 3的推论，我们有 定理 4：设 A为 阶半正定阵，记 n1r 为A的正特征值，则对任意非零向量 x， TT 2 1 2 T1 4r x r xAx xAx x 本节应用定理 4推广最速下降法收敛速度分析。设 f x为半正定二次函数，Hessen 阵为G，极小化 f x的 使用精确步长的最速下降法迭代公式为 *,0xxg T 1 TT T ,0 ,0 ,0 k k kkk k kk kkk kkk xg gGg gg xggGg gGg 如果 如果 如果 其中 为 f x k g 在 k x 处的梯度， * x 为最优解。上述迭代或者有限步内发散到负无穷，或者有限步中止并得到最 优解 * x ，或者收敛到最优解 * x ，且 *0gx 由Taylor 展开，有 *** 1 2 f xfx xxGxx Copyright © 2013 Hanspub 38  曹文涛，夏 勇 Kantorovich不等式的推广及其在最速下降法分析中的应用 Copyright © 2013 Hanspub 39 则 * 1 ** 11 TT ** TT 2 TT ** T* TT 1 2 1 2 11 22 k kk kk kk kk kk kk kk kk kk kk kk k kk kk fx fx xxGxx gg gg xgxGxgx gGggGg gggg T k x x GxxgGxxgGg gGggGg 由于 ** k kk k Gxxgx gxgxg 所以 2 T ** 1T 1 2 kk kk kk gg fxfx fxfx g Gg 又因为 T T* kk kk * g Ggx xGGGx x 所以 2 T ** 1TT 1kk kk kkk k gg fxfxfx fx g Gg g Gg 即有 2 ** 1 11 r kk r f xfx fxfx 其中 10 r 为G所有正特征值。上述不等式刻画了函数值的 k f x收敛到最优值 * f x 看到， 的线性收敛速 度， G正定的二次函数情形，参见[4] 广的结论我们收敛速度与 G 的零特征值个数似乎没有关系，不过如果只有一个非零特征值，那么仅一步迭代即可收敛。 本文探讨 Kantorovich 不等式。指出推广之一的Greub-Rheinboldt 不等式比 Kantorovich 不等式本身来得更 用最优化理论中经典的 Kuhn-Tucker 条件证明并实质推广了Kantorovich不等式。作为应用，将极小 化正定二次函数的最速下降法的收敛速度分析推广到了半正定情形。 [2] 王松桂, 吴密霞, 贾忠贞(2006) 矩阵不等式. 科学出版社, 北京. direct proof and a generalization for a Kantorovich type inequality. Linear Algebra and its Applications, 397, [4] 刘红英, 夏勇, 周水生 (2012) 数学规划基础. 北京航空航天大学出版社, 北京. 教科书中的类似结果只是针对 。从该推 4. 结论 弱。本文利 参考文献 (References) [1] 匡继昌 (2010) 常用不等式. 山东科学技术出版社, 济南. [3] Huang, J. and Zhou, J. (2005) A 185-192. |