单调线性矩阵互补问题的势函数约减法.doc
《单调线性矩阵互补问题的势函数约减法.doc》由会员分享,可在线阅读,更多相关《单调线性矩阵互补问题的势函数约减法.doc(10页珍藏版)》请在三一文库上搜索。
1、精品论文大全单调线性矩阵互补问题的势函数约减法崔娜南京航空航天大学理学院,江苏南京 (210016)摘要:线性矩阵互补问题是从欧式空间下的线性互补问题推广得到的,最早是由 M.Kajima 等人在中提出的,他们同时给出了对于该问题的内点法的理论框架及若干算法。本文构造了 一个势函数约减函数,借用路径跟踪法的思想构造算法,并证明了该算法的可行性及收敛性。 关键词:单调线性矩阵互补问题; 中心路径; 势函数约减法0 引言单调线性互补问题可在多项式时间内求解,而且人们已经设计出了多种求解单调线性 互补问题的有效内点算法1。线性矩阵互补问题是从欧式空间下的线性互补问题推广得到的,最早是由 M.Kaji
2、ma 等 人在2中提出的,他们同时给出了对于该问题的内点法的理论框架及若干算法。本文构造了一个势函数约减函数,借用路径跟踪法的思想构造算法,并证明了该算法的可行性及收敛 性。1 线性矩阵互补问题-10-nn 本文用 R nn 表示全体 n 阶实对称矩阵的集合,用 S, S nn ,及 S nn 分别表示 n 阶实+ +对称矩阵,实对称半正定矩阵及实对称正定矩阵的集合;用 Tr ( X ) 表示矩阵 X 的迹,对X , Y Rnn , 定义内积为 X Y = Tr ( X T Y ) 。线性矩阵互补问题的一般形式是:求 X , Y S nn 使其满足:Y = L( X ) + Q, X O, Y
3、 O, 且X Y = 0+其中 Q S nn , L : S nn S nn 为线性算子,而 X O表示X S nn , O 表示零矩阵。(*)记 = ( X,Y ) S nn | Y = L( X ) + Q, X O, Y O ,+ = ( X,Y ) S nn | Y = L( X ) + Q, X O,Y O ,称 为问题(*)的可行域,称 + 为问题(*)的严格可行域。定义 1.1 若 L : S nn S nn , Y = L( X ) + Q, 满足 X Y 0, X S nn , 则称 L 为单调算子,而相应的问题(*)称为单调线性矩阵互补问题。本文采用记号如下:用 M 表示矩
4、阵 M 的谱范数;用数;用 I 表示单位矩阵。M表示矩阵 M 的 Frobenius 范F1122记C = ( X , Y ) + | X YX= I , 0 + ,N ( ) = ( X , Y ) + |11X 2 YX 2 I , 0 + F1 ,n 11 2= ( X , Y ) + | i ( X 2 YX 2 ) i=1 , 0 0, 及初始点 ( X 0 , Y 0 ) N ( ), 令 k = 0 ;b)取( X ,Y ) = ( X k ,Y k ), 求 解(dX , dY )的 线 性 方 程 组 : D1 2 dXD1 2 + D1 2 dYD1 2 = D1 2 (
5、X 1 Y )D1 2dY = L(dX )(2.1)其中D = X 1 2 ( X 1 2YX 1 2 )1 2 X 1 2 , =nn + , = X Y 。 L 为线性算子。此方称组n称为 Nesterov-Todd 方程3,4中给出求解此方程组的一种有效数值方法。c)记 X = X + dX , Y = Y + dY*, =D1/ 2 X 1 D1/ 2,D1 2 ( X 1 Y )D1 2F ( 0,1) 为常数,求 f ( X,Y ) =min *0, f ( X ,Y )d)令 Xk +1*= X ,Yk +1*= Y ;e)若 X k +1 Y k +1 ,则停;否则,令 k
6、= k + 1,转(b)。3可行性及收敛性分析下面在假定 L为单调线性算子 的条件下,讨论用上述算法求解问题(*)时可行性及 收敛性。为此,先给出以下引理。+ 引理 3.1 设 X ,Y S nn , D = X 1 2 ( X 1 2YX 1 2 )1 2 X 1 2 ,则有(1)D1/ 2 XD1/ 2 = D1/ 2YD1/ 2 ;(2) X Y =引理 2 3.2 若1 + t 0, 则存在ln (1 + t ) t 。D1/ 2 XD1/ 2。2F引理 2 3.3 若 X S nn满足 X 1, 则有X。ln det ( I + X ) Tr ( X ) F2 (1 X )+ 引理
7、3.4 设 X ,Y S nn , D = X 1 2 ( X 1 2YX 1 2 )1 2 X 1 2 则有D1 2 ( X 1 Y )D1 2F3 22D1/2 X 1D1/2 。定理 3.1 设 ( X ,Y ) + , ( dX , dY ) 是方程组(2.1)的解,X = X + dX , Y = Y + dY ,则当 =D1/ 2 X 1 D1/ 2D1 2 ( X 1 Y )D1 22F(3.1)时, ( X ,Y ) +。这里 ( 0,1)为常数。证明由定理 2.1 有22D1 2UD1 2+D1 2VD1 2D1 2 ( X 1 Y )D1 2从而当 按(3.1)式取值时,F
8、FF X 1 2 dXX 1 2 = X 1 2 D1 2 D1 2 dXD1 2 D1 2 X 1 2 D1 2 X 1 D1 2D1 2 dXD1 2F= D1 2 X 1D1 2D1 2 ( X 1 Y )D1 2F同理可证当 按(3.1)式取值时 1 。(3.2) Y 1 2 dYY 1 2 1,故+ +X = X + dX = X 1 2 (I + X 1 2 dXX 1 2 ) X 1 2 S nn ,+ +Y = Y + dY = Y 1 2 (I + Y 1 2 dYY 1 2 )Y 1 2 S nn ,于是有 ( X ,Y ) + 。1定理 3.2 在与定理 3.3.1 相同
9、的条件下,若取 =, =4n,n + 则有f ( X ,Y ) f ( X ,Y ) ,1这里 =。12证明f ( X ,Y ) f ( X ,Y ) = ( n + ) ln ( X + dX ) (Y + dY ) ln det ( X + dX ) ln det (Y + dY ) ( n + ) ln ( X Y ) + ln det X + ln det Y() ( X dY + Y dX ) 2 dX dY = n + ln 1 + X YX Y ln det ( I + X 1/ 2 dXX 1/ 2 ) ln det ( I + Y 1/ 2 dYY 1/ 2 )从而由引理 3
10、.2 及引理 3.3 有 ( n + ) ( X dY + Y dX )f ( X ,Y ) f ( X , Y ) + 2 ( n + ) dX dY(1 1)22 X 1/ 2 dXX 1/ 2X YX Y2 Y 1/ 2 dYY 1/ 2Tr ( X1dX ) +(F Tr (Y)1dY ) +(F)2 1 X 1/ 2 dXX 1/ 22 1 Y 1/ 2 dYY 1/ 222 ( n + ) ( n + )= Tr ( XdY + YdX ) Tr X dX + Y dY+ dX dY X Y X Y X 1/ 2 dXX 1/ 2 Y 1/ 2 dYY 1/ 2+ F + F (3
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 单调 线性 矩阵 互补 问题 函数 减法
链接地址:https://www.31doc.com/p-3624709.html