关于一些凸规划问题的复杂性研究结果(英文)

Some results of convex programming complexity

目前,已发表了大量研究各类不同凸规划的低复杂度的障碍函数方法的文章.利用自和谐理论,对不同的几类凸规划问题构造相应的对数障碍函数,通过两个引理证明这些凸规划问题相应的对数障碍函数都满足自和谐,根据Nesterov和Nemirovsky的工作证明了所给问题的内点算法具有多项式复杂性.

Recently a number of papers were written that present low-complexity interior-point methods for different classes of convex programs. To guarantee the poly- nomiality of the procedure, in this paper we show that the logarithmic barrier function associated with these programs is self-concordant. In other words, we will present two different lemmas with different logarithmic barrier functions and apply them to several classes of structured convex optimization problems, using the self-concordancy.