An area-type nonmonotone filter method for nonlinear constrained optimization

1.   Introduction

Currently, numerical methods for solving nonlinear optimization problems have been widely used in the military, transportation, engineering design, economic analysis, artificial intelligence and other fields. In this paper, we consider the constrained optimization problems, where the objective function and the nonlinear constraints are smooth. The numerical solution to the following problem is considered.

where $\mathcal{I} = \left\{1, 2, 3, \dots, m\right\}$. The real valued objective function $f(x):\mathbb{R} ^{n}\rightarrow \mathbb{R}$ and the inequality constants $c_{i}(x) = (c_{1}, c_{2}, \dots, c_{m})^{T}:\mathbb{R}^{n}\rightarrow \mathbb{R}^{m}$ are twice continuously differentiable.

In traditional optimization problems, the objective function and constraints are usually analytical models with deterministic parameters. The method of this paper is to solve the deterministic problem, but there are widely uncertain problems in practical problems. In fact, there are many optimization problems with uncertain information that have their own specific solutions for uncertain optimization problems, but eventually it all comes down to a deterministic method. Although the algorithm in this paper is for solving deterministic problems, it is still valid for uncertain problems. That is, the problem of uncertainty can also be applied to our algorithm. As we all know, there are two main approaches to uncertainty optimization, robust optimization (RO) ^[1,2] and reliability-based design optimization (RBDO) ^[3,4].

The common solutions to uncertain problems are probabilistic constraints and robust constraints methods. The robust constraint can be transformed into a semi-infinite problem by subjecting the uncertain set to certain inscriptions. The semi-infinite problem can be transformed into a finite problem in the form of (1.1) under discretization methods or other appropriate transformations. Probabilistic constraints can be transformed into deterministic optimization by replacing the objective function and nonlinear constraints with a Kriging model. The transformed deterministic optimization problem can be solved by the method in this paper. Therefore, the algorithm in this paper has some potential applications to the study of uncertain problems.

It is generally known that the sequential quadratic programming (SQP) method is one of the most effective methods to solve this problem. The SQP algorithm converts a complex nonlinear constrained optimization problem into a relatively simple quadratic programming problem (QP) solution. The objective function of a quadratic programming problem is quadratic, and the constraint function is linear. At the $k$th iterate, the search direction $d_{k}$ is obtained by the following QP subproblem.

where $B_{k} \in \mathbb{R} ^{n \times n}$ is an appropriate symmetric matrix of the the Hessian $\nabla^{2}f(x_{k}).$

Unlike the line search method, the trust-region method computes a trial step by solving a subproblem in which the model function is minimized in the trust-region. In general, the trust-region method is easier to establish global convergence than the line search method. In recent years, the trust region method has been widely used in constrained optimization ^[5,6,7,8], unconstrained optimization ^[9,10,11,12], nonlinear equations ^[13,14], least-squares problems ^[15,16] and other problems ^[17,18,19].

In order to ensure sufficient descent of sequential quadratic programming, a penalty function is introduced as a merit function to decide whether to accept test points. The estimation of penalty parameters may be difficult to choose. The filter method was proposed by Fletcher and Leyffer^[20], and its convergence was proved in ^[21]. It avoids the difficulty of updating the parameter in the penalty function. The filter method adopts the idea of multi-objective constraints, and it balances the relationship between objective function and constraint violation function. The poor trial points can be rejected in the filter method. The global convergence of the filter method can be guaranteed by taking any point as the starting point.

In the traditional filter method, a pair $(h_{k}, f_{k})$ is dominated by $(f_{j}, f_{j})$ if and only if $h_{k}\leqslant h_{j}$ and $f_{k} \leqslant f_{j}$ for each $j \neq k$. $h$ and $f$ are constraint violation and objective functions, respectively. A filter set $\mathcal{F}$ is a set of pairs $(h, f)$ such that no pair dominates any other pair. The trial point $x_{k}$ is accepted by the filter set if and only if

where $0 < \gamma < \beta < 1, \ $ and $h(x)$ and $f(x)$ are the constraint violation function and objective function. $\mathcal{F}$ represents the filter set. As the criteria are satisfied, the point is accepted by the current filter set. The filter technique has become important in recent years^{[22,23,24,25,26,27,28]}.

