论文部分内容阅读
[摘要]本文主要是给出了非线性互补问题的一个新解法。首先通过引入一个隐式的拉格朗日函数把非线性互补问题转化为一个等价的无约束最优化问题，然后用广义模式搜索法来解决，并给出了此算法的收敛性。
[关键词]广义模式搜索 非线性互补 无约束最优化 收敛性
一、引言
经典的非线性互补问题NCP(F)的模型如下：
求解x∈Rn，使得x≥0,F(x)≥0,＜x,F(x)＞=0（1.1）
其中F∶Rn→Rn连续可微，＜•，•＞表示普通意义上的内积。
假设问题（1.1）的解集S≠Φ，在F(﹒)是仿射函数的情况下，（1.1）就退化成了线性互补问题。
二、原始非线性互补问题的转化
众所周知，NCP(F)可以看作求下面这个隐式拉格朗日函数的最小值问题：
其中α＞1是一个参数，(﹒)+表示在 Rn+上的正交投影。
特别地，在 Rn上，Mα(x)是非负的，假设在问题NCP(F)的解处Mα(x)取值为0。这样求解问题NCP(F)就可以转化为求解下面的无约束最优化问题：
可见若F(﹒)连续可微，则Mα(x)也是连续可微的。这里假设F(﹒)连续可微。
三、无约束最优化问题的广义模式搜索算法
1.搜索步和Poll步
在无约束最小化问题的模式搜索算法中的每一次迭代，都在一张网（下面所定义的Rn的一个离散集）上的有限个点处对目标函数进行估计，试图产生一个迭代点，使得该点的目标函数值比当前解处对应的目标函数值更小。这个过程称为搜索步。如果在搜索步失败，就进行Poll步，如果在这个过程中也没有找到改进的网点，则xk称为一个网格局部最优值。网格大小和迭代的更新规则见表3.1。首先给出[5]中的一些定义，当前网格定义如下：
其中Δk∈R+是网格大小的参数，nD是个有限数，表示矩阵D的列数，矩阵D的列看成Rn中的向量构成了Rn的一个正生成集。同时还要求D中的每个列向量都可以表示成一个可逆矩阵和一个整向量的乘积。Poll集以xk为中心，定义为Pk={xk+Δkd,d∈Dk}。（表示Dk的列选自D）是一个正生成矩阵。
假设3 .1 对d∈Dk都有βmin≤‖d‖≤βmax。
假设3.2 若min{Mα（xk+Δkd）｜d∈Dk}＜Mα(xk)，则必存在一个网格点xk+1,xk+1≠xk，使得Mα(xk+1)＜Mα(kx)，k=0,1,2,Λ.
算法3.1 设x0∈Rn，给定Δ0＞0.
a.计算Mα(xk)。
b.通过一种探测移动算法决定一个迭代点x+k.
c.计算ρk=Mα(xk)-Mα(x+k).
d.若ρk＞0，则令xk+1；否则，令xk+1=xk.
e.更新Dk和Δk.
2.参数更新规则
如果发现一个改进的网点，即：Mα(xk+1)＜Mα(xk)，则令Δk+1=λkΔk，λk∈(1,+∞)；
否则，即：若xk是网格局部最优值，则令Δk+1=θkΔk， θk∈(0,1).设,不依赖于.
引理3.1 对于k≥0，都存在一个rk∈Z，使得Δk=ιrkΔ0.
如[4]中所述，下述定理显然成立。
定理3.1由算法3.1产生的每一个迭代点XN都可以写成如下形式：
其中x0∈Rn是初始值，，α和β是互质的自然数，ι如Δk的更新规则中定义,Δ0是步长控制参数的初始值,D如当前网中定义。Zk∈Zn,k=0,Λ,N-1.
四、收敛结果
由算法3.1可以得到下面两个关于收敛结果的定理。
定理4.1 设Mα（x）是Rn上的连续可微函数，Mα（x）在Rn上利普希兹连续，常数为L,水平集LMα(x)(x0)是紧集。则GPS算法3.1产生的迭代满足
这个定理表明算法3.1产生的迭代序列至少有一个聚点是问题（1 .1）的稳定点。如果把条件加强就会得到下面定理4.2中更强的收敛结果。
假设4.1: 1.对于每一个网点
定理4.2假设上面三个条件成立， Mα(x)是Rn上的连续可微函数，Mα（x）在Rn上利普希兹连续，常数为L,水平集LMa(x)(x0)是紧集。则GPS算法3.1产生的迭代满足
参考文献：
[1]Cottle,R.,Giannessi,F., and Lions,J.L., Variational Inequalities and complementarity problems: Theory and Applications. Wiley. New York,New York,1980.
[2]Pang,J.s., complementarity problems, Handbook of Global Optimization, Edited by R.Horst and P.pardalos. Kluwer Academic Publishers, Boston, Massachusetts, 1995.271-338.
[3]Cottle, R.,Pang,J.S., and Stone,R., The Linear Complementarity problem, Academic Press, New York, New York, 1992.
[4]V.Torczon,On the convergence of pattern search algorithms,SIAM J.Optim. 1997，（7）：1-25.
[5]T.G.Kolda,A.R.M.Lewis and V.Torczon,Optimization by direct search :a new perspectives on some classical and modern methods,SIAM REVIEW. 2003，（45）：,385-482.
（作者单位：天津科技大学理学院）
[关键词]广义模式搜索 非线性互补 无约束最优化 收敛性
一、引言
经典的非线性互补问题NCP(F)的模型如下：
求解x∈Rn，使得x≥0,F(x)≥0,＜x,F(x)＞=0（1.1）
其中F∶Rn→Rn连续可微，＜•，•＞表示普通意义上的内积。
假设问题（1.1）的解集S≠Φ，在F(﹒)是仿射函数的情况下，（1.1）就退化成了线性互补问题。
二、原始非线性互补问题的转化
众所周知，NCP(F)可以看作求下面这个隐式拉格朗日函数的最小值问题：
其中α＞1是一个参数，(﹒)+表示在 Rn+上的正交投影。
特别地，在 Rn上，Mα(x)是非负的，假设在问题NCP(F)的解处Mα(x)取值为0。这样求解问题NCP(F)就可以转化为求解下面的无约束最优化问题：
可见若F(﹒)连续可微，则Mα(x)也是连续可微的。这里假设F(﹒)连续可微。
三、无约束最优化问题的广义模式搜索算法
1.搜索步和Poll步
在无约束最小化问题的模式搜索算法中的每一次迭代，都在一张网（下面所定义的Rn的一个离散集）上的有限个点处对目标函数进行估计，试图产生一个迭代点，使得该点的目标函数值比当前解处对应的目标函数值更小。这个过程称为搜索步。如果在搜索步失败，就进行Poll步，如果在这个过程中也没有找到改进的网点，则xk称为一个网格局部最优值。网格大小和迭代的更新规则见表3.1。首先给出[5]中的一些定义，当前网格定义如下：
其中Δk∈R+是网格大小的参数，nD是个有限数，表示矩阵D的列数，矩阵D的列看成Rn中的向量构成了Rn的一个正生成集。同时还要求D中的每个列向量都可以表示成一个可逆矩阵和一个整向量的乘积。Poll集以xk为中心，定义为Pk={xk+Δkd,d∈Dk}。（表示Dk的列选自D）是一个正生成矩阵。
假设3 .1 对d∈Dk都有βmin≤‖d‖≤βmax。
假设3.2 若min{Mα（xk+Δkd）｜d∈Dk}＜Mα(xk)，则必存在一个网格点xk+1,xk+1≠xk，使得Mα(xk+1)＜Mα(kx)，k=0,1,2,Λ.
算法3.1 设x0∈Rn，给定Δ0＞0.
a.计算Mα(xk)。
b.通过一种探测移动算法决定一个迭代点x+k.
c.计算ρk=Mα(xk)-Mα(x+k).
d.若ρk＞0，则令xk+1；否则，令xk+1=xk.
e.更新Dk和Δk.
2.参数更新规则
如果发现一个改进的网点，即：Mα(xk+1)＜Mα(xk)，则令Δk+1=λkΔk，λk∈(1,+∞)；
否则，即：若xk是网格局部最优值，则令Δk+1=θkΔk， θk∈(0,1).设,不依赖于.
引理3.1 对于k≥0，都存在一个rk∈Z，使得Δk=ιrkΔ0.
如[4]中所述，下述定理显然成立。
定理3.1由算法3.1产生的每一个迭代点XN都可以写成如下形式：
其中x0∈Rn是初始值，，α和β是互质的自然数，ι如Δk的更新规则中定义,Δ0是步长控制参数的初始值,D如当前网中定义。Zk∈Zn,k=0,Λ,N-1.
四、收敛结果
由算法3.1可以得到下面两个关于收敛结果的定理。
定理4.1 设Mα（x）是Rn上的连续可微函数，Mα（x）在Rn上利普希兹连续，常数为L,水平集LMα(x)(x0)是紧集。则GPS算法3.1产生的迭代满足
这个定理表明算法3.1产生的迭代序列至少有一个聚点是问题（1 .1）的稳定点。如果把条件加强就会得到下面定理4.2中更强的收敛结果。
假设4.1: 1.对于每一个网点
定理4.2假设上面三个条件成立， Mα(x)是Rn上的连续可微函数，Mα（x）在Rn上利普希兹连续，常数为L,水平集LMa(x)(x0)是紧集。则GPS算法3.1产生的迭代满足
参考文献：
[1]Cottle,R.,Giannessi,F., and Lions,J.L., Variational Inequalities and complementarity problems: Theory and Applications. Wiley. New York,New York,1980.
[2]Pang,J.s., complementarity problems, Handbook of Global Optimization, Edited by R.Horst and P.pardalos. Kluwer Academic Publishers, Boston, Massachusetts, 1995.271-338.
[3]Cottle, R.,Pang,J.S., and Stone,R., The Linear Complementarity problem, Academic Press, New York, New York, 1992.
[4]V.Torczon,On the convergence of pattern search algorithms,SIAM J.Optim. 1997，（7）：1-25.
[5]T.G.Kolda,A.R.M.Lewis and V.Torczon,Optimization by direct search :a new perspectives on some classical and modern methods,SIAM REVIEW. 2003，（45）：,385-482.
（作者单位：天津科技大学理学院）