非线性互补问题计算机实现

摘 要：分析了非线性互补问题求解困难，利用粒子群算法并结合极大熵函数法给出了该类问题的一种新的有效算法。该算法首先利用极大熵函数将非线性互补问题转化为一个无约束最优化问题，然后应用粒子群算法来优化该问题，计算机程序实现表明该算法是有效的。

关键词：计算机实现；非线性互补问题；粒子群算法

中图分类号：O224 文献标识码：A

Abstract：According to a class of nonlinear complementary problems difficult a new evolution algorithm is proposed this algorithm combines with maximum entropy function method.Firstly，the maximum entropy function is used to transform the nonlinear complementary problems into unconstrained optimization problem.Then particle swarm optimization algorithm（PSO） is applied to solving the unconstrained optimization problem.Lastly，computer procedure realization show that the proposed new algorithm has effectiveness.

Keywords：computer realization；nonlinear complementary problem；PSO

1 引言（Introduction）

经典的非线性互补问题[1]就是求一个向量使得

互补问题是数学规划的一个基本问题，在工程和经济等领域也有重要应用[3-5]，其算法研究引起广泛重视[6]：如非光滑法、内点法等。内点法对单调的互补问题具有多项式复杂界限，即算法的执行时间在最坏的情况下为问题规模的多项式函数。但在计算机不易实现，原因是初始点难以找到。非光滑牛顿法是将互补问题通过NCP函数转化为解方程组的问题，它的奇妙之处在于将包含等式和不等式的三个条件化为只含一个等式的问题，但基于可微的NCP函数的方程组在退化解处（互补问题（1）的退化解是指对某坐标下标有）的雅可比矩阵是奇异的[7]，这样牛顿法的局部快速收敛性不再具备。总的来说，目前这些算法都需要计算梯度，且需要给定初始点，并且针对解不唯一的互补问题，传统算法无法同时找到多个最优解。利用NCP函数把NCP（F）转化为非线性方程组的方法颇受青睐。如果函数满足条件

性质3：若二次连续可微，在光滑，则二阶连续可微且也为二次连续可微函数。

对于问题（6）我们采用粒子群优化算法[10，11]。粒子群优化（Particle Swarm Optimization，简称PSO）算法是由kennedy和Eberhart[12]于1995年提出，该方法对优化目标函数的连续可微性没有要求，且不需要给定初始点和梯度信息，简单易行，且收敛速度快，受到国内外学者的广泛关注。

2 粒子群算法（Particle Swarm Optimization algorithm（PSO））

文献[13]从量子力学角度，在标准PSO基础上提出量子粒子群算法（，

）。在中，由于粒子满足聚离态性质不同，粒子在整个可行解空间搜索寻求全局最优解。中，粒子群中每个粒子必须收敛于各自的随机点为粒子维数，粒子群按式（8）式（11）移动。

其中，为第个粒子在迭代中位置；为第个粒子本身所找到的局部最优位置；为整个种群目前找到的全局最优位置；为第个粒子最优位置中心；都是随机数；为收缩扩张系数，

为粒子当前迭代数；为种群规模，为最大迭代代数。

3 数值模拟（Numerical Simulation）

为了测试本文算法的求解性能，下面选择经典非线性互补问题，这些算例均来自MCPLIB算例库，其意义在文献 [14]中有所阐述。

本文参数设置如下：，，，程序由matlab编程，并在普通PC机上运行（CPU2.00GHz，内存1024MB），算法运行100次，取平均计算结果。限于篇幅，表1给出其中运行结果。

4 结论（Conclusion）

本文提出了混合量子粒子群优化算法来求解非线性互补问题。该方法主要是利用进化算法处理优化问题，计算结果更可靠。另外本文算法给求解非线性互补问题提供一种新途径，对于线性互补问题同样适用，同时也拓展了群智能优化算法适用范围。数值实验表明新算法的有效性。

参考文献（References）

[1] Harker P T，Pang Js.Finite-dimensional Variational inequality and nonliner complementarity problems， a survey review of theory，algorithms and applications[J].Math Prog，1990：161-220.

[2] F.Facchinei，J.S.Rang，Finite-demensional Variational inequalities and complenentarity problems Spring-Verlag NewYork，Inc.，2003.

[3] F.Faechinei and J-S.Pang，Finite-dimensional variationaline inequalities and complementarity probles，Springer-Verlag，NewYork，2003.endprint

[4] G.Isac.Complementarity problems，Springer-verlag，Berlin，1992.

[5] M.Cferris and J.S.pang，Engineering and ecomic aplications of complementarity problems，SIAM J.Review，39（1997），669-713.

[6] 修乃华，高自友.互补问题算法的新进展[J].数学进展，1999，28（3）：193-210.