Su and Pu ^[29] proposed a nonmonotone method based on the traditional filter and obtained good numerical results for equality constrained optimization. Wang et al.^[30] proposed a nonmonotone adaptive filter method for unconstrained optimization and adopted an adaptive strategy to fix that step size and update the trust-region radius. Xue and Liu^[31] propose a multidimensional filter algorithm. The constraint is divided into several parts, and the filter structure is composed of them. The individual behavior of each part of the constraints is considered, but how to divide the constraints is still a difficult problem to be explored. ^[32] proposed an area-based filtering algorithm, but feasibility recovery was used in its algorithm. Although its convergence property was proved, no numerical calculation was performed to know the performance of its numerical results.

This paper presents an area-type filter algorithm based on the trust-region approach. The discriminant criterion is different from that of the traditional filter method and has the following advantages. 1) This paper proposes a relaxed trust-region quadratic correction subproblem by which the direction at the current point is calculated. The subproblem is guaranteed to be feasible. It avoids the feasibility recovery algorithm and makes the algorithm more efficient and concise. 2) In our algorithm, point pairs are divided into four partitions by the dominant region of the filter, and we calculate the contributions of the point pairs to the area of the filter separately. The area-type filter algorithm takes the contribution of the trial point to the area of the filter as the acceptance criterion. Our proposed algorithm no longer requires the notion of a "margin" around the filter, a device common to all theoretical approaches to filter methods so far. 3) Compared with traditional filter methods, the use of filter acceptance criteria in our new iteration is relaxed to allow rules that are dominated in some cases. 4) The approach is extended into monotone and nonmonotone methods. The nonmonotone method avoids the situation where the points fall into the "valley" and may be not convergent. In this paper, the numerical analysis is also performed for nonmonotone methods.

Our paper is organized as follows. An area-type nonmonotone filter algorithm for solving nonlinear programming problems is described in the second section. In the third section, the global convergence is established under some certain conditions. The preliminary numerical results of the algorithm are shown in the fourth section. Finally, the fifth section concludes this paper.

2.   An area-type nonmonotone filter algorithm

2.1.   The SQP step

The iterative approach of the algorithm in this paper is based on the Sequential Quadratic Programming (SQP) algorithm. In the trust-region method, the trial point $x_{k}+d_{k}$ of the next iteration is ensured to be within the trust-region centered at the point $x_{k}$. Thus, the traditional trust-region method can be used to solve the quadratic programming subproblem given by

where $\Delta_{k}$ is the trust-region radius. Su ^[7] proposes a convex problem to avoid the infeasibility of the trust-region subproblem.

where $\Delta_{k} > 0$, and

Based on this, we introduce a relaxation variable $\tau$ in the quadratic subproblem to simplify the objective function and control constraints.

The $\psi^{+}(x_{k}, \Delta_{k})$ can be represented as

As a matter of fact, the (QP) is always feasible, as $(d_k, \tau_{k}) = (0, 0)$. Thus, at the $k$th iteration, the solution $d_{k}$ of (QP) is used as the sequential quadratic programming step for the next iteration. So,

where $x_{k}^{+}$ is a new trial point.

2.2.   The area-type filter criterion

At the current $k$th iteration, the first step is to consider whether the trial point $x_{k}^{+}$ satisfies the trust-region condition.

The trust-region ratio is

The trial point is accepted when the trust-region ratio is close to $1$. As the ratio is close to $0$, to decide whether the trial points are acceptable or not, the filter technique is adopted in this paper. Define a constraint violation function as an infeasibility measure.

where

In the traditional filtering technique, a trial point is accepted if the objective function or the constraint violation function is decreasing compared to the result of the filter set. However, in this paper, we adopt an area-type filter.

An area-type filter is one in which the area dominated by the trial point is accepted, and then the point is accepted by the set of filters. Define

such that the pair $(\mathcal{H}, f)$ is dominated by the filter. See Figure 1.

In this paper, the constraint violation degree function and the objective function are put into the two-dimensional surface with $\mathcal{H}(x)\times f(x) \in[0, +\infty]\times [- \infty, + \infty].$ The plane is divided into four regions.

