# An Improved Nonmonotone Filter Trust Region Method for Equality Constrained Optimization

Authors: Zhong Jin
Journal: Abstract and Applied Analysis
 (2013)

---

## Abstract

Motivated by the method of Su and Pu (2009), we present an improved nonmonotone filter trust region algorithm for solving nonlinear equality constrained optimization. In our algorithm a modified nonmonotone filter technique is proposed and the restoration phase is not needed. At every iteration, in common with the composite-step SQP methods, the step is viewed as the sum of two distinct components, a quasinormal step and a tangential step. A more relaxed accepted condition for trial step is given and a crucial
criterion is weakened. Under some suitable conditions, the global convergence is established. In the end, numerical results show our method is effective.


---

## Body

## 1. Introduction

We consider the problem of minimizing a nonlinear function subject to a set of nonlinear equality constraints as follows:(1)(P)minf(x)s.t.ci(x)=0,i∈I={1,2,…,m},
where the objective function f:Rn→R and the equality constraints ci(i∈I):Rn→R are all twice continuously differentiable.The algorithm that we discuss belongs to the class of trust region methods and, more specifically, to that filter methods suggested first by Fletcher and Leyffer [1], in which the use of a penalty function, a common feature of the large majority of the algorithms for constrained optimization, is replaced by the technique so-called “filter.” Subsequently, global convergences of the trust region filter SQP methods were established by Fletcher et al. [2, 3], and Ulbrich [4] got its superlinear local convergence. Especially, the step framework in [3] is similar in spirit to the composite-step SQP methods pioneered by Vardi [5], Byrd et al. [6], and Omojokun [7]. Consequently, filter method has been actually applied in many optimization techniques, for instance, the pattern search method [8], the SLP method [9], the interior method [10], the bundle approaches [11, 12], the system of nonlinear equations and nonlinear least squares [13], multidimensional filter method [14], line search filter methods [15, 16], and so on.In fact, filter method exhibits a certain degree of nonmonotonicity. The idea of nonmonotone technique can be traced back to Grippo et al. [17] in 1986, combined with the line search strategy. Due to its excellent numerical exhibition, over the last decades, the nonmonotone technique has been used in trust region method to deal with unconstrained and constrained optimization problems [18–25]. More recently, the nonmonotone trust region method without penalty function has also been developed for constrained optimization [26–29]. Especially, in [29] the nonmonotone idea is employed to the filter technique and restoration phase, a common feature of the large majority of filter methods, is not needed.Based on [29], motivated by above ideas and methods, in this paper we present an improved filter algorithm that combines the nonmonotone and trust region techniques for solving nonlinear equality constrained optimization. Our method improves previous results and gives a more flexible mechanism, weakens some needed conditions, and has the merits as follows.(i)
An improved nonnomotone filter technique is presented. Filter technique is viewed as a biobjective optimization problem that minimizes objective functionf and violation function h. In [29], the same nonmonotone measure is utilized for both f and h at the kth iteration. In the paper we improve it and define a new measure for h, which may make the discussion and consideration of the nonmonotone properties of f and h more freely.(ii)
The restoration phase is not needed. The restoration procedure has to be considered in most of filter methods. We employ the nonmonotone idea to the filter technique, so as [29] the restoration phase is not needed.(iii)
A more relaxed accepted condition for trial step is considered. Compared to general trust region methods, in [29] the condition for the accepted trial step is relaxed. In the paper we improve it and then the accepted condition for trial step is more relaxed.(iv)
A crucial criterion is weakened in the algorithm. By introducing a new parameterη∈(0,1], we improve the crucial criterion for implementation of the method in [29]. It is obvious that our criterion becomes same with [29] if η=1, but new criterion can be easier to satisfy, so this crucial criterion has been weakened when setting η<1 in the initialization of our algorithm.The presentation is organized as follows. Section2 introduces some preliminary results and improvements on filter technique and some conditions. Section 3 develops a modified nonmonotone filter trust region algorithm, whose global convergence is shown in Section 4. The results of numerical experience with the proposed method are discussed in the last section.


## 2. Preliminary and Improvements

In this section, we first recall some definitions and preliminary results about the techniques of composite-step SQP type trust region method and fraction of Cauchy decrease condition. And then the improvements on filter technique and some conditions are given.


### 2.1. Fraction of Cauchy Decrease Condition

