弧搜索內(nèi)點(diǎn)算法

楊喜美，劉紅衛(wèi)，劉長河

（1.西安電子科技大學(xué) 數(shù)學(xué)系，西安710071；2.河南科技大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，河南 洛陽471003）

內(nèi)點(diǎn)算法［1］是求解線性規(guī)劃的最有效方法之一［2］，它分為小步長算法和大步長算法.小步長算法具有較低的理論復(fù)雜度，但實(shí)踐性較差；大步長算法具有較高的理論復(fù)雜度，但實(shí)踐性較好.為了兼顧兩者的優(yōu)點(diǎn)，文獻(xiàn)［3－5］提出了高階矯正算法；文獻(xiàn)［6－7］提出了二階校正算法，這些算法都使用線搜索.文獻(xiàn)［8－9］提出了弧搜索內(nèi)點(diǎn)算法.文獻(xiàn)［8］通過數(shù)值試驗(yàn)表明弧搜索算法比一維搜索算法更好.但文獻(xiàn)［8－9］僅討論了小步長算法，本文考慮大步長算法，提出一種求解線性規(guī)劃的弧搜索大步長內(nèi)點(diǎn)算法.數(shù)值試驗(yàn)表明，該算法不僅具較好的實(shí)踐性，也具有較低的理論復(fù)雜度.

記e＝（1，…，1）T；‖x‖（‖x‖1）表示向量x∈?n的2－范數(shù)（1－范數(shù)）；對于向量x，s∈?n，xs∈?n表示對應(yīng)分量的乘；min（xs）表示xs∈?n的最小分量；對于x≥0，x1／2表示由x1／2i組成的向量；X＝diag（x）為向量x∈?n生成的對角矩陣，且xs∶＝Xs.

1 預(yù)備知識

考慮如下標(biāo)準(zhǔn)形式的原－對偶線性規(guī)劃問題：

其中：A∈?m×n；c，x，s∈?n；b，y∈?m.

求解（P）和（D）的最優(yōu)值等價(jià)于求解下列系統(tǒng)：

用xs＝μe，μ＞0代替系統(tǒng)（1）的第三個(gè)等式，得到（1）的擾動(dòng)系統(tǒng)：

如果（P）和（D）的嚴(yán)格可行集

并且A行滿秩，即rank（A）＝m，則系統(tǒng)（2）存在唯一解（x（μ），y（μ），s（μ））.所有的（x（μ），y（μ），s（μ））形成一個(gè)拓?fù)渎窂剑Q為中心路徑：

本文用一個(gè)橢圓ω近似中心路徑C，ω的表達(dá)式為

其中：a，b∈?2n＋m是橢圓ω的軸并且它們是正交的；c∈?2n＋m是橢圓ω的中心.

給定一點(diǎn)z＝（x（α0），y（α0），s（α0））在中心路徑上或者很接近中心路徑.為了計(jì)算a，b，c，α0，要求z的一階和二階導(dǎo)數(shù)滿足下列方程：

其中：μ＝xTs／n；σ∈（0，1）是中心參數(shù).

定理1［9］若（x（α），y（α），s（α））是通過點(diǎn)（x，y，s）∈ω的一個(gè)弧，并且它在（x，y，s）點(diǎn)處的一階和二階導(dǎo)數(shù)分別滿足式（4）和式（5），則有如下一個(gè)橢圓近似中心：

通過直接計(jì)算及g（α）＝1－cos（α），有

其中

利用正交性

有eTχ（α）＝0.進(jìn)一步，有

2 算法及復(fù)雜性分析

算法1 弧搜索內(nèi)點(diǎn)算法.

算法步驟如下：

1）如果（xk）Tsk≤ε，則算法終止；

為方便分析，省略指標(biāo)k并引入符號D＝X－1／2S1／2，其中x＞0，s＞0.

引理1［6］設(shè)u，v∈?n，則下列不等式成立：

證明：在方程（4）的第三個(gè)方程兩邊同乘（XS）－1／2，得

對式（11）兩邊同時(shí)取模平方，得

證明：在方程（5）的第三個(gè)方程兩邊同乘以（XS）－1／2，可得

對式（12）的兩邊同時(shí)取模平方，得

其中第二個(gè)不等式成立是因?yàn)槭剑?）.

由引理2和引理3，易得：

證明：由引理2～引理4及g（α）≤sin2（α），有

引理6 若（x，y，s）∈N（γ），定義如式（10），則

下面給出算法1的多項(xiàng)式復(fù)雜度.

證明：由式（8），有

故由算法1產(chǎn)生的迭代點(diǎn)列｛（xk，yk，sk）｝滿足

又因?yàn)?/p>

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

為了驗(yàn)證本文算法（算法1）的有效性，使用文獻(xiàn)［10］中線性規(guī)劃問題的測試函數(shù)，對比本文算法和文獻(xiàn)［11］中算法（記為算法2）的數(shù)值結(jié)果.通過自對偶嵌入［11］尋找可行初始點(diǎn)，使用 MATLAB R2011b編寫程序，硬件條件為Intel Core i3，3.10GHz，4Gb RAM微機(jī)測試.表1列出了算法1和算法2的數(shù)值結(jié)果，其中（m，n）表示問題的規(guī)模.算法1選取最優(yōu)參數(shù)σ＝0.05，γ＝0.1；算法2選取最優(yōu)參數(shù)β＝0.25.由表1可見，算法1的迭代次數(shù)比算法2減少了60.85%.

表1 算法1和算法2的數(shù)值結(jié)果Table 1 Results of algorithms 1and 2

［1］Karmarkar N.A New Polynomial－Time Algorithm for Linear Programming［J］.Combinatorica，1984，4（4）：373－395.

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

［3］Jansen B，Roos C，Terlaky T，et al.Improved Complexity Using Higher－Order Correctors for Primal－Dual Dikin Affine Scaling［J］.Math Program，1996，76（1）：117－130.

［4］Lahmam H，Cadou J M，Zahrouni H，et al.High－Order Predictor－Corrector Algorithms ［J］.Int J Numer Methods Engrg，2002，55（6）：685－704.

［5］Monteiro R D C，Adler I，Resende M G C.A Polynomial－Time Primal－Dual Affine Scaling Algorithm for Linear and Convex Quadratic Programming and Its Power Series Extension［J］.Math Oper Res，1990，15（2）：191－214.

［6］ZHANG Yin，ZHANG Detong.On Polynomiality of the Mehrotra－Type Predictor－Corrector Interior－Point Algorithms［J］.Math Program，1995，68（1／2／3）：303－318.

［7］Salahi M，Mahdavi－Amiri N.Polynomial Time Second－Order Mehrotra－Type Predictor－Corrector Algorithms［J］.Appl Math Comput，2006，183（1）：646－658.

［8］YANG Yaguang.Arc－Search Path－Following Interior－Point Algorithms for Linear Programming ［J／OL］.2009－08－14.http：／／www.optimization－onlin.org／DB＿FILE／2009／08／2375.pdf.

［9］YANG Yaguang.A Polynomial Arc－Search Interior－Point Algorithm for Convex Quadratic Programming［J］.Eur J Oper Res，2011，215（1）：25－38.

［10］Browne S，Dongarra J，Grosse E，et al.The Netlib Mathematical Software Repository［M］.Charlottesville：Corporation for National Research Initiatives，1995.