非线性互补问题的非精确算法分析

《非线性互补问题的非精确算法分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2非线性互补问题的非精确算法研究后期，互补问题在算法研究方面也取得了丰硕的成果：对于线性互补问题，主要的算法有直接法(如Lemke法，Cottle—Dentzig法)和迭代法(如Mangsarian法)等．对于非线性互补问题的研究，主要的算法有不动点法，内点法，同伦法，投影法，Newton法[1,21等，其算法的特征是：在迭代中需要求解线性互补子问题或者二次子规划．Lemke算法(1964年)是这个时期最著名的方法之一，主要有综述文献l101及部分优秀专著[1,2,11,12,181．互补问题是一类重要的最优化问题，目前在许多领域都有着广泛的应用，如工程物理，经济

2、和交通平衡等领域：同时，它也出现在约束优化的最优性条件中．因此，对互补问题的研究具有重要的意义，目前已产生了很多求解的方法，也得到了很好的全局和局部收敛性．1．2非线性互补问题的几种常见算法1．2．1光滑方程法用她w幻胛法求解．Mangasarian于1976年首先提出这种方程组‘291f，q,(Xl，巧(x))1G(x)=IiI=0(1．3)L矽(矗，FAx))／J缈(口，6)=口(1口一6I)一护(口)一秒(6)(1．4)鼻(z)是F(x)的第i个分量，江1，2，⋯，n．o(t)：R专R是一个严格递增的函数，满足o(o)=0，称妒(口，b)为NCP函数或势函数

3、，随后，Mangasarian证明了两个重要结定理1．11291假设汐(口，6)由(1．4)定义，则伊(口，b)=0§a≥0，b≥O，ab=0，进而x’∈R”为NCP(F)的解的充要条件为G(x‘)=0．定理1．2129]假设x’∈R”为NCP(F)的解，F(x)在x‘连续可微，若下面条件成(a)x+是非退化的，即x‘+F(x’)>0：(b)F(x)在x+的Jacobian矩阵VF(x‘)非奇异：第一章绪论3(C)o(t)连续可微、严格递增，且当f>0时，0’(，)十0’(O)>0，则G(x)在x‘的Jacobian矩阵VG(x’)非奇异的．显然，满足定理1．2的

4、函数秒(f)有很多，因此可以派生出许多光滑方程，并能用Newton法求解．同时，在满足定理1．2条件的解x’附近，算法超线性收敛．为了保证大范围收敛性，Wagon建立了一个同伦算法1421，即取目(f)=t3t。Subramanian提出了一个带阻尼因子的Gauss—Newton法【401，即取秒(，)=f．ItI，迭代格式为x”鲫=x+atp，P=(彳(x)+名(x)，)Vy(x)(1．5)其中口>0为步长，由非精确Armijo索求得，且沙(x)=专lla(x)112，旯(x)=缈(x)，A(x)=VG(x)r．VG(x)，1表示适当维数的单位矩阵．随后，凡∥括

5、和Lucidi用非单调搜索技术改进(1．4)，得到更好的结果．Xiu和Subramanian【4l】证明了：在F(x)连续可微时，(1．4)是大范围收敛的：在定理1．2的条件下，其点列局部超线性收敛．基于ⅣI凹函数(1．3)，Kanzow[2s1考虑如下光滑方程组(要求F至少是只一函数)H(x，少)=Y—F(x)缈(而，M)妒(吒，虬)=0(1．6)给出了Jacobian矩阵VH(x，Y)中NCP(F)的非解点处逆矩阵存在的几个充分条件，算法的大范围收敛性与水平集三(∥，广)=眠y)∈R2“IIIH(x,y)HH(∥，，)II)(1．7)的有界性有密切的联系．随后

6、，Tseng【451则把(1．6)变成日p(x，y)=(y-F(x))p矽(而，乃)矽(毛，％)=0。P≥0(1．8)进一np0的增长情况．利用光滑函数的彪∞6加相容性，Chen，Qi和Sun【201提出了光滑Newton法，也称为Jacobian光滑化方法，在每步迭代时求解混合Newton方程，并建立了全局收敛性与局部超线性或二阶收敛性，缺点是收敛性依赖于混合Newton方程系统的可解性，对一般非线性互补问题并不适用．后来，Kanzow和Pieper【26J通过引入梯度步，Ax七=一V沙(矿)4非线性互补问题的非精确算法研究提出了适用于一般非线性互补问题的Jac

7、obian光滑化方法．虽然种类方法有一定的优越性，但也有缺点，即使一个线性互补问题，转化后的方程组往往是非线性的，并且非线性程度比较高，这就使得理论和算法复杂化，而非光滑法恰恰弥补了这个不足．1．2．2非光滑方程法非光滑方程法就是把非线性互补问题转化为一个与之等价的非光滑方程组，然后利用广义Newton法求解．首先给出非光滑的几个概念：定义5f¨称函数H：R”一R”在点X∈R”是曰一可微的，如果存在一个度为1的正的齐次函数BH：R”专R“”(即对Vv∈R”，，>0，有BH(x)·tv=，·BH(x)·1，)，使得”llmv--,O塑≮产一o．——————1『忑——

8、——一5u