运筹学学报 ›› 2012, Vol. 16 ›› Issue (4): 112-124.

• 运筹学 • 上一篇    

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

楼烨1, 2    高越天1   

  1. 1.   上海大学数学系 2.  上海科学技术职业学院
  • 出版日期:2012-12-15 发布日期:2012-12-15
  • 通讯作者: 楼烨

Some results of convex programming complexity

LOU Ye1,2  GAO Yuetian1   

  1. 1. Department of Mathematics, Shanghai University 2. Shanghai Vocational College of Science and Technology
  • Online:2012-12-15 Published:2012-12-15
  • Contact: LOU Ye

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

关键词: 凸规划, 自和谐障碍函数, 熵规划, 最优化复杂性

Abstract: Recently a number of papers were written that present low-complexity interior-point methods for different classes of convex programs. To guarantee the polynomiality 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.

Key words: convex programming, self-concordant barrier functions, entropy programming, optimization complexity

中图分类号: