A new filled function method based on global search for solving unconstrained optimization problems

1.   Introduction

Global optimization methods have been widely used in many fields, such as economics, computer applications, artificial intelligence, bioengineering, etc., and have developed into an important research area. However, due to the existence of exponentially many local minima in global optimization problems, the functions of these multi-minima points pose the following difficulties in finding the global optimal solution: How to search for a better local minimum point from the domain where the current local minimum point is located, and how to determine whether the current minimum point is the global minimum point. With the wide application of global optimization problems, both the theory and algorithms of global optimization have been developed accordingly. Many methods have been proposed for solving global optimization problems, which can be broadly classified into two categories, i.e., deterministic algorithms and stochastic algorithms. Stochastic algorithms mainly include: cuckoo search algorithm ^[1], grey wolf optimization algorithm ^[2], pigeon-inspired optimization algorithm ^[3,4], Harris hawks optimization algorithm ^[5], snow geese algorithm ^[6], and other bionic algorithms. This type of method utilizes probabilistic mechanisms to search for satisfactory solutions within the feasible domain of an optimization problem. However, due to a lack of theoretical guarantees, these methods often get stuck in local minima and exhibit slower convergence rates. In contrast, deterministic algorithms can leverage the mathematical properties of the problem to ensure convergence to the global minimum within a specified error tolerance after a finite number of iterations. Deterministic algorithms mainly include: the filled function method ^[7,8], the branch and bound method ^[9], the tunneling method ^[10], and other algorithms; Among them, the filled function method is a type of deterministic algorithm capable of globally optimizing optimization problems, which has a strong ability to jump out of the current non-global minima, and it is one of the better ways to study and solve the first difficult problem, and it has a very high efficiency and practicability in practical applications. The method was originally proposed by Ge in ^[7], and its core idea is to construct an auxiliary function called the filled function at the current local minimum point of the objective function, and use it as a bridge to jump out of the current non-global minima, so that the objective function can keep searching for better local minima to avoid falling into the local optimum.

In general, the filled function method is an optimization algorithm that involves a two-stage alternating loop. The first stage is the minimization phase, which starts from a given initial point and uses a local search algorithm to obtain a local minima $x_{1}^{*}$ of the objective problem. Then, transitioning to the second stage, i.e., the filling stage, where a filled function is constructed at $x_{1}^{*}$, and the filled function is minimized by using the points near the current minima as the initial points. If the minima $x_{1}^{*}$ of the objective problem obtained in the minimization stage is a non-global minima, then the minima $x^{'}$ of the filled function must be in a basin which is lower than $B_{1}^{*}$, and $x^{'}$ serves as a better feasible point for the objective problem. Subsequently, the objective problem is resolved with $x^{'}$ as the new initial point, thus jumping out of the current local minima and finding another better point. The above two phases alternate until no better minima $x^{'}$ can be found in the filling phase, then the current local minima of the objective problem is considered to be the globally optimal solution. The original definition of the filled function was proposed by Ge in ^[7], and it is defined as follows:

Definition 1. A function $P(x)$ is called the filled function of $f(x)$ at the local minimum point $x_{1}^{*}$ if $P(x)$ has the following properties:

(i) $x_{1}^{*}$ is a maximizer of $P(x)$ and the whole basin $B_{1}^{*}$ of $f(x)$ at $x_{1}^{*}$ becomes a part of a hill of $P(x)$;

(ii) $P(x)$ has no minimizers or saddle points in any higher basin of $f(x)$ than $B_{1}^{*}$;

(iii) If $f(x)$ has a lower basin than $B_{1}^{*}$, then there is a point $x^{'}$ in such a basin that minimizes $P(x)$ on the line through $x^{'}$ and $x_{1}^{*}$.

In reference ^[7], the specific form of the first-generation filled function is also provided:

where $\gamma$ and $\rho$ are two parameters that need to be scientifically adjusted to ensure that the filled function method can be executed and that global minima can be obtained. Tuning these parameters poses a significant challenge, stemming from the unpredictable nature of their ideal values. Only via numerous trials can we home in on the right settings, a process that inevitably adds to the algorithm's computational intricacy. Additionally, the filled function contains an exponential term $exp(-\frac{\|x-x_{1}^{*}\|^{2}}{\rho^{2}})$. When the parameter $\rho$ is too small or the value of $\left \| x-x_{1}^{*} \right \|$ is too large, the graph of the filled function tends to be flat. This makes it difficult for the algorithm to discern changes in the filled function values, thereby causing the objective function to fall into local optima. Since there is still room for improvement in the form of the first-generation filled function, scholars have successively proposed some bi-parameter filled functions ^{[11,12,13,14,15,16]}. However, this type of filled function still faces issues such as strong dependence on parameters or exponential terms. In order to reduce the number of parameters, scholars also proposed some single-parameter filled functions. For example, the Q-function introduced by Ge and Qin ^[8] has the following form:

However, the filled function still contains exponential terms. In order to overcome the drawbacks caused by exponential terms, Liu proposed a new class of filled functions ^[17,18]:

The introduction of $H(x, \mu)$ reduces the number of parameters of the filled function from two to one and eliminates exponential terms. However, it is discontinuous at points $x\in S = \left \{ x\mid f(x) = f(x_{1}^{*}) \right \}$, where gradient information is not available. This limitation restricts the choice of local minimization methods during the minimization phase.

In response to the drawbacks of the Q-function, Lin proposed a one-parameter filled function in 2014 that does not contain exponential terms and is continuously differentiable, but still suffers from the disadvantage of needing to adjust the parameters, which is of the following form ^[19]:

where $p$ is a parameter, and

In further research on filled functions, we have discovered that regardless of the number of parameters incorporated, they inevitably exert a negative impact on the algorithm's performance. Consequently, several scholars have proposed various types of parameter-free filled functions ^{[20,21,22,23,24]}. However, their numerical experimental performance is often less than ideal. For instance, while the filled function in ^[22] is devoid of parameters and exponential terms, it incorporates a sign function within its formulation. Unfortunately, this sign function is characterized by its discontinuity and non-differentiability, rendering gradient-based local minimization methods ineffective during the minimization phase. The filled function presented in ^[23] successfully circumvents this significant limitation, yet it incorporates exponential terms that, as we have previously discussed, have the potential to hinder the effectiveness of the filled function algorithm. This integration of exponential terms, while possibly beneficial in certain contexts, may adversely affect the algorithm's performance in terms of stability, computational efficiency, and its ability to accurately converge to a global optimum. In ^[24], a novel continuous and differentiable filled function is introduced, distinguished by its exclusion of both parametric and exponential terms. Moreover, an algorithm is presented that is based on this filled function and incorporates coordinate directions during the minimization process. During the minimization process of the filled function in this algorithm, coordinate directions are utilized, but the determination of the perturbation step size $\alpha _{0}$ is not thoroughly deliberated. Notably, selecting an unsuitable initial point could gravely impact the efficacy of the filled function, potentially impeding its ability to guide the objective function toward a superior local minimum. Therefore, an inappropriate choice of the initial point may deteriorate the overall performance of the algorithm. To address the aforementioned issue, this paper introduces a significant refinement to the filled function originally presented in reference ^[22]. Specifically, we substitute the sign function within the filled function with a continuously differentiable univariate function. As a result, we propose a novel continuously differentiable filled function that is devoid of parameters, exponential terms, and logarithmic terms. This refined function is designed to effectively tackle the unconstrained global optimization problem. Based on the proposed filled function, we have devised a groundbreaking filled function method (hereinafter referred to as NFFM). During the minimization phase of this NFFM, we deliberately choose coordinate directions as our primary search directions. When perturbing the current local minimum point, we implement an incremental sequence for adjusting the perturbation step size. Precisely, if the local minimum discovered along a specific coordinate direction under the initial perturbation step size fails to yield an improved local minimum for the objective function, we enlarge the perturbation step size and persist in our search for a superior local minimum along that same coordinate direction. This iterative process continues until we reach the boundary of the objective function's feasible region, thus guaranteeing that our algorithm conducts an exhaustive global search without overlooking any potentially advantageous local minima of the objective function.

The organization of the subsequent sections in this paper is outlined as follows: In Section 2, we commence with the introduction of pivotal prerequisite knowledge, establishing a robust theoretical framework for subsequent deliberations. Proceeding from this, we shall construct an unprecedented parameter-free filled function and conduct in-depth research and analysis of its theoretical properties. Moving on to Section 3, we will design an innovative NFFM based on the aforementioned parameter-free filled function. In Section 4, we undertake a meticulous series of numerical experiments. Through a selection of 14 emblematic multimodal test functions, we comprehensively validate the viability and efficacy of the proposed NFFM. These outcomes not only underscore the superiority of NFFM but also furnish pivotal reinforcement for subsequent practical implementations. Finally, in the concluding section of this paper, we will provide a comprehensive summary of the research content and explicitly highlight the achievements and major contributions of this study.

2.   A new filled function for unconstrained global optimization problems

2.1.   Preliminaries

This paper considers the following unconstrained global optimization problem:

where $f(x):R^{n}\rightarrow R$ is the objective function.

To ensure the existence of the global optimal solution for problem $(P)$ and the feasibility of the proposed filled function method, the objective function should satisfy the following basic assumptions. Moreover, a related definitions are presented in this section.

Assumption 1. The objective function in problem $(P)$ is continuously differentiable.

Assumption 2. $\xi$ is a set of all local minimizers of problem $(P)$, and $\mathcal{L}^{*} = \left \{ f(x)\mid x\in \xi \right \}$ is finite.

Assumption 3. $f(x)$ is a coercive function, i.e., $\| x \| \rightarrow \infty$, $f(x)\rightarrow \infty$.

Assumption 3 indicates that there exists a compact set $\Omega\subset R^{n}$, which contains all the local minima of $f(x)$ in its interior, and the function values of $f(x)$ at the boundary of $\Omega$ are greater than the function values at any point inside $\Omega$. When the global optimization problem $(P)$ satisfies the above assumptions, all the global minima of problem $(P)$ will be contained within a bounded closed interval $\Omega$. Therefore, the problem $(P)$ considered in this paper can be converted into:

where $\Omega = \left \{ x_{i} \in R\mid l_{i}\le x_{i}\le u_{i}, i = 1, 2, \cdots n \right \}$ is referred to as the box constraint of problem $P^{*}$.

Lemma 1. If $x_{k}^{*}$ is a local minimum point of $f(x)$, then:

The original definition of the filled function was proposed by Ge in ^[7], which provides a reference criterion for researchers to construct filled functions that can escape from local non-global minima. However, the concepts of basins and peaks involved in the definition are more difficult to understand, and the third condition in the definition is not conducive to constructing and minimizing the filled function. In order to address these limitations, researchers have continuously improved the original definition of the filled function ^[11,12,25], among which the widely used definition ^[12] is as follows:

Definition 2. A function $P(x)$ is called the filled function of $f(x)$ at the local minimum point $x_{1}^{*}$ if $P(x)$ has the following properties:

(i) $x_{k}^{*}$ is a strictly local maximum of $P(x, x_{k}^{*})$;

(ii) For $P(x, x_{k}^{*})$, none of the points in $\varOmega_{1}$ is a stationary point;

(iii) If $x_{k}^{*}$ is not a global minimum of $f(x)$, then $P(x, x_{k}^{*})$ in $\varOmega_{2}$ has a local minimum.

The improved properties of the filled function ensure that when the local search method is used to minimize the constructed filled function, the sequence of iteration points does not terminate at any point where the objective function value is greater than $f(x_{k}^{*})$. If $x_{k}^{*}$ is not a global minima, then there must exist a local minimum $x^{'}$ of the filled function such that the function value at that point is less than the current local minimum value $f(x_{k}^{*})$ of the objective function. That is, any local minimum point of $P(x, x_{k}^{*})$ belongs to the set $\varOmega_{2}$, enabling the objective function $f(x)$ to escape from the current local minimum point and find a better minimum point by a local search algorithm starting from the minimum point of the filled function.

2.2.   A new filled function and its properties

We assume that $x_{k}^{*}$ represents the current local minimum point of $f(x)$. Based on Definition 2, we propose a novel continuous, differentiable, and parameter-free filled function:

First of all, we establish through the subsequent lemma and theorem that $x^{*}_{k}$ is a strictly local maximum for the function $\Psi(x, x^{*}_{k})$.

Lemma 2. If $x_{k}^{*} \in \xi$ and $x\in \varOmega_{1}$, then $\Psi(x, x_{k}^{*}) < 0 = \Psi(x_{k}^{*}, x_{k}^{*})$.

Proof. Since for $x\in \varOmega_{1}$, we have $f(x)\geq f(x_{k}^{*})$, then$\Psi(x, x_{k}^{*}) = -\arctan(\|x-x_{k}^{*}\|^{2})$.

From the properties of function $h(\omega) = -\arctan(\omega)$, we know that: (1) $h(\omega) > 0$, if $\omega < 0$, (2) $h(\omega) = 0$, if $\omega = 0$, (3) $h(\omega) < 0$, if $\omega > 0$. Because $\|x-x_{k}^{*}\|^{2} > 0$, and $\|x_{k}^{*}-x_{k}^{*}\|^{2} = 0$, then $\Psi(x, x_{k}^{*}) = -\arctan(\|x-x_{k}^{*}\|^{2}) < 0 = -\arctan(\|x_{k}^{*}-x_{k}^{*}\|^{2}) = \Psi(x_{k}^{*}, x_{k}^{*})$. □

Theorem 1. If $x_{k}^{*} \in \xi$, then $x_{k}^{*}$ is a strictly local maximum of $\Psi(x, x_{k}^{*})$.

Proof. Since $x_{k}^{*}$ is a local minimum point of $f(x)$, then there is a very small positive number $\delta > 0$, for any $\forall x \in B(x_{k}^{*}, \delta)\cap\varOmega_{1}$, $f(x)\geq f(x_{k}^{*})$. From Lemma 2, We know $\Psi(x, x_{k}^{*}) = -arctan(\left \| x-x_{k} ^{*} \right \|^{2}) < 0 = \Psi(x_{k}^{*}, x_{k}^{*})$. Thus, $x_{k}^{*}$ is a strictly local maximum of $\Psi(x, x_{k}^{*})$. □

The above Lemma 2 and Theorem 1 indicate that the function $\Psi(x, x^{*}_{k})$ satisfies the first condition of Definition 2. Next, we prove that the function $\Psi(x, x^{*}_{k})$ also satisfies the second and third conditions of Definition 2. First, we define $d^{*} = x-x^{*}_{k}$ as a feasible direction of $f(x)$.

Theorem 2. For $\forall x\in \Omega_{1}$, $\nabla^{T} \Psi(x, x^{*}_{k})d^{*} < 0$.

Proof. Since $x_{k}^{*}$ is a local minimum point of$f(x)$, then for $\forall x\in \Omega_{1}$, we have $f(x)\geq f(x_{k}^{*})$, and $\Psi(x, x_{k}^{*}) = -arctan(\left \| x-x_{k} ^{*} \right \|^{2})$; thus,

□

Remark 1. By Theorem 2, the following can be concluded:

(1) For each $x \in \varOmega_{1}$, the previously defined feasible direction $d^{*}$ is a descent direction for the function $\Psi(x, x_{k}^{*})$.

(2) For each $x \in \varOmega_{1}$, $\nabla \Psi(x, x_{k}^{*}) \neq 0$, thus none of the points in $\varOmega_{1}$ are stationary points or saddle points. This conclusion ensures that the numerical experimentation process will disregard regions where the objective function value exceeds the current local minimum value.

(3) The minimization process of $\Psi(x, x_{k}^{*})$ will not stop within $\varOmega_{1}$.

(4) Theorem 2 proves that the function $\Psi(x, x_{k}^{*})$ satisfies the second condition in Definition 2.

Theorem 3. Assume that $x_{k}^{*}$ is a local minimum point of $f(x)$. If it is not a global minimum point, then $\Psi(x, x_{k}^{*})$ has a local minimum point in $\varOmega_{2}$. Furthermore, let $d^{*} = x_{q}-x_{k}^{*}$, if there exists $x_{q} \in \varOmega_{2}$ such that $\nabla^{T}f(x_{q})d^{*} > \eta > 0$, then $\nabla^{T} \Psi(x_{q}, x_{k}^{*})d^{*} > 0$, where

Proof. Assume $x_{j}^{*}\notin\varOmega_{2}$ and is a local minimum of $\Psi(x, x_{k}^{*})$, then $x_{j}^{*}\in\varOmega_{1}$, and $\nabla\Psi(x_{j}^{*}, x_{k}^{*}) = \frac{-2\|x_j^*-x_k^*\|^2}{1+\|x_j^*-x_k^*\|^4} = 0$, so $x_{j}^{*} = x_{k}^{*}$. From Theorem 1, we know $x_{k}^{*}$ is a strictly local maximum of $\Psi(x, x_{k}^{*})$, so $x_{j}^{*}\neq x_{k}^{*}$, it contradicts Theorem 1. If $x_{j}^{*}$ is a saddle point, and it contradicts Theorem 2. Thus, $x_{j}^{*}$ must be in $\varOmega_{2}$.

Next, we will demonstrate that the feasible direction $d^*$ is an ascent direction for some $x_q \in \varOmega_2$. If there exists \(x_{q} \in \varOmega_{2} \) such that \(\nabla^{T}f(x_{q})d^{*} > \eta > 0 \), then, according to Eq (2.2), we know that

Equation (2.1) implies:

At this point, the gradient of $\Psi(x_{q}, x^{*}_{k})$ at $x_{q}$ is:

Hence,

That is,

□

Theorem 3 demonstrates that within the interval $\varOmega_{2}$, the direction $d^{*} = x_{q}-x_{k}^{*}$ is an ascent direction for $\Psi(x, x_{k}^{*})$. By Assumption 1, $f(x)$ is continuously differentiable, thus there exists a stationary point along the direction $d^{*}$ for $\Psi(x_{q}, x_{k}^{*})$ within $\varOmega_{2}$. Furthermore, Theorem 3 also confirms that Eq (2.1) satisfies the third condition of Definition 2.

Theorem 4. If $x_{k}^{*} \in \xi$, and $x_{a}, x_{b}\in \varOmega_{1}$ such that $\|x_{a}-x_{k}^{*}\| < \|x_{b}-x_{k}^{*}\|$, then $\Psi(x_{b}, x^{*}_{k}) < \Psi(x_{a}, x^{*}_{k})$.

Proof. Since $x_{k}^{*}$is a local minimum of $f(x)$, and $x_{a}, x_{b}\in \varOmega_{1}$, according to the filled function Eq (2.1), we have

because

and $\|x_{a}-x_{k}^{*}\| < \|x_{b}-x_{k}^{*}\|$, then $\|x_{a}-x_{k}^{*}\|^{2} < \|x_{b}-x_{k}^{*}\|^{2}$. From the properties of the arctan function $h(\omega) = -\arctan(\omega)$, it can be inferred that $\Psi(x_{b}, x^{*}_{k})-\Psi(x_{a}, x^{*}_{k}) < 0$. That is $\Psi(x_{b}, x^{*}_{k}) < \Psi(x_{a}, x^{*}_{k})$. □

Remark 2. Theorem 4 proves that for any two points in $\varOmega_{1}$, the further away from $x^{*}_{k}$, the smaller the value of the filled function, which shows that in the interval $\varOmega_{1}$, $\Psi(x, x^{*}_{k})$ will always be a peak, implying that the minimization process of $\Psi(x, x^{*}_{k})$ will always be realized.

Theorem 5. If $x_{k}^{*}$ is the global optimal solution of $f(x)$, then the filled function $\Psi(x_{q}, x_{k}^{*})$ is monotonically decreasing for all $x\in\varOmega$.

Proof. Because $x_{k}^{*}$ is the global optimal solution of $\varphi(x)$, for $\forall x\in\varOmega$, we have $\varphi(x) > \varphi(x_{k}^{*})$. Thus, from Eq (2.1), we obtain $\Psi(x, x^{*}_{k}) = -\arctan(\|x-x_{k}^{*}\|^{2})$. According to the property of the function $h(\omega) = -\arctan(\omega)$, we can conclude that $\Psi(x, x_{k}^{*})$ is monotonically decreasing for $\forall x\in\varOmega$. □

Theorem 5 is an additional property of the filled function $\Psi(x_{q}, x_{k}^{*})$, which shows that if $x_{k}^{*}$ is a global optimal solution of $f(x)$, then $\Psi(x, x_{k}^{*})$ has no stationary points in the global search domain, and for any feasible direction $d^{*} = x-x_{k}^{*}$, there will be $\nabla^{T}\Psi(x, x_{k}^{*})d^{*} < 0$.

3.   A new filled function algorithm

3.1.   A new filled function algorithm without parameter

The previous section has rigorously demonstrated through in-depth theoretical analysis that the constructed filled function $\Psi(x, x_{k}^{*})$ in this paper fully satisfies the properties of a filling function outlined in Definition 2. Based on this foundation, the current section will further elaborate on the development of a novel parameter-free filled function algorithm—the NFFM, derived from the formulated filled function as indicated in Eq (2.1). Subsequently, we shall present the pseudocode of the innovative filled function algorithm introduced in this study and provide a thorough textual elaboration of its entire operational procedure. Furthermore, we will offer precise explanations for each individual step.

Step 0: Choose an initial point $x_{0}\in \varOmega$; $e_{i}, i = 1, 2, ..., 2n$, where $e_{i}$ is a unit coordinate vector; $n$ is the number of variables of the objective function $f(x)$; $\varepsilon > 0(let \varepsilon = 10^{-6})$; set $k = 1, i = 1, a_{0} = 0$, where $k$ represents the number of iterations; let $\delta = \delta_{0}+a_{0} \cdot H$, where $\delta > 0$ is the step length, $\delta_{0}$ is the given initial step length, $H = D/G$ is the unit segment step length, $D = \frac{l_{1} -u_{1} }{2}$, and G is the maximum number of segments, then go to Step 1.

Step 1: Take $x_{0}$ as the initial point and use the local search method to minimize the objective function $f(x)$ to obtain its local minima $x_{k}^{*}$, then go to Step 2;

Step 2: Construct the non-parameter filled function at $x_{k}^{*}$

where,

and go to Step 3.

Step 3: If $a_{0} \leq G$, go to Step 4; otherwise, $x_{k}^{*}$ serves as a global optimum solution for the objective function $f(x)$, and the algorithm terminates.

Step 4: If $i \leq 2n$, then let $x_{i} = x_{k}^{*} + \delta e_{i}$ and go to Step 5; otherwise, let $a_{0} = a_{0} + 1$, $\delta = \delta_{0} + a_{0} \cdot H$, $i = 1$, and go to Step 3.

Step 5: If $x_{i} \in \Omega$, minimize $\Psi(x, x^{*}_{k})$ starting from $x_{i}$ to obtain a local minimum point $x_{k} ^{'}$, then go to Step 6; otherwise, let $i = i + 1$ and go to Step 4.

Step 6: Using $x_{k} ^{'}$ as the initial point, minimize the objective function $f(x)$ using a local minimization method to obtain a local minimum point $x_{k} ^{f}$. If $f(x^{f}_{k})-f(x^{*}_{k}) < -\varepsilon$, then set $x_{k} ^{*} = x^{f}_{k}$, $k = k+1$, $i = 1$, $a_{0} = 1$, $\delta = \delta_{0}+a_{0}\cdot H$, and go to Step 2; otherwise, let $i = i+1$, then go to Step 4.

Next, some detailed explanations are provided regarding the specific steps of NFFM:

(1) In the iteration process of NFFM, we commence by minimizing the objective function f(x) from a predefined initial point $x_0$ within the feasible domain $\Omega$ of the specified test function. To validate the escape capabilities of our proposed filled function algorithm, during experimentation, we select initial points that are situated relatively distant from the global minimum of the objective function, yet still within the feasible domain of the test function. Following this, we deploy local optimization algorithms to minimize the objective function, ultimately yielding a local minimum point denoted as $x_k^*$.

(2) Construct a filled function $\Psi(x, x_{k}^{*})$ at the local minimizer $x_{k}^{*}$ of the objective function. Since $x_{k}^{*}$ is a strict local maximizer of the filled function, it cannot be directly used as the initial point for minimizing the filled function. Therefore, it is necessary to perturb this point. In existing filled function algorithms, the initial point for minimizing the filled function is usually generated as $x_{i} = x_{k}^{*}+\delta e_{i}$, but the value of the perturbation step size $\delta$ is rarely discussed. The choice of $\delta$ is generally related to the number of local minimizers of the objective function or the size of the feasible domain. Therefore, in the proposed $NFFM$, during the stage of minimizing the filled function, an increasing arithmetic sequence with $H$ as the common difference is constructed, and $\delta = \delta_{0}+a_{0}\cdot H$ is set as the perturbation step size to generate the initial point for minimizing the filled function.

(3) The next step is to minimize $\Psi(x, x_{k}^{*})$ with the initial point $x_{i} = x_{k}^{*}+\delta e_{i}$. Since $i\leq2n$, this process will be executed. If a local minimizer $x_{k} ^{'}$ of $\Psi(x, x_{k}^{*})$ is found, then $x_{k} ^{'}$ will be used as the initial point to minimize the objective function $f(x)$ in order to obtain a local minimizer $x_{k} ^{f}$. If the function value of $f(x)$ at $x_{k} ^{f}$ is smaller than the function value at $x_{k}^{*}$, then $x_{k}^{*}$ is replaced by $x_{k} ^{f}$ and the process is repeated. If not, then $i = i+1$, change the search direction, and continue minimizing the filled function. If after iterating until $i > 2n$, a better local minimum of the objective function is still not obtained, then $a_0$ is incremented by one, increasing the perturbation step size. With the updated perturbation step size, a new initial point is generated for minimizing the filled function $\Psi(x, x_k^*)$ iteratively. This process of minimizing the filled function is repeated. If this iteration continues until reaching the threshold $G$ of $a_0$, and a superior local minimum of the objective function $f(x)$ is still not achieved, then $x_k^*$ is regarded as the global minimum point and the algorithm terminates.

(4) Since both the objective function and the filled function are continuously differentiable, gradient-based local optimization algorithms can be utilized for the minimization process. In this paper, we employ the quasi-Newton method (short for $BFGS$) as the local optimization method to minimize the objective function and the filled function.

3.2.   The time complexity analysis of NFFM

In this section, we will analyze the time complexity of NFFM jumping out one local minimum. NFFM is compatible with various local search algorithms, and during the experimental process, both NFFM and the other comparative algorithms adopt the same local search method. We assume that the time complexity of the local search algorithm for finding local solutions from an initial point is $T(local)$, a supposition that applies universally to all filled function methods. Subsequently, we utilize $T(local)$ to optimize the objective function from the initial point $x_0$, aiming to obtain the local minimum $x_k^*$. Since $x_k^*$ is a local maximum point of the filled function $\Psi(x, x_{k}^{*})$, it is necessary to perturb $x_k^*$ in order to minimize $\Psi(x, x_{k}^{*})$. In step four of the NFFM algorithm process, the worst-case scenario is that each of the generated initial points begins to perform a local search on the filled function. The maximum number of the generated initial points for the filled function is $(G+1)*2n$, where $n$ represents the dimension of the optimization problem and $G$ is the maximum threshold value of $a_0$. Then, it will take $(G+1)*2n*T(local) = O(n*T(local))$ for NFFM to optimize the filled function from all the generated initial points. Therefore, the time complexity of NFFM is $T(local)+O(n*T(local)+T(local) = O(n*T(local))$.

4.   Numerical experiment

To thoroughly validate the feasibility and effectiveness of NFFM, this section applies the algorithm to 14 classic test functions, which originate from a selection of global optimization problems listed in ^[26]. The results are then compared with four filled function algorithms that have emerged in the past four years. All numerical experiments were conducted using the Matlab(R2023a) software on a desktop computer equipped with a 64-bit Windows 10 operating system, an Intel(R) Core(TM) i5-8500 CPU @ 3.00 GHz processor, and 8.00 GB of RAM.

4.1.   Test functions

Problem 1. Treccani function.

The function is multimodal, with two global minima at $x^{*} = (0, 0)$ or $(-2, 0)$, and the global optimum value is $f(x^{*}) = 0$. The NFFM successfully found the global minima and optimal values using initial points of $(-1, -2)$ and $(-3, 3)$.

Problem 2. Six-hump back camel function.

The function is a commonly used multimodal, non-convex function, featuring six local minima and two global minima at either $x^* = (-0.0898, -0.7127)$ or $(0.0898, 0.7127)$, with a global optimum value of $f(x^*) = -1.0316$. The NFFM successfully located the global minimum points and global optimal values using $(2, -1)$ and $(-3, 3)$ as initial points.

Problem 3.Rastrigin function.

The function is a commonly used multimodal, non-convex function often employed as a test problem for assessing the performance of optimization algorithms. It features multiple local minima, presenting a challenging problem for optimization algorithms. It has a single global minimum at $x^{*} = (0, 0)$, with a global optimum value of $f(x^{*}) = -2$. The NFFM successfully found the global minima and optimal values using initial points of $(1, 1)$ and $(-2, -2)$.

Problem 4. Three-hump back camel function.

The function is a commonly used multimodal function with three local minima within the search domain and one global minimum. The global minimum is located at $x^{*} = (0, 0)$, with a global optimal value of $f(x^{*}) = 0$. The NFFM successfully found the global minimum and its optimal value using initial points of $(-2, 2)$ and $(-3, 3)$.

Problem 5. Two-dimensional function.

where $c = 0.5, 0.2, 0.05$.

The function is a multimodal, non-convex function with multiple local minima, but it has only one global optimum $f(x^{*}) = 0$ across different coefficients $c$. When $c = 0.5$, the NFFM successfully found the global optimum using initial points $(0, 0)$ and $(5, -5)$. Similarly, for $c = 0.2$, it utilized initial points $(6, -2)$ and $(0, -10)$, and for $c = 0.05$, it employed initial points $(10, -10)$ and $(5, -5)$ to achieve the global optimum.

Problem 6. Goldstein and Price function.

where,

The function is a classic optimization test function commonly employed for evaluating the performance of optimization algorithms. It features multiple local minima and a complex curve shape, exhibiting non-convexity and nonlinearity in the two-dimensional space. Thus, it serves as a robustness and global search capability test for algorithms. Within the search domain, the function has only one global minimum at $x^{*} = (0, -1)$, with a global optimal value of $f(x^{*}) = 3$. The NFFM successfully found the global minimum and its optimal value using an initial point of $(-3, -3)$.

Problem 7. Two-dimensional Shubert function.

The function is a complex multimodal, non-convex function, containing approximately 760 local minima within the search domain. These local minima are distributed around multiple peaks of the function, posing a greater challenge for algorithms to locate the global minimum. The intricate structure and numerous local minima of this function make it more difficult to assess the robustness and global search capabilities of algorithms, hence it is utilized to evaluate the performance of the algorithm proposed in this paper. Using $(5, 5)$ as the initial starting point, NFFM successfully found the global optimal value of the problem, which is $f(x^{*}) = -186.7309$.

Problem 8. Generalized penalized function.

where, $(a_{ij}) = \quad \begin{matrix} \end{matrix}\begin{pmatrix} -32 & -16 & 0 & 16 & 32 & -32 & \cdots & 0 & 16 & 32 \\ -32 & -32 & -32 & -32 & -32 & -16 & \cdots & 32 & 32 & 32 \end{pmatrix}$.

The function is one of the classic functions used to test the performance of optimization algorithms. It contains multiple local minima within its search domain, along with numerous steep valleys and peaks, presenting a challenge for optimization algorithms to find the global minimum. Therefore, testing the algorithm proposed in this paper on this function provides an effective evaluation of the algorithm's robustness and global search capabilities. The NFFM successfully found the global minimum point at the point $x^{*} = (-32, -32)$ and the global optimal value of $f(x^{*}) = 0.99800383779445$ starting from the initial points $(-40, 20)$ and $(50, 50)$.

Problem 9. Shekel's function

where $m = 5, 7, 10$, $a_{i, j}$ and $c_{i}$ with $i = 1, 2, 3, 4, 5, j = 1, 2, 3, 4$ are provided in Table 1.

This function is one of the classic multimodal optimization test functions, featuring multiple local minima, which poses a certain challenge for optimization algorithms to search for the global minimum. It can be used to evaluate the global search ability and convergence speed of the algorithm. The global minima of this function is $x^{*} = (4, 4, 4, 4)$, and the global optimum is $f(x^{*}) = -10.1532$ when $m = 5$, $f(x^{*}) = -10.4029$ when $m = 7$, and $f(x^{*}) = -10.5364$ when $m = 10$. The NFFM proposed in this paper, with $(0, 0, 0, 0)$ as the initial point, both successfully found its global minima and global optimum.

Problem 10. n-Dimensional Sine-square function.

The function is characterized by its periodicity, nonlinearity, multimodality, and non-convexity, with multiple local minima. The number of local minima within the feasible domain is approximately $10^{n}$. This problem is a high-dimensional optimization problem, and NFFM focuses on solving problems ranging from 2 to 200 dimensions. Starting from the initial point of $(-7.5, -7.5\cdots, -7.5)$, the algorithm successfully finds the global minimum $x^{*} = (1, 1, \cdots, 1)$, and its global optimum $f(x^{*}) = 0$.

Problem 11. n-Dimensional Rastrigin function.

The function exhibits multimodal and non-convex characteristics, encompassing multiple local minima within the feasible region, as well as a global minimum located at the origin of the parameter space, with a global minimum value of 0. This function is commonly used to evaluate the performance of optimization algorithms when dealing with challenging functions. To address this high-dimensional optimization problem, the NFFM specifically targets optimization tasks ranging from 2 to 200 dimensions. Starting from the initial point $(-2.56, -2.56..., -2.56)$, the algorithm successfully locates the global minimum point $x* = (0, 0, ..., 0)$ and achieves the global optimal value of $f(x^{*}) = 0$.

Problem 12. Griewank function.

The Griewank function is renowned for its high degree of nonlinearity and complex behavior in high-dimensional spaces, featuring multiple local minima and a single global minimum. This characteristic poses a significant challenge for many optimization algorithms in finding the global optimal solution. Therefore, it is commonly used as a benchmark test function to evaluate the performance of optimization algorithms. The NFFM proposed in this paper, focusing on the optimization search for 2–200 dimensional problems, takes $(300,300, \cdots, 300)$ as the initial point and successfully finds its global minima $x^{*} = (0, 0, \cdots, 0)$ and the global optimum value of $f(x^{*}) = 0$.

Problem 13. Schewefel function.

The function represents a multidimensional nonlinear optimization problem. It has a wide range of values, typically spanning from $[-500,500]$. The function exhibits multiple local optima, among which there is only one global optimum, occurring at $x_{i} = 420.9687$, with a global minimum value of $f(x^{*}) = 0$. Additionally, this function is a typical deceptive problem, as the global minimum is located far from another local optimum, and the function exhibits steep curves near the optimal solution, making it prone to falling into local optima. Escaping from a local optimum is challenging, posing high demands on the algorithm. Simple algorithms are unlikely to find the optimal solution, thus making it a suitable benchmark for verifying the global search capability and ability to escape local optima of the proposed algorithm in this paper. The NFFM algorithm introduced in this paper focuses on optimizing problems spanning 2 to 200 dimensions. Starting from the initial point $(0, 0, \cdots, 0)$, it successfully finds the global minimum and the corresponding global optimal value.

Problem 14. Rosenbrock function.

The function serves as a classic non-convex optimization problem for testing optimization algorithms. It possesses a global minimum point $x^{*} = (1, 1, \dots, 1)$, yet around this global minimum, there exists a long and tortuous valley. The valley is narrow, requiring optimization algorithms to overcome the function's tortuosity and avoid getting trapped in local optima in order to effectively find the global optimum. Therefore, it is used to evaluate the effectiveness and robustness of optimization algorithms in handling complex, multimodal, and long-valley optimization problems. The NFFM proposed in this paper, focusing on the optimization search for 2–200 dimensional problems, takes $(-15, -15, \cdots, -15)$ as the initial point and successfully finds its global minima $x^{*} = (1, 1, \dots, 1)$ and the global optimum value of $f(x^{*}) = 0$.

4.2.   Numerical results

This section compares the NFFM with five other filled function algorithm on 14 multimodal test functions, including high-dimensional complex unconstrained optimization problems (Problems 10–14). In Table 2, we offer comprehensive clarifications and explanations for the symbols utilized in Tables 3–8.

Table 3 details the specific numerical experimental results of NFFM on the 14 test functions. To verify the feasibility of NFFM, we employed the following evaluation metrics: the number of iterations ($Iter$), the global optimum of the objective problem ($f(x^{*})$), the total number of function evaluations ($NFf$), and the total running time (T(s)). As shown in Table 3, NFFM successfully finds the global optimal values for all the test problems, using points that are relatively far from the global minimum in the feasible region as the initial points. This demonstrates the effectiveness of the proposed non-parametric filled function algorithm in global optimization.

To comprehensively evaluate the performance of NFFM, we conducted a comparison with five other filled function algorithms (PFFF1–PFFF5) on 14 multimodal test functions. Tables 4 to 8 present detailed numerical results of these algorithms on the test functions, where "-" indicates a failure to locate the global optimum. These results were obtained by faithfully reproducing the procedures of the algorithms as described in the original literature. In our experiments, all algorithms used the same initial points and a local search method (Newton's method), while the parameter settings for the comparison algorithms adhered to the values provided in the original literature. One of the algorithms, PFFF1, designed based on a two-parameter filled function, has been proven to outperform the filled function algorithms in ^[7,13] as stated in ^[16]. PFFF2, while also based on a two-parameter filling function, was treated as a single-parameter algorithm in the experiments conducted in ^[15], where the parameter $\epsilon$ was fixed at $10^{-5}$. When compared with algorithms in ^[7,27], PFFF2 exhibited superior performance. Both PFFF3 and PFFF4 have shown better performance when compared to algorithms in ^[13,22,23], respectively. Additionally, the filled function proposed in this paper is an improvement of the one introduced in ^[13], and PFFF5 is a filled function algorithm designed based on the filled function from reference ^[13]. Comparing NFFM with these five algorithms provides strong evidence that the proposed NFFM algorithm possesses significant competitiveness.

Tables 4–8 show the numerical computation results of the NFFM compared with the other five filled function algorithms, respectively. The comparison of numerical results in Table 4 shows that the NFFM's accuracy of the global optimum is better than that of PFFF1 in 13 out of the 14 algorithms tested, and the number of iterations in 12 of these examples is also better or not worse than that of PFFF1. In this paper, the NFFM's performance advantage is more obvious in terms of the performance of the algorithms for solving the high-dimensional test problems. The NFFM successfully optimizes them all, and the accuracy and number of iterations of the obtained global optimums are better than PFFF1. However, for the successfully solved examples, the NFFM outperforms PFFF1 only for a few of the successfully solved cases, in terms of the total amount of function computation and time consumed for the objective function and the filled function.

Comparison of the numerical experimental results in Table 5 shows that the accuracy of the global optimum of PFFF2 is better than that of the NFFM only in solving the 30-dimensional and 50-dimensional problems of Problem 10 and the 2–200-dimensional problems of Problem 11, but the number of iterations used is higher than that of the NFFM. PFFF1 fails to find an optimal solution for the 200-dimensional problem of Problem 11. In addition, for Problem 13 and Problem 14, the NFFM in this paper is able to successfully find their global optimal solutions, while PFFF2 fails to find an optimal solution for them. Therefore, in summary, the NFFM performs better than PFFF2.

In order to prove the effectiveness of the algorithm more strongly, the NFFM was experimentally compared with the parameter-free filled function algorithms PFFF3 and PFFF4, which have been proposed in the last three years. The comparison of the specific experimental computational results is shown in Tables 6 and 7. It can be seen from Table 6 that PFFF3 fails in finding the optimum for some examples. Neglecting the problems with the same number of iterations and global optimum and the problems where PFFF3 fails to find the optimal value, and comparing the number of iterations and global optimum of the NFFM with those of PFFF3, the NFFM in this paper has a slightly higher number of iterations than that of PFFF3 only in the solving of Problem 8, and the NFFM's accuracy of the number of iterations and global optimum is superior to that of PFFF3 for the rest of the problems. Similarly, ignoring the problem with the same number of iterations and global optimum and the problem where PFFF4 fails to find the optimum, the NFFM outperforms PFFF4 in terms of the accuracy of the global optimum on the solution of the rest of the problems, and the number of iterations at the termination of the algorithm is slightly higher than that of PFFF4 in only one of the algorithms. In addition, for Problem 13, which is a typical spoofing problem, it is very easy to make the algorithm fall into a local optimal solution. In this paper, the NFFM can successfully find the global optimal solution of this problem, but the algorithms PFFF3 and PFFF4 cannot achieve it. Therefore, evaluated from the two perspectives of iteration number and global optimum, the NFFM is efficient and feasible in solving the above 14 unconstrained optimization problems. Furthermore, to highlight the superior performance of the improved filled function in this paper, we have conducted a comparative analysis of the numerical results of NFFM and algorithm PFFF5 on Problems 1 to 9. These problems utilize the same test functions as those used to validate PFFF5 in reference ^[22]. The detailed comparison results are presented in Table 8, showing that NFFM successfully finds the global optimal solutions for all nine problems with higher accuracy.

Tables 4–8 present the numerical results of the filled function algorithm in solving 14 test functions from a given initial point. To validate the independence of our proposed algorithm from the choice of the initial point, we have conducted additional experiments on Problems 11 and 12. Specifically, we randomly generated 10 points within the feasible region of the target problems and independently applied these points to these two problems. We employed three distinct metrics to compare the capabilities of the NFFM against other filled function algorithms. These metrics are: the average number of iterations($I_{t}$); the average value of the global optimum achieved by the algorithm($f_{m}$); and the success rate in successfully finding the global optimum over 10 independent runs of the algorithm are denoted as $SR$. The specific numerical experimental results are presented in Tables 9 and 10. In a comprehensive comparison, NFFM has exhibited comprehensive advantages in the numerical computation phase, with all its indicators surpassing those of the other four comparative algorithms. It is worth noting that the average global optimal value achieved by the NFFM possesses remarkably high precision, and its success rate nearly reaches $100\%$, thus proving the superior performance and reliability of NFFM in addressing related problems.

However, considering the total running time and the total number of function evaluations, the numerical results in Tables 4 to 7 indicate that, as the dimension of the test functions increases during the optimization of problems 10 to 14, the total running time and the total number of function evaluations also increase accordingly. This is primarily due to the fact that traditional filled function algorithms often employ a fixed or limited number of perturbation step sizes when generating initial points for minimizing filled functions. This approach can lead to the algorithms getting stuck in local minima and failing to find the global optimal solution when dealing with high-dimensional and complex unconstrained optimization problems. To address this issue, the proposed algorithm NFFM in this paper perturbs the current local minimum and uses it as an initial point during the minimization of the filled function. It continuously searches for a better local minimum. If a better solution is not found, the algorithm increases the perturbation of the current local minimum of the objective function until it reaches the boundary of the feasible region, at which point the algorithm terminates. This approach may require more time and computational resources when dealing with some high-dimensional problems. However, this design ensures a more comprehensive exploration of the solution space, increasing the likelihood of finding the global optimal solution. Although the proposed NFFM in this paper may require more time when sloving high-dimensional unconstrained optimization problems, the time complexity analysis reveals that the time complexity for other algorithms to escape a local minimum is $O(n*T(local))$. Similarly, the time complexity of NFFM to escape a local minimum is also $O(n*T(local))$. Therefore, in terms of time complexity, the proposed algorithm is comparable to other contrasting algorithms.

In summary, the proposed NFFM in this paper significantly reduces the number of iterations, improves the accuracy of the global optimal solution, and effectively tackles high-dimensional multimodal unconstrained optimization problems, exhibiting strong ability to escape from local minima. Through extensive numerical comparative experiments and validation on high-dimensional problems, the NFFM has been proven feasible and efficient, outperforming algorithms PFFF1–PFFF5 in terms of computational capability.

5.   Conclusions

This paper introduces a novel, parameter-free, and continuously differentiable filled function that eliminates the traditional exponential and logarithmic terms, while rigorously proving its filling property. By leveraging this innovative function, we have developed a new filled function algorithm that significantly enhances its performance in addressing multimodal global optimization problems by optimizing the perturbation step size. Through extensive testing and comparative analysis on 14 benchmark functions, we have convincingly demonstrated the efficacy and precision of our algorithm in addressing high-dimensional multimodal global optimization problems. Our proposed algorithm surpasses existing methods, exhibiting superior solution accuracy, stability, and reliability. This accomplishment introduces a robust new instrument for tackling global optimization challenges, thereby emphasizing the significant potential and widespread applicability of the filled function approach in contemporary optimization research.

Author contributions

J. Li, Y. Gao, T. Chen and X. Ma: writing, review and editing. All authors have read and approved the final version of the manuscript for publication.

Use of AI tools declaration

The authors declare that they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

This research is supported by the Natural Science Foundation of NingXia Hui Autonomous Region (2022AAC02043); the Construction Project of first-class subjects in Ningxia higher Education (NXYLXK2017B09); the Major Research Funding Project of North Minzu University (ZDZX201901); the Graduate Innovation Project of North Minzu University (2024YCX24037); the basic discipline research projects supported by Nanjing Securities (NJZQJCXK202201).

Conflict of interest

The authors declare no conflicts of interest.