線性規(guī)劃基于修正牛頓方向的寬鄰域內(nèi)點(diǎn)算法

汪威威，劉紅衛(wèi)，畢紅梅

（1.西安電子科技大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，西安710126；2.西安工業(yè)大學(xué)理學(xué)院，西安 710032；3.空軍工程大學(xué)理學(xué)院，西安 710051）

線性規(guī)劃基于修正牛頓方向的寬鄰域內(nèi)點(diǎn)算法

汪威威1，2，劉紅衛(wèi)1，畢紅梅3

（1.西安電子科技大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，西安710126；2.西安工業(yè)大學(xué)理學(xué)院，西安 710032；3.空軍工程大學(xué)理學(xué)院，西安 710051）

通過修正經(jīng)典寬鄰域算法的搜索方向，提出一種新的求解線性規(guī)劃問題的寬鄰域內(nèi)點(diǎn)算法，并對(duì)算法進(jìn)行收斂性分析，證明了該算法具有經(jīng)典寬鄰域算法的迭代復(fù)雜性界O（n L）.數(shù)值實(shí)驗(yàn)表明算法是有效的.

線性規(guī)劃；內(nèi)點(diǎn)算法；寬鄰域算法；多項(xiàng)式復(fù)雜性

0 引 言

考慮線性規(guī)劃問題（LP）及其對(duì)偶問題：

1 寬鄰域內(nèi)點(diǎn)算法

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

其中t∈（0，1）為中心參數(shù).

2 算法分析

3 迭代復(fù)雜性

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

證明：對(duì)偶測(cè)度

4 數(shù)值試驗(yàn)

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

表1 算法1的數(shù)值結(jié)果Table 1 Results of algorithm 1

表2 Ai算法的數(shù)值結(jié)果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］ 艾文寶.線性規(guī)劃的鄰域跟蹤算法［J］.中國科學(xué)A輯：數(shù)學(xué)，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］ 劉長河，劉紅衛(wèi)，朱見廣.具有O（）復(fù)雜性的Mehrotra型預(yù)估－矯正算法［J］.吉林大學(xué)學(xué)報(bào)：理學(xué)版，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—），男，漢族，博士研究生，講師，從事最優(yōu)化理論與算法的研究，E－mail：weiwei.wang2007＠163.com.通信作者：劉紅衛(wèi)（1967—），男，漢族，博士，教授，博士生導(dǎo)師，從事最優(yōu)化理論及其應(yīng)用的研究，E－mail：hwliu＠m(xù)ail.xidian.edu.cn.

國家自然科學(xué)基金（批準(zhǔn)號(hào)：61072144；61179040）.

趙立芹）