求解線性規(guī)劃的一種新的原始對(duì)偶內(nèi)點(diǎn)法

摘? 要：該文在線性規(guī)劃問題的目標(biāo)函數(shù)中增加二次項(xiàng)，并提出了一種新的原始對(duì)偶內(nèi)點(diǎn)法解該問題。該方法對(duì)增加二次項(xiàng)后的問題的KKT條件中的變量做代換。對(duì)新變量做凸松弛保證新變量元素全為正值。對(duì)互補(bǔ)性條件做凸松弛，互補(bǔ)性條件右側(cè)每一個(gè)分量為依賴于當(dāng)前迭代點(diǎn)相應(yīng)分量的松弛。數(shù)值實(shí)驗(yàn)表明，該文算法對(duì)解決線性規(guī)劃問題是有效的。

關(guān)鍵詞：線性規(guī)劃? 新的原始對(duì)偶內(nèi)點(diǎn)法? KKT? 條件? 互補(bǔ)性條件

中圖分類號(hào)：O221.1? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ? ? ? ? ? ? ? ? ? ? ?文章編號(hào)：1672-3791（2019）04（b）-0168-03

標(biāo)準(zhǔn)的線性規(guī)劃問題：

其中行滿秩。（P）的對(duì)偶問題是：

其中分別是等式和不等式約束的拉格朗日乘子。

Magasarian等[1]在（P）中加擾動(dòng)項(xiàng)：

其中。若（1）有唯一解，則存在充分小，當(dāng)時(shí)（1）的解是（P）的解。Gill等[2]在（P）中加擾動(dòng)項(xiàng)：

其中δ>0。Gill等用原始對(duì)偶障礙函數(shù)法解（2）。Wang等[8]在（P）中加擾動(dòng)項(xiàng)：

其中Xk是當(dāng)前迭代點(diǎn)。Wang等[8]用鄰近增廣拉格朗日同倫法解（3）。

Darvary[7]用加權(quán)路徑跟蹤內(nèi)點(diǎn)算法求解線性規(guī)劃問題。內(nèi)點(diǎn)法中Xz=τe互補(bǔ)性條件等于常向量τ∈R+，Darvary算法中Xz=w，w∈R+n不是常向量。

該文在線性規(guī)劃問題的目標(biāo)函數(shù)中增加二次項(xiàng)。受Darvary的啟發(fā)，提出一種新的原始對(duì)偶內(nèi)點(diǎn)法?；パa(bǔ)性條件右側(cè)每一個(gè)分量為依賴于當(dāng)前迭代點(diǎn)相應(yīng)分量的松弛。數(shù)值實(shí)驗(yàn)表明，該文算法對(duì)解決線性規(guī)劃問題是有效的。

該文結(jié)構(gòu)如下：第一節(jié)提出求解線性規(guī)劃的新模型并給出了相應(yīng)的算法：第二章為數(shù)值實(shí)驗(yàn);最后一部分是結(jié)束語及參考文獻(xiàn)。

1? 原始對(duì)偶正則內(nèi)點(diǎn)算法

原始對(duì)偶問題（P）-（D）的KKT條件是：

原始對(duì)偶問題（P）-（D）的嚴(yán)格可行集是：

（P）的目標(biāo)函數(shù)進(jìn)行松弛：

（5）的對(duì)偶問題是：

其中，原始對(duì)偶問題（5）（6）的KKT條件是：

其中是元素全為1的列向量。令，則：

其中V=diag（v）。對(duì)互補(bǔ)性條件和變量v做松弛：

令，上述方程變?yōu)椋?/p>

通過求解方程（8）的牛頓方程來找搜索方向

第三行左乘-Xk-1加到第一行得到：

△v可以通過下面的式子得到：

為了阻止迭代點(diǎn)太接近非負(fù)邊界，路徑追蹤算法要求每一個(gè)迭代點(diǎn)都滿足中心路徑的無窮范數(shù)鄰域：

同樣為了保證新算法產(chǎn)生的迭代點(diǎn)遠(yuǎn)離非負(fù)邊界，我們算法的中心路徑的鄰域定義為：

其中0<γ<1是給定常數(shù)。該文按如下方式產(chǎn)生下一次迭代點(diǎn)Wk+1（Xk+1，yk+1，vk+1）。通過（9）和（10）計(jì)算牛頓步，步長滿足：

下面給出新的原始對(duì)偶內(nèi)點(diǎn)算法。

算法 1

步驟1：初始正則參數(shù)，參數(shù)0<γ<1，停止ε>0準(zhǔn)則。選擇初始點(diǎn)保證，，k=0。

步驟2：若，收斂。

步驟3：通過方程（8）和（9）計(jì)算牛頓步。

步驟4：計(jì)算滿足

0且，的最大ak。這里。

步驟5：令

