对称锥规划的邻域跟踪算法  

Neighborhood-following algorithms for symmetric cone programming

作　　者：刘长河[1] 刘红卫[2] 尚有林[1] 

机构地区：[1]河南科技大学数学与统计学院,洛阳471023 [2]西安电子科技大学理学院数学系,西安710071

出　　处：《中国科学：数学》2013年第7期691-702,共12页Scientia Sinica：Mathematica

基　　金：国家自然科学基金(批准号:61072144和61179040)资助项目

摘　　要：本文把艾文宝的邻域跟踪算法推广到对称锥规划,定义中心路径的宽邻域N(τ,β),并证明该邻域的一个重要性质,该性质在算法的复杂性分析中起到关键作用.取宽邻域N(τ,β)中一点为初始点并采用Nesterov-Todd(NT)搜索方向,则该算法的迭代复杂界为O(r(1/2)logε-1),其中,r是Euclid Jordan代数的秩,ε是允许误差.这是对称锥规划的宽邻域内点算法最好的复杂界.The neighborhood-following algorithm of linear programming, developed by Ai, is extended to symmetric cones. We define a new wide neighborhood N（T,β） and prove a key property which plays a crucial role in the complexity analysis. Staring with an initial point in N（T,β）, the complexity bound is O（√logc-1） for the Nesterov-Todd （NT） direction, where r is the rank of the associated Euclidean Jordan algebra and ε 〉 0 is the required precision. Then, we get the best complexity bound of wide neighborhood interior-point algorithm for symmetric cone programming.

关 键 词：对称锥规划 EUCLID JORDAN代数 邻域跟踪算法 宽邻域 内点法 多项式复杂性 

分 类 号：O221.2[理学—运筹学与控制论]