To introduce the corresponding results, we consider the unconstrained optimization problem:min{f(x)∣x∈Rn}, where f:Rn→R is continuously differentiable. At iteration point xk, it obtains a trial step dk by solving the following quadratic program subproblem:
(2)minq(d)=∇f(xk)d+12dTHkds.t.∥d∥≤Δk,
where Hk is a symmetric matrix which is either the Hessian matrix of f at xk or an approximation to it, and Δk>0 is a trust region radius.To assure the global convergence, the step is only required to satisfy a fraction of Cauchy decrease condition. It meansd must predict via the quadratic model function q(d) at least as much as a fraction of the decreased given by the Cauchy step on q(d), that is, there exists a constant σ>0 fixed across all iterations, such that
(3)q(0)-q(d)≥σ(q(0)-q(dcp)),
where dcp is the steepest descent step for q(d) inside the trust region. And we have the following lemma.Lemma 1.
If the trial stepd satisfies a fraction of Cauchy decrease condition, then
(4)q(0)-q(d)≥σ2∥∇f(x)∥min{Δ,∥∇f(x)∥∥H∥}.Proof.
See Powell [30] for the proof.


### 2.2.    The Subproblems of Composite-Step SQP Type Trust Region Method

In the composite-step SQP type trust region methods, at current iteratexk we obtain the trial step dk=dkn+dkt by computing a quasi-normal step dkn and a tangential step dkt. The purpose of the quasi-normal step dkn is to improve feasibility and dkt in the tangential space of the linearized constraints can provide sufficient decrease for a quadratic model of the objective function f(x) to improve optimality.For problem (P), dkn is the solution to the subproblem
(5)min12∥ck+AkTdn∥2s.t.∥dn∥≤Δk,
where Δk is a trust region radius,
(6)c(x)=(c1(x)c2(x)⋮cm(x)),A(x)=∇c(x), ck=c(xk) and Ak=A(xk)∈Rn×m. In order to improve the value of the objective function, dkt can be obtained by the following subproblem
(7)minqk(dkn+dt)s.t.AkTdt=0∥dt∥≤Δk,
where qk(d)=gkTd+(1/2)dTHkd and gk=∇f(xk). Then we get the current trial step dk=dkn+dkt.In usual ways that impose a trust region in step-decomposition methods, the quasi-normal stepdkn and the tangential step dkt are required to satisfy
(8)∥dn∥≤0.8Δk,∥dkn+dt∥≤Δk.
Here, to simplify the proof, we only impose a trust region on ∥dn∥≤Δk and ∥dt∥≤Δk, which is natural.


### 2.3.    The Improved Accepted Condition fordk

Borrowed from the usual trust region idea, we also need to define the following predicted reduction for the violation functionh(x)=∥c(x)∥2(9)predkc=h(xk)-∥ck+AkTdkn∥2
and the actual reduction
(10)aredkc=h(xk)-h(xk+dk)=∥ck∥2-∥c(xk+dk)∥2.To evaluate the descent properties of the step for the objective function, we use the predicted reduction off(x)(11)predkf=qk(0)-qk(dk)=-qk(dk)
and the actual reduction of f(x)(12)aredkf=f(xk)-f(xk+dk).In general trust region method, the stepdk will be accepted if
(13)aredkf≥ρpredkf,
where ρ∈(0,1) is a fixed constant.In [29], considering nonmonotone technique, the condition (13) is replaced by
(14)raredkf≥ρpredkf,
where raredkf is the relaxed actual reduction of f(x),  that is,
(15)raredkf=max{f(xk),∑r=0m(k)-1λkrf(xk-r)}-f(xk+dk).But in this paper, we consider more relaxed accepted condition by increasingaredkf to raredkf and reducing predkf to min{predkf,predkc+ξ0} simultaneously, then the condition (14) is replaced by
(16)raredkf≥ρmin{predkf,predkc+ξ0},
where ξ0 is a small positive number.


### 2.4.    The Improved Nonmonotone Filter Technique