1) The upper left portion of the region, that not dominated by the filter $\mathcal{F}_{k}$.

2) The lower left portion of the region, that not dominated by the filter $\mathcal{F}_{k}$.

where $\mathcal{D}(\mathcal{F}_{k})^{C}$ is the complement of $\mathcal{D}(\mathcal{F}_{k})$.

3) The lower right portion of the region, that not dominated by the filter $\mathcal{F}_{k}$.

4) The region dominated by the filter.

See Figure 2 for the region division.

Next, we calculate the contribution $\mathcal{A}$ of the corresponding point pairs $(\mathcal{H}(x_{k}^{+}), f(x_{k}^{+}))$ to the area of the filter for each of the test points $x_{k}^{+}$, depending on the partition in which the trail point is located.

1) As the trial point $x_{k}^{+}$ is in the undominated upper left partition that is $(\mathcal{H}(x_{k}^{+}), f(x_{k}^{+})) \in \mathcal{R}_{1}(\mathcal{F}_{k})$,

where $\lambda$ is a positive constant.

2) As the trial point $x_{k}^{+}$ is in the undominated lower left partition, that is $(\mathcal{H}(x_{k}^{+}), f(x_{k}^{+})) \in \mathcal{R}_{2}(\mathcal{F}_{k})$,

3) As the trial point $x_{k}^{+}$ is in the undominated lower right partition, that is $(\mathcal{H}(x_{k}^{+}), f(x_{k}^{+})) \in \mathcal{R}_{3}(\mathcal{F}_{k})$,

4) As the trial point $x_{k}^{+}$ is in the dominated partition, that is $(\mathcal{H}(x_{k}^{+}), f(x_{k}^{+})) \in \mathcal{R}_{4}(\mathcal{F}_{k})$,

where

Figure 3 shows the contribution of the trial points in four different partitions, respectively, to the area of the filter $\mathcal{F}_{k}$. The contribution of the trial points in partitions $\mathcal{R}_{1}(\mathcal{F}_{k}), \mathcal{R}_{2}(\mathcal{F}_{k})$ and $\mathcal{R}_{3}(\mathcal{F}_{k})$ to the area of the filter is positive, while the contribution in partition $\mathcal{R}_{4}(\mathcal{F}_{k})$ is negative.

After obtaining the contribution of the trial point to the filter, it can be determined whether the point is accepted by the filter.

In this paper, we give two methods to determine whether the trial point is acceptable for the filter, the monotone method and the nonmonotone method, respectively. $x_{k}^{+}$ satisfies

that is, the acceptance criterion for the monotone method. $\lambda \in (0, 1)$ is a positive constant.

Define $J$ as a set of non-negative integers.

where the maximum value in the set $J$ is the number of updates of the filter, i.e. $j_{max}$.

Thus, the condition of the nonmonotone method is weaker than that of the monotone method

where $\lambda \in (0, 1)$, and

$\zeta \in \left[\zeta _{min}, \zeta _{max}\right], \zeta _{max} < 1.$ $\mathcal{A}_{j}$ is the contribution of the point to the filter at the $j$th successful iteration. $\mathcal{A}'(x_{k}, \mathcal{F}_{k})$ is the contribution of the updated points to the filter area, which is nonmonotone. $\mathcal{H}'(x_{k}, \mathcal{F}_{k})$ is the nonmonotone average of the constraint violation degree that corresponds to the point of $\mathcal{A}'(x_{k}, \mathcal{F}_{k})$. If (2.22) is satisfied, the point is accepted as a new iteration point even though it may be dominated by the filter. Meanwhile, the set $J$ and $\mathcal{F}$ need to be updated.

As (2.20) or (2.22) holds, the trial point is accepted, which means $x_{k+1} = x_{k}^{+}$.

Initialize the set of the filter at the beginning of the algorithm. Define $\mathcal{F}_{0} = \varnothing$. If $x_{k+1}$ is not dominated by the filter $x_{k+1} \in \mathcal{D}(\mathcal{F}_{k})^{C}$, that is, $x_{k}$ is in $\mathcal{R}_{1}(\mathcal{F}_{k}), \mathcal{R}_{2}(\mathcal{F}_{k})$ or $\mathcal{R}_{3}(\mathcal{F}_{k})$ partition, then

