二阶锥规划的基于自协调指数核函数的原始-对偶内点算法  

Self-concordant exponential kernel function based interior point algorithm for second-order cone optimization

作　　者：张景[1] 白延琴[1] 

机构地区：[1]上海大学理学院,上海200444

出　　处：《运筹学学报》2014年第4期11-24,共14页Operations Research Transactions

基　　金：国家自然科学基金(No.11371242)

摘　　要：基于一个自协调指数核函数,设计求解二阶锥规划的原始-对偶内点算法.根据自协调指数核函数的二阶导数与三阶导数的特殊关系,在求解问题的中心路径时,用牛顿方向代替了负梯度方向来确定搜索方向.由于自协调指数核函数不具有"Eligible"性质,在分析算法的迭代界时,利用牛顿方法求解目标函数满足自协调性质的无约束优化问题的技术,估计算法内迭代中自协调指数核函数确定的障碍函数的下降量,得到原始-对偶内点算法大步校正的迭代界O(2N log2N/ε),这里N是二阶锥的个数.这个迭代界与线性规划情形下的迭代界一致.最后,通过数值算例验证了算法的有效性.Abstract This paper presents a primal-dual interior point algorithm for second-order cone optimization based on a new self-concordant （SC） exponential kernel function. By the special relationship between the second derivative and the third derivative of SC exponential kernel function, we use Newton direction to replace the negative gradien- t direction in solving the central path. Since the SC exponential kernel function does not satisfy the ＂Eligible＂ property, we use the technique of Newton method minimizing the unconstraint problem with SC object function in analyzing the complexity bound of algorithm. We estimate the decrease of proximity function which is defined by SC expo- nential kernel function during the inner iteration. We obtain the complexity bound forlarge-update methods, which is ε , where N is the number of the second-ordercones. This result coincides with the complexity bound in the case of linear optimization. Finally, we give some numerical examples to show the efficiency of algorithm.

关 键 词：二阶锥规划 核函数 内点算法 

分 类 号：O224[理学—运筹学与控制论]