A nonmonotone trust region technique with active-set and interior-point methods to solve nonlinearly constrained optimization problems

1.   Introduction

In this paper, we will consider the following nonlinear constrained optimization problem

where $f$: $\Re^n \rightarrow \Re$ and $P_i(x)$: $\Re^n \rightarrow \Re^m$, such that

and

are twice continuously differentiable and $m < n$. We denote the feasible set

and the strict interior feasible set

where

and $\hat{u} < \hat{v}$.

This work combines an active-set strategy with the penalty approach to transform problem (1.1) into an unconstrained optimization problem with bounded variables. To solve the unconstrained optimization problem with bounded-on variables, Newton's interior-point method, which was suggested in^[1] and used by ^[2,3,4,5], is utilized. However, Newton's method is a local one, and it may not converge if the starting point is far from a stationary point. A nonmonotone trust-region mechanism deals with this problem and guarantees convergence from any starting point to the stationary point.

A trust-region technique can induce strong global convergence and is a very important method for solving unconstrained and constrained optimization problems ^[6,7,8,9]. The trust-region technique is more robust when dealing with rounding errors. One advantage of this technique is that it does not require the model's objective function to be convex.

A critical aspect in trust-region approaches is the strategy for determining the trust-region radius $\Delta_k$ at each iteration. The standard trust-region strategy is predicated on the objective function and the model agreement. The radius of the trust region is updated by paying attention to the ratio

where $Ared_k$ represents the actual reduction, and $Pred_k$ represents the predicted reduction. It is safe to increase $\Delta_k$ in the next iterate when $r_k$ is close to 1, and this is due to a good agreement between the objective function and the model over a current region of trust. Otherwise, $\Delta_k$ must be reduced.

It is well-known that the standard trust-region radius $\Delta_k$ is independent of the gradient and Hessian of the objective function, so we cannot know if the radius $\Delta_k$ is convenient for the whole implementation. This situation increases the number of subproblems to solve in the inner steps of the method, decreasing its efficiency. If we reduce the number of ineffective iterations, we can decrease the number of subproblems solved in each step. Authors in ^[10] proposed a method for determining the initial radius monitoring agreement between the objective function and the model along the steepest descent path evaluated.

Authors in ^[11] proposed the first customizable technique to reduce the number of solved subproblems. This technique used the gradient and Hessian information from the current iteration to calculate the trust-region radius $\Delta_k$ without requiring an initial trust-region radius.

Motivated by the idea proposed in ^[11], authors in ^[12] proposed an automatically adjustable radius for trust-region methods and demonstrated that nonmonotone trust-region methods inherit the conventional trust-region method's strong convergence features. On the other hand, authors in ^[13] presented a nonmonotone strategy to line search methods for unconstrained optimization problems. Numerical experiments and theoretical analysis have referred to the effectiveness of this method in improving both the possibility of obtaining the global optimum and the rate of convergence of algorithms ^[14]. Motivated by these outstanding results, many researchers have been interested in combining the nonmonotone strategy with the trust-region methods ^[15,16].

Nonmonotone approaches have altered the ratio $r_k$ when comparing $Ared_k$ to $Pred_k$. The following is a definition of one of the most common nonmonotone ratios:

where

in which

and

with an integer constant $N \geq 0$. It has been proven that the nonmonotone trust-region methods inherit the robust convergence properties of the trust-region method. The numerical experiments of the nonmonotone trust-region methods have shown that it is more efficient than the monotone versions, especially in the presence of the narrow, curved valley. Although the nonmonotone strategy in ^[13] performs well in many cases, it contains some drawbacks, and two important instances of these drawbacks can be described as follows:

● In any iterate, a good function value generated is essentially discarded due to $\{max\}$ term in

● The numerical performances in some cases seriously depend on the choice of parameter N.

Authors in ^[17] proposed a new nonmonotone strategy for line search methods. It was based on a weighted average of previous successive iterations. This strategy is generally efficient and promising when encountered with unconstrained optimization and can overcome the mentioned drawbacks. In this strategy, $f_l(k)$ is replaced with a weighted average of previous successive iterations $C_k$, which is defined as follows:

and

such that

where $\eta_k$ is updated as follows

Motivated by the advantage of the nonmonotone strategy in the trust-region framework ^[17], authors in ^[18] suggested a new nonmonotone trust-region method such that the ratio $\tilde{r_k}$ in their proposal changed as follows

The investigation has proved that the combination of the nonmonotone strategy of ^[17] with the trust region a new method that has inherited the strong theoretical properties of the trust-region method as well as the computational robustness of the nonmonotone strategy.

Motivated by the nonmonotone trust-region strategy in ^[18], we will utilize it in our proposed method. We expect it will significantly decrease the total number of iterations and function evaluations. We will clarify that under some conditions, the proposed nonmonotone trust-region active-set penalty (NTRAI) algorithm has global convergence properties.

