对称锥规划的邻域跟踪算法

本文把艾文宝的邻域跟踪算法推广到对称锥规划, 定义中心路径的宽邻域N(τ, β), 并证明该邻域的一个重要性质, 该性质在算法的复杂性分析中起到关键作用. 取宽邻域N(τ, β) 中一点为初始点并采用Nesterov-Todd (NT) 搜索方向, 则该算法的迭代复杂界为O(√r logε^-1), 其中, r是EuclidJordan 代数的秩, ε是允许误差. 这是对称锥规划的宽邻域内点算法最好的复杂界.

Neighborhood-following algorithms for symmetric cone programming

The neighborhood-following algorithm of linear programming, developed by Ai, is extended to symmetric cones. We define a new wide neighborhood N(τ, β) and prove a key property which plays a crucial role in the complexity analysis. Staring with an initial point in N(τ, β), the complexity bound is O(√r logε^-1) for the Nesterov-Todd (NT) direction, where r is the rank of the associated Euclidean Jordan algebra and ε>0 is the required precision. Then, we get the best complexity bound of wide neighborhood interior-point algorithm for symmetric cone programming.