摘要
基于不可行内点法和预估-校正算法的思想,提出两个新的求解二阶锥规划的内点预估-校正算法.其预估方向分别是Newton方向和Euler方向,校正方向属于Alizadeh-Haeberly-Overton(AHO)方向的范畴.算法对于迭代点可行或不可行的情形都适用.主要构造了一个更简单的中心路径的邻域,这是有别于其它内点预估-校正算法的关键.在一些假设条件下,算法具有全局收敛性、线性和二次收敛速度,并获得了O(rln(ε0/ε))的迭代复杂性界,其中r表示二阶锥规划问题所包含的二阶锥约束的个数.数值实验结果表明提出的两个算法是有效的.
Based on the ideas of infeasible interior-point methods and predictor-corrector algorithms,two interior-point predictor-corrector algorithms for second-order cone programming（SOCP） were presented.They use the Newton direction and the Euler direction as the predictor directions,respectively.The corrector directions belong to the category of the Alizadeh-Haeberly-Overton（AHO） directions.The two new algorithms were suitable to cases of feasible and infeasible interior iterative points.A simpler neighborhood of central path for the SOCP was proposed,which was the pivotal difference from other interior-point predictor-corrector algorithms.Under some assumptions,the algorithms possess global,linear and quadratic convergence.The complexity bound O（rln（ε0/ε）） was obtained,where r denotes the number of second-order cones in SOCP problem.The numerical results show that the proposed algorithms are effective.
出处
《应用数学和力学》
EI
CSCD
北大核心
2011年第4期497-508,共12页
Applied Mathematics and Mechanics
基金
国家自然科学基金资助项目(71061002
11071158)
广西自然科学基金资助项目(0832052
2010GXNSFB013047)
关键词
二阶锥规划
不可行内点算法
预估-校正算法
全局收敛性
复杂性分析
second-order cone programming
infeasible interior-point algorithm
predictor-corrector algorithm
global convergence
complexity analysis
