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

基于一个自协调指数核函数, 设计求解二阶锥规划的原始-对偶内点算法. 根据自协调指数核函数的二阶导数与三阶导数的特殊关系, 在求解问题的中心路径时, 用牛顿方向代替了负梯度方向来确定搜索方向. 由于自协调指数核函数不具有``Eligible'性质, 在分析算法的迭代界时, 利用牛顿方法求解目标函数满足自协调性质的无约束优化问题的技术, 估计算法内迭代中自协调指数核函数确定的障碍函数的下降量, 得到原始-对偶内点算法大步校正的迭代界O(2N\frac{\log2N}{\varepsilon}), 这里N是二阶锥的个数. 这个迭代界与线性规划情形下的迭代界一致. 最后, 通过数值算例验证了算法的有效性.

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

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.