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

Primal-Dual Interior-Point Algorithm for Second-Order Cone Optimization Based on a Finite Barrier

作　　者：王国强[1] 

机构地区：[1]上海工程技术大学高职学院

出　　处：《运筹学学报》2007年第2期31-42,共12页Operations Research Transactions

基　　金：Project Sponsored by Shanghai Educational Committee Foundation(No.06NS031);Shanghai Pujiang Program (No.06RJ14039).

摘　　要：本文基于一个有限罚函数,设计了关于二阶锥优化问题的原始-对偶路径跟踪内点算法,由于该罚函数在可行域的边界取有限值,因而它不是常规的罚函数,尽管如此,它良好的解析性质使得我们能分析算法并得到基于大步校正和小步校正方法目前较好的多项式时间复杂性分别为O(N^(1/2)log N log N/ε)和O(N^(1/2)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 harrier 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 harrier function. The complexity hounds for large- and small-update methods are O（√log N log N/ε） and O（√Nlog N/ε）, respectively, where N denotes the number of second-order cones.

关 键 词：运筹学 二阶锥优化 原始-对偶内点算法 大步和小步校正方法 

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