APP下载

求解非线性P0互补问题的填充函数法

2016-06-14袁柳洋唐秋华贾世会

武汉科技大学学报 2016年3期
关键词:计算结果定理武汉

袁柳洋,唐秋华,贾世会

(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

猜你喜欢

计算结果定理武汉
J. Liouville定理
别哭武汉愿你平安
我们在一起
武汉加油
不等高软横跨横向承力索计算及计算结果判断研究
决战武汉
A Study on English listening status of students in vocational school
“三共定理”及其应用(上)
存放水泥
趣味选路