弧搜索内点算法

杨喜美，刘红卫，刘长河

（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.