吉林大学学报(理学版)
吉林大學學報(理學版)
길림대학학보(이학판)
JOURNAL OF JILIN UNIVERSITY(SCIENCE EDITION)
2014年
3期
408-412
,共5页
汪威威%刘红卫%毕红梅
汪威威%劉紅衛%畢紅梅
왕위위%류홍위%필홍매
线性规划%内点算法%宽邻域算法%多项式复杂性
線性規劃%內點算法%寬鄰域算法%多項式複雜性
선성규화%내점산법%관린역산법%다항식복잡성
linear programming%interior-point methods%wide-neighborhood algorithm%polynomial complexity
通过修正经典宽邻域算法的搜索方向,提出一种新的求解线性规划问题的宽邻域内点算法,并对算法进行收敛性分析,证明了该算法具有经典宽邻域算法的迭代复杂性界O(nL)。数值实验表明算法是有效的。
通過脩正經典寬鄰域算法的搜索方嚮,提齣一種新的求解線性規劃問題的寬鄰域內點算法,併對算法進行收斂性分析,證明瞭該算法具有經典寬鄰域算法的迭代複雜性界O(nL)。數值實驗錶明算法是有效的。
통과수정경전관린역산법적수색방향,제출일충신적구해선성규화문제적관린역내점산법,병대산법진행수렴성분석,증명료해산법구유경전관린역산법적질대복잡성계O(nL)。수치실험표명산법시유효적。
Based on modifying the search direction of classic wide-neighborhood algorithm,a new wide-neighborhood interior point algorithm for linear programming was proposed.The convergence analysis of the new algorithm was presented.And the algorithm enj oys the iteration bound O(nL), the same as the complexity result for classic wide-neighborhood interior point method.The numerical calculation shows that the new algorithm is efficient.