Furthermore, the applicability of the NTRAI approach to solving problem (1.1) was examined using well-known test problems (the CUTE collection), three mechanical engineering problems from the most recent test suite ^[19], and a nonconvex problem from ^[20]. Numerical experiments show that the NTRAI method exceeds rival algorithms in terms of efficacy.

Some notations are utilized throughout this paper, and this is clarified in the rest of this section. The paper is organized as follows: In Section 2, a detailed description of the main steps of the NTRAI algorithm for constrained optimization problems is introduced. Section 3 is devoted to the global convergence theory of the NTRAI algorithm under some suitable conditions. Section 4 contains a Matlab implementation of the NTRAI algorithm and numerical results for three mechanical engineering problems. Finally, Section 5 contains concluding remarks.

To express the function value at a particular point, we use the symbol

and so on. We denote the Hessian of the objective function $f_k$ or an approximation to it by $P_k$. Finally, every norm is $l_2$-norms.

2.   Nonmonotone trust-region active-set penalty algorithm

In this section, we will first present a complete description of the significant steps of the active-set strategy using the penalty technique and Newton's interior-point approach. Then the nonmonotone trust-region algorithm's essential phases are presented. Finally, the key stages for applying the NTRAI method to problem (1.1) are shown.

2.1.   An active-set penalty interior-point method

Consider the active-set strategy introduced in ^[21] and used by ^[5,7]. We will introduce a diagonal matrix $Z(x)\in \Re^{m\times m}$ whose diagonal entries are

where $i = 1, \cdots, m$. Utilizing the diagonal matrix (2.1), we can write problem (1.1) as follows

where

is a twice continuously differentiable function. The above problem is converted to the following equivalent problem by utilizing the penalty method ^[22]

where $\rho > 0$ is a parameter.

Let

and then we will define a Lagrangian function associated with problem (2.2) as follows

where $\lambda_{\hat{u}}$ and $\lambda_{\hat{v}}$ are Lagrange multiplier vectors associated with the inequality constraints $x-\hat{u} \geq 0$ and $\hat{v} - x \geq 0$, respectively.

A point $x_*\in \boldsymbol{E}$ will be a local minimizer of problem (2.2) if there exists multiplier vectors $\lambda_{\hat{u}}(x_*) \in \Re_{+}^n$ and $\lambda_{\hat{v}}(x_*) \in \Re_{+}^n$ such that the following conditions are satisfied

where

Motivated by the interior point method introduced in ^[1] and used by ^[2,4,8,9], we define a diagonal scaling matrix $Y(x)$ whose diagonal elements are given by

Utilizing the matrix $Y(x)$, conditions (2.5)–(2.7) are equivalent to the following nonlinear system

Nonlinear Eq (2.9) is continuous but is not differentiable at some point $x \in \boldsymbol{E}$ for the following reasons:

● It may be non-differentiable when $y^{(j)} = 0$. To overcome this problem, we restrict $x \in int(\boldsymbol{E})$.

● It may be non-differentiable when $y^{(j)}$ has an infinite upper bound and a finite lower bound, and

To overcome this problem, we define a vector $\Psi(x)$ whose components

are defined as follows

When we apply Newton's technique to the system (2.9), we get

where

and $H$ is the Hessian of the objective function $f(x)$ or an approximation to it.

Assuming that $x \in int(\boldsymbol{E})$, then the matrix $Y(x)$ must be non-singular. Multiply both sides of Eq (2.9) by $Y^{-1}(x)$ and set

we have

Notice that the step $d_k$, which is generated by system (2.13) is equivalent the step generated by solving the following quadratic programming subproblem

where

Newton's approach has the advantage of being quadratically convergent under reasonable assumptions, but it has the drawback of requiring the initial point to be close to the solution. The nonmonotone trust-region globalization approach ensures convergence from any starting point. It is a crucial method for solving a smooth, nonlinear, unconstrained, or constrained optimization problem that can produce substantial global convergence.

For the purpose of solving problem (2.14), we introduce a detailed description of the nonmonotone trust-region algorithm.

2.2.   A nonmonotone trust-region algorithm

The trust-region subproblem associated with the problem (2.14) is

where $\Delta_k > 0$ is the radius of the trust region.

Using a dogleg method, which is a very cheap method, to solve subproblem (2.16) and obtain the step $d_k$. For more details, see ^[23].

● To compute the step $d_k$

In a dogleg method, the solution curve to the subproblem (2.16) is approximated by a piecewise linear function connecting the Newton point to the Cauchy point. The following algorithm explains the key phases of the dogleg approach to solve subproblem (2.16) and obtain $d_k$.

Algorithm 2.1. Dogleg algorithm.

Step 1. Compute the parameter $t_k^{cp}$ as follows:

Step 2. Compute the Cauchy step

Step 3. If

then set $d_k = d_k^{cp}$.

Else, If $Y_k\nabla \tilde{\phi}(x_k; \rho_k)+B_k d_k^{cp} = 0$, then set $d_k = d_k^{cp}$.

Else, compute Newton's step $s^N$ by solving the following subproblem:

End if.

Step 4. If $\|d_k^N\|\leq \Delta_k$, then set $d_k = d_k^N$.

Else, computing dogleg step between $d_k^{cp}$ and $d_k^N$ and compute $d_k$ as follows

End if.

By using dogleg Algorithm 2.1, the step $d_k$ satisfies the following condition, which is called a fraction-of-Cauchy decrease condition

for some $\varphi \in (0, 1]$.

When a condition is referred to as a fraction-of-Cauchy decrease, it indicates that the predicted reduction obtained by the step $d_k$ is more than or equal to a fraction of the predicted decrease obtained by the $d_kcp$ (Cauchy step).

To ensure that the matrix $Y_k$ is nonsingular, we need to guarantee that $x_{k+1}\in int (\boldsymbol{E})$. To do this, we need to a damping parameter $\tau_k$.

● To obtain damping parameter $\tau_k$

The main steps to obtain the damping parameter $\tau_k$ are clarified in the following algorithm:

Algorithm 2.2. Damping parameter $\tau_k$.

Step 1. Compute the parameter $\alpha_k$ as follows:

Step 2. Compute the parameter $\beta_k$ as follows:

Step 3. Compute the damping parameter $\tau_k$ as follows

Step 4. Set

To test the scaling step $\tau_k Y_k d_k$ to decide whether it will be accepted or not, a merit function is required. The merit function ties the objective function and the constraints in such a way that progress in the merit function means progress in solving the problem. The merit function that is used in our algorithm is the penalty function $\tilde{\phi}(x_k; \rho_k)$.

Let the actual reduction $Ared_k$ be defined as follows

Additionally, $Ared_k$ can be expressed as follows

Let the predicted reduction $Pred_k$ be defined as follows

where

● To test $\tau_k Y_kd_k$ and update $\Delta_k$

Motivated by the nonmonotone trust-region strategy in ^[18], we define

where

and

such that

The following algorithm clarifies how the trial step will be tested and updated the trust region radius $\Delta_k$:

Algorithm 2.3. Test $\tau_k Y_kd_k$ and update $\Delta_k$.

Step 0. Choose $0 < \theta_1 < \theta_2 \leq 1$, $\Delta_{max} > \Delta_{min}$, and $0 < \tilde{\alpha_1} < 1 < \tilde{\alpha_2}$.

Step 1. Compute $Q_k$ using (2.24) and $C_k$ using (2.23).

Evaluate $\hat{r_k}$ using (2.22).

While $\hat{r_k} < \theta_1$, or $Pred_k \leq 0$.

Set $\Delta_k = \tilde{\alpha_1}\parallel d_k \parallel$.

Return to algorithm (2.1) to evaluate a new step $d_k$.

Step 2. If $\theta_1 \leq \hat{r_k} < \theta_2$, then set $x_{k+1} = x_k + \tau_k Y_k d_k$.

Set $\Delta_{k+1} = \max(\Delta_{min}, \Delta_k)$.

End if.

Step 3. If $\hat{r_k} \geq \theta_2$, then set $x_{k+1} = x_k + \tau _k Y_k d_k$.

Set $\Delta_{k+1} = \min\{\max\{\Delta_{min}, \tilde{\alpha_2}\Delta_k\}, \Delta_{max}\}$.

End if.

● To update the parameter $\rho_k$

To update $\rho_k$, a scheme proposed by ^[24] is used; and we will clarify this in the algorithm that follows:

Algorithm 2.4. Updating $\rho_k$.

Step 1. Set $\rho_0 = 1$ and use Eq (2.21) to evaluate $Pred_k$.

Step 2. If

Then, set $\rho_{k+1} = \rho_k$.

Else, set $\rho_{k+1} = 2\rho_k$.

End if.

Finally, the nonmonotone trust-region algorithm is terminated, if

or

for some $\epsilon_1 > 0$ and $\epsilon_2 > 0$.

● Nonmonotone trust-region algorithm

We will clarify the main steps of the nonmonotone trust-region algorithm to solve subproblem (2.16) in the algorithm that follows:

Algorithm 2.5. The nonmonotone trust-region algorithm.