In order to obtain next iterate, it needs to determine the step; this procedure that decides which trial step is accepted is “filter method.” For the optimization problem with equality constraints(17)min{f(x)∣c(x)=0},
a promising trial step should either reduce the constraint violation h or the objective function value f. Since h(x)=∥c(x)∥2, it is easy to see that h(x)=0 if and only if x is a feasible point. So in the traditional filter method, a point x is called acceptance to the filter if and only if
(18)h(x)≤βhjorf(x)≤fj-γhj∀(hj,fj)∈ℱ,
where 0<γ<β<1,    ℱ denotes the filter set.Different from above criteria of filter idea, with nonmonotone technique, in [29] a point x is called to be acceptable to the filter if and only if
(19)eitherh(x)≤βmax0≤r≤m(k)-1hk-rorf(x)≤max[fk,∑r=0m(k)-1λkrfk-r]-γh(x),
where (hk-r,fk-r)∈ℱk for 0≤r≤m(k)-1, and 1≤m(k)≤min{m(k-1)+1,M},  M≥1 is a given positive integer, ∑r=0m(k)-1λkr=1,λkr∈(0,1), and there exists a positive constant λ such that λkr≥λ.Observe thatm(k) is used in both conditions (19), while in this paper we wish to reduce the relationship of the nonmonotone properties of f and h. We consider the nonmonotone properties of f and h, respectively, and call a trial point x is acceptable to the filter if and only if
(20)eitherh(x)≤βmax0≤j≤m(p)-1θM+p-jorf(x)≤max[fk,∑r=0m(k)-1λkrfk-r]-γh(x),
where θM+p-j comes from {θi}i=1+∞ such that θ1=θ2=⋯=θM-1=0 and {θi}i=M+∞ is a subsequence of {h(xk)}, and 1≤m(p)≤min{m(p-1)+1,M}.Similar to the traditional filter methods, if (20) is satisfied, it is called an h-type iteration and the filter set ℱk needs to be updated at each successful h-type iteration.


### 2.5. The Weakened Criterion for Implementation of Algorithm

We replace the crucial criterionpredkf≥predkc in [29] by
(21)predkfpredkc≥η,
where η∈(0,1]. It is obvious that this new criterion becomes the same with [29] if η=1, but it can be easier to satisfy, so the criterion has been weakened when setting η<1 in the initialization of our algorithm.


## 2.1. Fraction of Cauchy Decrease Condition

To introduce the corresponding results, we consider the unconstrained optimization problem:min{f(x)∣x∈Rn}, where f:Rn→R is continuously differentiable. At iteration point xk, it obtains a trial step dk by solving the following quadratic program subproblem:
(2)minq(d)=∇f(xk)d+12dTHkds.t.∥d∥≤Δk,
where Hk is a symmetric matrix which is either the Hessian matrix of f at xk or an approximation to it, and Δk>0 is a trust region radius.To assure the global convergence, the step is only required to satisfy a fraction of Cauchy decrease condition. It meansd must predict via the quadratic model function q(d) at least as much as a fraction of the decreased given by the Cauchy step on q(d), that is, there exists a constant σ>0 fixed across all iterations, such that
(3)q(0)-q(d)≥σ(q(0)-q(dcp)),
where dcp is the steepest descent step for q(d) inside the trust region. And we have the following lemma.Lemma 1.
If the trial stepd satisfies a fraction of Cauchy decrease condition, then
(4)q(0)-q(d)≥σ2∥∇f(x)∥min{Δ,∥∇f(x)∥∥H∥}.Proof.
See Powell [30] for the proof.


## 2.2.    The Subproblems of Composite-Step SQP Type Trust Region Method

In the composite-step SQP type trust region methods, at current iteratexk we obtain the trial step dk=dkn+dkt by computing a quasi-normal step dkn and a tangential step dkt. The purpose of the quasi-normal step dkn is to improve feasibility and dkt in the tangential space of the linearized constraints can provide sufficient decrease for a quadratic model of the objective function f(x) to improve optimality.For problem (P), dkn is the solution to the subproblem
(5)min12∥ck+AkTdn∥2s.t.∥dn∥≤Δk,
where Δk is a trust region radius,
(6)c(x)=(c1(x)c2(x)⋮cm(x)),A(x)=∇c(x), ck=c(xk) and Ak=A(xk)∈Rn×m. In order to improve the value of the objective function, dkt can be obtained by the following subproblem
(7)minqk(dkn+dt)s.t.AkTdt=0∥dt∥≤Δk,
where qk(d)=gkTd+(1/2)dTHkd and gk=∇f(xk). Then we get the current trial step dk=dkn+dkt.In usual ways that impose a trust region in step-decomposition methods, the quasi-normal stepdkn and the tangential step dkt are required to satisfy
(8)∥dn∥≤0.8Δk,∥dkn+dt∥≤Δk.
Here, to simplify the proof, we only impose a trust region on ∥dn∥≤Δk and ∥dt∥≤Δk, which is natural.


## 2.3.    The Improved Accepted Condition fordk

Borrowed from the usual trust region idea, we also need to define the following predicted reduction for the violation functionh(x)=∥c(x)∥2(9)predkc=h(xk)-∥ck+AkTdkn∥2
and the actual reduction
(10)aredkc=h(xk)-h(xk+dk)=∥ck∥2-∥c(xk+dk)∥2.To evaluate the descent properties of the step for the objective function, we use the predicted reduction off(x)(11)predkf=qk(0)-qk(dk)=-qk(dk)
and the actual reduction of f(x)(12)aredkf=f(xk)-f(xk+dk).In general trust region method, the stepdk will be accepted if
(13)aredkf≥ρpredkf,
where ρ∈(0,1) is a fixed constant.In [29], considering nonmonotone technique, the condition (13) is replaced by
(14)raredkf≥ρpredkf,
where raredkf is the relaxed actual reduction of f(x),  that is,
(15)raredkf=max{f(xk),∑r=0m(k)-1λkrf(xk-r)}-f(xk+dk).But in this paper, we consider more relaxed accepted condition by increasingaredkf to raredkf and reducing predkf to min{predkf,predkc+ξ0} simultaneously, then the condition (14) is replaced by
(16)raredkf≥ρmin{predkf,predkc+ξ0},
where ξ0 is a small positive number.


## 2.4.    The Improved Nonmonotone Filter Technique

In order to obtain next iterate, it needs to determine the step; this procedure that decides which trial step is accepted is “filter method.” For the optimization problem with equality constraints(17)min{f(x)∣c(x)=0},
a promising trial step should either reduce the constraint violation h or the objective function value f. Since h(x)=∥c(x)∥2, it is easy to see that h(x)=0 if and only if x is a feasible point. So in the traditional filter method, a point x is called acceptance to the filter if and only if
(18)h(x)≤βhjorf(x)≤fj-γhj∀(hj,fj)∈ℱ,
where 0<γ<β<1,    ℱ denotes the filter set.Different from above criteria of filter idea, with nonmonotone technique, in [29] a point x is called to be acceptable to the filter if and only if
(19)eitherh(x)≤βmax0≤r≤m(k)-1hk-rorf(x)≤max[fk,∑r=0m(k)-1λkrfk-r]-γh(x),
where (hk-r,fk-r)∈ℱk for 0≤r≤m(k)-1, and 1≤m(k)≤min{m(k-1)+1,M},  M≥1 is a given positive integer, ∑r=0m(k)-1λkr=1,λkr∈(0,1), and there exists a positive constant λ such that λkr≥λ.Observe thatm(k) is used in both conditions (19), while in this paper we wish to reduce the relationship of the nonmonotone properties of f and h. We consider the nonmonotone properties of f and h, respectively, and call a trial point x is acceptable to the filter if and only if
(20)eitherh(x)≤βmax0≤j≤m(p)-1θM+p-jorf(x)≤max[fk,∑r=0m(k)-1λkrfk-r]-γh(x),
where θM+p-j comes from {θi}i=1+∞ such that θ1=θ2=⋯=θM-1=0 and {θi}i=M+∞ is a subsequence of {h(xk)}, and 1≤m(p)≤min{m(p-1)+1,M}.Similar to the traditional filter methods, if (20) is satisfied, it is called an h-type iteration and the filter set ℱk needs to be updated at each successful h-type iteration.


## 2.5. The Weakened Criterion for Implementation of Algorithm

We replace the crucial criterionpredkf≥predkc in [29] by
(21)predkfpredkc≥η,
where η∈(0,1]. It is obvious that this new criterion becomes the same with [29] if η=1, but it can be easier to satisfy, so the criterion has been weakened when setting η<1 in the initialization of our algorithm.


## 3. Description of the Algorithm

It will be convenient to introduce the reduced gradientg^(x)=W(x)Tg(x) where g(x)=∇f(x) and W(x) denotes a matrix whose columns are from a basis of the null space of A(x)T. The first order necessary optimality conditions (Karush-Kuhn-Tucher or KKT conditions) at a local solution x-∈Rn of (P) can be written as
(22)c(x-)=0,g^(x-)=0.For brevity, at the current iteratexk, we use gk, ck, Ak, fk, hk, Wk, Hk to denote ∇f(xk), c(xk), A(xk), f(xk), h(xk), W(xk), H(xk). We are now in a position to present a formal statement of our algorithm.Algorithm 2.
Step  0. Initialization: choose an initial guess x0, a symmetric matrix H0∈Rn×n, an initial region radius Δ0≥Δmin>0,  0<γ<β<1,  0<λ≤1 and ℱ0={(h0,f0)}. Set η∈(0,1],  ξ0>0,  0<ρ<1,  0<γ0<γ1<1<γ2 and M>0. Let m(0)=1,  θ1=θ2=⋯=θM-1=0, θM=h(x0), p=0 and k=0.
Step  1. Compute fk, gk, ck, hk, Ak, Wk. If ∥g^k∥+hk=0, then stop.
Step  2. Compute (5) and (7) to obtain dkn and dkt, and set dk=dkn+dkt.
Step  3. If xk+dk is acceptable to the filter, go to Step 4, otherwise go to Step 5.
Step  4. If raredkf<ρmin{predkf,predkc+ξ0} and predkf/predkc≥η, then go to Step 5, otherwise go to Step 6.
Step  5.
Δ
k
∈
[
γ
0
Δ
k
,
γ
1
Δ
k
], go to Step 2.
Step  6.
x
k
+
1
=
x
k
+
d
k, Δk+1∈[Δk,γ2Δk]≥Δmin. Update Hk to Hk+1, m(k+1)=min{m(k)+1,M}. If (20) holds, update the filter set; let θM+p+1=h(xk+1),    m(p+1)=min{m(p)+1,M} and p=p+1. Let k=k+1 and go to Step 1.Remark 3.
At the beginning of each iteration, we always setΔk≥Δmin, which will avoid too small trust region radius.Remark 4.
Ifh-type iteration is satisfied, then θM+p+1 is generated, so if the number of h-type iterations is infinite, we obtain a sequence {θi}i=1+∞ such that θ1=θ2=⋯=θM-1=0 and {θi}i=M+∞ is a subsequence of {h(xk)}. Specially, (20) always holds on the whole obtained sequence {θi}i=1+∞.Remark 5.
In the above algorithm, letM be a positive integer. For each k, let m(k) satisfying
(23)m(0)=1,1≤m(k)≤min{m(k-1)+1,M},fork≥1,
and we also find m(p) satisfy
(24)m(0)=1,1≤m(p)≤min{m(p-1)+1,M},forp≥1,
so the nonmonotonicity is showed as M>1.


