弧搜索內點算法

楊喜美，劉紅衛，劉長河

（1.西安電子科技大學 數學系，西安710071；2.河南科技大學 數學與統計學院，河南 洛陽471003）

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

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

1 預備知識

考慮如下標準形式的原－對偶線性規劃問題：

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

求解（P）和（D）的最優值等價于求解下列系統：

用xs＝μe，μ＞0代替系統（1）的第三個等式，得到（1）的擾動系統：

如果（P）和（D）的嚴格可行集

并且A行滿秩，即rank（A）＝m，則系統（2）存在唯一解（x（μ），y（μ），s（μ））.所有的（x（μ），y（μ），s（μ））形成一個拓撲路徑，稱為中心路徑：

本文用一個橢圓ω近似中心路徑C，ω的表達式為

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

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

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

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

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

其中

利用正交性

有eTχ（α）＝0.進一步，有

2 算法及復雜性分析

算法1 弧搜索內點算法.

算法步驟如下：

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

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

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

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

對式（11）兩邊同時取模平方，得

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

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

其中第二個不等式成立是因為式（9）.

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

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

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

下面給出算法1的多項式復雜度.

證明：由式（8），有

故由算法1產生的迭代點列｛（xk，yk，sk）｝滿足

又因為

3 數值試驗

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

表1 算法1和算法2的數值結果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.