可微无约束全局优化问题的一种新的无参数填充函数法

A New Non-Parameter Filled Function Method for Differentiable Unconstrained Global Optimization Problems

摘要: 填充函数法在求解全局优化问题中有广泛的应用，此方法利用目标函数的局部性质搜索局部极小点，并通过构造填充函数避免陷入局部极小，通过极小化过程和填充过程的迭代，直到满足终止条件，得到问题的全局极小点。本文提出了一个新的求解无约束全局优化问题的无参数填充函数，其局部极小点与目标函数相同，能够减少算法计算量。在合理的假设条件下，证明该函数的填充性质和相关性质，并设计相应的算法，利用经典算例进行实验，表明该算法是有效可行的。

Abstract: The filled function method has a wide range of applications in solving global optimization problems. This method utilizes the local properties of the objective function to search for local minima, and avoids getting stuck in local minima by constructing a filled function. Through the iteration of the minimization process and filled process until the termination condition is satisfied, the global minima of the problem is obtained. In this paper, we propose a new parameter free filled function, whose local minima are the same as the objective function, which can reduce the computational complexity of the algorithm. Based on reasonable assumptions, we discuss the theoretical properties of the filled function, and develop a corresponding algorithm. Numerical experiments demonstrate the algorithm’s effectiveness and feasibility.

1. 引言

全局优化是数学优化领域中非常有意义的研究方向，近年来，随着科学技术的发展，科学和技术领域中需要解决的问题越来越追求全局最优解，特别是在图像处理、金融规划、工程设计等领域中遇到的很多现实问题，都可以将其转化为数学的全局优化问题进行求解。

从算法的结构来看，全局优化算法可以分为确定性算法和随机性算法，其中确定性算法利用目标函数的一些局部特性，并根据某种确定性策略搜索得到局部极小点，并试图跳出已获得的局部极小点而达到全局极小点。填充函数算法是求解全局优化问题的一种确定性算法，这一概念最初是由西安交通大学的葛人溥教授提出的[1]。

考虑如下的无约束优化问题：

$\begin{array}{l}\min f\left(x\right)\\ \text{s}\text{.t}.x\in R^n,\end{array}$

其中，$f\left(x\right)$ 为$R^n$ 上的二阶连续可微函数，且满足假设[1]：1) 目标函数$f\left(x\right)$ 满足强制性条件，当$\Vert x\Vert \to \infty$ 时，$f\left(x\right)\to \infty$ ；2) $f\left(x\right)$ 含有有限个局部极小值。该假设说明存在有界闭集$X\subset R^n$ 包含$f\left(x\right)$ 的所有全局极小点和函数值较小的局部极小点，且可认为目标函数在X边界上的函数值大于在其内部的函数值。

填充函数法的基本思想如下：首先运用已有的局部极小化算法对目标函数进行运算，得到一个局部极小点$x^{*}$ ，在$x^{*}$ 处构造填充函数，并对填充函数进行极小化运算，这样就能使填充函数的局部极小点$\overline{x}$ 跳出原目标函数局部极小点$x^{*}$ 所在的谷域，接着以$\overline{x}$ 作为新的初始点，再次对目标函数进行极小化运算，就能进入目标函数值更小的区域进行搜索，从而逐步逼近全局极小点。不断重复迭代，直到满足终止条件，即可以当前局部极小点作为全局极小点输出。

在文献[1]中，葛人溥教授提出一个填充函数为：

$P\left(x,x^{*},\gamma ,\rho \right)=\frac{1}{\gamma +f\left(x\right)}\cdot \exp \left(-\frac{\Vert x-x^{*}\Vert }{{\rho }^2}\right).$

后续学者针对上述函数中参数选取困难和指数项会导致出现假的平稳点等不足之处，对填充函数理论进行了一系列的研究和改进，提出了许多不含指数项的、单参数或是无参数的填充函数[2]-[14]，填充函数的理论得到不断发展。杨永建教授等在文献[4]中提出了一种新的填充函数定义。