## 4. Global Convergence of Algorithm

In this section, we will prove the global convergence properties of Algorithm2 under the following assumptions.(A1)
The objectivef(x) and the constraint functions ci(x), i=1,2,…m are all twice continuously differentiable on an open set containing X.(A2)
All pointsxk that are sampled by algorithm lie in a nonempty closed and bounded set X.(A3)
The matrix sequence{Hk} is uniformly bounded.(A4)
A(x)=∇c(x), (AT(x)A(x))-1, W(x) and (WT(x)W(x))-1 are uniformly bounded on X.From the above assumptions, it is easier to suppose that there exist five constantsv1,v2,v3,v4,v5 such that ∥f(x)∥≤v1,  ∥∇f(x)∥≤v1,  ∥∇2f(x)∥≤v1,  ∥c(x)∥≤v2, ∥A(x)∥≤v2,  ∥∇2c(x)∥≤v2,  ∥(AT(x)A(x))-1∥≤v3,  ∥W(x)∥≤v4,  ∥WT(x)H(x)∥≤v5; this can make our following results convenient to prove.Lemma 6.
At the current iteratexk, let the trial point component dkn actually be normal to the tangential space. Under the above assumptions, there exists a constant α1>0 independent of the iterates such that
(25)∥dkn∥≤α1∥ck∥.Proof.
Sincedkn is actually normal to the tangential space, it follows that
(26)∥dkn∥=∥Ak(AkTAk)-1AkTdk∥=∥Ak(AkTAk)-1(ck+AkTdk-ck)∥=∥Ak(AkTAk)-1∥+(∥ck+AkTdk∥+∥ck∥),
together with the fact that ∥ck+AkTdk∥≤∥ck∥, we have
(27)∥dkn∥≤2∥Ak(AkTAk)-1∥∥ck∥≜α1∥ck∥.Lemma 7.
Suppose that the assumptions hold, there exist positiveα2, α3 independent of the iterates such that
(28)∥ck∥2-∥ck+AkTdk∥2≥α2∥ck∥min{∥ck∥,Δk},(29)qk(dkn)-qk(dk)≥α3∥WkT∇qk(dkn)∥min{∥WkT∇qk(dkn)∥,Δk}.Proof.
The statement is established by an application of Lemma1 to two subproblems (5) and (7).Lemma 8.
Under problem assumptions, Algorithm2 is well defined.Proof.
We will show that there existsδ>0 such that step dk is accepted whenever Δk≤δ. In fact,
(30)|aredkf-predkf|=∥f(xk)-f(xk+dk)+gkTdk+12dkTHkdk∥=∥-gkTdk-12dkT∇2f(yk)dk+gkTdk+12dkTHkdk∥=4nΔk212∥∇2f(yk)-Hk∥≤4nΔk2b,
where yk=xk+ξdk, ξ∈(0,1) denotes some point on the line segment from xk to xk+dk, b=(1/2)(sup∥Hk∥+maxx∈S∥∇2f(x)∥), ∥dkt∥≤nΔk, ∥dkn∥≤nΔk and ∥dk∥≤2nΔk. We consider two cases in the following.
Case  1  (h(xk)≠0). To prove the implementation of Algorithm 2, we need only to show that if predkf/predkc≥η>0, it follows raredkf≥ρmin{predkf,predkc+ξ0}. Without loss of generality, we can assume that ∥ck∥≥ϵ. Then we start with δ∈(0,ϵ] such that the closed δ-ball about xk lies in S. It is obvious from δ≤ϵ that Δk≤δ≤ϵ. And from (28), we have predkc≥α2ϵΔk. Observe that
(31)|aredkf-predkfpredkf|·|predkfpredkc|=|aredkf-predkfpredkc|≤4nΔk2bα2ϵΔk→0asΔk→0,predkfpredkc≥η>0.
Hence we have
(32)|aredkf-predkfpredkf|→0asΔk→0,
which implies aredkf≥ρpredkf≥0, then raredkf≥aredkf≥ρpredkf≥ρmin{predkf,predkc+ξ0} for some ρ∈(0,1).
Case  2  (h(xk)=0). If ∥g^k∥=0, then xk is a KKT-point of (1) by Algorithm 2. Thus, we assume that there exists a constant ϵ such that ∥g^k∥≥ϵ. Then
(33)∥WkT∇qk(dkn)∥=∥WkT(gk+Hkdkn)∥≥∥WkTgk∥-∥WkTHkdkn∥≥ϵ-υ5Δk.
Next, if we reduce δ such that δ≤(1/2υ5)ϵ, then for all Δk≤δ, we have Δk≤(1/2υ5)ϵ. Therefore
(34)∥WkT∇qk(dkn)∥≥ϵ2.
And it holds from h(xk)=0 that dkn=0, then, combining with (29), we find that
(35)predkf=-qk(dk)≥α2ϵmin{ϵ2,Δk}=α2ϵΔk.
Hence,
(36)|aredkf-predkfpredkf|≤4nΔk2b(α/2)ϵΔk→0asΔk→0,
which also implies raredkf≥aredkf≥ρpredkf≥ρmin{predkf,predkc+ξ0} for some ρ∈(0,1). Thus, the trial step is accepted for all Δk≤δ.Lemma8 has provided the implementation of Algorithm 2. By mechanism of Algorithm 2, it is obvious that there exists a constant Δ->0, such that Δk≥Δ- for sufficiently large k.In the remainder of this paper we denote the set of indices of those iterations in which the filter has been augmented by𝒜, that is to say, if the kth iteration is h-type iteration, we have k+1∈𝒜. By this definition, if (20) holds for infinite iterations, then |𝒜|=∞; otherwise, we can say |𝒜|≠∞.Lemma 9.
Let{xk} be an infinite sequence generated by Algorithm 2. If |𝒜|≠∞, then limk→∞h(xk)=0.Proof.
By mechanism of Algorithm2, we can assume that for all k, it follows
(37)f(xk+1)≤max{f(xk),∑r=0m(k)-1λkrf(xk-r)}-γh(xk).
Then we first show that for all k, it holds
(38)f(xk)≤f(x0)-λγ∑r=0k-2h(xr)-γh(xk-1)≤f(x0)-λγ∑r=0k-1h(xr).
Next we prove (38) by induction.
Ifk=1, we have f(x1)≤f(x0)-γh(x0)≤f(x0)-λγh(x0).
Assume that (38) holds for 1,2,…,k, then we consider that (38) holds for k+1 in the following two cases.
Case  1. If max{f(xk),∑r=0m(k)-1λkrf(xk-r)}=f(xk), then
(39)f(xk+1)≤f(xk)-γh(xk)≤f(x0)-λγ∑r=0k-1h(xr)-γh(xk)≤f(x0)-λγ∑r=0kh(xr).
Case  2. If max{f(xk),∑r=0m(k)-1λkrf(xk-r)}=∑r=0m(k)-1‍λkrf(xk-r), let q=m(k)-1, then
(40)f(xk+1)≤∑t=0qλktf(xk-t)-γh(xk)≤∑t=0q‍λkt(f(x0)-λγ∑r=0k-t-2‍h(xr)-γh(xk-t-1)∑r=0k-t-2‍)-γh(xk)=λk0(f(x0)-λγ∑r=0k-q-2‍h(xr)-λγ×∑r=k-q-1k-2‍h(xr)-γh(xk-1))+λk1(f(x0)-λγ∑r=0k-q-2‍h(xr)-λγ∑r=k-q-1k-3‍h(xr)-γh(xk-2))+⋯+λkp(f0(x0)-λγ∑r=0k-q-2‍h(xr)-γh(xk-q-1)∑r=0k-q-2‍)-γh(xk)≤∑t=0q‍λktf(x0)-λγ∑r=0k-q-2‍(∑t=0q‍λkt)h(xr)-∑t=0q‍λktγh(xk-t-1)-γh(xk). By the fact that ∑t=0qλkt=1,   λkt≥λ and h(xr)≥0, we have
(41)f(xk+1)≤f(x0)-λγ∑r=0k-q-2h(xr)-λγ∑r=k-q-1k-1h(xr)-γh(xk)=f(x0)-λγ∑r=0k-1h(xr)-γh(xk)≤f(x0)-λγ∑r=0kh(xr).
Then for all k, (38) holds.
Moreover, since{f(xk)} is bounded below, let k→∞, we can get that
(42)λγ∑k=0∞h(xk)<∞,
which implies h(xk)→0. Hence the result follows.Lemma 10.
Suppose that the assumptions hold. If Algorithm2 does not terminate finitely, let {xk} be an infinite sequence generated by Algorithm 2; if |𝒜|≠∞, then limk→∞inf∥g^k∥=0.Proof.
Suppose to contrary that there exist constantϵ>0 and k->0 such that ∥g^k∥>2ϵ for all k>k-. Then similar to the proof of Lemma 8, we have
(43)∥WkT∇qk(dkn)∥≥∥g^k∥-∥WkTHkdkn∥≥2ϵ-υ5∥dkn∥≥2ϵ-υ5α1∥ck∥,
for all k>k-. Since h(xk)→0, then ∥ck∥→0; there exists k^>k- such that
(44)∥WkT∇qk(dkn)∥≥ϵ∀k>k^.
From h(xk)→0, we also have dkn→0, then qk(dkn)→0. Hence
(45)predkf=-qk(dk)=-qk(dkn)+qk(dkn)-qk(dk)≥-qk(dkn)+αϵmin{Δk,ϵ}≥α2ϵmin{Δ-,ϵ}.
As in the proof of Lemma8, there exists ρ∈(0,1) such that raredkf≥ρmin{predkf,predkc+ξ0}. That is, (46)f(xk+1)≤max{f(xk),∑r=0m(k)-1λkrf(xk-r)}-ρmin{predkf,predkc+ξ0}.
In common with the proof of Lemma 9, we have
(47)ρ∑k=0∞min{predkf,predkc+ξ0}→0,
which implies predkf→0. It contradicts (45). Hence the result follows.Lemma 11.
Let{xk} be an infinite sequence generated by Algorithm 2. If |𝒜|=∞, then limk∈𝒜,k→∞h(xk)=0.Proof.
In view of convenience, denote(48)θl(p)=max0≤j≤m(p)-1θM+p-j,
where M+p-m(p)+1≤l(p)≤M+p. From the algorithm, we know θM+p+1=h(xk+1) and it holds
(49)θM+p+1≤βθl(p).
Sincem(p+1)≤m(p)+1, we have
(50)θl(p+1)=max0≤j≤m(p+1)-1θM+p+1-j≤max0≤j≤m(p)θM+p+1-j=max{θM+p+1,θl(p)}=θl(p).
This implies that {θl(p)} converges. Moreover, by θM+p+1≤βθl(p), we obtain
(51)θl(p)≤βθl(l(p)-M-1).
And since β∈(0,1), eventually θl(p)→0(p→∞).
Thus(52)θM+p+1≤βθl(p)→0
holds by Algorithm 2, then, with the facts θM+p+1=h(xk+1) and k+1∈𝒜, we have limk∈𝒜,k→∞h(xk)=0.Lemma 12.
Suppose that the assumptions hold. If Algorithm2 does not terminate finitely, let {xk} be an infinite sequence generated by Algorithm 2; if |𝒜|=∞, then limk∈𝒜,k→∞inf∥g^k∥=0.Proof.
Suppose to the contrary that there exist constantϵ>0 and k->0 such that ∥g^k∥>2ϵ for all k>k- and k∈𝒜. Then similar to the proof of Lemma 8, we have
(53)∥WkT∇qk(dkn)∥≥∥g^k∥-∥WkTHkdkn∥≥2ϵ-υ5∥dkn∥≥2ϵ-υ5α1∥ck∥,
for all k>k- and k∈𝒜. Since limk∈𝒜,k→∞h(xk)→0, that is, ∥ck∥→0 for k∈𝒜, then there exists k^>k- such that
(54)∥WkT∇qk(dkn)∥≥ϵ∀k>k^,k∈𝒜.
From limk∈𝒜,k→∞h(xk)=0, we also have dkn→0 for k∈𝒜, then qk(dkn)→0 for k∈𝒜. Thus, for k∈𝒜(55)predkf=-qk(dk)=-qk(dkn)+qk(dkn)-qk(dk)≥-qk(dkn)+αϵmin{Δk,ϵ}≥α2ϵmin{Δ-,ϵ}.
Similar to the proof of Lemma10, it is obtained that
(56)ρ∑k=0∞min{predkf,predkc+ξ0}→0,
which implies predkf→0 for all k. But predkf→0 for k∈𝒜 is also true, which contradicts (55). Hence the result follows.Theorem 13.
Suppose{xk} is an infinite sequence generated by Algorithm 2, one has
(57)limk→∞inf[∥ck∥+∥g^k∥]=0.
Namely, there exists at least one cluster point of {xk} that is a KKT point of problem (P).Proof.
The conclusion follows immediately by Lemmas9, 10, 11, and 12. Thus, the whole proof is completed.


## 5. Numerical Experiments

In this section, we carry out some numerical experiments based on the algorithm over a set of problems from [31, 32]. The program is written in MATLAB and we test and give the performance of Algorithm 2 on these problems. For each test example, we choose the initial matrix H0=I. As to those constants, we set γ=0.02, β=0.98, ρ=0.5, η=0.75, ξ0=0.05, γ0=0.1, γ1=0.5, γ2=2, Δmin=10-6, Δ0=1, M=3. We use 10-6 as the stopping criterion.During the numerical experiments, updating ofHk is done by
(58)Hk+1=Hk-Hksk(sk)THk(sk)THksk+rk(rk)T(sk)Trk,
where sk=xk+1-xk,  rk=θkyk+(1-θk)Hksk,  yk=gk+1-gk and
(59)θk={1if(sk)Tyk≥0.2(sk)THksk,0.8(sk)THksk(sk)THksk-(sk)Tykotherwise.In the following tables, the notations mean as follows:(i)
SC: the problems from Schittkowski [32];(ii)
HS: the problems from Hock and Schittkowski [31];(iii)
n: the number of variables;(iv)
m: the number of inequality constraints;(v)
NIT: the number of iterations;(vi)
NF: the number of evaluations of the objective functions;(vii)
NG:  the number of evaluations of scalar constraint functions;(viii)
Algorithm 1: our method in this paper;(ix)
Algorithm 2: the method proposed in [29];(x)
Algorithm 3: the method proposed in [33].The detailed numerical results are summarized in Tables1 and 2. Now we give a brief analysis for numerical test results. From Table 1, we can see that our algorithm executes well for these typical problems taken from [31, 32]. From the computation efficiency in Table 2, by solving same problems in [31, 32] we should point out our algorithm is competitive with the some existed nonmonotone filter type methods to solve equality constrained optimization, for example, [29, 33]. However, in our method an improved nonmonotone filter technique is proposed, which may make the discussion and consideration of the nonmonotone properties of f and h more freely. Furthermore, we consider a more relaxed accepted condition for trial step and a weakened crucial criterion is presented. It is easier to meet those new criteria, so our method is much more flexible. All results summarized show that our algorithm is promising and numerically effective.Table 1
Detailed numerical results.
Problem
n
m
NIT
NF
NG
SC216
2
1
5
16
7
SC219
4
2
28
52
36
SC235
3
1
20
48
30
SC252
3
1
22
46
36
SC254
3
2
18
45
37
SC265
4
2
3
7
3
SC269
5
3
5
10
8
SC344
3
1
12
24
16
HS006
2
1
4
7
5
HS007
2
1
8
14
8
HS008
2
2
3
11
5
HS009
2
1
5
12
6
HS026
3
1
35
87
45
HS028
3
1
7
29
11
HS042
4
2
8
31
10
HS047
5
3
25
86
72
HS050
5
3
12
39
14
HS051
5
3
7
18
9
HS077
5
2
12
22
16
HS079
5
3
11
23
13Table 2
Comparison among three algorithms for same problems in [31, 32].
Problem
(
n
,
m
)
NG-NF (Algorithm 1)
NG-NF (Algorithm 2)
NG-NF (Algorithm 3)
SC216
(
2,1
)
7-16
6-15
11-13
SC235
(
3,1
)
30-48
39-50
39-50
SC252
(
3,1
)
36-46
99-122
26-35
SC265
(
4,2
)
3-7
3-3
3-3
HS006
(
2,1
)
5-7
7-7
9-9
HS007
(
2,1
)
8-14
10-13
10-13
HS047
(
5,3
)
72-86
95-95
95-95
HS050
(
5,3
)
14-39
15-15
15-15
HS051
(
5,3
)
9-18
16-16
16-16
HS077
(
5,2
)
16-22
22-28
22-28



---

*Source: 163487-2013-02-04.xml*