Step 0. Initial value

      Starting $x_0\in int (\boldsymbol{E})$. Compute matrices $Z_0$, $Y_0$ and $\Psi_0$. Set $\rho_0 = 1$.

      Choose $\epsilon_1, \epsilon_2, \tilde{\alpha_1}, \tilde{\alpha_2}, \theta_1, \theta_2$, such that $\epsilon_1 > 0, \epsilon_2 > 0, \tilde{\alpha_2} > 1 > \tilde{\alpha_1} > 0$ and $0 < \theta_1 < \theta_2 \leq 1$.

      Choose $\Delta_0$, $\Delta_{min}$, and $\Delta_{max}$, such that $\Delta_{min}\leq \Delta_0 \leq \Delta_{max}$.

      Set $k = 0$.

Step 1. If $\parallel Y_k \nabla f_k \parallel+ \parallel Y_k\nabla P_k Z_k P_k \parallel \leq \epsilon_1$, then stop.

Step 2. Evaluating the trial step $d_k$ using the Algorithm 2.1.

Step 3. Stop and end the algorithm if $\parallel d_k\parallel \leq \epsilon_2$.

Step 4. Compute both $\tau_k$ and $Y_k$ using Algorithm 2.2 and Eq (2.8), respectively.

Set $x_{k+1} = x_k + \tau_k Y_k d_k$.

Step 5. Utilize (2.1) to evaluate $Z_{k+1}$.

Step 6. To test the scaling step and update $\Delta_k$:

      i) Computing $Q_k$ using (2.24) and $C_k$ using (2.23).

      ii) Compute $\hat{r_k}$ using (2.22).

      iii) Using Algorithm 2.3 to test the scaling step $\tau_k Y_k d_k$ and update the radius of the trust-region $\Delta_k$.

Step 7. Updating the parameter $\rho_k$ using Algorithm 2.4.

Step 8. Utilize (2.10) to evaluate $\Psi_{k+1}$.

Step 9. Set $k = k+1$ and return to Step 1.

2.3.   Nonmonotone trust-region active-set penalty algorithm

The main steps for the NTRAI algorithm to solve problem (1.1) will be clarified in the following algorithm:

Algorithm 2.6. NTRAI algorithm.

Step 1. Utilize active-set strategy and penalty method to convert a nonlinearly constrained optimization problem (1.1) to an unconstrained optimization problem with bounded variables (2.2).

Step 2. Utilize an interior-point method and a diagonal scaling matrix $Y(x)$ given in (2.8), and the first-order necessary conditions (2.5)–(2.7) equivalent to the nonlinear system in (2.9).

Step 3. Utilize Newton's method to solve the nonlinear system (2.9) and obtain the equivalent subproblem (2.14).

Step 4. Solve subproblem (2.14) using nonmonotone trust-region Algorithm 2.5.

The global convergence analysis for NTRAI Algorithm 2.6 is conducted in the following section.

3.   Analysis of global convergence

In this section, a global convergence analysis for the NTRAI Algorithm 2.6 to solve problem (1.1) will be presented. First, we will introduce the necessary assumptions that are requested to prove the theory of global convergence for the NTRAI Algorithm 2.6. Second, we will introduce some lemmas that are required to prove the main results. Third, we will study the iteration sequence convergence when $\rho_k$ is unbounded and bounded, respectively. Finally, the main global convergence results for the NTRAI Algorithm 2.6 will be proved.

3.1.   Necessary assumptions

Let $\{ x_k \}$ be the sequence of points generated by the NTRAI Algorithm 2.6 and let $\Omega$ be a convex subset of $\Re^n$ that contains all iterates $x_k\in int (\boldsymbol{E})$ and $x_k + \tau_k Y_k d_k \in int (\boldsymbol{E})$, for all trial steps $d_k$. On the set $\Omega$, we assume the following assumptions, under which the global convergence theory will be proved.

● Assumptions:

[$As_1$] For all $x \in \Omega$, the functions $f(x)$ and $P(x)$ are at least twice continuously differentiable.

[$As_2$] All of $f(x)$, $\nabla f(x)$, $\nabla^2 f(x)$, $P(x)$, and $\nabla P(x)$ are uniformly bounded in $\Omega$.

[$As_3$] The sequence of Hessian matrices $\{B_k\}$ is bounded.

Some lemmas are required to prove the main global convergence theory. These lemmas are introduced in the following section:

3.2.   Required lemmas

We shall introduce some lemmas that are necessary to support the main results.

Lemma 3.1. Under assumptions $As_1$–$As_3$, there exists a constant $K_1 > 0$ such that,

Proof. Since the fraction-of-Cauchy decrease condition (2.18) is satisfied by the trial step $d_k$, then we will consider the following two cases:

ⅰ) If

and

then

ⅱ) If

and

then we have

From inequalities (2.18), (3.2), and (3.3), we have

From inequality (3.4) and the following fact

where $0\leq\tau_k \leq 1$, then we have

From (2.21), we have

Hence

This completes the proof. □

Lemma 3.2. Under assumptions $As_1$ and $As_3$, then $Z(x)P(x)$ is Lipschitz continuous in $\Omega$.

Proof. The proof of this lemma similar [21, Lemma 4.1].

We can verify that $\nabla P(x) Z(x) P(x)$ is Lipschitz continuous in $\Omega$ and $\| Z(x) P(x)\|^2$ is differentiable from Lemma 3.2. □

Lemma 3.3. At any iteration $k$, we have

where $A(x_k) \in \Re^{m \times m}$ is a diagonal matrix whose diagonal entries are defined as follows

where $i = 1, 2, \cdots, m$.

Proof. See [6, Lemma 6.2].□

Lemma 3.4. Under assumptions $As_1$–$As_3$, there exists a constant $K_2 > 0$, such that

Proof. See [6, Lemma 6.3].□

Lemma 3.5. Under assumptions $As_1$–$As_3$, there exists a constant $K_3 > 0$, such that

Proof. From Eqs (2.20) and (3.5), we have

Subtracting the above equation from (2.21), and using Cauchy-Schwarz inequality, we have

for some $\xi_1$ and $\xi_2 \in (0, 1)$. From assumptions $As_1$–$As_3$ and using Lemma 3.4, the proof is completed.□

The following section is devoted to the analysis of global convergence for NTRAI Algorithm 2.6 when $\rho_k$ is unlimited.

3.3.   Global convergence when $\rho_k$ is unbounded

Observe that we do not assume that $\nabla P(x)$ has full column rank for all $x \in \Omega$ in assumptions $As_1$-$As_3$; therefore, we may have alternative types of stationary points. The definitions that follow describe these stationary spots.

Definition 3.1. (A Fritz John (FJ) point.) If there is $\omega_*\in \Re$ and a Lagrange multiplier vector $\sigma_* \in \Re^m$ that is not all zero, then the point $x_*\in \Re$ is said to be a FJ point if the following conditions are satisfied

The conditions (3.9)–(3.12) are referred to as FJ conditions. See ^[25] for further information.

The FJ conditions are referred to as a Karush-Kuhn-Tucker (KKT) conditions, and the point $(x_*, 1, \frac{\sigma_*}{\omega_*})$ is referred to as the KKT point if $\omega_*\neq 0$.

Definition 3.2. (Infeasible Fritz John (IFJ) point.) If there is $\omega_*\in \Re$ and a Lagrange multiplier vector $\sigma_* \in \Re^m$ that is not all zero, then the point $x_*\in \Re$ is said to be a IFJ point if the following conditions satisfy

The conditions (3.13)–(3.16) are referred to as IFJ conditions. See ^[25] for further information.

The IFJ conditions are referred to as the infeasible KKT conditions and the point $(x_*, 1, \frac{\sigma_*}{\omega_*})$ is referred to as the infeasible KKT point if $\omega_*\neq 0$.

The next two lemmas provide conditions that are equivalent to those stated in Definitions 1 and 2.

Lemma 3.6. Under assumptions $As_1$–$As_3$, there exists $\{x_{k_i}\}\subseteq \{x_k\}_{k\geq0}$, satisfies IFJ conditions if:

1) $\lim_{{k_i} \rightarrow \infty}\| Z_{k_i} P_{k_i} \| > 0.$

2) $\lim_{{k_i} \rightarrow \infty}\left \{ \min_d \left \{\| Z_{k_i}(P_{k_i}+\nabla P_{k_i}^T Y_{k_i}\tau_{k_i}d)\|^2\right \} \right \} = \lim_{{k_i} \rightarrow \infty}\| Z_{k_i} P_{k_i}\|^2$.

Proof. The proof of this lemma is similar to the proof of [2, Lemma 3.1]. □

Lemma 3.7. Under assumptions $As_1$–$As_3$, there exists $\{x_{k_i}\} \subseteq \{ x_k\}_{k\geq0}$ satisfies FJ conditions if:

1) For all $k_i$, $\| Z_{k_i} P_{k_i} \| > 0$ and $\lim_{k_i \rightarrow \infty } Z_{k_i} P_{k_i} = 0.$

2) $\lim_{{k_i} \rightarrow \infty}\left \{ \min_{d}\left \{ \frac{\| Z_{k_i}(P_{k_i}+\nabla P_{k_i}^T Y_{k_i}\tau_{k_i} d)\|^2}{\| Z_{k_i} P_{k_i}\|^2} \right \} \right \} = 1$.

Proof. The proof of this lemma similar the proof of [26, Lemma 3.2].□

According to the Algorithm 2.4, the sequence of parameters $\{\rho_k\}$ is only unlimited when there is an infinite subsequence of indexes $k_i$ indexing iterates of acceptable steps that fulfill, for every $k\in\{k_i\}$,

A subsequence of iterates $\{ x_k\}$ satisfies the FJ conditions or IFJ conditions if $\rho_k \rightarrow \infty$ as $k \rightarrow \infty$. This is demonstrated by the next two lemmas.