The other situation is that $x_{k+1}$ is dominated by the filter, $x_{k+1} \in \mathcal{D}(\mathcal{F}_{k})$. Thus, $x_{k+1}$ is in the $\mathcal{R}_{4}(\mathcal{F}_{k})$ partition.

Add a new iteration point to the filter, but remove the points that can dominate the new iteration points. See Figure 4.

For convenience, define

It is followed by the full statement of the algorithm.

Algorithm 1.

${\bf{Step\ 0}}$   Initialization. Given a start point $x_{0},$ an initial trust-region radius $\Delta _{0} \geqslant 0$ and a symmetric matrix $B_{0}$, choose constants $1 > \eta_{3} > \eta_{2} > 0, \eta_{1}\in (1, 2]$ and $\rho_{1}, \rho_{2}, \lambda, \zeta \in (0, 1)$. Let $\mathcal{F}_{0} = \left\{(\mathcal{H}_{0}, f_{0})\right\}$, $k = 0, j = 0.$

${\bf{Step\ 1}}$   Solve the modified subproblem (QP) to obtain $\tau_{k}$ and $d_{k}.$ ${\bf{Step\ 2}}$\ \ If $|\tau_{k}| \leqslant \epsilon,$ stop.

${\bf{Step\ 3}}$   Set $x_{k}^{+} = x_{k}+d_{k}$ and compute $\rho_{k}$ by (2.8).

${\bf{Step\ 4}}$   If $\rho_{k} \geqslant \rho_{1}$, go to Step 6.

If $\rho_{k} \leqslant \rho_{2}$, set $x_{k+1} = x_{k}, \Delta_{k+1} = \eta_{2}\Delta_{k}$ and $k = k+1.$ Go to Step 1.

Otherwise, determine the partition of the trial point $x_{k}^{+}$ and compute the contribution of the point to the area of the filter.

${\bf{Step\ 5}}$   If $x_{k}^{+}$ is not accepted by the filter $\mathcal{F}_{k}$, then set $x_{k+1} = x_{k}, \Delta_{k+1} = \eta_{3}\Delta_{k}$ and $k = k+1$. Go to Step 1. Otherwise, update the filter $\mathcal{F}_{k+1}, j = j+1$, and go to Step 6.

${\bf{Step\ 6}}$   Set $x_{k+1} = x_{k}^{+}, \Delta_{k+1} = \eta_{1}\Delta_{k}.$ Update $B_{k+1}$, $k = k+1$. Go to Step 1.

Remark 1. If the pair $(\mathcal{H}(x_{k}^{+}), f(x_{k}^{+}))$ of the trial point $x_{k}^{+}$ is on the boundary of the dominated region $\mathcal{D}(\mathcal{F}_{k})$, then the contribution of this point to the area of the filter is zero.

Remark 2. $j$ is the number of filter set updates.

3.   Convergent properties

Assumption 1. The objective function $f(x)$ and the inequality constraints $c_{i}(x), i \in \mathcal{I}$ are twice continuous and differentiable. $\nabla f(x)$ is Lipschitz continuous.

Then, there exists a positive constant $L$, such that

Assumption 2. Sequence $\left\{x_{k}\right\}$ is a compact convex subset of $\mathbb{R} ^{n}$, generated by Algorithm 1.

Assumption 3. The matrix sequence $\left\{B_{k}\right\}$ and sequence $\left\{d_{k}\right\}$ are uniformly bounded. That is, there exist positive constants $M_{1}, M_{2} > 0$, such that $\| B_{k} \|\leqslant M_{1}$ and $\| d_{k}\| \leqslant M_{2}$.

Assumption 4. The Mangasarian Fromovitz Constraint Qualification (MFCQ) holds at feasible point $x \in \mathbb{R} ^{n}$. There exists a vector $p$ such that $\{ d|\nabla c(x)^{T}p < 0 \}\neq \emptyset$.

Lemma 1.   Suppose that Assumptions 1 and 4 hold; the (QP) has an optimal solution.

Proof. First, we prove the feasible region of the (QP) is not an empty set. As $(d_{k}, \tau _{k}) = (0, 0)$, the constraints

