凸二次半定规划一个新的路径跟踪算法

作者：谢琴; 黎健玲^*

来源：玉林师范学院学报, 2019, 40(02): 26-39.

DOI：10.13792/j.cnki.cn45-1300/z.2019.02.005

• 凸二次半定规划
• 中心路径
• NT方向
• 路径跟踪算法
• 迭代复杂性

给出了求解凸二次半定规划一个原始-对偶路径跟踪算法。引进了中心路径函数,在每次迭代中,基于牛顿法和对称化技术计算NT方向作为搜索方向,证明了满NT步的可行性以及中心函数在新迭代点的性质。在一定条件下算法经0 (n1/2log[(n+1/4)η0/ε])次迭代后得到一个ε-最优解。