A novel nonmonotone trust region method based on the Metropolis criterion for solving unconstrained optimization

1.   Introduction

Unconstrained optimization is one of the fundamental problems in the optimization theory ^[4,26]. It has broad applications across various fields such as engineering design, financial investments, signal processing, and so on ^[6,18,21]. In engineering design, unconstrained optimization is used to determine the most efficient design parameters for systems or products, which may either include optimizing the dimensions of mechanical components or minimizing material usage while maintaining the structural integrity. In financial investments, unconstrained optimization techniques enable investors to identify the optimal portfolio allocation, thereby balancing the risk and the return without being confined by predefined constraints. This helps investors maximize the expected returns while minimizing the potential losses. In signal processing, unconstrained optimization is employed in tasks such as signal denoising, image quality enhancement, and performance optimization of communication systems. By either minimizing error functions or maximizing the signal-to-noise ratio, unconstrained optimization algorithms can extract meaningful information from noisy data. Therefore, the discussion of methods for solving unconstrained optimization problems becomes very important.

The trust region method is one of the most commonly used iterative algorithms to solve unconstrained optimization problems ^[14,27]. The fundamental concept behind the trust region method lies in constructing a surrogate model that approximates the objective function within the neighborhood of the current iteration point. This surrogate model captures the local behavior of the original objective function, thus allowing the algorithm to compute the optimal step size or the trial step within the predefined trust region.

In most practical implementations, a quadratic model is typically chosen as the approximation function due to its mathematical convenience and the availability of efficient solvers. However, the effectiveness of the quadratic model heavily depends on the proper tuning of its parameters. Researchers have proposed various techniques to solve trust region subproblems, including exact solutions, dog-leg methods, and conjugate gradient methods ^[1,5,33].

However, trust region subproblems are often difficult to solve, particularly for complex objective functions and high-dimensional problems, thus leading to increased computational costs. The challenges typically arise from the non-convexity and multimodal nature of the surrogate function within the trust region, requiring frequent subproblem solutions during the iterative process. To address this, researchers have explored methods to improve the efficiency of solving these subproblems by developing more efficient solvers, employing advanced optimization techniques, and exploring alternative approximation functions ^[8,22,23].

Overall, trust region methods remain powerful tools for unconstrained optimization, and further advancements in subproblem solvers could enhance their performance and applicability to a wider range of problems. To handle situations where the trial step is not accepted, trust region methods combined with line search techniques have been proposed ^[11,25]. When the trial step is rejected, these algorithms use the trial step as the search direction and apply a line search technique to determine the corresponding step size. However, these methods require the objective function to monotonically decrease at each iteration, which has some impact on the convergence rate of the algorithm. With the introduction of nonmonotone techniques ^[12], a new class of nonmonotone trust region algorithms was developed ^[7], which allowed the sequence of the objective function values to be nonmonotone. Numerical results show that these methods outperform traditional trust region methods. Further research has been conducted in this area ^[10,28,29].

However, in some cases, the class of aforementioned nonmonotone techniques that used a maximum of recent function values may ignore some better function values. To address this, scholars have proposed improved nonmonotone strategies. Zhang and Hager ^[34] introduced a new nonmonotone line search algorithm that replaced the maximum function value with the average of recent function values. Gu and Mo ^[13] developed a simplified nonmonotone strategy that was applied within the trust region framework, which avoided the complex parameterization process of Zhang and Hager ^[34]. Zhou et al. ^[35] proposed a nonmonotone trust region method based on a simple model, which performed well on large-scale problems. Improved nonmonotone techniques have also been applied to solve other problems, such as the nonmonotone BFGS (Broyden, Fletcher, Goldfarb and Shanno) algorithm proposed by Wan et al. ^[31] for smooth nonlinear equations, where the nonmonotone parameters were updated using known information of the nonlinear equation. Some scholars have developed new nonmonotone line search rules that were applied to unconstrained and box-constrained optimization problems ^[16,19]. In contrast to previous work, we study a stochastic nonmonotone technique that allows the algorithm to explore a larger solution space during the search process.

To reduce the number of subproblem computations and improve the overall efficiency of the algorithm, we propose a modified trust region method that incorporates recent advances in this field, with the following key innovations and advantages.

