English

运筹学学报 ›› 2014, Vol. 18 ›› Issue (4): 11-24.

• 运筹学 • 上一篇    下一篇

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

张景1, 白延琴1,*   

  1. 1. 上海大学理学院, 上海 200444
  • 收稿日期:2014-03-12 出版日期:2014-12-15 发布日期:2014-12-15
  • 通讯作者: 白延琴 E-mail:yqbai@shu.edu.cn
  • 基金资助:

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

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

ZHANG Jing1, BAI Yanqin1,*   

  1. 1. College of Science, Shanghai University, Shanghai 200444, China
  • Received:2014-03-12 Online:2014-12-15 Published:2014-12-15

PDF

621

被引次数

1

摘要： 基于一个自协调指数核函数, 设计求解二阶锥规划的原始-对偶内点算法. 根据自协调指数核函数的二阶导数与三阶导数的特殊关系, 在求解问题的中心路径时, 用牛顿方向代替了负梯度方向来确定搜索方向. 由于自协调指数核函数不具有``Eligible''性质, 在分析算法的迭代界时, 利用牛顿方法求解目标函数满足自协调性质的无约束优化问题的技术, 估计算法内迭代中自协调指数核函数确定的障碍函数的下降量, 得到原始-对偶内点算法大步校正的迭代界O(2N\frac{\log2N}{\varepsilon}), 这里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 gradient 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 exponential kernel function during the inner iteration. We obtain the complexity bound for large-update methods, which is O(2N \frac{\log 2N}{\varepsilon}), where N is the number of the second-order cones. 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.

中图分类号: