A New Nonparametric Filled Function Method for Integer Programming Problems with Constraints

Abstract

In this paper, we investigate and develop a new filled function method for solving integer programming problems with constraints. By adopting the appropriate equivalent transformation method, these problems are transformed into a class of box-constrained integer programming problems. Then, an effective nonparametric filled function is constructed, and a new global optimization algorithm is designed using the discrete steepest descent method. Numerical experiments illustrate that this algorithm has effectiveness, feasibility, and better global optimization ability.

1. Introduction

Consider the following integer programming problem with constraints:

$$\left(\mathrm{P}\right)\left\{\begin{array}{c}minf\left(x\right)\hfill \\ s.t.g_i\left(x\right)\le 0,i=1,2,\cdots ,m,\hfill \\ x\in {\mathbb{Z}}^n,\hfill \end{array}\right.$$

where ${\mathbb{Z}}^n$ denotes the set of integer points in ${\mathbb{R}}^n$, and $S=\{x\in {\mathbb{Z}}^n|g_i\left(x\right)\le 0,i=1,2,\cdots ,m\}$ is bounded.

Some problems in economy, finance, engineering, and other fields can often be quantified as a global optimization problem (P). Most of these problems, however, are computationally and theoretically difficult to solve in polynomial time, so they are often referred to as NP-hard problems. So far, the existing global optimization algorithms for solving problem P can be classified into deterministic algorithms [1,2,3,4,5] and stochastic algorithms [6,7,8,9]. Among them, the filled function method, which was first proposed by Ge [1], is favored by many scholars as a deterministic method of global optimization. The main idea of this method is to continuously construct the filled function (FF) at the local minimizer $\left(x_k^{*}\right)$ in the current iteration and then take the point near $x_k^{*}$ as the initial point to minimize FF, so as to get out of the basin where $x_k^{*}$ is located and find the local minimizer $x_{k+1}^{*}$ better than $x_k^{*}$, which achieves the purpose of global optimization. Therefore, the filled function method avoids the “precocity” defect of general optimization algorithms. As defined in [1], if $\mathsf{\Psi }(x,x_k^{*})$ is called a FF of the objective function $f\left(x\right)$ at a local minimizer $x_k^{*}$, it needs to satisfy:

(i)

$x_k^{*}$ is a strictly local maximizer of $\mathsf{\Psi }(x,x_k^{*})$, and the basin $B_k^{*}$ of $f\left(x\right)$ at $x_k^{*}$ becomes a part of a hill of $\mathsf{\Psi }(x,x_k^{*})$ at $x_k^{*}$;

(ii)

in the basin where $f\left(x\right)$ is higher than $B_k^{*}$, $\mathsf{\Psi }(x,x_k^{*})$ has no local minimizer;

(iii)

if $f\left(x\right)$ has a basin $\overline{B}$ lower than $B_k^{*}$, then minimizing $\mathsf{\Psi }(x,x_k^{*})$ must be able to find its local minimizer $x_{k+1}^{*}$ in the line between x and $x_k^{*}$ in $\overline{B}$.

In the late 1990s, Zhu [10] first proposed the discrete equivalent method of continuous FF, and the FF formula is as follows:

$${\mathsf{\Psi }}_{\gamma ,\rho ,x^{*}}\left(x\right)=\frac{1}{\gamma +f\left(x\right)}exp\left(-\frac{\parallel x-x^{*}{\parallel }^2}{{\rho }^2}\right),$$

(1)

where $\gamma$ and $\rho$ denote parameters to ensure that the algorithm can be executed and the global minimizer can be obtained. For the exponential term $exp\left(-\frac{\parallel x-x_k^{*}{\parallel }^2}{{\rho }^2}\right)$ with large $\parallel x-x_k^{*}{\parallel }^2$ or small $\rho$, this Formula (1) produces an almost flat image, which makes it difficult for the computer to distinguish between changes in function values. In addition, Zhu’s approach has been discussed in depth in [11,12,13]. In 2006, Wu et al. [14] proposed a FF (2) for solving integer programming problems with box constraints.

$$\mathsf{\Psi }(x,x^{*},r,q)=\frac{1}{1+\parallel x-x^{*}{\parallel }^2}{g}_r(f\left(x\right)-\frac{f\left(x^{*}\right)}{2})+q{f}_r(f\left(x\right)-\frac{f\left(x^{*}\right)}{2}),$$

(2)

where,

$$\begin{array}{cc}\hfill g_r\left(t\right)=& \hfill \left\{\begin{array}{cc}0,\hfill & t\le -r,\\ -\frac{2}{r^3}{t}^3-\frac{3}{r^2}{t}^2+1,\hfill & -r<t\le 0,\\ 1,\hfill & t\ge 0,\end{array}\right. f_r\left(t\right)=\left\{\begin{array}{cc}t+r,\hfill & t\le -r,\\ \frac{r-2}{r^3}{t}^3+\frac{r-3}{r^2}{t}^2+1,\hfill & -r<t\le 0,\\ 1,\hfill & t>0.\end{array}\right.\hfill \end{array}$$

To address the nonlinear integer programming problem with inequality constraints, Yang et al. [15] proposed a FF in the following form in 2008:

$$\mathsf{\Psi }(r,x,x^{*})=\left(\frac{1}{1+\parallel x-x^{*}{\parallel }^2}+1\right)h\left(h_r(f\left(x\right)-f\left(x^{*}\right))\right)+\sum _{i=1}^m{h}_r(g_i\left(x\right)-r),$$

(3)

where

$$\begin{array}{cc}\hfill h_r\left(t\right)& \hfill =\left\{\begin{array}{cc}0,\hfill & t\le -r,\\ \frac{r-2}{r^3}{t}^3+\frac{2r-3}{r^2}{t}^2+t+1,\hfill & -r<t\le 0,\\ t+1,\hfill & t>0,\end{array}\right.\hfill \\ \hfill h\left(t\right)& \hfill =\left\{\begin{array}{cc}0,\hfill & t\le \frac{1}{2},\\ -16t^3+36t^2-24t+5,\hfill & \frac{1}{2}<t\le 1,\\ 1,\hfill & t>1.\end{array}\right.\hfill \end{array}$$

To overcome the defect of FF in solving constrained global optimization problems, the Formula (3) combines the FF in unconstrained optimization with the penalty function in constrained optimization. For solving the nonlinear integer programming problem with box constraints, Lin et al. [16] also proposed a FF as follows.

$$\mathsf{\Psi }(x,x^{*},q)=\frac{1}{q+\parallel x-x^{*}\parallel }{\varphi }_q\left(f\left(x\right)-\frac{f\left(x^{*}\right)}{4}\right),$$

(4)

where

$${\displaystyle {\varphi }_q\left(t\right)\left\{\begin{array}{cc}arctan(-\frac{q^2}{t^2})+\frac{\pi }{2},\hfill & t\ne 0,\\ 0,\hfill & t=0.\end{array}\right.}$$

The above four FFs contain either parameters or exponential factors, which will reduce the computational efficiency of the FF algorithm. This is because such FFs are highly dependent on parameters, but the parameter selection is usually particularly difficult, and the exponential factors will lead to the overflow of numerical results. In addition to the above FFs, many scholars have also made innovations, such as [12,17,18,19]. More importantly, in [19], these two authors reviewed and summarized nine existing filled functions, and they believed that these filled functions had a broad development prospect. However, most of the FFs mentioned above are aimed at box constrained or unconstrained optimization problems, and some researches on constrained integer programming problems are still relatively few, so it is necessary to further propose a new filled function, which can solve constrained integer programming problems. At present, the research methods of constrained integer programming problems are mainly divided into two categories. One is to directly construct FF satisfying constraints; the other is to use penalty function method [20] to convert constrained optimization problems into unconstrained optimization problems or box-constrained optimization problems. It is satisfying that Lin [18] et al. cleverly used the idea of equivalent transformation for problem P, that is, the second type method; on this basis, it is worth us to further improve its transformation process more accurately.

In this paper, a new equivalent transformation method is used to reconstruct the problem P into a box-constrained optimization problem (OP). Based on the problem OP, a nonparametric FF with the same local minimizer as its objective function is constructed, and a new global optimization algorithm is designed. In the iterative process of the algorithm, only FF needs to be continuously minimized. A series of numerical experiments are carried out on a large number of test problems, and the numerical results show that the algorithm is effective.

The rest of this paper is organized as follows. Section 2 is a review of some assumptions and definitions. Section 3 is the detailed description of the equivalent transformation to the problem P. The nonparametric FF constructed and its properties are analyzed and proved in Section 4. In Section 5, a new global optimization algorithm is designed combined with the proposed new FF. Numerical experiments and conclusions are given in Section 6 and Section 7, respectively.

2. Assumptions and Definitions

To make the problem P solvable, it is necessary to give some assumptions and definitions. In [21], the content of the improved definition of FF is extended as follows:

Definition 1.

Suppose $x_k^{*}$ is a discrete local minimizer of the objective function $f\left(x\right)$. If $\mathsf{\Psi }(x,x_k^{*})$ is called a FF of $f\left(x\right)$ at $x_k^{*}$, then it needs to satisfy:

(i) 

$x_k^{*}$ is a strictly discrete local maximizer of $\mathsf{\Psi }(x,x_k^{*})$; and the basin $B_k^{*}$ of $f\left(x\right)$ at $x_k^{*}$ becomes a part of a hill of $\mathsf{\Psi }(x,x_k^{*})$ at $x_k^{*}$;

(ii) 

$\mathsf{\Psi }(x,x_k^{*})$ has no discrete local minimizer in set $S_k^1=\left\{x\right|f\left(x\right)⩾f\left(x_k^{*}\right),x\in S\backslash \left\{x_k^{*}\right\}\}$;

(iii) 

If $x_k^{*}$ is not a discrete global minimizer of $f\left(x\right)$, then $S_k^2\ne ⌀$, $\mathsf{\Psi }(x,x_k^{*})$, and $f\left(x\right)$ have the same discrete local minimizer in $S_k^2=\left\{x\right|f\left(x\right)<f\left(x_k^{*}\right),x\in S\}$.

Assumption 1.

Let  τ be the set of all the local minimizers of problem $\mathrm{P}$, and $L^{*}=\left\{f\left(x\right)\right|x\in \tau \}$.

Definition 2.

For any integer point $x\in {\mathbb{Z}}^n$, the set $N\left(x\right)\subseteq {\mathbb{Z}}^n$ can be called a discrete neighborhood for x, where $N\left(x\right)=\{x,x\pm e_i:i=1,2,\cdots ,n\}$. The set of all axial directions $d\in N\left(x\right)$ can be defined as $D=\{d\in {\mathbb{R}}^n:d=\pm e_i,i=1,2,\cdots ,n\}$, where n denotes the number of variables of the $f\left(x\right)$, and $e_i$ is a unit vector with the ith component equal to 1 and the remaining components equal to 0.

Definition 3.

A vector $d\in D$ is called a discrete descent direction of $f\left(x\right)$ at $x\in S$ if d is such that $x+d\in S$ and $f(x+d)<f\left(x\right)$.

Definition 4.

A vector $d^{*}\in D$ is called a discrete steepest descent direction of $f\left(x\right)$ at $x\in S$ if $f(x+d^{*})\le f(x+d)$ for any $d\in D^{*}$, where $D^{*}$ denotes the set of all discrete descent directions of $f\left(x\right)$ at $x\in S$.

Definition 5.

A point $x_0$ is called a (strictly) discrete local minimizer of problem $\mathrm{P}$ if an integer point $x_0\in S$ is such that $f\left(x\right)(>)\ge f\left(x_0\right)$ for any $x\in N\left(x_0\right)\cap S$.

Definition 6.

A point $x_0$ is called a (strictly) discrete global minimizer of problem $\mathrm{P}$ if an integer point $x_0\in S$ is such that $f\left(x\right)(>)\ge f\left(x_0\right)$ for any $x\in S$.

At present, there are many local optimization algorithms to solve continuous optimization problems. However, there are few local search methods to solve discrete optimization problems. Different from continuous optimization problems, the discreteness of discrete optimization problems makes the gradient of function unusable, which leads to the birth of discrete descent algorithm. After that, many scholars also improved the algorithm for different problems, and proposed various discrete local minimization methods, such as variable neighborhood search algorithm [22], neighborhood search algorithm [22], and discrete steepest descent algorithms [18,23,24]. In this paper, we adopt the following discrete steepest descent algorithm in [24].

3. Transformation of the Original Problem

To facilitate the construction of the FF, we first make an equivalent transformation to the problem P, so that the problem can be easily handled. The specific contents are as follows:

Theorem 1.

For any $\overline{x}\in S$, let $\overline{u}=f\left(\overline{x}\right)$, then problem

$$\left(\overline{\mathrm{P}}\right)\left\{\begin{array}{c}minf\left(x\right)\hfill \\ s.t.g_i\left(x\right)\le 0,i=1,2,\cdots ,m,\hfill \\ x\in {\mathbb{Z}}_n,\hfill \\ f\left(x\right)\le \overline{u},\hfill \end{array}\right.$$

and $\mathrm{P}$ have the same global optimal solution.

Proof. 

Let $x^{*}$ be a global optimal solution to $\overline{\mathrm{P}}$. Suppose $x^{*}$ is not global optimal for P, there must exist a $\widehat{x}\in S=\{x\in {\mathbb{R}}^n|x\in {\mathbb{Z}}^n,g_i\left(x\right)\le 0,i=1,2,\cdots ,m\}$ such that

$$f\left(\widehat{x}\right)<f\left(x^{*}\right),$$

(5)

and

$$f\left(x^{*}\right)<\overline{u},$$

(6)

then, it follows from Formulas (5) and (6) that $f\left(\widehat{x}\right)<\overline{u}$, which indicates that $\widehat{x}$ is feasible for $\overline{\mathrm{P}}$, so Formula (5) shows that $\widehat{x}$ contradicts the global optimal solution $x^{*}$ of $\overline{\mathrm{P}}$. □

From the boundness of set S, it follows that there must be a feasible region of the problem $\overline{\mathrm{P}}$ contained in box $\mathsf{\Omega }$.

For convenience, let us define the following two univariate functions:

$$g\left(t\right)=\left\{\begin{array}{c}0,t>0,\hfill \\ 1,t\le 0,\hfill \end{array}\right.s\left(t\right)=\left\{\begin{array}{c}0,t=m+1,\hfill \\ 1,t<m+1,\hfill \end{array}\right.$$

where m denotes the number of constraints of problem P.

Next, consider the following problem:

$$\left(\mathrm{OP}\right)\left\{\begin{array}{c}min\mathrm{F}\left(\mathrm{x}\right),\hfill \\ s.t.\mathrm{x}\in \mathsf{\Omega }\cap {\mathbb{Z}}^{\mathrm{n}},\hfill \end{array}\right.$$

where

$$F\left(x\right)=f\left(x\right)+(\overline{u}-f\left(x\right))\times s\left(\sum _{i=1}^{m}g\left(g_i\left(x\right)\right)+g(f\left(x\right)-\overline{u})\right).$$

Theorem 2.

If $\overline{x}$ is a local minimizer of $\overline{\mathrm{P}}$, then $\overline{x}$ is also a local minimizer of $\mathrm{OP}$; conversely, if $\overline{x}$ is a local minimizer of $\mathrm{OP}$, then $\overline{x}$ is also a local minimizer of $\overline{\mathrm{P}}$, or $F\left(\overline{x}\right)=\overline{u}+1$.

Proof. 

In Theorem 3.1 of [18], let $M=\overline{u}+1$, then the proof of this theorem can be obtained, so it will not be repeated here. □

Remark 1.

According to Theorem 2, we can know that problems $\overline{\mathrm{P}}$ and $\mathrm{OP}$ have the same minimizer except infeasible point. If the global minimizer of problem $\mathrm{OP}$ can be found, then the global minimizer of problem $\overline{\mathrm{P}}$ can also be found.

4. Nonparametric Filled Function and Its Analytical Properties

Based on the previous three sections, we propose a new nonparametric FF:

$$\mathsf{\Psi }(x,x_k^{*})=\left(\pi -arctan\left(\parallel x-x_k^{*}{\parallel }^2\right)\right)\times \varphi \left(F\left(x\right)-F\left(x_k^{*}\right)\right)+min\{0,{(F\left(x\right)-F\left(x_k^{*}\right))}^3\},$$

(7)

where

$$\varphi \left(r\right)=\left\{\begin{array}{c}1,r\ge 0,\hfill \\ 0,r<0,\hfill \end{array}\right.$$

$\parallel ·\parallel$ denotes Euclidean norm and $x_k^{*}$ represents a discrete local minimizer. This FF avoids some of the disadvantages discussed in Section 1 and has the nice property of having the same local minimizer as the objective function.

Now, we define two sets:

$$S_k^1=\{x\in \mathsf{\Omega }\cap {\mathbb{Z}}^n\mid F\left(x\right)\ge F\left(x_k^{*}\right)\},$$

$$S_k^2=\{x\in \mathsf{\Omega }\cap {\mathbb{Z}}^n\mid F\left(x\right)<F\left(x_k^{*}\right)\},$$

the following is the verification that $\mathsf{\Psi }(x,x_k^{*})$ satisfies the FF defined in Section 2.

Theorem 3.

If $x_k^{*}\in \tau$, $x_1\in S_k^1$, then $x_k^{*}$ is a strictly discrete local maximizer of $\mathsf{\Psi }(x,x_k^{*})$.

Proof. 

It follows from $x_1\in S_k^1$ that $F\left(x_1\right)\ge F\left(x_k^{*}\right)$. From the definition of $\varphi$, there is

$$\begin{array}{cc}\hfill \mathsf{\Psi }(x_1,x_k^{*})& \hfill =\pi -arctan\left(\parallel x_1-x_k^{*}{\parallel }^2\right)<\pi =\mathsf{\Psi }(x_k^{*},x_k^{*}).\hfill \end{array}$$

Obviously, $x_k^{*}$ is a strictly discrete local maximizer of $\mathsf{\Psi }(x,x_k^{*})$. □

Theorem 4.

If $x_k^{*}\in \tau$ and $x_a,x_b\in S_k^1$ satisfy $\parallel x_a-x_k^{*}\parallel <\parallel x_b-x_k^{*}\parallel$, then

$$\mathsf{\Psi }(x_b,x_k^{*})<\mathsf{\Psi }(x_a,x_k^{*})<\pi =\mathsf{\Psi }(x_k^{*},x_k^{*}).$$

Proof. 

Since $x_a,x_b\in S_k^1$, then $F\left(x_a\right)\ge F\left(x_k^{*}\right),F\left(x_b\right)\ge F\left(x_k^{*}\right)$. From the definition of function $\varphi$, it follows that

$$\mathsf{\Psi }(x_a,x_k^{*})=\pi -arctan\left(\parallel x_a-x_k^{*}{\parallel }^2\right),$$

$$\mathsf{\Psi }(x_b,x_k^{*})=\pi -arctan\left(\parallel x_b-x_k^{*}{\parallel }^2\right),$$

Upon the condition $\parallel x_a-x_k^{*}\parallel <\parallel x_b-x_k^{*}\parallel$, we have

$$\begin{array}{c}\hfill \mathsf{\Psi }(x_b,x_k^{*})-\mathsf{\Psi }(x_a,x_k^{*})=-arctan\left(\parallel x_b-x_k^{*}{\parallel }^2\right)-\left(-arctan\left(\parallel x_a-x_k^{*}{\parallel }^2\right)\right)<0,\end{array}$$

thus $\mathsf{\Psi }(x_b,x_k^{*})<\mathsf{\Psi }(x_a,x_k^{*})<\pi =\mathsf{\Psi }(x_k^{*},x_k^{*})$. □

Theorem 4 shows that, on the high level set $S_k^1$, the farther away from the current local minimizer $x_k^{*}$, the faster the FF value decreases. Thus, it ensures that the minimization process of $\mathsf{\Psi }(x,x_k^{*})$ can always be realized and a better point can be found faster.

Lemma 1.

For any $x,x^{*}\in S$, if there is an $i\in \{1,2,\cdots ,n\}$ such that $x+e_i\in S$, there must be a $d\in D$ that satisfies $\parallel x+d-x_k^{*}\parallel >\parallel x-x_k^{*}\parallel$.

Proof. 

If $x=x_k^{*}$, the conclusion is obvious. If $x\ne x_k^{*}$, there must be an $i\in \{1,2,\cdots ,n\}$ such that $x_i\ne x_{ki}^{*}$. If $x_i>x_{ki}^{*}$, let $d=e_i$; otherwise, let $d=-e_i$. □

Theorem 5.

If $x_k^{*}$ is a discrete local minimizer of $F\left(x\right)$, then $\mathsf{\Psi }(x,x_k^{*})$ has no discrete local minimizer over the set $S_k^1$.

Proof. 

For any $x\in S_k^1$, we know $\mathsf{\Psi }(x,x_k^{*})=\pi -arctan\left(\parallel x-x_k^{*}{\parallel }^2\right)$. The existence of $d\in D$ is such that $\parallel x+d-x_k^{*}\parallel >\parallel x-x_k^{*}\parallel$. Hence, we discuss the conclusion in the following two cases:

(1)

If $F(x+d)\ge F\left(x_k^{*}\right)$, then

$$\begin{array}{cc}\hfill \mathsf{\Psi }(x+d,x_k^{*})-\mathsf{\Psi }(x,x_k^{*})& \hfill =arctan(\parallel x-x_k^{*}{\parallel )}^2-arctan(\parallel x+d-x_k^{*}{\parallel )}^2<0;\hfill \end{array}$$

(2)

If $F(x+d)<F\left(x_k^{*}\right)<F\left(x\right)$, then

$$\begin{array}{cc}\hfill \mathsf{\Psi }(x+d,x_k^{*})-\mathsf{\Psi }(x,x_k^{*})& \hfill ={\left(F(x+d)-F\left(x_k^{*}\right)\right)}^3-\left(\pi -arctan(\parallel x-x_k^{*}{\parallel )}^2\right)<0.\hfill \end{array}$$

Therefore, for all $x\in S_k^1$, there is always a $d\in D^{*}$ such that $\mathsf{\Psi }(x+d,x_k^{*})<\mathsf{\Psi }(x,x_k^{*})$, i.e., $\mathsf{\Psi }(x,x_k^{*})$ has no discrete local minimizers in the set $S_k^1$. □

Theorems 6 and 7 state that $F\left(x\right)$ and $\mathsf{\Psi }(x,x_k^{*})$ have the same local minimizer over $S_k^2$.

Theorem 6.

If $x_1^{*}$ is a discrete local minimizer of $F\left(x\right)$ and satisfies $F\left(x_1^{*}\right)<F\left(x_k^{*}\right)$, then $x_1^{*}$ is also a discrete local minimizer of $\mathsf{\Psi }(x,x_k^{*})$.

Proof. 

If $x_1^{*}$ is a discrete local minimizer of $F\left(x\right)$ and satisfies $F\left(x_1^{*}\right)<F\left(x_k^{*}\right)$, then $x_1^{*}\in S_k^2$ and $\mathsf{\Psi }(x_1,x_k^{*})={(F\left(x_1\right)-F\left(x_k^{*}\right))}^3<0.$ For any $x\in N\left(x_1^{*}\right)$, there is $F\left(x\right)⩾F\left(x_1^{*}\right)$; let us consider the following two cases:

(1).

If $x\in S_k^1\cap N\left(x_1^{*}\right)$, then $\mathsf{\Psi }(x,x_k^{*})=\pi -arctan(\parallel x-x_k^{*}{\parallel }^2)>0>\mathsf{\Psi }(x_1,x_k^{*})$.

(2).

If $x\in S_k^2\cap N\left(x_1^{*}\right)$, then $\mathsf{\Psi }(x,x_k^{*})={(F\left(x\right)-F\left(x_k^{*}\right))}^3\ge {(F\left(x_1^{*}\right)-F\left(x_k^{*}\right))}^3=\mathsf{\Psi }(x_1^{*},x_k^{*})$.

 □

Theorem 7.

If $x_2^{*}$ is a discrete local minimizer of $\mathsf{\Psi }(x,x_k^{*})$ and satisfies $\mathsf{\Psi }\left(x_2^{*}\right)<0$, then $x_2^{*}$ is also a discrete local minimizer of $F\left(x\right)$, and $F\left(x_2^{*}\right)<F\left(x_k^{*}\right)$.

Proof. 

Let $x_2^{*}$ be a discrete local minimizer of $\mathsf{\Psi }(x,x_k^{*})$ and satisfies $\mathsf{\Psi }\left(x_2^{*}\right)<0$, then $\mathsf{\Psi }\left(x_2^{*}\right)<\mathsf{\Psi }\left(x_k^{*}\right)$ and $x_2^{*}\in S_k^2$.

Now, let us prove that $x_2^{*}$ is also a discrete local minimizer of $F\left(x\right)$. Suppose $x_2^{*}$ is not a local minimizer of $F\left(x\right)$, there must be a $x_3^{*}\in N\left(x_2^{*}\right)$ such that $F\left(x_3^{*}\right)<F\left(x_2^{*}\right)$. Since $F\left(x_2^{*}\right)<F\left(x_k^{*}\right)$, then $F\left(x_3^{*}\right)<F\left(x_k^{*}\right)$. Thus,

$$\mathsf{\Psi }(x_3^{*},x_k^{*})={(F\left(x_3^{*}\right)-F\left(x_k^{*}\right))}^3<{(F\left(x_2^{*}\right)-F\left(x_k^{*}\right))}^3=\mathsf{\Psi }(x_2^{*},x_k^{*}),$$

which contradicts the fact that $x_2^{*}$ is a discrete local minimizer of $\mathsf{\Psi }(x,x_k^{*})$. □

In summary, it is proved by Theorems 3–7 that $\mathsf{\Psi }(x,x_k^{*})$ is a nonparametric FF.

5. Filled Function Algorithm

In this section, we develop a new nonparametric FF algorithm NPFFA based on the FF constructed in the previous section. The local descent method adopts the Algorithm 1. In this algorithm, the problem of boundary overflow is improved and some unnecessary computation is avoided. Moreover, the proposed FF has the same local minimizer as the objective function, so the constructed algorithm only needs to minimize the FF in the iterative process, which greatly reduces the amount of calculation.

Algorithm 1: (DSDA)

Step 1. Select a starting point $x_0\in S$. Step 2. If $x_0$ is a local minimizer for $f\left(x\right)$, then stop. Otherwise, let $$d^{*}=argmin\{f(x_0+d_i):d_i\in D_{x_0},f(x_0+d_i)<f\left(x_0\right)\},$$ where $D_{x_0}=\{d\in D:x_0+d\in S\}$ is a set of feasible directions at $x_0$; Step 3. Let $x_0=x_0+d^{*}$, and return to step 2.

6. Numerical Experiment

This section uses MATLAB (2016a) to encode and execute the Algorithm 2 and the algorithm in [18]. All calculations are performed on a desktop computer with Intel(R) Core(TM)i5-8500 3.00 GHz power processor 8.00 GB memory and Win10 operating system. The reliability and effectiveness of Algorithm 2 are verified using 13 test problems (a total of 84 test instances) to test and compare these two algorithms.

Algorithm 2:$\left(\mathbf{NPFFA}\right)$

Step 0. Give a starting point $x_0\in S$; Let $\overline{u}=f\left(x_0\right),D=\{d_1,d_2,\dots ,d_{2n}\}$, where $d_i=e_i,d_{n+i}=-e_i,i=1,2,\dots ,n$. Step 1. Use Algorithm 1 to minimize $F\left(x\right)$ with $x_0$ and obtain a local minimizer $x_1^{*}$. Set $k=1$. Step 2. Construct the following FF $$\mathsf{\Psi }(x,x_k^{*})=(\pi -arctan\left(\parallel x-x_k^{*}{\parallel }^2\right))\times \varphi (F\left(x\right)-F\left(x_k^{*}\right))+min\{0,(F\left(x\right)-F{\left(x_k^{*}\right))}^3\}.$$ Step 3. Take $x_i=x_k^{*}+d_i$ as the initial point to minimize $\varphi (x,x_k^{*})$ and obtain the local minimizer $x_k^f$. Step 4. If $F\left(x_k^f\right)<F\left(x_k^{*}\right)$, let $x_k^{*}=x_k^f$, $F\left(x_k^{*}\right)=F\left(x_k^f\right)$, $k=k+1$, and return to step 2. Step 5. If $i\ge 2n$, go to step 6; otherwise, let $i=i+1$ and return to step 3. Step 6. Output $x_k^{*}$.

6.1. Test Function

This section mainly gives 13 test functions, where $f\left(x\right)$ denotes the objective function, $x_0$ is the initial point, and the global minimizer and the global minimum value are represented by $x^{*}$ and $f\left(x^{*}\right)$, respectively.

Problem 1

([25]).

$$\begin{array}{cc}& minf\left(x\right)=x_1^2+x_2^2+3x_3^2+4x_4^2+2x_5^2-8x_1-2x_2-3x_3-x_4-2x_5,\hfill \\ & s.t.x_1+x_2+x_3+x_4+x_5\le 400,x_1+2x_2+2x_3+x_4+6x_5\le 800,\hfill \\ & 2x_1+x_2+6x_3\le 200,x_3+x_4+5x_5\le 200,\hfill \\ & x_1+x_2+x_3+x_4+x_5\ge 55,x_1+x_2+x_3+x_4\ge 48,\hfill \\ & x_2+x_4+x_5\ge 34,6x_1+7x_5\ge 104,\hfill \\ & 0\le x_i\le 99,x_i\in {\mathbb{Z}}^n,i=1,2,3,4,5.\hfill \end{array}$$

For Problem 1, the discrete global optimal solution is $x^{*}={(16,22,5,5,7)}^T$, $f\left(x^{*}\right)=807$. This problem was tested with five different initial points, and the numerical results are shown in Table 1.

Problem 2

([26]).

$$\begin{array}{cc}& minf\left(x\right)=100{(x_2-x_1^2)}^2+{(1-x_1)}^2,\hfill \\ & s.t.x_1^2+x_2^2\ge 0.25,-\frac{1}{3}{x}_1+x_2\ge -0.1,\hfill \\ & x_i=y_i/\mathrm{10,000},0\le y_i\le {10}^5,\hfill \\ & y_i\in {\mathbb{Z}}^n,i=1,2.\hfill \end{array}$$

Problem 2 has about $8.413\times {10}^9$ points in the feasible region. The discrete global optimal solution is $x^{*}={(1,1)}^T$, $f\left(x^{*}\right)=0$. This problem was tested with nine different initial points, and the numerical results are shown in Table 1.

Problem 3

([27]).

$$\begin{array}{cc}& minf\left(x\right)=2x_1{x}_2^2-4x_1{x}_2+x_1^2+x_2^2-27x_1^2{x}_2^2,\hfill \\ & s.t.x_1^2+2x_1{x}_2+x_2^2\le 500,x_1+2x_2^2\le 400,\hfill \\ & 0\le x_1\le 500,0\le x_2\le 100,\hfill \\ & x_i\in {\mathbb{Z}}^n,i=1,2.\hfill \end{array}$$

Problem 3 has a lot of feasible points. The discrete global optimal solution is $x^{*}={(11,11)}^T$, $f\left(x^{*}\right)=-\mathrm{392,887}$. This problem was tested with two different initial points, and the numerical results are shown in Table 1.

Problem 4

(Powell’s singular function [19,21]).

$$\begin{array}{cc}& minF\left(x\right)={(x_1+10x_2)}^2+5{(x_3-x_4)}^2+{(x_2-2x_3)}^4+10{(x_1-x_4)}^4,\hfill \\ & s.t.x_i=\frac{y_i}{1000},-\mathrm{10,000}\le y_i\le \mathrm{10,000},i=1,2,3,4.y_i\in {\mathbb{Z}}^n\hfill \end{array}$$

Problem 4 has $1.60032\times {10}^{17}$ feasible points and multiple local minimizers. The discrete global minimizer is $x^{*}={(0,0,0,0)}^T$, $F\left(x^{*}\right)=0$. This problem was tested with four different initial points, and the numerical results are shown in Table 1.

Problem 5

(Goldstein and Price’s function [19,21]).

$$\begin{array}{cc}& minF\left(x\right)=g\left(x\right)h\left(x\right),\hfill \\ & s.t.x_i=\frac{y_i}{1000},-2000\le y_i\le 2000,i=1,2.y_i\in {\mathbb{Z}}^n.\hfill \end{array}$$

$g\left(x\right)=1+{(x_1+x_2+1)}^2(19-14x_1+3x_1^2-14x_2+6x_1{x}_2+3x_2^2),h\left(x\right)=30+{(2x_1-3x_2)}^2(18-32x_1+12x_1^2+48x_2-36x_1{x}_2+27x_2^2)$ There are $1.60018001\times {10}^7$ feasible points and many discrete local minimizers in the feasible region of Problem 5. The discrete global optimal solution is $x^{*}={(0,-1)}^T$, $F\left(x^{*}\right)=3$. This problem was tested with six different initial points, and the numerical results are presented in Table 1.

Problem 6

([27]).

$$\begin{array}{cc}& minf\left(x\right)=6x_1^2+18x_2^2+7x_3^2-2x_1-16x_2-31x_3-12x_1{x}_2{x}_3,\hfill \\ & s.t.x_1+x_2+2x_3\le 2000,x_1+17x_2\le 8000,\hfill \\ & x_2+5x_3\le 4000,x_1+7x_2+x_3\ge 200,\hfill \\ & x_1+x_2+x_3\ge 200,x_1^2+x_2{x}_3\ge 900,\hfill \\ & 0\le x_i\le 999,x_i\in {\mathbb{Z}}^n,i=1,2,3.\hfill \end{array}$$

This problem has a great number of feasible points. The discrete global optimal solution is ${(720,424,428)}^T$, $f\left(x^{*}\right)=-$1,560,310,784. This problem was tested with one initial point, and the numerical results are presented in Table 2.

Problem 7

([18]).

$$\begin{array}{cc}& minf\left(x\right)=-2^4\times \prod _{i=1}^4\frac{x_i}{100},\hfill \\ & s.t.\sum _{i=1}^4{\left(\frac{x_i}{100}\right)}^2=1,\hfill \\ & 0\le x_i\le 100,\hfill \\ & x_i\in {\mathbb{Z}}^n,i=1,2,3,4.\hfill \end{array}$$

The global optimal solution of Problem 5 is $x^{*}={(50,50,50,50)}^T$, $f^{*}=-1$. This problem was tested with three initial points, and the results are listed in Table 2.

Problem 8

([9,18]).

$$\begin{array}{cc}& minf\left(x\right)={(x_1-10)}^3+{(x_2-20)}^3,\hfill \\ & s.t.-{(x_1-5)}^2-{(x_2-5)}^2+100\le 0,\hfill \\ & -x_1+10\le 0,-x_2+5\le 0,\hfill \\ & 0\le x_i\le 100,x_i\in {\mathbb{Z}}^n,i=1,2.\hfill \end{array}$$

The discrete global optimal solution of Problem 6 is $x^{*}={(15,5)}^T$, $f^{*}=-3250$. This problem was tested with three initial points, and the results are listed in Table 2.

Problem 9

([9,18]).

$$\begin{array}{cc}& minf\left(x\right)=-25{(x_1-2)}^2-{(x_2-2)}^2-{(x_3-1)}^2-{(x_4-4)}^2-{(x_5-1)}^2-{(x_6-4)}^2,\hfill \\ & s.t.-{(x_3-3)}^2-x_4+4\le 0,-{(x_5-3)}^2-x_6+4\le 0,\hfill \\ & x_1-3x_2-2\le 0,-x_1+x_2-2\le 0,\hfill \\ & x_1+x_2-6\le 0,-x_1-x_2+2\le 0,\hfill \\ & 0\le x_1\le 6,0\le x_2\le 8,0\le x_3\le 5,\hfill \\ & 0\le x_4\le 6,0\le x_5\le 10,0\le x_6\le 10,\hfill \\ & x_i\in {\mathbb{Z}}^n.\hfill \end{array}$$

The global optimal solution of Problem 7 is $x^{*}={(5,1,5,0,5,10)}^T$, $f^{*}=-310$. The problem was tested with three initial points and the results are listed in Table 2.

Problem 10

(Colville’s function [1,2,19]).

$$\begin{array}{cc}& minF\left(x\right)=100{(x_2-x_1^2)}^2+{(1-x_1)}^2+90{(x_4-x_3^2)}^2+{(1-x_3)}^2\hfill \\ & +10.1[{(x_2-1)}^2+{(x_4-1)}^2]+19.8(x_2-1)(x_4-1),\hfill \\ & s.t.-10\le x_i\le 10,i=1,2,3,4.x\in {\mathbb{Z}}^n.\hfill \end{array}$$

Problem 10 has $1.94481\times {10}^5$ feasible points and 41 discrete local minimizers. The discrete global minimizer is $x^{*}={(1,1,1,1)}^T$, $F\left(x^{*}\right)=0$. This problem was tested with four different initial points, and the numerical results are shown in Table 2.

Problem 11

(Beale’s function [5]).

$$\begin{array}{cc}& minF\left(x\right)={[1.5-x_1(1-x_2)]}^2+{[2.25-x_1(1-x_2^2)]}^2+{[2.625-x_1(1-x_2^3)]}^2,\hfill \\ & s.t.x_i=\frac{y_i}{1000},-\mathrm{10,000}\le y_i\le \mathrm{10,000},i=1,2.x\in {\mathbb{Z}}^n.\hfill \end{array}$$

This problem has $4.00040001\times {10}^8$ feasible points in the feasible region. The discrete global optimal solution is $x^{*}={(3,0.5)}^T$, $F\left(x^{*}\right)=0$. This problem was tested with six different initial points, and the numerical results are presented in Table 2.

Problem 12

(Rosenbrock’s function [1]).

$$\begin{array}{cc}& minf\left(x\right)=\sum _{i=1}^{n-1}[100{(x_{i+1}-x_i^2)}^2+{(1-x_i)}^2],\hfill \\ & s.t.-5\le x_1\le 5,i=1,2,\cdots ,n.x\in {\mathbb{Z}}^n.\hfill \end{array}$$

This problem has about ${11}^n$ feasible points and many discrete local minimizers in the feasible region (it is known that this problem has 5, 6, 7, 9, and 11 discrete local minimizers when n is set to 2, 3, 4, 5, and 6, respectively, but for any n, it has only one discrete global minimizer). Besides, its discrete global optimal solution is $x^{*}={(1,1,\dots ,1)}^T$, $\left(x^{*}\right)=0$. The test results are presented in Table 3.

Problem 13

(Consider the following n-dimensional function [5]).

$$\begin{array}{cc}& minF\left(x\right)={(x_1-1)}^2+{(x_n-1)}^2+n\sum _{i=1}^{n-1}\left[(n-i){(x_i^2-x_{i+1})}^2\right],\hfill \\ & s.t.-5\le x_1\le 5,i=1,2,\cdots ,n.x\in {\mathbb{Z}}^n.\hfill \end{array}$$

There are about ${11}^n$ feasible points and many discrete local minimizers in the feasible region of Problem 11. When $n=2,3,4,5,6$, the problem has $4,6,7,10,12$ local minimizers, respectively, but it has only one discrete global minimizer $x^{*}={(1,1,\cdots ,1)}^T$ for any n. The global minimum is $f\left(x^{*}\right)=0$. The test results are presented in Table 3.

6.2. Numerical Results

This section is a numerical test of numerical examples, the results of which are given in Table 1, Table 2, Table 3, Table 4.

Table 1. Numerical comparison results of Problems 1–5.

$\mathbf{PN}$	$\mathbf{Alg}$	$\mathbf{DN}$	${\mathbf{x}}_0$	${\mathbf{x}}^{*}$	$\mathbf{f}\left({\mathbf{x}}^{*}\right)$	$\mathbf{T}$	$\mathbf{Iter}$	N${}_{\mathit{F}+\mathsf{\Psi }}$
1	ours	5	$(17,18,7,7,9)$	$(16,22,5,5,7)$	807	0.9520	4	48,861
		5	$(21,34,0,0,0)$	$(16,22,5,5,7)$	807	2.9375	11	150,531
		5	$(0,0,0,48,15)$	$(16,22,5,5,7)$	807	3.4343	42	177,769
		5	$(100,0,0,0,40)$	$(16,22,5,5,7)$	807	4.9339	28	252,769
		5	$(0,8,32,8,32)$	$(16,22,5,5,7)$	807	1.7434	34	88,589
	[18]	5	$(17,18,7,7,9)$	$(16,22,5,5,7)$	807	2.5070	4	116,365
		5	$(21,34,0,0,0)$	$(16,22,5,5,7)$	807	5.0296	11	231,931
		5	$(0,0,0,48,15)$	$(16,22,5,5,7)$	807	14.1812	44	636,267
		5	$(100,0,0,0,40)$	$(16,22,5,5,7)$	807	10.8155	33	486,107
		5	$(0,8,32,8,32)$	$(16,22,5,5,7)$	807	11.1178	34	496,607
2	ours	2	$(2,2)$	$(1,1)$	0	0.0095	1	245
		2	$(4,4)$	$(1,1)$	0	0.0114	2	413
		2	$(6,6)$	$(1,1)$	0	0.0124	2	429
		2	$(8,8)$	$(1,1)$	0	0.0141	3	541
		2	$(10,10)$	$(1,1)$	0	0.0148	3	549
		2	$(0,0.5)$	$(1,1)$	0	0.0161	4	653
		2	$(0,10)$	$(1,1)$	0	0.0141	3	533
		2	$(10,3.2334)$	$(1,1)$	0	0.0172	4	645
		2	$(0.3536,0.3536)$	$(1,1)$	0	0.0185	5	753
	[18]	2	$(2,2)$	$(1,1)$	0	0.0162	2	418
		2	$(4,4)$	$(1,1)$	0	0.0129	2	433
		2	$(6,6)$	$(1,1)$	0	0.0149	2	500
		2	$(8,8)$	$(1,1)$	0	0.0160	3	614
		2	$(10,10)$	$(1,1)$	0	0.0164	3	608
		2	$(0,0.5)$	$(1,1)$	0	0.0175	4	710
		2	$(0,10)$	$(1,1)$	0	0.0154	3	582
		2	$(10,3.2334)$	$(1,1)$	0	0.0180	4	675
		2	$(0.3536,0.3536)$	$(1,1)$	0	0.0191	5	777
3	ours	2	$(0,13)$	$(11,11)$	$-392,887$	0.1396	3	7093
		2	$(0,0)$	$(11,11)$	$-392,887$	0.1378	2	7127
	[18]	2	$(0,13)$	$(11,11)$	$-392,887$	0.1808	3	10,205
		2	$(0,0)$	$(11,11)$	$-392,887$	0.1444	2	7127
4	ours	4	$(10,10,10,10)$	$(0,0,0,0)$	0	0.0725	2	4131
		4	$(-10,-10,-10,-10)$	$(0,0,0,0)$	0	0.0538	2	2907
		4	$(10,-10,-10,10)$	$(0,0,0,0)$	0	0.0736	2	4131
		4	$(1,-1,-1,1)$	$(0,0,0,0)$	0	0.0575	2	3843
		4	$(-10,1,0,5)$	$(0,0,0,0)$	0	0.0456	2	2731
		4	$(0,0,0,0)$	$(0,0,0,0)$	0	0.0392	1	2585
	[18]	2	$(10,10,10,10)$	$(0,0,0,0)$	0	0.0777	2	4439
		4	$(-10,-10,-10,-10)$	$(0,0,0,0)$	0	0.0725	2	4599
		4	$(10,-10,-10,10)$	$(0,0,0,0)$	0	0.0715	2	4439
		4	$(1,-1,-1,1)$	$(0,0,0,0)$	0	0.0560	2	4151
		4	$(-10,1,0,5)$	$(0,0,0,0)$	0	0.0653	2	4423
		4	$(0,0,0,0)$	$(0,0,0,0)$	0	0.0343	1	2585
5	ours	2	$(2,-2)$	$(0,-1)$	3	1.3741	2	84,013
		2	$(0,-1)$	$(0,-1)$	3	0.8289	2	72,013
		2	$(-2,-2)$	$(0,-1)$	3	1.3745	1	84,013
		2	$(-0.5,-1)$	$(0,-1)$	3	0.8986	2	74,013
		2	$(1,-1.5)$	$(0,-1)$	3	1.0622	1	78,013
		2	$(1,-1)$	$(0,-1)$	3	0.9923	1	76,013
	[18]	2	$(2,-2)$	$(0,-1)$	3	1.5708	2	84,013
		2	$(0,-1)$	$(0,-1)$	3	0.9917	2	71,922
		2	$(-2,-2)$	$(0,-1)$	3	1.5720	1	84,077
		2	$(-0.5,-1)$	$(0,-1)$	3	1.1065	2	74,103
		2	$(1,-1.5)$	$(0,-1)$	3	1.2851	1	78,031
		2	$(1,-1)$	$(0,-1)$	3	1.1790	1	76,101

Table 1. Numerical comparison results of Problems 1–5.

$\mathbf{PN}$	$\mathbf{Alg}$	$\mathbf{DN}$	${\mathbf{x}}_0$	${\mathbf{x}}^{*}$	$\mathbf{f}\left({\mathbf{x}}^{*}\right)$	$\mathbf{T}$	$\mathbf{Iter}$	N${}_{\mathit{F}+\mathsf{\Psi }}$
1	ours	5	$(17,18,7,7,9)$	$(16,22,5,5,7)$	807	0.9520	4	48,861
		5	$(21,34,0,0,0)$	$(16,22,5,5,7)$	807	2.9375	11	150,531
		5	$(0,0,0,48,15)$	$(16,22,5,5,7)$	807	3.4343	42	177,769
		5	$(100,0,0,0,40)$	$(16,22,5,5,7)$	807	4.9339	28	252,769
		5	$(0,8,32,8,32)$	$(16,22,5,5,7)$	807	1.7434	34	88,589
	[18]	5	$(17,18,7,7,9)$	$(16,22,5,5,7)$	807	2.5070	4	116,365
		5	$(21,34,0,0,0)$	$(16,22,5,5,7)$	807	5.0296	11	231,931
		5	$(0,0,0,48,15)$	$(16,22,5,5,7)$	807	14.1812	44	636,267
		5	$(100,0,0,0,40)$	$(16,22,5,5,7)$	807	10.8155	33	486,107
		5	$(0,8,32,8,32)$	$(16,22,5,5,7)$	807	11.1178	34	496,607
2	ours	2	$(2,2)$	$(1,1)$	0	0.0095	1	245
		2	$(4,4)$	$(1,1)$	0	0.0114	2	413
		2	$(6,6)$	$(1,1)$	0	0.0124	2	429
		2	$(8,8)$	$(1,1)$	0	0.0141	3	541
		2	$(10,10)$	$(1,1)$	0	0.0148	3	549
		2	$(0,0.5)$	$(1,1)$	0	0.0161	4	653
		2	$(0,10)$	$(1,1)$	0	0.0141	3	533
		2	$(10,3.2334)$	$(1,1)$	0	0.0172	4	645
		2	$(0.3536,0.3536)$	$(1,1)$	0	0.0185	5	753
	[18]	2	$(2,2)$	$(1,1)$	0	0.0162	2	418
		2	$(4,4)$	$(1,1)$	0	0.0129	2	433
		2	$(6,6)$	$(1,1)$	0	0.0149	2	500
		2	$(8,8)$	$(1,1)$	0	0.0160	3	614
		2	$(10,10)$	$(1,1)$	0	0.0164	3	608
		2	$(0,0.5)$	$(1,1)$	0	0.0175	4	710
		2	$(0,10)$	$(1,1)$	0	0.0154	3	582
		2	$(10,3.2334)$	$(1,1)$	0	0.0180	4	675
		2	$(0.3536,0.3536)$	$(1,1)$	0	0.0191	5	777
3	ours	2	$(0,13)$	$(11,11)$	$-392,887$	0.1396	3	7093
		2	$(0,0)$	$(11,11)$	$-392,887$	0.1378	2	7127
	[18]	2	$(0,13)$	$(11,11)$	$-392,887$	0.1808	3	10,205
		2	$(0,0)$	$(11,11)$	$-392,887$	0.1444	2	7127
4	ours	4	$(10,10,10,10)$	$(0,0,0,0)$	0	0.0725	2	4131
		4	$(-10,-10,-10,-10)$	$(0,0,0,0)$	0	0.0538	2	2907
		4	$(10,-10,-10,10)$	$(0,0,0,0)$	0	0.0736	2	4131
		4	$(1,-1,-1,1)$	$(0,0,0,0)$	0	0.0575	2	3843
		4	$(-10,1,0,5)$	$(0,0,0,0)$	0	0.0456	2	2731
		4	$(0,0,0,0)$	$(0,0,0,0)$	0	0.0392	1	2585
	[18]	2	$(10,10,10,10)$	$(0,0,0,0)$	0	0.0777	2	4439
		4	$(-10,-10,-10,-10)$	$(0,0,0,0)$	0	0.0725	2	4599
		4	$(10,-10,-10,10)$	$(0,0,0,0)$	0	0.0715	2	4439
		4	$(1,-1,-1,1)$	$(0,0,0,0)$	0	0.0560	2	4151
		4	$(-10,1,0,5)$	$(0,0,0,0)$	0	0.0653	2	4423
		4	$(0,0,0,0)$	$(0,0,0,0)$	0	0.0343	1	2585
5	ours	2	$(2,-2)$	$(0,-1)$	3	1.3741	2	84,013
		2	$(0,-1)$	$(0,-1)$	3	0.8289	2	72,013
		2	$(-2,-2)$	$(0,-1)$	3	1.3745	1	84,013
		2	$(-0.5,-1)$	$(0,-1)$	3	0.8986	2	74,013
		2	$(1,-1.5)$	$(0,-1)$	3	1.0622	1	78,013
		2	$(1,-1)$	$(0,-1)$	3	0.9923	1	76,013
	[18]	2	$(2,-2)$	$(0,-1)$	3	1.5708	2	84,013
		2	$(0,-1)$	$(0,-1)$	3	0.9917	2	71,922
		2	$(-2,-2)$	$(0,-1)$	3	1.5720	1	84,077
		2	$(-0.5,-1)$	$(0,-1)$	3	1.1065	2	74,103
		2	$(1,-1.5)$	$(0,-1)$	3	1.2851	1	78,031
		2	$(1,-1)$	$(0,-1)$	3	1.1790	1	76,101

Table 2. Numerical comparison results of Problems 6–11.

$\mathbf{PN}$	$\mathbf{Alg}$	$\mathbf{DN}$	${\mathbf{x}}_0$	${\mathbf{x}}^{*}$	$\mathbf{f}\left({\mathbf{x}}^{*}\right)$	$\mathbf{T}$	$\mathbf{Iter}$	N${}_{\mathit{F}+\mathsf{\Psi }}$
6	ours	3	$(700,400,450)$	$(720,424,428)$	−1,560,310,784	0.7027	1	35,971
	[18]	3	$(700,400,450)$	$(720,424,428)$	−1,560,310,784	0.9201	1	46,178
7	ours	4	$(25,25,25,25)$	$(50,50,50,50)$	$-1$	0.3793	1	5869
		4	$(50,50,50,50)$	$(50,50,50,50)$	$-1$	0.1189	1	5509
		4	$(75,75,75,75)$	$(50,50,50,50)$	$-1$	0.1888	2	8949
	[18]	4	$(25,25,25,25)$	$(50,50,50,50)$	$-1$	0.1429	1	5968
		4	$(50,50,50,50)$	$(50,50,50,50)$	$-1$	0.1228	1	5670
		4	$(75,75,75,75)$	$(50,50,50,50)$	$-1$	0.2517	3	11,930
8	ours	2	$(25,25)$	$(15,5)$	$-3250$	0.0576	5	2421
		2	$(50,50)$	$(15,5)$	$-3250$	0.0655	5	2620
		2	$(75,75)$	$(15,5)$	$-3250$	0.0755	5	2819
	[18]	2	$(25,25)$	$(15,5)$	$-3250$	0.0621	5	2730
		2	$(50,50)$	−	−	−	−	−
		2	$(75,75)$	$(15,5)$	$-3250$	0.0840	5	3132
9	ours	6	$(0,0,0,0,0,0)$	$(5,1,5,0,5,10)$	$-310$	0.2280	5	11,263
		6	$(3,4,2,3,5,5)$	$(5,1,5,0,5,10)$	$-310$	0.1689	3	8639
		6	$(6,8,5,6,10,10)$	$(5,1,5,0,5,10)$	$-310$	0.1304	1	6589
	[18]	6	$(0,0,0,0,0,0)$	$(5,1,5,0,5,10)$	$-310$	0.3489	5	16,037
		6	$(3,4,2,3,5,5)$	$(5,1,5,0,5,10)$	$-310$	0.2197	3	10,017
		6	$(6,8,5,6,10,10)$	$(5,1,5,0,5,10)$	$-310$	0.2649	3	12,153
10	ours	4	$(5,\cdots ,5)$	$(1,1,1,1)$	0	0.1000	5	5761
		4	$(-5,\cdots ,-5)$	$(1,1,1,1)$	0	0.0448	2	2667
		4	$(10,\cdots ,10)$	$(1,1,1,1)$	0	0.1169	6	7969
		4	$(-10,\cdots ,-10)$	$(1,1,1,1)$	0	0.0542	2	2827
	[18]	4	$(5,\cdots ,5)$	$(1,1,1,1)$	0	0.1075	5	6761
		4	$(-5,\cdots ,-5)$	$(1,1,1,1)$	0	0.0707	2	4615
		4	$(10,\cdots ,10)$	$(1,1,1,1)$	0	0.1245	6	7969
		4	$(-10,\cdots ,-10)$	$(1,1,1,1)$	0	0.0756	2	4775
11	ours	2	$(10,-10)$	$(3,0.5)$	0	1.0960	5	742,921
		2	$(9.997,-6.867)$	$(3,0.5)$	0	12.5392	5	730,377
		2	$(0,-1)$	$(3,0.5)$	0	4.0511	4	244,019
		2	$(1,1)$	$(3,0.5)$	0	3.8061	4	237,587
		2	$(2,2)$	$(3,0.5)$	0	3.7028	4	237,579
		2	$(0,0)$	$(3,0.5)$	0	3.8508	4	240,019
	[18]	2	$(10,-10)$	$(3,0.5)$	0	15.7839	5	892,789
		2	$(9.997,-6.867)$	$(3,0.5)$	0	15.1406	5	880,245
		2	$(0,-1)$	$(3,0.5)$	0	6.0974	4	470,075
		2	$(1,1)$	$(3,0.5)$	0	5.8505	4	463,643
		2	$(2,2)$	$(3,0.5)$	0	5.8602	4	463,635
		2	$(0,0)$	$(3,0.5)$	0	5.9400	4	466,075

Table 2. Numerical comparison results of Problems 6–11.

$\mathbf{PN}$	$\mathbf{Alg}$	$\mathbf{DN}$	${\mathbf{x}}_0$	${\mathbf{x}}^{*}$	$\mathbf{f}\left({\mathbf{x}}^{*}\right)$	$\mathbf{T}$	$\mathbf{Iter}$	N${}_{\mathit{F}+\mathsf{\Psi }}$
6	ours	3	$(700,400,450)$	$(720,424,428)$	−1,560,310,784	0.7027	1	35,971
	[18]	3	$(700,400,450)$	$(720,424,428)$	−1,560,310,784	0.9201	1	46,178
7	ours	4	$(25,25,25,25)$	$(50,50,50,50)$	$-1$	0.3793	1	5869
		4	$(50,50,50,50)$	$(50,50,50,50)$	$-1$	0.1189	1	5509
		4	$(75,75,75,75)$	$(50,50,50,50)$	$-1$	0.1888	2	8949
	[18]	4	$(25,25,25,25)$	$(50,50,50,50)$	$-1$	0.1429	1	5968
		4	$(50,50,50,50)$	$(50,50,50,50)$	$-1$	0.1228	1	5670
		4	$(75,75,75,75)$	$(50,50,50,50)$	$-1$	0.2517	3	11,930
8	ours	2	$(25,25)$	$(15,5)$	$-3250$	0.0576	5	2421
		2	$(50,50)$	$(15,5)$	$-3250$	0.0655	5	2620
		2	$(75,75)$	$(15,5)$	$-3250$	0.0755	5	2819
	[18]	2	$(25,25)$	$(15,5)$	$-3250$	0.0621	5	2730
		2	$(50,50)$	−	−	−	−	−
		2	$(75,75)$	$(15,5)$	$-3250$	0.0840	5	3132
9	ours	6	$(0,0,0,0,0,0)$	$(5,1,5,0,5,10)$	$-310$	0.2280	5	11,263
		6	$(3,4,2,3,5,5)$	$(5,1,5,0,5,10)$	$-310$	0.1689	3	8639
		6	$(6,8,5,6,10,10)$	$(5,1,5,0,5,10)$	$-310$	0.1304	1	6589
	[18]	6	$(0,0,0,0,0,0)$	$(5,1,5,0,5,10)$	$-310$	0.3489	5	16,037
		6	$(3,4,2,3,5,5)$	$(5,1,5,0,5,10)$	$-310$	0.2197	3	10,017
		6	$(6,8,5,6,10,10)$	$(5,1,5,0,5,10)$	$-310$	0.2649	3	12,153
10	ours	4	$(5,\cdots ,5)$	$(1,1,1,1)$	0	0.1000	5	5761
		4	$(-5,\cdots ,-5)$	$(1,1,1,1)$	0	0.0448	2	2667
		4	$(10,\cdots ,10)$	$(1,1,1,1)$	0	0.1169	6	7969
		4	$(-10,\cdots ,-10)$	$(1,1,1,1)$	0	0.0542	2	2827
	[18]	4	$(5,\cdots ,5)$	$(1,1,1,1)$	0	0.1075	5	6761
		4	$(-5,\cdots ,-5)$	$(1,1,1,1)$	0	0.0707	2	4615
		4	$(10,\cdots ,10)$	$(1,1,1,1)$	0	0.1245	6	7969
		4	$(-10,\cdots ,-10)$	$(1,1,1,1)$	0	0.0756	2	4775
11	ours	2	$(10,-10)$	$(3,0.5)$	0	1.0960	5	742,921
		2	$(9.997,-6.867)$	$(3,0.5)$	0	12.5392	5	730,377
		2	$(0,-1)$	$(3,0.5)$	0	4.0511	4	244,019
		2	$(1,1)$	$(3,0.5)$	0	3.8061	4	237,587
		2	$(2,2)$	$(3,0.5)$	0	3.7028	4	237,579
		2	$(0,0)$	$(3,0.5)$	0	3.8508	4	240,019
	[18]	2	$(10,-10)$	$(3,0.5)$	0	15.7839	5	892,789
		2	$(9.997,-6.867)$	$(3,0.5)$	0	15.1406	5	880,245
		2	$(0,-1)$	$(3,0.5)$	0	6.0974	4	470,075
		2	$(1,1)$	$(3,0.5)$	0	5.8505	4	463,643
		2	$(2,2)$	$(3,0.5)$	0	5.8602	4	463,635
		2	$(0,0)$	$(3,0.5)$	0	5.9400	4	466,075

Table 3. Numerical comparison results of Problems 12 and 13.

$\mathbf{PN}$	$\mathbf{Alg}$	$\mathbf{DN}$	${\mathbf{x}}_0$	${\mathbf{x}}^{*}$	$\mathbf{f}\left({\mathbf{x}}^{*}\right)$	$\mathbf{T}$	$\mathbf{Iter}$	N${}_{\mathit{F}+\mathsf{\Psi }}$
12	ours	25	$(5,\cdots ,5,-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	7.1418	1	258,951
		25	$(-5,\cdots ,-5,5,\cdots ,5)$	$(1,\cdots ,1)$	0	13.4385	2	496,651
		25	$(5,\cdots ,5)$	$(1,\cdots ,1)$	0	14.1907	2	495,451
		25	$(-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	8.8529	1	318,901
	[18]	25	$(5,\cdots ,5,-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	7.4281	1	269,332
		25	$(-5,\cdots ,-5,5,\cdots ,5)$	$(1,\cdots ,1)$	0	15.7155	2	580,802
		25	$(5,\cdots ,5)$	$(1,\cdots ,1)$	0	14.0939	2	495,451
		25	$(-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	9.1232	1	328,637
	ours	50	$(5,\cdots ,5,-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	59.5855	1	2,035,301
		50	$(-5,\cdots ,-5,5,\cdots ,5)$	$(1,\cdots ,1)$	0	113.7989	2	3,985,901
		50	$(5,\cdots ,5)$	$(1,\cdots ,1)$	0	114.7591	2	3,980,901
		50	$(-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	73.8136	1	2,525,301
	[18]	50	$(5,\cdots ,5,-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	62.4965	1	2,134,733
		50	$(-5,\cdots ,-5,5,\cdots ,5)$	$(1,\cdots ,1)$	0	116.8327	2	4,092,162
		50	$(5,\cdots ,5)$	$(1,\cdots ,1)$	0	116.1587	2	4,029,451
		50	$(-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	75.7253	1	2,590,704
	ours	100	$(5,\cdots ,5,-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	515.5150	1	16,140,600
		100	$(-5,\cdots ,-5,5,\cdots ,5)$	$(1,\cdots ,1)$	0	996.9730	2	31,941,801
		100	$(5,\cdots ,5)$	$(1,\cdots ,1)$	0	983.3028	2	31,921,800
		100	$(-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	637.1618	1	20,100,602
	[18]	100	$(5,\cdots ,5,-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	523.2555	1	16,382,953
		100	$(-5,\cdots ,-5,5,\cdots ,5)$	$(1,\cdots ,1)$	0	1026.1101	2	32,874,946
		100	$(5,\cdots ,5)$	$(1,\cdots ,1)$	0	996.5619	2	32,352,242
		100	$(-5,\cdots ,-5)$	−	−	−	−	−
13	ours	25	$(5,\cdots ,5,-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	7.1793	1	240,873
		25	$(-5,\cdots ,-5,5,\cdots ,5)$	$(1,\cdots ,1)$	0	14.0434	2	443,610
		25	$(5,\cdots ,5)$	$(1,\cdots ,1)$	0	12.7954	2	495,453
		25	$(-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	8.5232	1	318,902
	[18]	25	$(5,\cdots ,5,-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	7.7181	1	258,951
		25	$(-5,\cdots ,-5,5,\cdots ,5)$	$(1,\cdots ,1)$	0	15.7225	2	496,652
		25	$(5,\cdots ,5)$	$(1,\cdots ,1)$	0	13.8766	2	537,318
		25	$(-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	9.3565	1	350,080
	ours	50	$(5,\cdots ,5,-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	58.2227	1	2,035,301
		50	$(-5,\cdots ,-5,5,\cdots ,5)$	$(1,\cdots ,1)$	0	134.6884	2	4,931,800
		50	$(5,\cdots ,5)$	$(1,\cdots ,1)$	0	108.2429	2	3,980,891
		50	$(-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	70.6625	1	2,525,306
	[18]	50	$(5,\cdots ,5,-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	62.0151	1	2,185,716
		50	$(-5,\cdots ,-5,5,\cdots ,5)$	$(1,\cdots ,1)$	0	117.6758	2	3,985,901
		50	$(5,\cdots ,5)$	$(1,\cdots ,1)$	0	117.5395	2	4,322,674
		50	$(-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	76.3166	1	2,727,364
	ours	100	$(5,\cdots ,5,-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	483.2232	1	16,140,601
		100	$(-5,\cdots ,-5,5,\cdots ,5)$	$(1,\cdots ,1)$	0	994.5747	2	39,723,601
		100	$(5,\cdots ,5)$	$(1,\cdots ,1)$	0	927.8696	2	31,921,801
		100	$(-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	594.7694	1	20,100,601
	[18]	100	$(5,\cdots ,5,-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	516.1914	1	17,241,803
		100	$(-5,\cdots ,-5,5,\cdots ,5)$	$(1,\cdots ,1)$	0	1555.5000	2	62,127,119
		100	$(5,\cdots ,5)$	$(1,\cdots ,1)$	0	995.4259	2	34,245,962
		100	$(-5,\cdots ,-5)$	−	−	−	−	−

Table 3. Numerical comparison results of Problems 12 and 13.

$\mathbf{PN}$	$\mathbf{Alg}$	$\mathbf{DN}$	${\mathbf{x}}_0$	${\mathbf{x}}^{*}$	$\mathbf{f}\left({\mathbf{x}}^{*}\right)$	$\mathbf{T}$	$\mathbf{Iter}$	N${}_{\mathit{F}+\mathsf{\Psi }}$
12	ours	25	$(5,\cdots ,5,-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	7.1418	1	258,951
		25	$(-5,\cdots ,-5,5,\cdots ,5)$	$(1,\cdots ,1)$	0	13.4385	2	496,651
		25	$(5,\cdots ,5)$	$(1,\cdots ,1)$	0	14.1907	2	495,451
		25	$(-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	8.8529	1	318,901
	[18]	25	$(5,\cdots ,5,-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	7.4281	1	269,332
		25	$(-5,\cdots ,-5,5,\cdots ,5)$	$(1,\cdots ,1)$	0	15.7155	2	580,802
		25	$(5,\cdots ,5)$	$(1,\cdots ,1)$	0	14.0939	2	495,451
		25	$(-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	9.1232	1	328,637
	ours	50	$(5,\cdots ,5,-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	59.5855	1	2,035,301
		50	$(-5,\cdots ,-5,5,\cdots ,5)$	$(1,\cdots ,1)$	0	113.7989	2	3,985,901
		50	$(5,\cdots ,5)$	$(1,\cdots ,1)$	0	114.7591	2	3,980,901
		50	$(-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	73.8136	1	2,525,301
	[18]	50	$(5,\cdots ,5,-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	62.4965	1	2,134,733
		50	$(-5,\cdots ,-5,5,\cdots ,5)$	$(1,\cdots ,1)$	0	116.8327	2	4,092,162
		50	$(5,\cdots ,5)$	$(1,\cdots ,1)$	0	116.1587	2	4,029,451
		50	$(-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	75.7253	1	2,590,704
	ours	100	$(5,\cdots ,5,-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	515.5150	1	16,140,600
		100	$(-5,\cdots ,-5,5,\cdots ,5)$	$(1,\cdots ,1)$	0	996.9730	2	31,941,801
		100	$(5,\cdots ,5)$	$(1,\cdots ,1)$	0	983.3028	2	31,921,800
		100	$(-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	637.1618	1	20,100,602
	[18]	100	$(5,\cdots ,5,-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	523.2555	1	16,382,953
		100	$(-5,\cdots ,-5,5,\cdots ,5)$	$(1,\cdots ,1)$	0	1026.1101	2	32,874,946
		100	$(5,\cdots ,5)$	$(1,\cdots ,1)$	0	996.5619	2	32,352,242
		100	$(-5,\cdots ,-5)$	−	−	−	−	−
13	ours	25	$(5,\cdots ,5,-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	7.1793	1	240,873
		25	$(-5,\cdots ,-5,5,\cdots ,5)$	$(1,\cdots ,1)$	0	14.0434	2	443,610
		25	$(5,\cdots ,5)$	$(1,\cdots ,1)$	0	12.7954	2	495,453
		25	$(-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	8.5232	1	318,902
	[18]	25	$(5,\cdots ,5,-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	7.7181	1	258,951
		25	$(-5,\cdots ,-5,5,\cdots ,5)$	$(1,\cdots ,1)$	0	15.7225	2	496,652
		25	$(5,\cdots ,5)$	$(1,\cdots ,1)$	0	13.8766	2	537,318
		25	$(-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	9.3565	1	350,080
	ours	50	$(5,\cdots ,5,-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	58.2227	1	2,035,301
		50	$(-5,\cdots ,-5,5,\cdots ,5)$	$(1,\cdots ,1)$	0	134.6884	2	4,931,800
		50	$(5,\cdots ,5)$	$(1,\cdots ,1)$	0	108.2429	2	3,980,891
		50	$(-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	70.6625	1	2,525,306
	[18]	50	$(5,\cdots ,5,-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	62.0151	1	2,185,716
		50	$(-5,\cdots ,-5,5,\cdots ,5)$	$(1,\cdots ,1)$	0	117.6758	2	3,985,901
		50	$(5,\cdots ,5)$	$(1,\cdots ,1)$	0	117.5395	2	4,322,674
		50	$(-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	76.3166	1	2,727,364
	ours	100	$(5,\cdots ,5,-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	483.2232	1	16,140,601
		100	$(-5,\cdots ,-5,5,\cdots ,5)$	$(1,\cdots ,1)$	0	994.5747	2	39,723,601
		100	$(5,\cdots ,5)$	$(1,\cdots ,1)$	0	927.8696	2	31,921,801
		100	$(-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	594.7694	1	20,100,601
	[18]	100	$(5,\cdots ,5,-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	516.1914	1	17,241,803
		100	$(-5,\cdots ,-5,5,\cdots ,5)$	$(1,\cdots ,1)$	0	1555.5000	2	62,127,119
		100	$(5,\cdots ,5)$	$(1,\cdots ,1)$	0	995.4259	2	34,245,962
		100	$(-5,\cdots ,-5)$	−	−	−	−	−

Table 4. Numerical results of Problems 10 and 12.

$\mathbf{PN}$	$\mathbf{DN}$	${\mathbf{x}}_0$	${\mathbf{x}}^{*}$	$\mathbf{f}\left({\mathbf{x}}^{*}\right)$	$\mathbf{T}$	$\mathbf{Iter}$	N${}_{\mathit{F}+\mathsf{\Psi }}$
10	4	$(1,1,0,0)$	$(1,1,1,1)$	0	0.0500	3	3023
	4	$(1,1,1,1)$	$(1,1,1,1)$	0	0.0362	1	2393
	4	$(-10,10,-10,10)$	$(1,1,1,1)$	0	0.4176	7	8947
	4	$(-10,-5,0,5)$	$(1,1,1,1)$	0	0.0730	3	4539
	4	$(-10,0,0,-10)$	$(1,1,1,1)$	0	0.0548	3	3201
	4	$(0,0,0,0)$	$(1,1,1,1)$	0	0.0462	3	3041
12	25	$(0,\cdots ,0)$	$(1,\cdots ,1)$	0	8.5956	2	312,651
	25	$(3,\cdots ,3)$	$(1,\cdots ,1)$	0	9.3240	1	493,051
	25	$(-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	8.6237	3	318,901
	25	$(2,-2,\cdots ,2,-2,2)$	$(1,\cdots ,1)$	0	7.0355	1	315,151
	25	$(3,-3,\cdots ,3,-3,3)$	$(1,\cdots ,1)$	0	11.7225	2	611,549
	25	$(5,-5,\cdots ,5,-5,5)$	$(1,\cdots ,1)$	0	12.7954	2	613,949

Table 4. Numerical results of Problems 10 and 12.

$\mathbf{PN}$	$\mathbf{DN}$	${\mathbf{x}}_0$	${\mathbf{x}}^{*}$	$\mathbf{f}\left({\mathbf{x}}^{*}\right)$	$\mathbf{T}$	$\mathbf{Iter}$	N${}_{\mathit{F}+\mathsf{\Psi }}$
10	4	$(1,1,0,0)$	$(1,1,1,1)$	0	0.0500	3	3023
	4	$(1,1,1,1)$	$(1,1,1,1)$	0	0.0362	1	2393
	4	$(-10,10,-10,10)$	$(1,1,1,1)$	0	0.4176	7	8947
	4	$(-10,-5,0,5)$	$(1,1,1,1)$	0	0.0730	3	4539
	4	$(-10,0,0,-10)$	$(1,1,1,1)$	0	0.0548	3	3201
	4	$(0,0,0,0)$	$(1,1,1,1)$	0	0.0462	3	3041
12	25	$(0,\cdots ,0)$	$(1,\cdots ,1)$	0	8.5956	2	312,651
	25	$(3,\cdots ,3)$	$(1,\cdots ,1)$	0	9.3240	1	493,051
	25	$(-5,\cdots ,-5)$	$(1,\cdots ,1)$	0	8.6237	3	318,901
	25	$(2,-2,\cdots ,2,-2,2)$	$(1,\cdots ,1)$	0	7.0355	1	315,151
	25	$(3,-3,\cdots ,3,-3,3)$	$(1,\cdots ,1)$	0	11.7225	2	611,549
	25	$(5,-5,\cdots ,5,-5,5)$	$(1,\cdots ,1)$	0	12.7954	2	613,949

To better reveal the effectiveness of our algorithm, we compared it with the algorithm in [18]. For fair, these two algorithms all use the same initial point and the same local descent Algorithm 1. Then, these two algorithms are adopted to test 13 kinds of test problems (72 test examples in total) in the same computing environment. Finally, the T, Iter, and N${}_{F+\mathsf{\Psi }}$ of these two algorithms are compared, respectively. Furthermore, all boldface data in these tables indicate that our algorithm is superior to that in [18].

The numerical results in Table 1, Table 2 and Table 3 show that the proposed algorithm can accurately find the global minimizers of these 72 test instances and solve the test problem of up to 100 variables, which indicates that our algorithm is feasible. Among all the test instances, the algorithm in [18] fails to solve three of them. The comparison results of numerical calculation of the 72 test examples in Table 1, Table 2 and Table 3 show that these two algorithms have almost the same number of iterations, which indicates that their performance may be similar in a sense. However, the proposed algorithm can always find the global minimizer faster than the algorithm in [18] for 66 test instances, and our algorithm had 64 test instances with less N${}_{F+\mathsf{\Psi }}$ than the latter, which shows that our algorithm can save more CPU time than the latter.

To further test the effectiveness of our algorithm, we calculated Problems 4–6, 8, and 9 using our algorithm and algorithms A, B, C, and D in [19] and compared the total evaluation times of functions (include filled function and objective function) solved by the five algorithms. The comparison results are shown in

Table 5. Numerical comparison results of Problems 4, 5, and 10–12.

$\mathbf{PN}$	$\mathbf{DN}$	${\mathbf{x}}^{*}$	$\mathbf{f}\left({\mathbf{x}}^{*}\right)$	N${}_{\mathit{F}+\mathsf{\Psi }}$
				Ours	A	B	C	D
4	4	$(0,0,0,0)$	0	3388	9065	6472	37,906	18,936
5	2	$(0,-1)$	3	78,041	266,455	173,605	1,218,432	663,573
10	4	$(1,1,1,1)$	0	4024	9735	6927	39,650	19,252
11	2	$(3,0.5)$	0	405,417	1,970,575	1,145,488	245,235	2,826,691
12	25	$(1,\cdots ,1)$	0	396,936	1,173,742	646,390	3,558,639	1,732,339

. Note that for problems 4, 5, and 11, the initial points (in Table 1 and Table 2) adopted by our algorithm are the same as those in [19]; however, for problems 10 and 12, the initial points used in Table 2 and Table 3 are different from those in [19]. Therefore, by adopting the same initial point as in [19], we have carried out additional numerical experiments on problems 10 and 12, which ensures the fairness of the numerical results (see Table 4).

The numerical comparison results of N${}_{F+\mathsf{\Psi }}$ in Table 5 indicate that our algorithm is superior to A, B, and D in solving these five problems and is inferior to C in solving Problem 11. This means that algorithm C may be better than the other four algorithms at solving certain problems. Besides, the above results also show that most numerical results of algorithm B are better than algorithms A, C, and D, except for Problem 11.

To sum up, on the premise of ensuring the effectiveness, the proposed algorithm can solve the difficult constrained integer programming problem with few function evaluations in a short time, and the computational performance is better than the algorithms in [18,19], which shows that our algorithm is efficient. The disadvantage of our algorithm is that it is difficult to solve higher-dimensional problems.

7. Conclusions

In this paper, a new nonparametric filled function is constructed, which not only has good discreteness but also has no exponential and logarithmic terms. On the basis of theoretical analysis, a new global algorithm for solving constrained integer programming problems is designed, and its feasibility and effectiveness are verified by numerical comparison experiments. In future studies, we will try to apply the proposed algorithm to other problems in the optimization field, such as fractional programming problems with constraints [28]. The equivalent transformation method in this paper is promising, so further work could propose the filled function with better properties.