摘要
对于满足尺度李谱希茨条件的一类线性约束凸规划问题,提出了一种基于代数等价路径的原始-对偶内点算法,并讨论了计算复杂性.该算法可以在任一内部可行点启动,并且全局收敛,当初始点靠近中心路径时,此算法便成为中心路径跟踪算法,总迭代次数为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.
出处
《三峡大学学报（自然科学版）》
CAS
2007年第3期272-275,278,共5页
Journal of China Three Gorges University：Natural Sciences
基金
湖北省教育厅重点科研项目(D200613009)
关键词
凸规划
内点算法
路径跟踪法
代数等价路径
全局收敛性
多项式时间算法
convex programming
interior point algorithms
path-following method
algebraically equivalent path
global convergence
polynomial-time algorithms