Lemma 3.8. Under assumptions $As_1$–$As_3$ and $\rho_k \rightarrow \infty$ as $k \rightarrow \infty$.

If $\| Z_k P_k \| \geq \varepsilon > 0$ for all $k\in \{ k_i\}$, a subsequence of the iteration sequence with index $k_i$ exists and fulfills the IFJ conditions in the limit.

Proof. For simplification, we assume $k_i$ is $k$. This lemma's proof is due to a contradiction, so, assume that there is no subsequence of iterates that satisfies the IFJ conditions in the limit. From Lemma 3.6 and Definition 3.2, we have

and

respectively. Hence

From (2.15) and (2.12), we have

From inequalities (3.1) and (3.18), we have

for $k$ sufficiently large. There is an infinite number of acceptable iterates at which inequality (3.17) holds since $\rho_k \rightarrow \infty$. From inequalities (3.17) and (3.19), we have

According to the assumption $As_2$, the preceding inequality's right side tends toward infinity as $k \rightarrow \infty$ and the left-hand side is bounded such that

This result gives a contradiction unless $\rho_k\Delta_k$ is bounded. That is $\Delta_k \rightarrow 0$.

Now, if $\rho_k \rightarrow \infty$, at $k \rightarrow \infty$, we will consider two cases:

First, if

then

Hence, $Pred_k\rightarrow \infty$ using assumptions $As_2$ and $As_3$. In other words, the left-hand side of inequality (3.17) goes to infinity since $k \rightarrow \infty$, but the right-hand side goes to zero since $\Delta_k \rightarrow 0$. Then we get a contradiction with the assumption in this case.

Second, if

then we have

Similar to the first case, $Pred_k\rightarrow -\infty$, but $Pred_k > 0$ and this gives a contradiction. These two contradictions prove the lemma. □

The following lemma shows that the behavior of NTRAI Algorithm 2.6 when

and $\rho_k \rightarrow \infty$ as $k \rightarrow \infty$.

Lemma 3.9. Under assumptions $As_1$–$As_3$ and at $\rho_k \rightarrow \infty$ as $k \rightarrow \infty$, then there exists a subsequence $\{k_i\}$ of iterates that satisfies the FJ conditions in the limit if $\| Z_k P_k \| > 0$ for all $k\in \{k_i\}$ and

Proof. For simplification, we assume $k_i$ is $k$. Assume that there is no subsequence of iterations that fulfills the FJ conditions in the limit since the demonstration of this lemma relies on contradiction. From Lemma 3.7, we have

for each $k$ very large.

Now we will consider three cases if $\rho_k \rightarrow \infty$, at $k \rightarrow \infty$:

First, if

then there is a contradiction with inequality (3.20).

Second, if

From subproblem (2.16), we have

where $0 < \upsilon_k$ is the Lagrange multiplier vector of the trust region constraint. Hence, we can write inequality (3.1) as follows

From (2.15) and the above inequality, we have

where

As a result, there are an infinite number of acceptable steps at which inequality (3.17) holds. From inequality (3.17), we have

and using inequalities (3.22) and (3.23), we have

where

Dividing the above inequality by $\| Z_k P_k\|$, then

As $k \rightarrow \infty$, the right-hand side of the previous inequality goes to zero. That is,

is bounded along the subsequence $\{ k_i\}$ where

That is, either $\frac{d_{k_i}}{\| Z_{k_i} P_{k_i} \|}$ lies in the null space of

or

The first possibility only occurs when $\frac{\upsilon_{k_i}}{\rho_{k_i}}\rightarrow 0$ as $k_i \rightarrow \infty$ and $\frac{d_{k_i}}{\| Z_{k_i} P_{k_i} \|}$ lies in the matrix's null space. $Y_{k_i}\nabla P_{k_i} Z_{k_i} \nabla P_{k_i}^T Y_{k_i}$ contradicts assumption (3.20) and implies that a subsequence of $\{ k_i\}$ satisfies the FJ conditions in the limit.

The second possibility implies

as $k_i \rightarrow \infty$. Hence, $\rho_{k_i} \|Y_{k_i}\nabla P_{k_i} Z_{k_i} P_{k_i}\|$ must be bounded, and we have $\nabla f_{k_i} = 0$. This implies that a subsequence of $\{k_i\}$ satisfies the FJ conditions in the limit.

Third, if

and

Therefore $\| d_k\|\rightarrow 0$. As a result, in the second case, as $k \rightarrow \infty$, the right-hand side of (3.24) goes to zero. Hence

This implies that, either

or

In a similar way to the above second case, we can prove that a subsequence of $\{k_i\}$ satisfies the FJ conditions in the limit. The proof is now complete.□

3.4.   Convergence when $\rho_k$ is bounded

