半定规划的预估校正内点算法
2023-05-30
来源:易榕旅网
维普资讯 http://www.cqvip.com 第22卷第3期 北京机械工业学院学报 Vo1.22 No.3 2007年9月 Journal of Beijing Institute of Machinery Sep.2007 文章编号:1008—1658(2007)03—0034—03 半定规划的预估校正内点算法 黄静静,王爱文 (北京机械工业学院基础部,北京100085) 摘 要:半定规划有着广泛的应用领域,例如系统论,控制论,模式识别等领域。为了更 好地求解这些领域中遇到的半定规划问题,给出了半定规划的原始对偶预估校正内点算法。该算 法由不同的搜索方向构成,利用牛顿法得到了3个搜索方向,数值实验表明:基于NT方向的算法 最为稳健。 关键词:半定规划;内点算法;预估校正;牛顿法;搜索方向 中图分类号:O 221.2 文献标识码:A Predictor・-corrector Interior・-point algorithm for semidefinite programming HUANG Jing—jing,WANG Ai—wen (Division of Basic Courses,Beijing Institute of Machinery,Beijing 100085,China) Abstract:Semidefinite programming(SDP)has a wide range of applications,such as system theo— ry,control theory,mode recognition,etc.Primal—dual predictor—corrector interior—point algorithm is pres— ented to solve SDP problems in these fields.The algorithm is composed of diferent search directions,and three directions are given by using Newton method.Numerical test suggests that NT direction is most reli— able. Key words:semidefinite programming;interior—point algorithm;predictor—corrector;Newton method; search direction 半定规划与线性规划有着紧密的联系,但又有 很大区别。对于半定规划的研究,要追溯到20世纪 1半定规划的标准形式 40年代。从20世纪60年代开始,涌现出许多关于 半定规划的标准形式如下: 半定规划的理论和最优性条件的文章。1984年, minC・X Karmarkar¨ 把内点算法引入到线性规划,虽然其基 A ・ =b ,i=1,…,m (1) 本原理不是新的,但是其算法和随后发展起来的内 Xt>0 点法在实践中具有良好的表现,且具有多项式时间 其中b ∈R (i=1,…,m)为实数,“・”表示 复杂性,所以Karmarkar的文章在当时具有巨大的 Frobenius内积,即对任意A,B∈SR (SR 表示n 冲击力。1988年,Nesterov和Nemirovsky 获得了 阶实对称方阵的集合),(A,B)=A・B=tr(A B), 一个重大突破,他们证明了解线性规划的内点法原 ≥0(X>0)表示矩阵 为半正定(正定)矩阵,C, 则上可以推广到一切凸优化问题,而半定规划是一 A ∈SR (i=1,…,m)为n阶实对称矩阵。 类重要的凸优化问题,因而内点法适用。自20世纪 90年代初开始,人们对半定规划的兴趣逐渐增加。 2半定规划的搜索方向 半定规划的应用领域很广,比如组合优化、统计、结 像线性规划一样,大多数的半定规划的内点算 构优化、系统控制、统计学、电子工程、金融、模式识 法都可以看作是牛顿算法。在每一次迭代中,通过 别等领域。 在一个被称为中心路径的非线性方程系统中应用牛 收稿日期:2007—07—04 作者简介:黄静静(1978一),女,山东济宁人,北京机械工业学院基础部讲师,硕士,主要从事优化算法方面的研究。 维普资讯 http://www.cqvip.com 第3期 黄静静等:半定规划的预估校正内点算法 35 2州一 ~一P SXP (2d ) 文 。 A y r p㈩ b—Asvec(X), Rd C—S— A R =州一 (XS) (5) 这里A为一个维数为/Tt X ( +1)/2的矩阵, A =[svec(A ),…,svec(A )] 假设集合{A }是线性独立的,也就是说A是满 秩的。 为了证明搜索方向的存在唯一性,只需证明系 统(3)的如下同伦系统只有平凡解 f,0 A 0、r Ay 、 lA 0 I Il svec(AX)I=0 (6) 1 0 E F八svec(△ ) 引理2.1:当 和 正定时,矩阵E和F是非 奇异的。 引理2.2:当 和 正定,且 (XS)半正定 时,矩阵E F是正定的。 定理2.3:假设 和 是正定矩阵, (XS)半 正定,那么系统(6)一定有唯一解(Ay,AX,AS)∈ E X SR X SR 。 证明:由引理2.1知,当 和 是正定矩阵时, E是可逆的,使用块Gauss消去法将式(6)化为如下 Schur互补方程, (AE FA )Ay:0 (7) 因为E F被假定是正定的,且A行满秩,这意 味着(AE FA一 。)也是正定的,因而Ay=0是式 (7)的唯一解。 现在在(式6)中的第二个块等式里给出△ = 一smat(A Ay)=0,且第3块等式给出AX=一E FAS=0,这表明式(3)的解存在且唯一。 由此定理知,只要x和S是正定的,NT方向和 HKM方向就是存在唯一的,而AHO方向是个例外, 必须同时要求 (XS)半正定。 3一维搜索方法 首先给定前提条件:原问题和对偶问题存在 严格可行解。假定当前的迭代点为(X ,S ), X ’=(X ’) >0, ( )=(S ’) >0。下面讨论 如何选取步长Ol, ,使得下一步迭代点X “’=X +aAX>0.S ’=S ’+flAS>0 对 , ‘ 进行Cholesky分解得到: ( )儿 . ( ):GG 贝4 ( ’+ AX>0 f+吐一 AXLT>0 故 > ,用同样方法可确定 维普资讯 http://www.cqvip.com 36 北京机械工业学院学报 第22卷 4算法的计算步骤 上面得出了Mehrotra型的预估校正算法的步长 和方向,现在来描述一下整个算法的具体步骤: 5数值实验 5.1 实验问题的选取 ①随机半定规划:初始点不一定位于中心路径 上。 ①预估步 计算牛顿步长( , , ),在式(3)中的or被 定义为0 定义参数or: :②教育测试问题 max e d S.t. A—diag(d)≥0 【 -'r….广这里, …d≥0 面) lf=min(1, 南)为步长。 =min 1,这里的A是一个N x N正定矩阵。e=(1,1, 1 T这个问题也可以转化为含有rt×rt阶对称的 SDP问题,凡=2N。这个问题也可以选用可行的初 始点。 ②校正步 用上面确定的or和 ,计算牛顿步长(AX,Ay, AS)。 对于每次的10个用例,下=0.98在本章实验中 所使用的expon分别在各自方向中所对应的值如 r3 AHO 用下列各式来更新( ,Y,S)为( ,Y ,S ) 下:expon=J 1 HKM 【1 NT 5.2 实验结果 表1基于不同方向的采用固定步长的预估校正内点算法在求解各类SDP问题时的计算结果 注:表1中的 表示基于该方向的预估校正内点算法在求解所对应问胚时无效。 参考文献: [1]Karmarkar N K.A new polynomial time algorithm for linear programming[J].Combinatorica,1984 (4):373—395 gorithms for semidefinte programming[J].SIMA J Optim,1997(7):476—480 [6]Helmberg F Rendl,VANDERBEL R,Wolkowicz H.An interior-point method for semidefinite pro- [2]Nesterov Yu.Semidefinite relaxation and noncon. vex quadratic optimization[J].Optimization Meth. ods Software,1997(12):1—20 gramming[J]。SIAM J Optim,1996(6):342— 361 [3]Zhang Y.On extending some primal-dual interior. point algorithms for semidefinite programming [7]Kojima M,Shindoh J,Hara S.Interior-point meth- 0d for the monotone semidefinite linear comple- [J].SIAM J Optim,1997(7):663—678 [4]Alizadeh J A,Haeberly M.OVERTON,Prina1.dual interior-point methods for semidefinit program— ming:Convergence rate,stability and numerical mentarity problem in symmetirc matrices[J].sI- MA J Optim,1997(7):86—125 [8]Todd M J,Toh K C,Tutuncu R C.On the Nester- OV-Todd Direction in SDP[J].SIAM J Optim, 1998,8(3):769—79 results[J].SIAM J Optim,1998(8):746—768 [5]MOTEIRO R D C.Primal-dual path.following a1.