线性凸规划问题的一个势降不可行内点算法

A Potential Reduction and Infeasible Inner-point Algorithm for A Linear Convex Programming Problem

基于Tanabe-Todd-Ye势函数提出了求解线性凸规划问题的一个势降不可行内点算法,分析了算法的复杂度,并证明了在每一次迭代之后算法使用的势函数至少有一个正常数的下降量,从而说明了算法的多项式复杂性。

A potential reduction and infeasible inner-point algorithm for a linear convex programming problem is proposed based on Tanable-Todde-Ye potential function,the complexity of the algorithm is analyzed. It is demonstrated that after each iteration algorithm is used the reduction for at least one number is taken place,which indicates that there exists polynomial complication in the algorithm.