We continue our analysis in this section on the assumption that the penalty parameter $\rho_k$ is bounded. In other words, we proceed with our analysis assuming that there is an integer $\bar{k}$ such that $\rho_k = \bar{\rho} < \infty$ for all $k\geq \bar{k}$.

Lemma 3.10. Assume that $\{x_ k\}$ is the sequence of iterations generated by the NTRAI algorithm, then we have

Proof. Let iterate $k$ be a successive iterate, then from Algorithm 2.3, we have

That is,

and by using inequality (3.1), we have

From (2.23), (2.24) and using inequality (3.26), then we have

That is,

From (2.23), we have

Using (2.24), then we have

Hence

From (3.27) and (3.28), we have

From (3.27) and (3.29), we have

This completes the proof. □

Lemma 3.11. Under assumptions $As_1$–$As_3$ and at any iteration $k$ at which

Then, there exists a constant $K_4 > 0$ such that

Proof. From (2.12), (2.15), and using assumptions $As_1$–$As_3$, then there exists a constant $b_1 > 0$ such that $\|B_k\|\leq b_1$ for all $k$. Let

and using inequality (3.1), we have

where

This completes the proof. □

Lemma 3.12. Under assumptions $As_1$–$As_3$ and if

then an acceptable step is found after finitely many trials. That is, the condition

will be satisfied.

Proof. Since

then from Lemmas 3.5, 3.10, and 3.11, we have

As a result of step $d_k$ being rejected, $\Delta_k$ is now small, and after a finite number of trials, the acceptance rule will finally be satisfied. That is

and this ends the proof. □

Lemma 3.13. Under assumptions $As_1$–$As_3$ and if

at a given iteration $k$, the $j^{th}$ trial step satisfies

then it has to be accepted.

Proof. Since the proof of this lemma is by a contradiction, we assume that the inequality (3.31) is true and the step $d_{k^j}$ is rejected. Since $d_{k^j}$ is rejected, then we have from Algorithm 2.3

Using, inequalities (3.8) and (3.30), we have Hence

This demonstrates the lemma and provides a contradiction. □

3.5.   Global convergence theory

The fundamental global convergence theorem for Algorithm 2.6 is covered in this section.

Theorem 3.1. Under assumptions $As_1$–$As_3$, the sequence of iterates generated by the NTRAI algorithm satisfies

Proof. First, we will prove the following limit by contradiction

So, suppose that,

for all $k$. Consider a trial step indexed $j$ of the iteration indexed k such that $k^j\geq \bar{k}$ and $k\geq \bar{k}$. Using Algorithm 2.3 and Lemma 3.11, we have the following for any acceptable step indexed $k^j$,

As $k$ goes to infinity, we have

This implies that the value of $\Delta_{k^j}$ is not bounded below:

If we consider an iteration with indexed $k^j > \bar{k}$ and if the preceding step was approved, that is, if $j = 1$, then $\Delta_{k^1} \geq \Delta_{min}$. Thus, in this case, $\Delta_{k^j}$ is bounded.

If $j > 1$, at least one trial step has been rejected, and according to Lemma 3.13, we have

for all $i = 1, 2, \cdots, j-1$. Since $d_{k^i}$ is a rejected trial step, then from algorithm 2.3, we have

Hence, $\Delta_{k^j}$ is bounded and this contradicts condition (3.35). Hence, the supposition is wrong and the limit in (3.33) holds. Hence, limit in (3.32) holds and this completes the proof of the theorem. □

4.   Numerical results

This section compares the performance of the NTRAI algorithm and demonstrates its robustness and efficiency using a collection of test problems with varying features that are commonly utilized in the literature. First, the tested problems are the Hock and Schittkowski's subset of the general nonlinear programming testing environment (the CUTE collection) ^[27]. Second, three engineering design problems are also tested.

We provided the numerical results of NTRAI algorithm obtained on a laptop with 8 GB RAM, USB 3 (10x), Nvidia GEFORCE GT, and Intel inside Core (TM)i7-2670QM CPU 2.2 GHz. NTRAI was run under MATLAB (R2013a)(8.2.0.701)64-bit(win64). The values of the required constants in Step 0 of nonmonotone trust-region Algorithm 2.5 were selected to be

Successful termination with respect to the nonmonotone trust-region Algorithm 2.5 means that the termination condition of the algorithm is met with $\epsilon_1$.

4.1.   Benchmark test problems

Benchmark problems are listed in Hock and Schittkowski^[27] to show the effectiveness of the NTRAI algorithm. For comparison, we have included the corresponding results of the NTRAI algorithm against the numerical results in^[3,28,29]. This is summarized in Table 1, where Niter refers to the number of iterations. The algorithm has the ability to locate the optimal solution for either a feasible or infeasible initial reference point.

