求解线性规划的一种新的原始对偶内点法

摘  要：该文在线性规划问题的目标函数中增加二次项，并提出了一种新的原始对偶内点法解该问题。该方法对增加二次项后的问题的KKT条件中的变量做代换。对新变量做凸松弛保证新变量元素全为正值。对互补性条件做凸松弛，互补性条件右侧每一个分量为依赖于当前迭代点相应分量的松弛。数值实验表明，该文算法对解决线性规划问题是有效的。

关键词：线性规划  新的原始对偶内点法  KKT  条件  互补性条件

中图分类号：O221.1                                文獻标识码：A                         文章编号：1672-3791（2019）04（b）-0168-03

标准的线性规划问题：

其中行满秩。（P）的对偶问题是：

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

Magasarian等[1]在（P）中加扰动项：

其中。若（1）有唯一解，则存在充分小，当时（1）的解是（P）的解。Gill等[2]在（P）中加扰动项：

其中δ>0。Gill等用原始对偶障碍函数法解（2）。Wang等[8]在（P）中加扰动项：

其中Xk是当前迭代点。Wang等[8]用邻近增广拉格朗日同伦法解（3）。

Darvary[7]用加权路径跟踪内点算法求解线性规划问题。内点法中Xz=τe互补性条件等于常向量τ∈R+，Darvary算法中Xz=w，w∈R+n不是常向量。

该文在线性规划问题的目标函数中增加二次项。受Darvary的启发，提出一种新的原始对偶内点法。互补性条件右侧每一个分量为依赖于当前迭代点相应分量的松弛。数值实验表明，该文算法对解决线性规划问题是有效的。

该文结构如下：第一节提出求解线性规划的新模型并给出了相应的算法：第二章为数值实验;最后一部分是结束语及参考文献。

1  原始对偶正则内点算法

原始对偶问题（P）-（D）的KKT条件是：

原始对偶问题（P）-（D）的严格可行集是：

（P）的目标函数进行松弛：

（5）的对偶问题是：

其中，原始对偶问题（5）（6）的KKT条件是：

其中是元素全为1的列向量。令，则：

其中V=diag（v）。对互补性条件和变量v做松弛：

令，上述方程变为：

通过求解方程（8）的牛顿方程来找搜索方向

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

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

为了阻止迭代点太接近非负边界，路径追踪算法要求每一个迭代点都满足中心路径的无穷范数邻域：

同样为了保证新算法产生的迭代点远离非负边界，我们算法的中心路径的邻域定义为：

其中0<γ<1是给定常数。该文按如下方式产生下一次迭代点Wk+1（Xk+1，yk+1，vk+1）。通过（9）和（10）计算牛顿步，步长满足：

下面给出新的原始对偶内点算法。

算法 1

步骤1：初始正则参数，参数0<γ<1，停止ε>0准则。选择初始点保证，，k=0。

步骤2：若，收敛。

步骤3：通过方程（8）和（9）计算牛顿步。

步骤4：计算满足

0且，的最大ak。这里。

步骤5：令

，选取扰动系数

。返回步骤2。

假设：

（1）原始对偶问题的最优解*有界;

（2）非空。

由对偶理论可知为原问题（P）和对偶问题（D）的解的充要条件是式（11）成立。因为{ηk}是下降序列，当η→0且*是有界值时，方程组的解将分别收敛于（P）和（D）的最优解。

定理1  算法1产生序列且有界。当η→0时，方程组的解是原始对偶问题（P）-（D）的最优解。

2  数值实验

该章所有的数值测试都是在MATLAB-R2012a中进行的，运行环境为联想电脑 （Intel（R） Core＼＼（TM） i5-3230M CPU 2.60GHz，4.00GB）。

数值实验的算例来自Netlib测试集。用算法1计算Netlib测试集。我们给出了算法1的实验结果，并对实验结果进行分析。

对于大部分问题来说，严格初始可行点很难找到。找严格初始可行点通常要对问题进行变形，但是对问题进行变形往往会让问题变得更难求解。因此我们在实际计算中选取不可行初始点。不可行初始点仅要求X0>0，Z0>0。不可行初始点遵循Methora线性规划初始点选取规则：

选取。我们得到：

因此初始点为和。文中表明生成的初始点满足X0>0，Z0>0。

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

文中证明了当ρ、δ取固定常数时算法收敛并且该算法在实际计算中也没有要求满足中心路径。该文在实际计算中使用方程（11）求方向ρ=δ=10-10。

我们选取算法1的终止条件是：

其中ε=10-5。当η→0时，v→z第三个条件就变成了对原始对偶问题的对偶间隙的限制。

表1表示算法1在Netlib测试集上的计算结果。第一列是Netlib测试问题的名称，第二列是问题的维数，第三列是等式约束的个数，第四列是Netlib测试集网站提供的最优值，第五列是算法1的迭代次数，第六列是算法1的最优值。由表1可以看出算法1对解决线性规划问题是有效的，且对每一个算例算法1的计算结果在一定误差范围内。

3  结语

该文在线性规划问题的目标函数中增加二次项并提出了一种新的原始对偶内点算法。受到加权路径追踪算法的启发，对增加二次项后的问题的KKT条件中的变量做变量代换。对变量代换后的KKT条件中的新变量做凸松弛保证新变量元素全为正值。对互补性条件做凸松弛，互补性条件右侧每一个分量由相同数值松弛变为依赖于当前迭代点相应分量的松弛。数值实验表明，该文算法对解决线性规划问题是有效的，但其收敛速度还有待研究。

参考文献

[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—），女，汉族，河北辛集人，硕士研究生，研究方向：运筹与优化，E-mail：2645816447@qq.com。