计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (20): 30-35.DOI: 10.3778/j.issn.1002-8331.2008.20.010
• 理论研究 • 上一篇 下一篇
孙秀萍1,郑丕谔2
收稿日期:
修回日期:
出版日期:
发布日期:
通讯作者:
SUN Xiu-ping1,ZHENG Pi-e2
Received:
Revised:
Online:
Published:
Contact:
摘要： 对线性规划的最优性条件，给出一个扩展系统，设计一个连续化的光滑型算法求解该系统。所设计的算法的全局收敛性不需要添加任何假设条件。在每一个迭代点处，只需要解一个线性方程组和做一次线性搜索，比现有求解线性规划问题的连续化方法具有更好的收敛性质。
关键词: 线性规划, 光滑型牛顿算法, 全局收敛, 严格互补解
Abstract: We propose a continuation method for solving the Linear Program（LP） by making use of an augmented system of its optimality conditions.The algorithm is shown to be globally convergent without requiring any assumption.It only needs to solve one system of linear equations and to perform one line search at each iteration.To the best of our knowledge this is the first continuation smoothing-type algorithm for solving the LP having the above desired convergence features.
Key words: linear program, smoothing Newton algorithm, global convergence, strictly complementary solution
孙秀萍1,郑丕谔2. 求解线性规划问题的光滑型牛顿算法[J]. 计算机工程与应用, 2008, 44(20): 30-35.
SUN Xiu-ping1,ZHENG Pi-e2. Smoothing Newton algorithm for solving linear programs problem[J]. Computer Engineering and Applications, 2008, 44(20): 30-35.
0 / 推荐
导出引用管理器 EndNote|Ris|BibTeX
链接本文: http://cea.ceaj.org/CN/10.3778/j.issn.1002-8331.2008.20.010
http://cea.ceaj.org/CN/Y2008/V44/I20/30