For all problems, these algorithms achieved the same optimal solution in ^[27]. Figure 1 shows the numerical results, which are summarized in Table 1 by using the performance profile that is proposed by Dolan and More ^[30].

The performance profile in terms of Niter is given in Figure 1, which shows a distinctive difference between the NTRAI algorithm and the other algorithms ^[3,28,29]. Figure 2 represents the number of iterations required for each problem with different methods.

4.2.   Applicability of NTRAI algorithm to solve mechanical engineering problems

In this section, to evaluate the applicability of the NTRAI algorithm in real-world applications, we will consider three constrained mechanical engineering problems from the latest test suite ^[19].

In this experimental estimation, the NTRAI algorithm was compared with algorithms AOA ^[31], CGA ^[32], ChOA ^[33], SA ^[34], LMFO ^[35], I-MFO^[36], MFO ^[37], WOA ^[38], GWO ^[39], SMFO ^[40], and WCMFO^[41]. All algorithms attempt to solve three distinct problems, including: a gas transmission compressor design problem, a three-bar truss design problem, and a tension/compression spring design problem.

● $P_1$. Gas transmission compressor design (GTCD) problem

Minimizing the objective function utilizing four design variables is the fundamental objective of the GTCD problem. Figure 3 clarifies the GTCD problem. The mathematical formulation for the GTCD problem is

The performance of the NTRAI algorithm was evaluated against other methods when solving the GTCD problem. Table 2 presents the numerical results and comparisons for the GTCD problem. As seen in the table, the NTRAI algorithm is the most effective in addressing this problem.

● $P_2$. Three-bar truss design (TBTD) problem

In the TBTD problem, three constraints and two variables are used to formulate the weight of the bar structures, which is the objective function. Figure 4 clarifies the schematic for the TBTD problem. The mathematical formula for the TBTD problem is

The NTRAI algorithm is compared with the other algorithms when solving the TBTD problem. Table 3 shows the numerical results for the TBTD problem. The NTRAI algorithm outperforms other algorithms in approximating the optimal values for variables with minimum weight.

● $P_3$. Tension/compression spring design (TCSD) problem

In the TCSD problem, four constraints and three variables are utilized to formulate the weight of the tension/compression spring, which is an objective function. As shown in Figure 5, the variables are wire diameter d, the mean coil diameter D, and the number of active coils N. These variables are denoted in mathematical formulation by $x_1$, $x_2$, and $x_3$, respectively.

The mathematical formulation for the TCSD problem is

The NTRAI Algorithm 2.6 is compared with other algorithms when solving the tension/compression spring design problem. The numerical results and the comparison between algorithms for the TCSD problem are shown in Table 4. The NTRAI algorithm is better than other algorithms in approximating the optimal values for variables with minimum weight.

● Example. Nonconvex optimization problem ^[20]

Consider the following nonconvex nonlinear constrained optimization problem

The above problem possesses two strong local minima points $(1, 4)$ and $(6, 0.66667)$. Applying the NTRAI Algorithm 2.6 on this nonconvex problem, we have the local points $(1.0000001220725, 4)$ are obtained and the value of objective function is $-5.0000001220725.$

5.   Conclusions

This research focused on combining a nonmonotone technique with an autonomously modified trust-region radius to provide a more efficient hybrid of trust-region approaches for constrained optimization problems. The active-set strategy was combined with a penalty and Newton's interior point method to transform a nonlinearly constrained optimization problem into an identical unconstrained one. A nonmonotone trust region was used to ensure convergence from any starting point to the stationary point. A global convergence theory for the suggested method was developed based on certain assumptions. Well-known test problems (the CUTE collection) were used to evaluate the suggested method; three engineering design problems were performed, and the outcomes were compered with those of other reputable optimizers. The results showed that, compared with the other algorithms under discussion, the proposed method typically yields better approximation solutions and requires fewer iterations. Computational findings, which also examined the algorithm's performance, demonstrated the suggested algorithm's competitiveness and superiority over alternative optimization algorithms.

Several questions should be answered in future research:

● Improving the nonmonotone trust-region algorithm to be able to handle nondifferentiation-constrained optimization problems.

● Improving the nonmonotone trust-region algorithm to be able to handle large-scale constrained optimization problems.

● Utilize a secant approximation of the Hessian matrix to output a more effective algorithm.

Author contributions

Bothina Elsobky: conceived the study, developed the theoretical framework and performed the numerical experiments; Yousria Abo-Elnaga: conceived the study, supervised the application; Gehan Ashry: aided in the analysis. All authors have read and agreed to the published version of the manuscript.

Use of Generative-AI tools declaration

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

Acknowledgments

The authors are very grateful to the anonymous reviewers for their valuable and insightful comments, which have aided us in improving the quality of this paper.

Conflict of interest

The authors declare no conflicts of interest.