基于代数等价路径的一类线性约束凸规划问题的内点算法

An Interior Point Algorithm for a Class of Linearly Constrained Convex Programming Problem Based on Algebraically Equivalent Path

对于满足尺度李谱希茨条件的一类线性约束凸规划问题,提出了一种基于代数等价路径的原始-对偶内点算法,并讨论了计算复杂性.该算法可以在任一内部可行点启动,并且全局收敛,当初始点靠近中心路径时,此算法便成为中心路径跟踪算法,总迭代次数为O(nL),其中L是问题的输入长度,数值实验结果表明算法是有效的.

A primal-dual interior point algorithm based on algebraically equivalent path for linearly constrained convex programming problem which satisfies scaled Lipschitz condition is presented; and its computational complexity is discussed. It can start at any primal-dual interior feasible point, and enjoys the global conver- gence. If the Initial point is close to the central path, it becomes a central path-following algorithm and requires a total of O（√nL） number of iterations, where L is the input length. Numerical results show that the method is promising.