基于一个有限罚函数的二阶锥优化的原始-对偶内点算法

摘要

本文基于一个有限罚函数[2],设计了关于二阶锥优化问题的原始-对偶路径跟踪内点算法.由于该罚函数在可行域的边界取有限值,因而它不是常规的罚函数.尽管如此,它良好的解析性质使得我们能分析算法并得到基于大步校正和小步校正方法目前较好的多项式时间复杂性分别为O(√N log N log N/ε)和O(√N log N/ε),其中N为二阶锥的个数.%In this paper we present a primal-dual path-following interior-point algorithm for second-order cone optimization based on a finite barrier function which was first introduced in [2]. The barrier function is not a conventional one because it takes the finite value at the boundary of the feasible region. We analyze the algorithm and obtain the favorable complexity bounds of the algorithm in terms of the elegant analytic properties of the finite barrier function. The complexity bounds for large- and small-update methods are O(√N log N logN/ε) and O(√N log N/ε), respectively, where N denotes the number of second-order cones.