定义1 $x^{*}$ 是函数$f\left(x\right)$ 的当前局部极小点，函数$P\left(x,x^{*}\right)$ 称为函数$f\left(x\right)$ 在局部极小点$x^{*}$ 处的填充函数，如果满足：

1) $x^{*}$ 是$P\left(x,x^{*}\right)$ 的一个严格局部极大点；

2) $P\left(x,x^{*}\right)$ 在$S_1=\left\{x\in X|f\left(x\right)\ge f\left(x^{*}\right),x\ne x^{*}\right\}$ 上没有平稳点；

3) 如果$x^{*}$ 不是全局极小点，那么$f\left(x\right)$ 和$P\left(x,x^{*}\right)$ 在$S_2=\left\{x\in X|f\left(x\right)<f\left(x^{*}\right)\right\}$ 上有相同平稳点。

定义1修改了文献[1]定义中峰和盆谷的概念，使得填充函数的定义更加清晰，在该定义下，当$x^{*}$ 非全局极小点，则极小化填充函数$P\left(x,x^{*}\right)$ 所得的下一个局部极小点只会出现在函数值比$f\left(x^{*}\right)$ 小的区域中，且填充函数与目标函数有相同的局部极小点，于是在算法运行过程中可以通过极小化填充函数而不用极小化原函数得到局部极小点，提高了算法的运行效率。本文在该定义的基础上，提出了一个新的无参数填充函数，并设计了相应填充函数算法，证明了其有效性。

2. 一个新的无参数填充函数

令$L\left(P\right)$ 表示目标函数$f\left(x\right)$ 的所有局部极小点的集合，给出在定义1下的如下填充函数：

$P\left(x,x^{*}\right)=\left[\frac{\pi }{2}-\arctan \left(\Vert x-x^{*}\Vert \right)\right]\cdot \max \left\{0,\phi \left(f\left(x\right)-f\left(x^{*}\right)\right)\right\}+\phi \left(f\left(x\right)-f\left(x^{*}\right)\right),$ (1.1)

其中