hold. Therefore, the feasible region of the subproblem is not an empty set. For every possible solution to the modified (QP), we have $g_{k}^{T}d_{k} \leqslant \tau_{k}$. Thus,

Because $B_{k}$ is a positive symmetry, the objective function of the (QP) has a lower bound. Hence, there exists a constant $V \in (-\infty, +\infty),$ such that

where $X_{k}$ is the feasible region. From the Weierstrass theorem, there exists a subsequence $\left\{d_{k_{j}}, \tau _{k_{j}}\right\}$ such that

Since $j$ is sufficiently large, there is

According to the boundedness of $\left\{d_{k_{j}}\right\}_{j}$, $\left\{ \tau _{k_{j}} \right\}_{j}$, there exists a subset $J\subseteq \left[0, \infty \right)$,

The optimal solution is unique, because the (QP) is a convex programming problem.

Thus, the (QP) has an optimal solution.

Lemma 2. Suppose that Assumptions 1–4 hold, and $(d_{k}, \tau _{k})$ is the optimal solution to the (QP); then

(1) $(d_{k}, \tau _{k})$ is the Karush-Kuhn-Tucker (KKT) point of the (QP).

(2) $\tau _{k} = 0$ if and only if $d_{k} = 0$.

Proof. (1) If $(d_{k}, \tau _{k})$ is the optimal solution of (QP), and the constraints are linear functions, then $(d_{k}, \tau _{k})$ is the Karush-Kuhn-Tucker point of the modified quadratic problem.

(2) According to the assumptions, $(\tau_{k}, d_{k}) = (0, 0)$ is a feasible solution to the (QP). From hypothesis, we know that $(\tau_{k}, d_{k})$ is the optimal solution to the (QP). It means that $\tau _{k} +\frac{1}{2} d_{k}^{T} B_{k} d_{k} \leqslant 0$.

(i) If $\tau_{k} = 0$, then $\frac{1}{2} d_{k}^{T} B_{k} d_{k} \leqslant 0$. Because $B_{k}$ is a positive definite matrix, $d_{k} = 0$.

(ii) If $d_{k} = 0$, according to the positive quality of $B_{k}$, we have $\tau_{k}\leqslant 0$. By the constraint condition of the modified (QP), we have $\nabla f(x_{k})^{T}d_{k} \leqslant \tau_{k}$, and then $\tau_{k}\geqslant 0$. Therefore, $\tau_{k} = 0$.

The proof is completed.

$\tau _{k} = 0$ can serve as the termination condition of Algorithm 1 for the following lemma.

Lemma 3. Suppose that Assumptions hold, and $\tau _{k} = 0$ is the optimal solution of the modified (QP); then, $x_{k}$ is the (KKT) point of the problem (1.1).

Proof. From Lemmas 1 and 2, from $\tau _{k} = 0$, we get $d _{k} = 0$.

First we need to prove $\psi^{+}(x_{k}, \Delta_{k}) = 0$. Suppose $\psi^{+}(x_{k}, \Delta_{k}) > 0$, and there exists

Let

From Mangasarian-Fromovitz constraint qualification, there exits $d \in \mathbb{R} ^{n}$ and $\|d\| \leqslant \Delta_{k}$ such that

Thus,

that is,

So,

We have $0 \notin \left\{d:c_{i}(x_{k})+ \nabla c_{i}(x_{k})^{T} d_{k} \leqslant \psi^{+}(x_{k}, \Delta_{k}), \|d\|\leqslant \Delta_{k}, i \in \mathcal{I} \right\}$. This contradicts with $d_{k} = 0$. Hence, $\psi^{+}(x_{k}, \Delta_{k}) = 0$.

Next, we prove $u_{i} \neq 0$. According to (2.4), there exist Lagrange multipliers $U = (u_{1}, u_{2}, \ldots, u_{n})^{T}$, $V = (v_{1}, v_{2}, \ldots, v_{m})^{T}$, $W = (w_{1}, w_{2}, \ldots, w_{n})^{T}$ and $L = (l_{1}, l_{2}, \ldots, l_{n})^{T}$, such that

