線性規劃基于修正牛頓方向的寬鄰域內點算法

汪威威，劉紅衛，畢紅梅

（1.西安電子科技大學數學與統計學院，西安710126；2.西安工業大學理學院，西安 710032；3.空軍工程大學理學院，西安 710051）

線性規劃基于修正牛頓方向的寬鄰域內點算法

汪威威1，2，劉紅衛1，畢紅梅3

（1.西安電子科技大學數學與統計學院，西安710126；2.西安工業大學理學院，西安 710032；3.空軍工程大學理學院，西安 710051）

通過修正經典寬鄰域算法的搜索方向，提出一種新的求解線性規劃問題的寬鄰域內點算法，并對算法進行收斂性分析，證明了該算法具有經典寬鄰域算法的迭代復雜性界O（n L）.數值實驗表明算法是有效的.

線性規劃；內點算法；寬鄰域算法；多項式復雜性

0 引 言

考慮線性規劃問題（LP）及其對偶問題：

1 寬鄰域內點算法

新的搜索方向（Δx，Δy，Δs）由下列方程解出：

其中t∈（0，1）為中心參數.

2 算法分析

3 迭代復雜性

定理1給定t，r∈（0，1），存在與n無關的常數δ，使得?k≥0，有μk＋1≤（1－δ／n）μk.

證明：對偶測度

4 數值試驗

表1和表2分別列出了算法1和Ai算法的數值結果.由表1和表2可見，相比Ai算法，算法1數值結果稍差，其原因是算法1未采用任何預估－矯正技術及中心參數更新策略.

表1 算法1的數值結果Table 1 Results of algorithm 1

表2 Ai算法的數值結果Table 2 Results of Ai’s algorithm

［1］ Roos C，Terlaky T，Vial J P.Theory and Algorithms for Linear Optimization：An Interior Point Approach［M］.Chichester：John Wiley ＆Sons，1997.

［2］ Kojima M，Mizuno S，Yoshise A.A Primal－Dual Interior Point Algorithm for Linear Programming［C］／／Progress in Mathematical Programming Interior－Point and Related Methods.New York：Springer－Verlag，1988：29－47.

［3］ Mizuno S，Todd M J，YE Yinyu.On Adaptive－Step Primal－Dual Interior－Point Algorithms for Linear Programming［J］.Math Oper Res，1993，18（4）：964－981.

［4］ 艾文寶.線性規劃的鄰域跟蹤算法［J］.中國科學A輯：數學，2004，34（1）：40－47.（AI Wenbao.Neighborhood－Following Algorithms for Linear Programming［J］.Science in China Ser A：Mathematics，2004，34（1）：40－47.）

［5］ 劉長河，劉紅衛，朱見廣.具有O（）復雜性的Mehrotra型預估－矯正算法［J］.吉林大學學報：理學版，2011，49（4）：633－637.（LIU Changhe，LIU Hongwei，ZHU Jianguang.Mehrotra－Type Predictor－Corrector Algorithm withO（）－Iteration Complexity［J］.Journal of Jilin University：Science Edition，2011，49（4）：633－637.）

［6］ ZHANG Lipu，XU Yinghong.A Full－Newton Step Interior－Point Algorithm Based on Modified Newton Direction［J］.Operations Research Letters，2011，39（5）：318－322.

［7］ Wright S J.Primal－Dual Interior－Point Methods［M］.Philadelphia：SIAM，1997.

［8］ YE Yinyu，Todd M J，Mizuno S.AnO（）－Iteration Homogeneous and Self－dual Linear Programming Algorithm［J］.Math Oper Res，1994，19（1）：53－67.

Wide－Neighborhood Interior－Point Algorithm Based on Modified Newton Direction for Linear Programming

WANG Weiwei1，2，LIU Hongwei1，BI Hongmei3
（1.SchoolofMathematicsandStatistics，XidianUniversity，Xi’an710126，China；2.SchoolofScience，Xi’anTechnologicalUniversity，Xi’an710032，China；3.SchoolofScience，AirForceEngineeringUniversity，Xi’an710051，China）

Based on modifying the search direction of classic wide－neighborhood algorithm，a new wideneighborhood interior point algorithm for linear programming was proposed.The convergence analysis of the new algorithm was presented.And the algorithm enjoys the iteration boundO（n L），the same as the complexity result for classic wide－neighborhood interior point method.The numerical calculation shows that the new algorithm is efficient.

linear programming；interior－point methods；wide－neighborhood algorithm；polynomial complexity

O221.1

A

1671－5489（2014）03－0408－05

10.13413／j.cnki.jdxblxb.2014.03.02

2013－08－29.

汪威威（1981—），男，漢族，博士研究生，講師，從事最優化理論與算法的研究，E－mail：weiwei.wang2007＠163.com.通信作者：劉紅衛（1967—），男，漢族，博士，教授，博士生導師，從事最優化理論及其應用的研究，E－mail：hwliu＠mail.xidian.edu.cn.

國家自然科學基金（批準號：61072144；61179040）.

趙立芹）