求解非线性P0互补问题的填充函数法
2016-06-14袁柳洋唐秋华贾世会
袁柳洋,唐秋华,贾世会
(1.武汉科技大学理学院,湖北 武汉,430065;2.武汉科技大学机械自动化学院,湖北 武汉,430081 )
求解非线性P0互补问题的填充函数法
袁柳洋1,唐秋华2,贾世会1
(1.武汉科技大学理学院,湖北 武汉,430065;2.武汉科技大学机械自动化学院,湖北 武汉,430081 )
摘要:首先利用光滑Fischer-Burmeister函数, 将非线性P0互补问题转化成相应的约束优化问题;然后对此约束优化问题构造出一种新的无参数的填充函数, 讨论了该填充函数的有关性质,并提出了求解非线性P0互补问题的填充函数算法。通过几个数值算例验证了该算法的有效性。
关键词:非线性互补问题;P0函数;Fischer-Burmeister函数;填充函数; 局部极小点;全局极小点
1问题描述
本文考虑如下形式的非线性互补问题(简写为NCP(F)):找到一个向量x*∈Rn, 满足
(1)
式中:F(x)∶Rn→Rn是一个非线性向量函数。若F(x)=Mx+q, 其中M∈Rn×n,q∈Rn, 则NCP(F)被称为线性互补问题, 简写为LCP(M,q)。若F是P0函数,即对任意的u,v∈Rn,u≠v, 存在下标k(1≤k≤n), 使得
(2)
同时成立, 则称NCP(F)为非线性P0互补问题。
非线性P0互补问题是单调互补问题和P函数互补问题的推广, 近年来受到许多学者的关注。求解非线性P0互补问题最常用的方法是牛顿法[1-2]、磨光算法[3]等, 而本文将提出另外一种求解方法——填充函数法。
在大多数求解非线性P0互补问题的算法中, 最普遍的做法是先通过NCP函数将非线性P0互补问题转化成一个方程组, 然后再用求解方程组的方法间接求解。本文则首先利用NCP函数中的光滑Fischer-Burmeister函数, 将非线性P0互补问题转化成相应的约束优化问题,然后根据填充函数的定义, 对此约束最优化问题构造出一种新的无参数的填充函数, 并分析讨论该填充函数的有关性质,最后建立求解非线性P0互补问题的填充函数算法。
2非线性P0互补问题的转化
minθ(x)
(3)
并且θ()=0。
(4)
式中:x=(x1,…,xn)T;F(x)=(F1(x),…,Fn(x))T。
(5)
否则, θ定义为
(6)
NCP函数有很多种, 其中非常重要的一种是Fischer-Burmeister函数:
(7)
(8)
令
(9)
并定义
(10)
显然H(z)=0⟺μ=0,x是NCP(F)的解。
上述方程组又可转化为如下的约束优化问题:
minf(z)=‖H(z)‖2
(11)
式中:‖·‖2为欧几里得范数;X={(μ,x)|μ>0,x∈Rn}。
若x*是NCP(F)的一个解, 当且仅当z*是问题(11)的全局最优解且最优值f(z*)=0。
3填充函数的构造及其性质分析
考虑问题(11), 在本文中做如下假设。
假设2NCP(F)的解集非空且有界。
下面给出填充函数的定义。
定义3[4]函数P(z,z*)被称为f(z)在局部极小点z*处的填充函数, 如果它满足:
(1)z*是P(z,z*)的一个严格局部极大点;
(2)对任意的z∈S1, 有P(z,z*)≠0, 其中S1={z|f(z)≥f(z*),z∈X{z*}};
不少研究人员[4-11]提出的填充函数都具有一个或两个参数, 而在实际计算中, 这些填充函数参数必须满足一些条件才能符合其定义,而这将大大增加计算量。文献[5]中指出, 要克服其所提出的填充函数的缺陷,有一种方法是构造单参数或无参数的填充函数。本文据此提出了一种新的无参数的填充函数:
(12)
式中:z*是问题(11)的当前局部极小点;对r>0,hr(t)定义为
(13)
以下的定理表明F(z,z*)满足填充函数的定义3。
定理1若z*∈X满足f(z*)>0, 则z*是F(z,z*)的严格极大点。
证明:由于当t∈R时, 0≤hr(t)≤1, 则由F(z,z*)的定义, 可得
因此,z*是F(z,z*)的严格极大点。
定理1表明F(z,z*)满足定义3的条件(1)。
定理2若z*∈X满足f(z*)>0, 则对任意的z∈S1={z|f(z)≥f(z*),z∈X{z*}} , 有F(z,z*)≠0。
因此,对任意的z∈S1, 有F(z,z*)≠0。
定理2表明F(z,z*) 满足定义3的条件(2)。
定理3表明F(z,z*)满足定义3的条件(3)。
4算法描述
考虑如下的填充函数问题:
(14)
本文算法简称为APPF,具体步骤如下。
步骤0选择足够小的正数λL;选择一个正整数K和方向ei,i=1,…,K;选择一个初始点z0∈X;置k∶=0。
步骤2令
其中,
置l∶=1和λ∶=1。
步骤3
(a) 若l≤K, 转(b); 否则, 转步骤5。
(15)
APPF算法的主要思想是:
(1)按以下方法选取步骤0中的方向ei。例如,当n=2时, 取K=6n,方向ei被选为
当n≥3时, 取K=2n,这时,当i=1,…,n时,ei中的第i个分量为1, 其他分量为0;当i=n+1,…,K时,ei中的第i个分量为-1, 其他分量为0。
5算法验证
例1NCP(F)中的函数F由下式给出:
该函数是P0函数, 它有唯一的解(2,0,1,0)T, 取μ的初值μ0=0.1。
例1的数值计算结果见表1。由表1可知, 两种算法的计算结果相同, 但本文APPF算法所需要的CPU时间更短。
表1 例1的数值计算结果
注:t为找到第k个局部极小点时所需要的CPU时间。
例2NCP(F)中的函数F由下式给出:
例2的数值计算结果见表2。同样,APPF算法与AOPF算法的计算结果相同, 但前者所花CPU时间更少。
由以上算例可推知, 采用APPF算法和AOPF算法可得到相同的数值结果, 但大多数情况下前者的计算效率更高。这是因为,一般来说判断目前的点是全局极小点比找到全局极小点更花时间。
表2 例2的数值计算结果
注:t为找到第k个局部极小点时所需要的CPU时间。
6结语
本文首先通过光滑的Fischer-Burmeister函数, 将非线性P0互补问题转化为相应的约束优化问题(11)。然后根据填充函数的定义, 对问题(11) 构造出了一种无参数的填充函数F(z,z*),分析讨论了该填充函数的有关性质。最后构造了求解非线性P0互补问题的填充函数算法, 并对该算法进行了数值实验。针对所给的两个算例,本文APPF算法和文献[6]中AOPF算法虽有同样的数值结果,但APPF算法所使用的CPU时间更少,因此该填充函数算法是有效的。
参考文献
[1]Huang N, Ma C F. The numerical study of a regularized smoothing Newton method for solvingP0-NCP based on the generalized smoothing Fischer-Burmeister function[J].Applied Mathematics and Computation, 2012, 218: 7253-7269.
[2]Zhang L P, Wu S -Y, Gao T R. Improved smoothing Newton methods forP0nonlinear complementarity problems[J]. Applied Mathematics and Computation, 2009, 215: 324-332.
[3]Zhu J G, Liu H W, Li X L. A regularized smoothing-type algorithm for solving a system of inequalities with aP0-function[J]. Journal of Computational and Applied Mathematics, 2010, 233:2611-2619.
[4]Yang Y J, Shang Y L. A new filled function method for unconstrained global optimization[J]. Applied Mathematics and Computation, 2006, 173: 501-512.
[5]Ge R P. A filled function method for finding a global minimizer of a function of several variables[J]. Mathematical Programming, 1990, 46: 191-204.
[6]Yuan L Y, Wan Z P, Zhang J J, et al. A filled function method for solving nonlinear complementarity problem[J]. Journal of Industrial and Management Optimization, 2009, 5(4): 911-928.
[7]Zhang L S, Ng C-K, Li D, et al. A new filled function method for global optimization[J]. Journal of Global Optimization, 2004, 28:17-43.
[8]Xu Z, Huang H-X, Pardalos P M, et al. Filled functions for unconstrained global optimization[J]. Journal of Global Optimization, 2001, 20:49-65.
[9]Liu H W, Gao Y L,Wang Y P. A continuously differentiable filled function method for global optimization[J]. Numerical Algorithms, 2014, 66: 511-523.
[10]Wei F, Wang Y P,Lin H W. A new filled function method with two parameters for global optimization[J]. Journal of Optimization Theory and Applications, 2014, 163: 510-527.
[11]Yuan L Y, Wan Z P, Tang Q H. A criterion for an approximation global optimal solution based on the filled functions[J]. Journal of Industrial and Management Optimization, 2016, 12(1): 375-387.
[责任编辑尚晶]
A filled function method for nonlinearP0complementarity problems
YuanLiuyang1,TangQiuhua2,JiaShihui1
(1.College of Science, Wuhan University of Science and Technology, Wuhan 430065, China;2. College of Machinery and Automation, Wuhan University of Science and Technology, Wuhan 430081, China)
Abstract:Firstly, the nonlinear P0 complementarity problem is converted into a corresponding constrained optimization problem by using the smoothing Fischer-Burmeister function. Subsequently, a novel parameter-free filled function is constructed for the constrained optimization problem,and the function’s properties are also discussed. A filled function algorithm is proposed to solve the nonlinear P0 complementarity problem, and its validity is verified by several numerical examples.
Key words:nonlinear complementarity problem; P0 function; Fischer-Burmeister function; filled function; local minimizer; global minimizer
收稿日期:2016-01-21
基金项目:国家自然科学基金青年科学基金项目(11401450,11401126);国家自然科学基金面上项目(51275366).
作者简介:袁柳洋(1988-),女,武汉科技大学讲师,博士. E-mail:yangly0601@126.com通讯作者:唐秋华(1971-),女,武汉科技大学教授,博士生导师. E-mail:tangqiuhua@wust.edu.cn
中图分类号:O224
文献标志码:A
文章编号:1674-3644(2016)03-0236-05