where $e = (1, 1, \cdots, 1)_{n \times 1}^{T}$.

With $\tau_{k} = 0$ and $d_{k} = 0$, the KKT condition of the (QP) can be reworded as

From the above, we have $\sum_{i = 1}^{n} u_{i} = 1$. Thus, $u_{i} \neq 0$. By the KKT condition, we have $W = L = 0$. Let

The KKT condition of the problem (1.1) is

Thus, there exist Lagrange multipliers $\lambda \in \mathbb{R} ^{n}$, $\lambda _{i} = \frac{v_{i}}{u_{i}}, \sum_{i = 1}^{n} u_{i} = 1$ and $W = L = 0$ such that $x_{k}$ is a KKT point of the inequality constraint problem (1.1).

Lemma 4. Suppose that Assumptions 1-4 hold, and then for all $k$, we have

Proof. From Lemma 1, the subproblem is always feasible. So, $\nabla f(x_{k})^{T}d_{k} \leqslant \tau_{k}$ and $\tau_{k} \geqslant 0$.

According to Taylor's theorem, we obtain

The proof is completed.

${x_{k}}$ is generated by Algorithm 1. We consider that there exists a constant $\epsilon > 0$, such that $\|\nabla f(x_{k})\| > \epsilon$. Then, for every $k$, $x_{k+1}$ is a successful iteration point.

Lemma 5. Suppose that Assumptions hold. Then, the inner loop of the Algorithm 1 terminates finitely.

Proof. There are two inner loops in the algorithm, but their proofs are the same, as follows. Assume that the algorithm does not terminate at finite iterations. That is, in $k$th, $x_{k+1}$ is not the successful iteration point.

From Algorithm 1, we get $\rho_{k} < \rho_{1}, \Delta_{k}\rightarrow 0$ and $d_{k}\rightarrow 0.$

From the last lemma,

We obtain

This means $\rho_{k} \geqslant \rho_{1}$, which contradicts $\rho_{k} < \rho_{1}.$

Thus the inner loop of Algorithm 1 terminates at a finite number of iterations.

Lemma 6. Suppose that Assumptions hold. In the iteration, for each $k$,

Proof. The proof is similar to Lemma 3.3 in Gould et al. ^[32].

Lemma 7. Suppose that Assumptions hold, and the filter set is updated infinitely. That is, $|\mathcal{U}| = + \infty$. Then, there exists a subsequence $\left\{k_{j}\right\}$ such that

Proof. Suppose that there exists an infinite subsequence $k_{i} \subseteq \mathcal{U}$ such that $\mathcal{H}(x_{k_{i}}) \geqslant \epsilon$ for $\epsilon > 0.$ According to Lemma 6, we deduce that

From Assumptions 1 and 2 can be directly derived that, for all k,

and

for some constants $f^{min} \leqslant f^{max}$ and $0 \leqslant \mathcal{H}^{max}$. This means that the domain of the $(f, \mathcal{H})-$points is $\left[f^{min}, f^{max}\right]\times \left[0, \mathcal{H}^{max}\right].$

Hence, for any $k$, $area\left(\mathcal{D}\left(\mathcal{F}_{k_{i}+1}\right) \right)$ is bounded above by a constant $\sigma^{max} \geqslant 0$ independent of $k$. Thus, we have

Therefore, $i$ is finite. This contradicts that the subsequence $k_{i}$ is infinite.

So, the conclusion is valid.

Lemma 8. Suppose that Assumptions hold, and the filter is updated finitely. This means that $|\mathcal{U}| < \infty.$ Then, $\mathcal{H}(x_{k}) = 0.$

Proof. According to the termination condition of Algorithm 1, if the algorithm is finitely terminated, we obtain $\tau_{k} = 0$ and $d_{k} = 0$. Thus, $\mathcal{H}(x_{k}) = 0$. The proof is completed.

Theorem 1. Suppose that Assumptions hold, and sequence $\left\{x_{k}\right\}$ is obtained by Algorithm 1. There exists a subsequence $\left\{x_{k_{j}}\right\}$ and

The cluster point $x^*$ is the KKT point for the problem (1.1).

Proof. It is easy to prove by the above hypothesis and lemma.

4.   Numerical results

