不定二次规划的一个改进算法

不定二次规划的一个改进算法（共1篇）

1.不定二次规划的一个改进算法 篇一

1984年在美国Bell实验室工作的印度学者N.K.Karmarkar[1]提出了“投影尺度法”, 使线性规划出现了自单纯形方法问世以来最重要的一次突破。该算法不仅在理论上被证明是多项式算法, 而且在实际计算中也能与单纯形法相媲美, 尤其在大型问题的应用中, 它显示出能与单纯形法竞争的潜力, 从而打破了单纯形方法一统天下的格局。该方法的出现激起许多学者对内点算法的研究热情。以后许多学者将其算法进行了推广, 用来解决一些非线性规划问题。1989年, R.C.Monteiro和I.Adler[2]给出了用原对偶内点算法求解凸二次规划问题的一个版本, 并证明了其复杂度为O (n3L) , 其中迭代次数为O (nL) 。由于该算法对初始点的要求很严格, 这就给数值实验带来很大的困难。本文我们利用算法的基本思想, 在文献[3]给出线性规划原对偶算法数值实验的基础上, 给出凸二次规划原对偶算法的数值实验, 作为对原文的一个重要补充, 使得内点算法的应用更加广泛。

1 问题提出

凸二次规划原-对偶内点算法的思想是线性规划原-对偶内点算法的一种合理推广[4]。考虑下面的凸二次规划问题 (P) 及其对偶问题 (D) :

这里A是m×n阶的矩阵, 且假设A是行满秩矩阵, Q是n×n阶正定矩阵, b和c分别是m维和n维向量, z是对偶问题中加入的n维松弛变量。

对原对偶问题做出如下假设:

(i) 集合

(ii) 集合, 定义W={ (x, y, z) ;x∈S, (y, z) ∈T}, 和在线性规划中一样, 将对数障碍函数法扩展到凸二次规划中, 通过引入障碍因子μ>0, 我们有下面的问题:

s.t Ax=b, x>0, 其中μ>0, μ称为壁垒参数.则可得到该问题的K-K-T条件如下:

其中, X=diag (x1, x2, …, xn) , Z=diag (z1, z2, …, zn) , e= (1, 1, …, 1) T, 记上述系统的解 (x (μ) , y (μ) , z (μ) ) =ΔW (μ) ,

此时, 原问题与对偶问题的对偶间隙为:

显然当μ※0时, p (x) -d (x) ※0, 因此我们得到下面的定理:

定理1在假设条件 (i) , (ii) 下, 上述系统的解W (μ) , 当μ※0时, x (μ) , (y (μ) , z (μ) ) 分别收敛到原问题 (P) 和对偶问题 (D) 的最优解。

2 算法分析

为了给出算法, 对初始点的选择要求很严格:

原对偶内点算法要求初始点严格满足原可行性和对偶可行性, 而且要求初始点和障碍因子必须满足如下条件:

其中, 是欧式范数, θ是一个很小的正数, 如0.1

算法按下列要求更新障碍因子:

μk+1=μk (1-δ/n) , 其中δ是一个很小的正数, 如0.1。

算法的具体步骤如下:

Step1:选取初始点W 0= (x0, y0, z0) ∈W, 且满足 (*) 式, 给定θ, δ是小的正数, 如0.2, 0.1;给定终止误差ε>0, 置k=0;

Step2:计算对偶间隙 (x (k) ) Tz (k) ≤ε, 则停止迭代, x (k) 为 (P) 的近似解;否则转第三步;

Step3:令μk+1=μk (1-δ/n) , 计算ΔW (k) = (Δx, Δy, Δz) ;

Step4:W (k+1) =W (k) -ΔW (k) , k=k+1, 转第二步;

注1ΔW (k) = (Δx, Δy, Δz) 由用牛顿法解如下方程组确定:

注2关于该算法的收敛性参考文献[2,3,5]。

3 数值实验

例1考察如下的凸二次规划问题及其对偶问题:

给出一组初始解x (1) = (1/2, 9/2, 11/2) T, y (1) = (-15, 50) T, z (1) = (18, 2, 2) T。

取δ=0.1, θ=0.18, 则满足初始解的要求, 用MATLAB 7.0编程, 取ε=0.001, 运行结果如图1所示, 从运行结果可以看出, x越来越趋近最优解 (0, 5, 5) , 从函数图1上可以看出最优目标解趋近235。

例2考虑如下凸二次规划问题及其对偶问题:

给出一组初始解x (1) = (6, 4, 11, 1) T, y (1) = (-3, -3) T, z (1) = (2, 3, 1, 13) T, 取δ=0.1, θ=0.12, 则满足初始解的要求, 用MATLAB 7.0编程, 取ε=0.01, 运行结果如图所示, 过程同例1, 从运行图像上我们可以看出x越来越趋近接近最优解, 从函数图2上可以看出最优目标解趋近。

4 结束语

本文我们初步给出了文献[2]中关于凸二次规划原对偶内点算法的数值例子, 实验结果表明该算法从线性规划推广到凸二次规划后, 仍然具有很好的收敛性和稳定性。

参考文献

[1]Karmarkar N.A new polynomial time algorithm or linear program-ming.Combinatorica, 1984;4 (4) :373—395

[2]Monteiro R D C, Adleri.Interior path following primal-dual algorithm II:convex quadratic programming.Math Programming, 1989;44 (1) :43—66

[3]雍龙泉, 线性规划的原-对偶内点算法数值实验初步.科学技术与工程, 2007;7 (18) :4576—4579

[4]方述成, 普森普拉S.线性优化及扩展, 理论与算法.北京:科学出版社, 1994