$\phi \left(t\right)=\{\begin{array}{l}1,t\ge 0,\\ t^3,t<0.\end{array}$

下证函数$P\left(x,x^{*}\right)$ 是满足定义2的填充函数。

定理1 假设$x^{*}$ 是函数$f\left(x\right)$ 的一个局部极小点，则$x^{*}$ 是$P\left(x,x^{*}\right)$ 的一个严格局部极大点。

证明：因为$x^{*}$ 是函数$f\left(x\right)$ 的一个局部极小点，那么，存在$\delta >0$ ，使得对任意$x\in O\left(x^{*},\delta \right)$ 且$x\ne x^{*}$ 时，有$f\left(x\right)\ge f\left(x^{*}\right)$ ，所以有$\phi \left(f\left(x\right)-f\left(x^{*}\right)\right)=1$ ，由此得到

$\begin{array}{l}P\left(x^{*},x^{*}\right)=\frac{\pi }{2}+1\\ P\left(x,x^{*}\right)=\frac{\pi }{2}-\arctan \left(\Vert x-x^{*}\Vert \right)+1\\ P\left(x^{*},x^{*}\right)-P\left(x,x^{*}\right)=\arctan \left(\Vert x-x^{*}\Vert \right)>0,\end{array}$

从而$x^{*}$ 是$P\left(x,x^{*}\right)$ 的一个严格局部极大点，定理得证。 □

定理2 $P\left(x,x^{*}\right)$ 在$S_1=\left\{x\in X|f\left(x\right)\ge f\left(x^{*}\right),x\ne x^{*}\right\}$ 上没有平稳点。

证明：任意$x\in S_1$ ，有

$\begin{array}{l}P\left(x,x^{*}\right)=\frac{\pi }{2}-\arctan \left(\Vert x-x^{*}\Vert \right)+1\\ \nabla P\left(x,x^{*}\right)=-\frac{x-x^{*}}{\Vert x-x^{*}\Vert }\cdot \frac{1}{1+{\Vert x-x^{*}\Vert }^2},\end{array}$

又因为$x\ne x^{*}$ ，由此

$\begin{array}{c}{\left(x-x^{*}\right)}^{\text{T}}\cdot \nabla P\left(x,x^{*}\right)=-\frac{{\left(x-x^{*}\right)}^{\text{T}}\left(x-x^{*}\right)}{\Vert x-x^{*}\Vert }\cdot \frac{1}{1+{\Vert x-x^{*}\Vert }^2}\\ =-\frac{\Vert x-x^{*}\Vert }{1+{\Vert x-x^{*}\Vert }^2}<0,\end{array}$

故对任意的$x\in S_1$ ，$\nabla P\left(x,x^{*}\right)\ne 0$ ，定理得证。 □

注1：当$f\left(x\right)\ge f\left(x^{*}\right)$ 时，由定理2可知$d=x-x^{*}$ 是$P\left(x,x^{*}\right)$ 在$x^{*}$ 处的下降方向，即$d^{\text{T}}\nabla P\left(x,x^{*}\right)<0$ 。

定理3 假设函数$f\left(x\right)$ 连续可微，则$f\left(x\right)$ 和$P\left(x,x^{*}\right)$ 在$S_2=\left\{x\in X|f\left(x\right)<f\left(x^{*}\right)\right\}$ 上有相同平稳点。

证明：对任意$x\in S_2$ ，$f\left(x\right)-f\left(x^{*}\right)<0$ ，$\phi \left(f\left(x\right)-f\left(x^{*}\right)\right)={\left(f\left(x\right)-f\left(x^{*}\right)\right)}^3<0$ ，则

$P\left(x,x^{*}\right)={\left(f\left(x\right)-f\left(x^{*}\right)\right)}^3$ ，那么$\nabla P\left(x,x^{*}\right)=3{\left(f\left(x\right)-f\left(x^{*}\right)\right)}^2\cdot \nabla f\left(x\right)$ 。则当$\nabla f\left(x\right)=0$ 时，$\nabla P\left(x,x^{*}\right)=0$ ，反之亦然。定理得证。 □

综上，说明式(1.1)定义的函数$P\left(x,x^{*}\right)$ 是满足定义2的填充函数。

性质1 若对任意$x_1,x_2\in S_1$ ，满足$f\left(x_1\right)\ge f\left(x^{*}\right)$ 和$f\left(x_2\right)\ge f\left(x^{*}\right)$ ，则$P\left(x_2,x^{*}\right)<P\left(x_1,x^{*}\right)<P\left(x^{*},x^{*}\right)$ 的充要条件是$\Vert x_2-x^{*}\Vert >\Vert x_1-x^{*}\Vert$ 。

证明：充分性：因为$f\left(x_1\right)\ge f\left(x^{*}\right)$ ，$f\left(x_2\right)\ge f\left(x^{*}\right)$ ，由定义，得到

$\begin{array}{l}P\left(x_1,x^{*}\right)=\frac{\pi }{2}-\arctan \left(\Vert x_1-x^{*}\Vert \right)+1\\ P\left(x_2,x^{*}\right)=\frac{\pi }{2}-\arctan \left(\Vert x_2-x^{*}\Vert \right)+1.\end{array}$

因$\Vert x_2-x^{*}\Vert >\Vert x_1-x^{*}\Vert$ ，故$P\left(x_2,x^{*}\right)<P\left(x_1,x^{*}\right)$ ，又由定理2知$P\left(x_1,x^{*}\right)<P\left(x^{*},x^{*}\right)$ ，因此$P\left(x_2,x^{*}\right)<P\left(x_1,x^{*}\right)<P\left(x^{*},x^{*}\right)$ 。

反之，必要性显然，若$P\left(x_2,x^{*}\right)<P\left(x_1,x^{*}\right)$ ，则有$\frac{\pi }{2}-\arctan \left(\Vert x_1-x^{*}\Vert \right)+1<\frac{\pi }{2}-\arctan \left(\Vert x_2-x^{*}\Vert \right)+1$ ，由

此可得$\Vert x_2-x^{*}\Vert >\Vert x_1-x^{*}\Vert$ ，定理得证。 □

注2：性质1说明在$S_1$ 中，填充函数$P\left(x,x^{*}\right)$ 的值离$f\left(x\right)$ 当前局部极小点$x^{*}$ 越远就越小，从而保证算法运行中，能有效地跳出当前局部极小点所在的区域，避免出现重复往返搜索的现象，得到一个函数值更小的局部极小点。

性质2 对任意$x_1,x_2\in X\backslash \left\{x^{*}\right\}$ ，若$f\left(x_1\right)\ge f\left(x^{*}\right)>f\left(x_2\right)$ ，则$P\left(x_2,x^{*}\right)<P\left(x_1,x^{*}\right)<P\left(x^{*},x^{*}\right)$ 。

证明：因为$f\left(x_1\right)\ge f\left(x^{*}\right)>f\left(x_2\right)$ ，由填充函数的定义，得到

$\begin{array}{l}P\left(x_1,x^{*}\right)=\frac{\pi }{2}-\arctan \left(\Vert x_1-x^{*}\Vert \right)+1\\ P\left(x_2,x^{*}\right)={\left(f\left(x_2\right)-f\left(x^{*}\right)\right)}^3.\end{array}$

因$\Vert x_1-x^{*}\Vert \ge 0$ ，$f\left(x_1\right)\ge f\left(x^{*}\right)>f\left(x_2\right)$ ，则$P\left(x_2,x^{*}\right)<0<P\left(x_1,x^{*}\right)<P\left(x^{*},x^{*}\right)$ ，定理得证。 □

性质3 对$P\left(x,x^{*}\right)$ 的任一个局部极小点$x_P^{*}$ ，其中$x_P^{*}\ne x^{*}$ ，有$f\left(x_P^{*}\right)<f\left(x^{*}\right)$ 。

证明：根据定理2，$P\left(x,x^{*}\right)$ 在$S_1$ 上没有平稳点，则$P\left(x,x^{*}\right)$ 的任一局部极小点$x_P^{*}$ 都在$S_2$ 中，而根据$S_2$ 的定义，立即得到$f\left(x_P^{*}\right)<f\left(x^{*}\right)$ 。 □

3. 算法与数值实验

根据上述填充函数的性质，极小化该填充函数$P\left(x,x^{*}\right)$ 得到的局部极小点同时也是目标函数$f\left(x\right)$ 的一个更好的局部极小点，于是在计算过程中就不用再对目标函数进行极小化，相比传统的填充函数算法减少了一个循环，减少了计算量。在此基础上提出了一个新的无参数填充函数算法，称为NPFF算法，具体算法如下：

步骤0：选取$\epsilon ={10}^{-8}$ ，作为该算法的容许误差;选取方向$e_i$ ，$i=1,2,\cdots ,m$ ，$m\ge 2n$ ，其中n是变量的个数；令$k=1$ ，表示迭代次数，记迭代次数上界为K，可取$K=20$ ；选取初始点$x_0\in X$ 。

步骤1：以$x_0$ 为初始点，利用局部极小化算法得到目标函数$f\left(x\right)$ 的一个局部极小点$x_1^{*}$ 。

步骤2：在局部极小点$x_1^{*}$ 处构造填充函数

$P\left(x,x_1^{*}\right)=\left[\frac{\pi }{2}-\arctan \left(\Vert x-x_1^{*}\Vert \right)\right]\cdot \max \left\{0,\phi \left(f\left(x\right)-f\left(x_1^{*}\right)\right)\right\}+\phi \left(f\left(x\right)-f\left(x_1^{*}\right)\right).$

步骤3：如果$i\le m$ ，则以${\overline{x}}_k:=x_1^{*}+\delta e_i$ 作为初始点，应用局部极小化算法得到$P\left(x,x_1^{*}\right)$ 的局部极小点$x^{*}$ ；否则，我们认为使用初始点${\overline{x}}_k$ 已经找不到更好地局部极小点，终止算法，将当前极小点$x_1^{*}$ 和$f\left(x_1^{*}\right)$ 作为近似全局极小点和近似全局极小值输出。

步骤4：如果$x^{*}$ 不在$X$ 中，则令$i:=i+1$ ，转步骤3；否则，转步骤5。

步骤5：如果$f\left(x^{*}\right)<f\left(x_1^{*}\right)$ ，则令$x_1^{*}=x^{*}$ ，$k:=k+1$ ，转步骤2；否则，令$i:=i+1$ ，转步骤3。

NPFF算法相比当前大部分填充函数算法，只需对填充函数进行极小化计算，而不需要对原函数进行极小化计算，减小了相当一部分计算量，同时NPFF算法不含有参数，省略了调整参数的步骤，使得算法的运行速度变得更快。

对上述算法，使用Python3.9软件进行编程，并通过以下数值实验对NPFF算法的有效性进行验证。以下是符号说明：

$x_0$ ：目标函数局部极小化时的初始点；

k：外循环目标函数局部极小化迭代次数；

$x_k^{*}$ ：目标函数的第k个局部极小点；

$f\left(x_k^{*}\right)$ ：目标函数第k个局部极小点处的局部极小值；

T：算法运行时间。

例1 (Six-hump back camel function)

$\begin{array}{l}\min f\left(x\right)=4x_1^2-2.1x_1^4+\frac{1}{3}{x}_1^6-x_1{x}_2-4x_2^2+4x_2^4\\ \text{s}\text{.t}.-3\le x_i\le 3,i=1,2.\end{array}$

选取若干不同初始点得到的算法运行结果如下表1所示：

Table 1. Result of Example 1

表1. 算例1结果

$x_0$	k	$x_k^{*}$	$f\left(x_k^{*}\right)$	T
$\left(1,1\right)$	1	$\left(0.0898,0.7126\right)$	−1.0316	0.7248 s
$\left(-3,3\right)$	1	$\left(-1.7036,-0.7961\right)$	−0.2154
	2	$\left(-0.0898,-0.7126\right)$	−1.0316	0.7554 s
$\left(-3,-3\right)$	1	$\left(-1.6071,0.5686\right)$	2.1042
	2	$\left(-0.0898,-0.7126\right)$	−1.0316	0.7262 s

通过选取三个不同初始点，得到全局最优解为$x^{*}=\left(-0.0898,-0.7126\right)$ 和$\left(0.0898,0.7126\right)$ ，全局极小值为$f^{*}=-1.0316$ 。

例2 (Two-dimensional Rastrigin function)

$\begin{array}{l}\min f\left(x\right)=x_1^2+x_2^2-\cos \left(18x_1\right)-\cos \left(18x_2\right)\\ \text{s}\text{.t}\text{.}-2\le x_i\le 2,i=1,2.\end{array}$

选取若干不同初始点得到的算法运行结果如下表2所示：

Table 2. Result of Example 2

表2. 算例2结果

$x_0$	k	$x_k^{*}$	$f\left(x_k^{*}\right)$	T
$\left(1,1\right)$	1	$\left(1.0407,-1.0407\right)$	0.1791
	2	$\left(-3.63e^{-14},1.04e^{+00}\right)$	−0.9101
	3	$\left(-7.65e^{-17},-4.92e^{-14}\right)$	−2.0	0.0986 s
$\left(2,2\right)$	1	$\left(1.0407,2.0814\right)$	3.4493
	2	$\left(-4.59e^{-10},2.08e^{+00}\right)$	2.3594
	3	$\left(-3.29e^{-10},1.04e^{+00}\right)$	−0.9101
	4	$\left(2.07e^{-12},-4.59e^{-10}\right)$	−2.0	0.0871 s
$\left(1,-2\right)$	1	$\left(1.0407,-1.0407\right)$	0.1791
	2	$\left(-4.22e^{-14},-6.93e^{-01}\right)$	−1.5156
	3	$\left(1.09e^{-11},1.62e^{-10}\right)$	−2.0	0.0935 s

通过选取三个不同初始点，均算得该问题的全局极小值为$f^{*}=-2.0$ 。

例3 (Three-hump back camel function)

$\begin{array}{l}\min f\left(x\right)=2x_1^2-1.05x_1^4+\frac{1}{6}{x}_1^6-x_1{x}_2+x_2^2\\ \text{s}\text{.t}.-3\le x_i\le 3,i=1,2.\end{array}$

选取若干不同初始点得到的算法运行结果如下表3所示：

Table 3. Result of Example 3

表3. 算例3结果

$x_0$	k	$x_k^{*}$	$f\left(x_k^{*}\right)$	T
$\left(1,1\right)$	1	$\left(6.44e^{-12},2.80e^{-12}\right)$	$7.28e^{-23}$	0.2773 s
$\left(3,1\right)$	1	$\left(1.7475,0.8737\right)$	0.2986
	2	$\left(-1.29e^{-16},3.51e^{-17}\right)$	$2.02e^{-32}$	0.4381 s
$\left(-3,2\right)$	1	$\left(-1.7475,-0.8737\right)$	0.2986
	2	$\left(3.32e^{-17},9.01e^{-17}\right)$	$7.33e^{-33}$	0.3742 s

通过选取三个不同初始点，均算得该问题的全局极小值为$f^{*}=0$ 。

例4 (n-dimensional function)

$\begin{array}{l}\min f\left(x\right)=\frac{\pi }{n}\left[10{\sin }^2\left(\pi x_1\right)+g\left(x\right)+{\left(x_n-1\right)}^2\right]\\ \text{s}\text{.t}.-10\le x_i\le 10,i=1,2,\cdots ,n.\end{array}$

其中$g\left(x\right)={\displaystyle \sum }_{i=1}^{n-1}\left\{{\left(x_i-1\right)}^2\left[1+10{\sin }^2\left(\pi x_{i+1}\right)\right]\right\}$ 。选取不同n的值得到的算法运行结果如下表4所示：

Table 4. Result of Example 4

表4. 算例4结果

n	$x_0$	$x_k^{*}$	$f\left(x_k^{*}\right)$	T
3	$\left(2,2,2\right)$	$\left(1.00,1.00,1.00\right)$	$6.31e^{-16}$	0.62 s
5	$\left(2,2,2,2,2\right)$	$\left(1.00,0.99,\mathrm{1.001.00},0.99\right)$	$4.31e^{-15}$	0.77 s
8	$\left(3,3,3,3,3,3,3,3\right)$	$\left(0.99,1.00,1.00,\mathrm{1.001.00},1.00,0.99,1.00\right)$	$3.66e^{-16}$	1.24 s

通过选取$n=3,5,8$ 三个维度的初始点，均能算得该问题全局极小值为$f^{*}=0$ 。

4. 结语

本文提出的填充函数与原目标函数有相同的局部极小点，省去了以往填充函数算法中需要重新计算目标函数局部极小点的过程，并且不含参数，省去了参数调节的过程，所构造的填充函数算法形式简单，便于计算。数值算例的结果表明该算法是有效可行的，在此基础上，可以将其与机器学习算法结合，进行进一步的理论探讨与应用研究。

NOTES

^*通讯作者。