，選取擾動(dòng)系數(shù)

。返回步驟2。

假設(shè)：

（1）原始對(duì)偶問題的最優(yōu)解*有界;

（2）非空。

由對(duì)偶理論可知為原問題（P）和對(duì)偶問題（D）的解的充要條件是式（11）成立。因?yàn)閧ηk}是下降序列，當(dāng)η→0且*是有界值時(shí)，方程組的解將分別收斂于（P）和（D）的最優(yōu)解。

定理1? 算法1產(chǎn)生序列且有界。當(dāng)η→0時(shí)，方程組的解是原始對(duì)偶問題（P）-（D）的最優(yōu)解。

2? 數(shù)值實(shí)驗(yàn)

該章所有的數(shù)值測(cè)試都是在MATLAB-R2012a中進(jìn)行的，運(yùn)行環(huán)境為聯(lián)想電腦 （Intel（R） Core＼＼（TM） i5-3230M CPU 2.60GHz，4.00GB）。

數(shù)值實(shí)驗(yàn)的算例來自Netlib測(cè)試集。用算法1計(jì)算Netlib測(cè)試集。我們給出了算法1的實(shí)驗(yàn)結(jié)果，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析。

對(duì)于大部分問題來說，嚴(yán)格初始可行點(diǎn)很難找到。找嚴(yán)格初始可行點(diǎn)通常要對(duì)問題進(jìn)行變形，但是對(duì)問題進(jìn)行變形往往會(huì)讓問題變得更難求解。因此我們?cè)趯?shí)際計(jì)算中選取不可行初始點(diǎn)。不可行初始點(diǎn)僅要求X0>0，Z0>0。不可行初始點(diǎn)遵循Methora線性規(guī)劃初始點(diǎn)選取規(guī)則：

選取。我們得到：

因此初始點(diǎn)為和。文中表明生成的初始點(diǎn)滿足X0>0，Z0>0。

Friedlander等提出了新的正則化方法：

文中證明了當(dāng)ρ、δ取固定常數(shù)時(shí)算法收斂并且該算法在實(shí)際計(jì)算中也沒有要求滿足中心路徑。該文在實(shí)際計(jì)算中使用方程（11）求方向ρ=δ=10-10。

我們選取算法1的終止條件是：

其中ε=10-5。當(dāng)η→0時(shí)，v→z第三個(gè)條件就變成了對(duì)原始對(duì)偶問題的對(duì)偶間隙的限制。

表1表示算法1在Netlib測(cè)試集上的計(jì)算結(jié)果。第一列是Netlib測(cè)試問題的名稱，第二列是問題的維數(shù)，第三列是等式約束的個(gè)數(shù)，第四列是Netlib測(cè)試集網(wǎng)站提供的最優(yōu)值，第五列是算法1的迭代次數(shù)，第六列是算法1的最優(yōu)值。由表1可以看出算法1對(duì)解決線性規(guī)劃問題是有效的，且對(duì)每一個(gè)算例算法1的計(jì)算結(jié)果在一定誤差范圍內(nèi)。

3? 結(jié)語

該文在線性規(guī)劃問題的目標(biāo)函數(shù)中增加二次項(xiàng)并提出了一種新的原始對(duì)偶內(nèi)點(diǎn)算法。受到加權(quán)路徑追蹤算法的啟發(fā)，對(duì)增加二次項(xiàng)后的問題的KKT條件中的變量做變量代換。對(duì)變量代換后的KKT條件中的新變量做凸松弛保證新變量元素全為正值。對(duì)互補(bǔ)性條件做凸松弛，互補(bǔ)性條件右側(cè)每一個(gè)分量由相同數(shù)值松弛變?yōu)橐蕾囉诋?dāng)前迭代點(diǎn)相應(yīng)分量的松弛。數(shù)值實(shí)驗(yàn)表明，該文算法對(duì)解決線性規(guī)劃問題是有效的，但其收斂速度還有待研究。

參考文獻(xiàn)

[1] Mangasarian OL.Iterative Solution of Linear Programs[J].SIAM Journal on Numerical Analysis， 1979， 18（18）：606-614.

[2] Saunders M， Tomlin J. A.Solving regularized linear programs using barrier methods and KKT systems[D].SOL Report 96-4， Dept. of EESOR， Stanford University，1996.

[3] Friedlander MP.Orban DA primal-dual regularized interior-point method for convex quadratic programs[J].Mathematical Programming Computation，2012，4（1）：71-107.

[4] Chen S，Donoho DL，Saunders MA.Atomic decomposition by basis pursuit[J].SIAM Journal on Scientific Computing，1998，20（1）：33-61.

①通訊作者：張溪（1992，11—），女，漢族，河北辛集人，碩士研究生，研究方向：運(yùn)籌與優(yōu)化，E-mail：2645816447@qq.com。