We have implemented the preliminary numerical result of the Algorithm 1 in Matlab R2020a. All experiments are run on a laptop with Intel(R) Core(TM) i7-10510U CPU @ 1.80GHz 2.30 GHz and 16GB RAM. The performance of our area-type filter method is compared with other methods for solving nonlinear programming problems. SNOPT is an SQP algorithm that uses a smooth augmented Lagrangian merit function^[33]. IPOPT is an interior-point filter line-search algorithm for nonlinear programming^[34]. In this paper, the monotone and the nonmonotone area-type methods are denoted by Monotone and Nonmonotone, respectively.

The following values are exploited: $B_{0} = I \in R^{n}\times R^{ n}, \rho_{1} = 0.75, \rho_{2} = 0.01, \lambda = 0.0001, \eta_{1} = 2, \eta_{2} = 0.1, \eta_{3} = 0.5$and $\zeta = 0.85.$ In addition, $B_{k+1}$ is updated by the BFGS formula ^[35]:

where

and

$\epsilon = 10^{-4}$ is the convergence tolerance of the algorithm.

The test problems are from ^[36,37]. In Table 1, the number of iterations calculated by monotone and nonmonotone area-type filter algorithms are compared with the traditional filter method (FILTER)^[20], SNOPT and IPOPT. n, m are the numbers of problem variables and general constraints. NIT represents the number of iterations to solve the nonlinear programming problem.

For simplicity of comparison, we have compared the efficiency of the number of iterations in Figure 5 by using the performance profile^[38]. Define the performance profile by

where

$NIT_{p, s}$ means the number of iterations calculated by solver S for problem P. $\underset{ s \in S}{\min} NIT_{p, s}$ means the minimum of the number of iterations to solve problem P for all solvers compared.

When the solver S cannot solve the problem P, the ratio R goes to infinity. If $T \rightarrow \infty$, $\varTheta _{s}(T)$ is the percentage of the number of problems that can be solved by solver S. The performance of the considered algorithm is best in the range of the optimal T.

Next, the different results of monotone and nonmonotone are taken to have a comparison in detail. The number of iterations, CPU runtime and optimal values are compared, and the corresponding results are shown in Table 2.

As shown in Table 1 and Figure 5, most of the area-type filter algorithm is better than FILTER, SNOPT, and IPOPT. Our algorithm usually requires a small number of iterations. As a whole, our algorithm can be applied to this problem generally. There are slightly worse cases for individual problems. However, on the scale of the problem, it can be negligible. In most of the problems, Algorithm 1 requires fewer iterations, such as HS17, HS18, HS33, HS49 and so on. As for HS10, HS13, HS31, HS39 and HS46, the traditional filter method can not obtain the optimal solution as the subproblem is infeasible, but this paper can avoid this problem. Moreover, Algorithm 1 is a good solver. It can be observed from Table 2 that the monotone method is slightly better than the nonmonotone method in terms of both the number of iterations and CPU time. The nonmonotone method avoids the situation where the points fall into the "valley" and cannot get out, making the algorithm more efficient. As can be seen from the above table, our algorithm outperforms the traditional filter method for most problems. The result indicates the use of the area-type filter method provides a fast, convergent mechanism that reduces the number of iterations.

5.   Conclusions

In this paper, a new area-type filter algorithm is proposed based on the trust-region method. A relaxed trust-region quadratic correction subproblem is proposed to compute the direction. The subproblem is guaranteed to be feasible. It avoids the feasibility recovery phase and makes the algorithm more efficient and concise. The discriminant criterion is different from that of the traditional filter method. The point pairs are divided into four partitions by the dominant region of the filter. The area-type filter algorithm takes the contribution of the trial point to the area of the filter as the acceptance criterion. The criterion is extended into monotone and nonmonotone methods. Both of them are compared, and better numerical results are obtained. The global convergence of the area-type filter method is also demonstrated. This algorithm can reduce the computational effort to a certain extent, as shown in the numerical results.

Acknowledgments

This research is supported by the National Natural Science Foundation of China (No. 61572011) and the Natural Science Foundation of Hebei Province (No. A2022201002).

Conflict of interest

All authors disclosed no relevant relationships.