Construction of a New Function Sequence: To prevent convergence to the local optima and to improve algorithmic performance, we introduce the idea of simulated annealing to construct a new function sequence. Based on this sequence, a new nonmonotone trust region ratio is defined, which leads to corresponding improvements in the iteration criterion of the trust region framework, thus providing a greater flexibility during the iterative process.

Improved Nonmonotone Strategy: When the current trial step is not accepted, we utilize an improved nonmonotone strategy that leverages the new function sequence to determine the step size. This approach effectively reduces the required number of subproblem solutions, thus enhancing the algorithm's overall efficiency.

Global Convergence and Efficiency: Our algorithm guarantees a global convergence under certain assumptions. Furthermore, numerical experiments demonstrate that the algorithm significantly reduces the number of iterations, improves the efficiency, and delivers a strong performance.

The structure of this paper is as follows: in Section 2, we describe the new nonmonotone trust region algorithm; in Section 3, the global convergence of our algorithm is proved under certain assumptions; in Section 4, the related numerical experimental results are given; and finally, the conclusion of this paper is given in Section 5.

2.   New nonmonotone trust region method

Consider the following unconstrained optimization problem:

where $f$: ${{\mathbb{R}}^{n}}\to \mathbb{R}$ is continuously differentiable. The difficulty in solving the trust region problem often stems from the need to balance multiple objectives: minimizing the approximate objective function, satisfying the trust region constraint, and potentially incorporating additional requirements such as sparsity or regularization. The trust region method computes the trial step $d_k$ by solving the following subproblem:

where ${{g}_{k}} = \nabla f\left({{x}_{k}} \right)$, ${{B}_{k}}$ is the approximation of the Hessian matrix at $x_k$, $\Delta_k$ is the trust region radius, and $\left\| \cdot \right\|$ denotes the Euclidean norm.

As we all know, in trust region method, the trust region ratio is the key to determining whether the algorithm iterates using the current trial step. The following original trust region ratio is monotone:

where ${f_k} = f\left(x_k\right)$, $Ared$ is the actual reduction, and $Pred$ is the predicted reduction. The monotone technique may slow down the rate of convergence, particularly in a narrow curved valley. In order to overcome this disadvantage, the nonmonotone trust region ratio ^[30] has been proposed:

where ${f_{lk}} = \max \limits_{0\le j \le q\left(k\right)} f(x_{k-j})$, $N$ is a fixed positive constant, and

However, this method may result in missing some well-performing function values, so some scholars have proposed improved nonmonotone algorithms. Gu and Mo ^[13] constructed the following trust region ratio in 2008:

where

and $0 < \eta < 1$ or a variable $\eta$.

Based on the inspiration from the above ideas, we propose a new nonmonotone trust region algorithm, which allows the algorithm to use the existing favorable information, and also avoids the algorithm from falling into local optimal solutions. To achieve these, we consider introducing the idea of simulated annealing ^[15,17,32] into the trust region method. A new trust region framework is constructed, which includes the improvement of the trust region iteration criterion and the trust region ratio, etc.

First, we construct a new trust region ratio:

where

and

Here, we introduce the above parameter $p_k$ ^[3,20] into the $R_k$, where $T_k$ is the temperature during annealing, $\tau$ is a given constant, and $r_{k}$ is the trust region ratio. It is crucial to control the rate of the annealing cooling process ^[2], which is usually updated according to the following:

From the definition of $p_k$, we know that it is dynamically updated by the value of $r_k$. From this, it can be observed that our trust region ratio $r_k$ can be adaptively adjusted according to the existing information.

Furthermore, considering the relation between $r_k$ and $\tau$ in the parameter $p_k$, we use the parameter $p_k$ to determine whether the current trial step $d_k$ is accepted. For a random number $l_k < 1$, if $p_k\ge l_k$ is satisfied, then the current trial step is accepted. When $r_k\geq \tau$, $p_k = 1$, the current trial step is naturally accepted. Otherwise, the current trial step will be accepted with a certain probability, and the larger $p_k$ is more probable when the current trial step is accepted. If $p_k < l_k$, then the current trial step is rejected. Using our sequence ${R}_k$, we propose a new nonmonotone line search:

where $0 < \delta < 1$, $0 < {\lambda} < 1$. According to the line search, the corresponding step size is obtained for the iteration. The parameter ${i}_{m}$ is computed by this method, which is iterated through ${{x}_{k+1}} = {{x}_{k}}+{{\lambda }^{{{i}_{m}}}}{{d}_{k}}$. The nonmonotone line search doesn't require the objective function to be monotonically decreasing, which makes the overall algorithm more flexible and faster.

Combined with the above improvements, we propose the nonmonotone trust region algorithm based on the Metropolis criterion (Algorithm 2.1).

Algorithm 2.1.

Step 0. Given an initial point ${{x}_{0}}\in {{\mathbb{R}}^{n}}$, ${{R}_{0}} = f\left({{x}_{0}} \right)$, ${{\Delta }_{0}} > 0$, ${{T}_{0}} > 0$, $\varepsilon > 0$, $v > 1$,

$0 < {\lambda} < 1$, $0 < {\delta}\le 0.5$, $0 < {{\eta }_{1}} < {{\eta }_{2}} < 1$, $0 < {{\gamma }_{1}} < 1 < {{\gamma }_{2}}$, $0 < \beta < 1$,

$0 < \tau \le{{\eta }_{1}}$, $B_0 = \xi I, \xi > 0$, let $k: = 0$.

Step 1. Compute $g_k$. If $\left\| g_k \right\|\le\varepsilon$, stop.

Step 2. Solve the subproblem (2.2) to obtain ${{d}_{k}}$.

Step 3. Compute ${{r}_{k}}$ and ${{p}_{k}}$ by (2.4) and (2.6), respectively. Additionally, compute the following:

Step 4. If ${{p}_{k}}\ge{{l}_{k}}$, then ${{x}_{k+1}} = {{x}_{k}}+{{d}_{k}}$. Otherwise, compute ${{i}_{m}}$, which is the minimum nonnegative integer $i$ which satisfies the following:

then, ${{x}_{k+1}} = {{x}_{k}}+{{\lambda }^{{{i}_{m}}}}{{d}_{k}}$.

Step 5. Update the trust region radius:

Step 6. Compute $f_{k+1}$ and ${{R}_{k+1}} = \left(1-{{p}_{k}} \right){{R}_{k}}+{{p}_{k}}f_{k+1}$, ${{T}_{k+1}} = \beta {{T}_{k}}$, and compute $B_{k+1}$ by a quasi-Newton update. Set $k: = k+1$, then go to Step 1.

Remark 2.1. In Step 3, if $r_{k}\geq \tau$, then the function approximation of the previous iteration is better; then, $p_{k} = 1$ and $R_{k+1} = f_{k+1}$, which is reduced to the case of the traditional trust region ratio. If $r_k < \tau$, then $0 < p_{k} < 1$, and $R_{k+1}$ is the convex combination of $R_{k}$ and $f_{k+1}$.

3.   Convergence analysis

Nonmonotone trust region methods have good global convergence as described in ^[13,24]. In this section, we will analyze the convergence of our algorithm, which also inherits the properties of nonmonotone trust region methods. First, the following assumptions are made.

Assumption 3.1. Let $L = \left\{{x\in {\mathbb{R}}^{n}} \left |f\left (x\right)\le f\left({x_{0}}\right)\right.\right\}\subset\Omega$ be the level set, where $\Omega \in {{\mathbb{R}}^{n}}$ is a bounded closed set.

Assumption 3.2. There exists a positive constant $m$ such that $d^{T}B_{k}d\ge m{\left\|d \right\|}^2$, $\forall d\in {\mathbb{R} ^{n}}$.

Remark 3.1. Combining with Assumptions 3.1 and 3.2, $f\left(x\right)$ is a quadratic continuous differentiable function. It follows that there exists a positive constant $M > m$, such that $\left\| B_{k} \right\| \le M$.

Lemma 3.1. Let the sequence $\left\{x_n\right\}$ be generated by the Algorithm 2.1. There are

Lemma 3.2. Let the sequence $\left\{x_n\right\}$ be generated by the Algorithm 2.1. Then,

holds for all k.

Proof. (1) From the definition of $R_{k+1}$ and $p_k$, if $r_k\geq \tau$, then we have the following:

(2) From $T_{k+1} = \beta T_{k}$, if $r_k < \tau$ and $p_k = exp\{-\frac{\tau-r_{k}}{T_k}\} \ge l_k$, then we can have $\lim\limits_{k\rightarrow \infty}T_{k} = 0$. It is known that $l_{k}\in [e^{-v}, e^{-1/v}]$, and we can obtain $-v\le lnl_k \le -\frac{1}{v}$. Therefore, there exists a positive integer $N$ such that $0 < -T_{k}lnl_k < \varepsilon_1$ holds for any $k > N$, $\varepsilon_1 > 0$. From the definition of $p_k$, we have the following:

From the definition of $r_k$ and (3.1), we have the following:

Let $\varepsilon_1 = \frac{\tau}{2}$; then

(3) If $r_k < \tau$ and $p_k\le l_k$, then $f\left({{x}_{k}}+{{\lambda }^{{{i}_{m}}}}{{d}_{k}} \right)\le {{R}_{k}}+\delta {{\lambda }^{{{i}_{m}}}}{{g}_{k}^{T}}{{d}_{k}}$ holds. Combining with (3.2), we obtain the following:

Therefore, $R_{k+1}\ge f_{k+1}$ holds. The proof is completed. □

Lemma 3.3. Let the sequence $\left\{x_n\right\}$ be generated by the Algorithm 2.1. The sequence $\left\{{R_k}\right\}$ is monotonically decreasing.

Proof. (1) If $r_k\geq \tau$, namely,

then

According to the definition of $R_{k+1}$, we have the following:

(2) By (3.3) and the definition of $R_{k+1}$, if $r_k < \tau$ and $p_k > l_k$, then we obtain the following:

(3) If $r_k < \tau$ and $p_k\le l_k$, then $f\left({{x}_{k}}+{{\lambda }^{{{i}_{m}}}}{{d}_{k}} \right)\le {{R}_{k}}+\delta {{\lambda }^{{{i}_{m}}}}{{g}_{k}^{T}}{{d}_{k}}$ holds. Since ${g_k^T}{d_k}\le 0$, then ${f_{k+1}}\le R_k$.

By the definition of $R_{k+1}$, we obtain the following:

Therefore, $R_{k+1}\le R_{k}$ holds. The proof is completed. □

Lemma 3.4. Let the sequence $\left\{x_n\right\}$ be generated by the Algorithm 2.1. Then, the step length ${\alpha}_{k}$ satisfies ${\alpha}_{k} > \frac{\left(1- \delta \right) \lambda m}{M}$.

Proof. The proof can be proved similarly to the proof of Lemma 3.3 in ^[13] and is omitted here. □

To facilitate the subsequent discussion, the definition of the sequence $M_k$ is introduced as ${M_k} = 1+\ \mathop{\max}\limits_{0\le i\le k}\ \left\|B_i\right\|$.

Lemma 3.5. Assume that the sequences $\left\{{x_k}\right\}$ and $\left\{{R_k}\right\}$ are generated by the Algorithm 2.1. If there exists a positive constant $\varepsilon$, such that $\left\|g_k\right\| \ge \varepsilon$ holds, then for any $k$, there is the following:

where $\psi = \min \left\{\frac{1}{2}\tau, \frac{\delta\left(1-\delta\right)\lambda m}{M}\right\}$.

Proof. (1) By (3.4) and (3.5), if $p_k > l_k$, then we know that

(2) By combining (3.2), Lemma 3.4, and $f_{k+1}\le R_k+\delta{\alpha}_{k}{g_{k}^{T}}{{d}_{k}}$, if $p_k\le l_k$, then the following holds:

According to the definition of $R_{k+1}$, we obtain the following:

Additionally, if $\psi = \min \left\{\frac{1}{2}\tau, \frac{\delta\left(1-\delta\right)\lambda m}{M}\right\}$ and $\left\|g_k\right\| \ge \varepsilon$, then

The proof is completed. □

Lemma 3.6. Assume that Assumption 3.1 holds. If the sequence $\left\{x_k\right\}$ generated by the Algorithm 2.1 does not converge (i.e., there exists a positive constant $\varepsilon$, such that $\left\|g_k\right\| \ge \varepsilon$), then

Proof. Algorithm 2.1 shows that ${R_0} = f_0$. From Lemmas 3.2 and 3.3, we know that $f_{k+1}\le R_{k+1} \le R_{k} \le f_{0}$. Assumption 3.1 shows that if $\left\{f\left(x_k\right)\right\}$ is bounded, then $\left\{R_k\right\}$ is bounded. According to Lemma 3.5, we can know that $\lim\limits_{k\rightarrow \infty}\min\left\{{{\Delta}_k}, \frac{\varepsilon}{M_k}\right\} = 0$. □

Lemma 3.7. If the sequence $\left\{x_k\right\}$ generated by the Algorithm 2.1 does not converge (i.e., there exists a positive constant $\varepsilon$ such that $\|g_k\|\ge\varepsilon$), then there exists a set $J = \left\{k|p_k < l_k \right\}$ such that the following inequality holds for a sufficiently large $k\in J$:

Proof. Based on $\alpha$, we consider the following two cases.

Case 1. If ${i_m} = 0$ (i.e., $\alpha_k = 1$), then

At this point, there is $r_k < \tau$. According to $f_{k+1}\le {R_{k+1}}$ and the definition of $r_k$, we have the following:

According to the Taylor's expansion and Remark 3.1, we obtain the following:

Combining (3.8) and (3.9), we have the following:

Combining (3.10) and Assumption 3.2, we obtain the following:

Combining (3.2) and (3.11), we have the following:

From the definition of $M_k$ and $\left\|g_k\right\| \ge \varepsilon$, and combined with $\|{x_{k+1}-x_k}\| = \|d_k\|$ and (3.12), we obtain the following:

Therefore, it is proved that $\left\|x_{k+1}-x_{k}\right\|\ge \sqrt{\frac{\left(1-\tau \right)\varepsilon \min \left\{ {{\Delta }_{k}}, \frac{\varepsilon }{{{M}_{k}}} \right\}}{M-\tau m}}, {{\alpha}_k} = 1$.

Assuming $\Delta_k\le\frac{\varepsilon}{M_k}$, there is (3.6) to obtain $\Delta_k\ge \sqrt{\frac{\left(1-\tau \right)\varepsilon{\Delta }_{k}}{M-\tau m}}$ (i.e., $\Delta_k\ge \frac{\left(1-\tau \right)\varepsilon}{M-\tau m}$). Combined with $\Delta_k\le\frac{\varepsilon}{M_k}$, there is $\frac{\varepsilon}{M_k}\ge \Delta_k\ge \frac{\left(1-\tau \right)\varepsilon}{M-\tau m}$. This contradicts Lemma 3.6, so we have $\Delta_k > \frac{\varepsilon}{M_k}$.

Case 2. If ${i_m} > 0$ (i.e., $\alpha_k < 1$), then by combining (3.2), Remark 3.1, Lemma 3.2, and the Step 4 of Algortihm 2.1, according to the Taylor's expansion yield,

Therefore, it is proved that $\left\|x_{k+1}-x_{k}\right\| > \frac{\left(1-\delta \right)\varepsilon \lambda}{M} \min\left\{1, \frac{\varepsilon}{{{\Delta}_k}{M_k}}\right\}, {{\alpha}_k} < 1$.

There is

Suppose there exists $\Delta_k\le\frac{\varepsilon}{M_k}$. Combining (3.7), we have the following:

Combining (3.13), (3.14), and Assumption 3.1, there are $\frac{\varepsilon}{M_k}\ge \Delta_k\ge \|{x_{k+1}-x_k}\| > \frac{\left(1-\delta \right)\varepsilon \lambda}{M}$. This contradicts $\lim\limits_{k\rightarrow \infty}\min\left\{{{\Delta}_k}, \frac{\varepsilon}{M_k}\right\} = 0$. Therefore, $\Delta_k > \frac{\varepsilon}{M_k}$ holds.

In summary, the proof is completed. □

Lemma 3.8. If the sequence $\left\{x_k\right\}$ generated by the Algorithm 2.1 does not converge (i.e., there exists a positive constant $\varepsilon$ such that $\|g_k\|\ge\varepsilon$), then ${\Delta_k} > \frac{\varepsilon}{M_k}$ holds for all sufficiently large k.

Proof. (1) If there are only finitely many $k$ such that $\Delta_{k+1}\le\Delta_k$ (i.e., J is a finite set), then there exists a positive constant $\Delta^*$ such that $\Delta_k > \Delta^*$. According to Lemma 3.6, we know that $\lim\limits_{k\rightarrow \infty}\ \frac{\varepsilon}{M_k} = 0$.

(2) We assume that J is an infinite set. It follows from Lemma 3.7 that there exists $\bar{k}\in J$, such that $\Delta_k > \frac{\varepsilon}{M_k}$ holds when $\forall k\in J, k\ge\bar{k}$. When $k\notin J$, $k\ge\bar{k}$, noted as $\tilde{k} = \max \left\{i|i\in J, i\le k\right\}$. We have $\Delta_{\tilde{k}} > \frac{\varepsilon}{M_{\tilde{k}}}$, and $\tilde{k}+s\notin J$, $s = 1, 2, \cdots, k-\tilde{k}$. We can obtain $\Delta_{\tilde{k}}\le \Delta_{\tilde{k}+1} \le \Delta_{\tilde{k}+2} \le \cdots \le \Delta_{k}$, so $\Delta_{k} > \frac{\varepsilon}{M_{\tilde{k}}}$ holds. According to the definition of $M_k$, $\left\{M_k\right\}$ is a monotonically increasing sequence.

The proof is completed. □

Theorem 1. If Assumptions 3.1 and 3.2 hold, and $\left\{B_k\right\}$ satisfies $\sum\limits_{k = 0}^{\infty }{\frac{1}{{{M}_{k}}} = \infty }$, then the sequence $\left\{x_k\right\}$ generated by the Algorithm 2.1 satisfies the following:

Proof. Suppose there exists a positive constant $\varepsilon$ such that $\|g_k\|\ge \varepsilon$. Lemma 3.8 holds, that is ${\Delta_k} > \frac{\varepsilon}{M_k}$ holds for sufficiently large $k$. By Lemma 3.5, we know that ${{R}_{k}}-{{R}_{k+1}}\ge \frac{1}{2}\varepsilon {{p}_{k}}\psi \min \left\{ {{\Delta }_{k}}, \frac{\varepsilon }{{{M}_{k}}} \right\}$. We have $\sum\limits_{k = 0}^{\infty }{({{R}_{k}}-{{R}_{k+1}})}\ge \sum\limits_{k = 0}^{\infty }{\frac{1}{2}}{{\varepsilon }^{2}}{{p}_{k}}\psi \frac{1}{M_k}$, then $\sum\limits_{k = 0}^{\infty }{\frac{1}{{{M}_{k}}} < \infty }$ contradicts $\sum\limits_{k = 0}^{\infty }{\frac{1}{{{M}_{k}}} = \infty }$. The theorem is proved. □

4.   Numerical experiments

In the following, we will show the effectiveness of our Algorithm 2.1 through some numerical experimental results. The numerical experiments are all implemented by using MATLAB (R2017a) on a PC with a CPU of 2.30 GHz and 8.00 GB RAM. The relevant parameters in Algorithm 2.1 and other comparison algorithms are selected as $T_0 = 200$, $v = 100$, $\varepsilon = 10^{-5}$, ${{\Delta }_{0}} = \|g_0\|$, $\lambda = 0.5$, $\delta = 0.5$, $\eta_{1} = 0.25$, $\eta_{2} = 0.75$, $\gamma_{1} = 0.5$, $\gamma_{2} = 2$, $\beta = 0.9$, and $\tau = 0.25$. The matrix $B_k$ is updated by the BFGS formula, i.e.,

In order to explore the influence of the simulated annealing idea, nonmonotone technologies, and different trust region ratios on the algorithm, we perform the following three sets of comparison experiments:

(a) Algorithm 2.1 is compared with the existing trust region algorithm. The NTRM (Nonmonotone Trust Region Method With Line Search) algorithm ^[13] is a classical nonmonotone trust region algorithm. The SATRBB (Simulated Annealing-based Trust Region Bazilai-Borwein) algorithm ^[20] is a trust region algorithm combined with simulated annealing.