[7] Wright S.J An infeasible-interior-point algorithm for linear complementarity problems[J].Mathematical programming Newton，1994，64：29-51.

[8] 李兴斯.一类不可微优化问题的有效解法.中国科学（A辑），1994，4（2）：371-377.

[9] 李兴斯.解非线性极大极小问题的凝聚函数方法[J].计算结构力学及其应用，1991（8）：85-92.

[10] He Q，WangL.An effective co-evolutionary particle swarm.optimization for constrained engineering design problems[J].Engineering Applications of Artifical Intelligence，2007，20（1）：89-99.

[11] Runarsson T P，Yao X.Stochastic ranking for constrained evolutionary optimization [J].IEEE Trans，Evol.Comput，2000，4（3）：284-294.

[12] Kennedy J，Eberhart R.particle swarm optimization [C]IEEE.International conference on Neural Networks，Peth，Australia，1995：1942-1948.

[13] Sun.Jun，Xu Feng-bin，Xu Wen-bo.Particle Swarm optimization with particles having quantum behavior[C].proc of congress on Evolutionary computation，2004：325-331.

[14] J.S.Pang and L.Qi Nonsmooth equations：motivation and algorithm，SIAM Optim.3，1993：443-465.

作者简介：

朱铁锋（1979-），男，硕士，讲师.研究领域：计算数学，程序实现.endprint

[4] G.Isac.Complementarity problems，Springer-verlag，Berlin，1992.

[5] M.Cferris and J.S.pang，Engineering and ecomic aplications of complementarity problems，SIAM J.Review，39（1997），669-713.

[6] 修乃华，高自友.互补问题算法的新进展[J].数学进展，1999，28（3）：193-210.

[7] Wright S.J An infeasible-interior-point algorithm for linear complementarity problems[J].Mathematical programming Newton，1994，64：29-51.

[8] 李兴斯.一类不可微优化问题的有效解法.中国科学（A辑），1994，4（2）：371-377.

[9] 李兴斯.解非线性极大极小问题的凝聚函数方法[J].计算结构力学及其应用，1991（8）：85-92.

[10] He Q，WangL.An effective co-evolutionary particle swarm.optimization for constrained engineering design problems[J].Engineering Applications of Artifical Intelligence，2007，20（1）：89-99.

[11] Runarsson T P，Yao X.Stochastic ranking for constrained evolutionary optimization [J].IEEE Trans，Evol.Comput，2000，4（3）：284-294.

[12] Kennedy J，Eberhart R.particle swarm optimization [C]IEEE.International conference on Neural Networks，Peth，Australia，1995：1942-1948.

[13] Sun.Jun，Xu Feng-bin，Xu Wen-bo.Particle Swarm optimization with particles having quantum behavior[C].proc of congress on Evolutionary computation，2004：325-331.

[14] J.S.Pang and L.Qi Nonsmooth equations：motivation and algorithm，SIAM Optim.3，1993：443-465.

作者简介：

朱铁锋（1979-），男，硕士，讲师.研究领域：计算数学，程序实现.endprint

[4] G.Isac.Complementarity problems，Springer-verlag，Berlin，1992.

[5] M.Cferris and J.S.pang，Engineering and ecomic aplications of complementarity problems，SIAM J.Review，39（1997），669-713.

[6] 修乃华，高自友.互补问题算法的新进展[J].数学进展，1999，28（3）：193-210.

[7] Wright S.J An infeasible-interior-point algorithm for linear complementarity problems[J].Mathematical programming Newton，1994，64：29-51.

[8] 李兴斯.一类不可微优化问题的有效解法.中国科学（A辑），1994，4（2）：371-377.

[9] 李兴斯.解非线性极大极小问题的凝聚函数方法[J].计算结构力学及其应用，1991（8）：85-92.

[10] He Q，WangL.An effective co-evolutionary particle swarm.optimization for constrained engineering design problems[J].Engineering Applications of Artifical Intelligence，2007，20（1）：89-99.

[11] Runarsson T P，Yao X.Stochastic ranking for constrained evolutionary optimization [J].IEEE Trans，Evol.Comput，2000，4（3）：284-294.

[12] Kennedy J，Eberhart R.particle swarm optimization [C]IEEE.International conference on Neural Networks，Peth，Australia，1995：1942-1948.

[13] Sun.Jun，Xu Feng-bin，Xu Wen-bo.Particle Swarm optimization with particles having quantum behavior[C].proc of congress on Evolutionary computation，2004：325-331.

[14] J.S.Pang and L.Qi Nonsmooth equations：motivation and algorithm，SIAM Optim.3，1993：443-465.

作者简介：

朱铁锋（1979-），男，硕士，讲师.研究领域：计算数学，程序实现.endprint