(b) Algorithm 2.1 is compared with the algorithms that combine different line search techniques (i.e., Algorithm 2.1 without a line search (SATR) and with a monotonic line search (ATR)).

(c) Algorithm 2.1 is compared with algorithms that combine different ratios (i.e., Algorithm 2.1 by using the original trust region ratio (SATR-OR), correcting the numerator portion of the trust region ratio to the form in ^[13] (SATR-U), and correcting the numerator and denominator portions of the trust region ratio according to $C_k$ in ^[13] (SATR-UD)).

Remark 4.1. The SATR-UD algorithm is inspired by Remark in ^[29], and the form of trust region ratio is as follows:

The test functions used and their associated dimensionality are shown in Table 1. We require the maximum number of iterations of the algorithm to be 5000. It is worth noting that the algorithm which uses the idea of simulated annealing is random in practice; therefore the relevant data are the average of the results of 10 tests.

To further investigate the efficiency of the algorithm, we use the performance profiles ^[9] to evaluate and compare the performance of the solvers. Assume that $k$ denotes the number of iterations required, and $t$ denotes the time required for the algorithm. Moreover, there exist $n_s$ solvers on the test set $S$ and $n_p$ problems on test set $P$. If the computation running time is used as the performance metric, then we define $t_{p, s}$ as computing time required to solve problem $p$ by the solver $s$. We define the performance ratio as follows:

There exists a $r_M$ such that there is $r_M \ge r_s$ for any $p$ and $s$. For the overall evaluation of the solver, we define the following:

where $\rho$ is the cumulative distribution function of the performance ratio, which is the probability that the performance ratio $r_{p, s}$ of the solver $s$ is within the best possible ratio factor $\tau$.

The above three sets of experiments were conducted on the efficiency of solving some problems using the number of iterations and the time required for the algorithm as the performance metrics. The results are shown in Figures 1–3. It is not difficult to see from Figures 1 and 2 that Algorithm 2.1 has good properties compared with existing algorithms, and the nonmonotone line search technology proposed in this paper greatly improves the performance of the algorithm. Figure 3 shows that although the SATR-UD algorithm has a slight advantage for some problems. However, compared with Algorithm 2.1, there are still some problems that the SATR-UD algorithm cannot solve. All in all, the algorithm proposed in this paper is the preferred solver for the above problem with a high probability. Algorithm 2.1 solves the problems with a higher accuracy and requires fewer iterations.

5.   Conclusions

In this paper, we proposed a novel stochastic nonmonotone trust region algorithm, which incorporated the simulated annealing for an enhanced performance. This integration of ideas aimed to address some of the challenges faced by traditional optimization methods, especially in terms of avoiding the local minima and achieving a global convergence. At the heart of our algorithm lies the construction of a new sequence, which was governed by the Metropolis criterion. The trust region ratio was modified based on this sequence, and the iterative criterion was adjusted according to the improved ratio. When the current trial step was not accepted, the iteration step size was obtained based on the modified nonmonotone line search. By doing so, we not only reduced the number of solutions required for the trust region subproblem, but also enhanced the algorithm's ability to escape the local minimum and converge to a global optimum. A theoretical analysis showed that our proposed algorithm achieved a global convergence under certain conditions, making it avoid local optimal solutions as much as possible. Furthermore, numerical experiments were conducted to demonstrate the effectiveness of our algorithm in practical applications. These experiments revealed that our algorithm outperformed traditional methods.

Author contributions

Yiting Zhang: Conceptualization, Methodology, Investigation, Software, Validation, Writing-original draft; Chongyang He: Funding acquisition, Investigation, Software; Wanting Yuan: Validation, Writing-review & editing; Mingyuan Cao: Funding acquisition, Methodology, Software, Writing-review & editing. All authors have read and approved the final version of the manuscript for publication.

Acknowledgments

The key project of the natural science foundation joint fund of Jilin province (YDZJ202201ZYTS303, YDZJ202101ZYTS167, 20230508184RC, JJKH20200037KJ); The graduate innovation project of Beihua University (2023003); The science and technology development plan project of Jilin province (20200403193SF).

Conflict of interest

All authors declare no conflicts of interest in this paper.