# Global Convergence of a New Nonmonotone Filter Method for Equality Constrained Optimization

Authors: Ke Su; Wei Liu; Xiaoli Lu
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

A new nonmonotone filter trust region method is introduced for solving optimization problems with equality constraints. This method directly uses the dominated area of the filter as an acceptability criterion for trial points and allows the dominated area decreasing nonmonotonically. Compared with the filter-type method, our method has more flexible criteria and can avoid Maratos effect in a certain degree. Under reasonable assumptions, we prove that the given algorithm is globally convergent to a first order stationary point for all possible choices of the starting point. Numerical tests are presented to show the effectiveness of the proposed algorithm.


---

## Body

## 1. Introduction

We analyze an algorithm for solving optimization problems where a smooth objective function is to be minimized subject to smooth nonlinear equality constraints. More formally, we consider the problem,(P)minf(x),s.t.ci(x)=0,i∈I={1,2,…,m},
where x∈Rn, the functions f:Rn→R and ci(i∈I):Rn→R are all twice continuously differentiable. For convenience, let g(x)=∇f(x),c(x)=(c1(x),c2(x),…,cm(x))T and A(x)=(∇c1(x),∇c2(x),…,∇cm(x)), and fk refers to f(xk), ck to c(xk), gk to g(xk) and Ak to A(xk), and so forth.There are many trust region methods for equality constrained nonlinear programming(P), for example, Byrd et al. [1], Dennis Jr. et al. [2] and Powell and Yuan [3], but in these works, a penalty or augmented Lagrange function is always used to test the acceptability of the iterates. However, there are several difficulties associated with the use of penalty function, and in particular the choice of the penalty parameter. Hence, in 2002, Fletcher and Leyffer [4] proposed a class of filter method, which does not require any penalty parameter and has promising numerical results. Consequently, filter technique has been employed to many approaches, for instance, SLP methods [5], SQP methods [6–8], interior point approaches [9], bundle techniques [10], and so on.Filter technique, in fact, exhibits a certain degree of nonmonotonicity. The nonmonotone technique was proposed by Grippo et al. in 1986 [11] and combined with many other methods. M. Ulbrich and S. Ulbrich [12] proposed a class of penalty-function-free nonmonotone trust region methods for nonlinear equality constrained optimization without filter technique. Su and Pu [13] introduced a nonmonotone trust region method which used the nonmonotone technique in the traditional filter criteria. Su and Yu [14] presented a nonmonotone method without penalty function or filter. Gould and Toint [15] directly used the dominated area of the filter as an acceptability criteria for trial points and obtained the global convergence properties. We refer the reader [16–18] for some works about this issue.Motivated by the ideas and methods above, we propose a modified nonmonotone filter trust region method for solving problem(P). Similar to the Byrd-Omojokun class of algorithms, each step is decomposed into the sum of two distinct components, a quasi-normal step and a tangential step. The main contribution of our paper is to employ the nonmonotone idea to the dominated area of the filter so that the new and more flexible criteria is given, which is different from that of Gould and Toint [15] and Su and Pu [13]. Under usual assumptions, we prove that the given algorithm is globally convergent to first order stationary points.This paper is organized as follows. In Section2, we introduce the fraction of Cauchy decrease and the composite SQP step. The new nonmonotone filter technique is given in Section 3. In Section 4, we propose the new nonmonotone filter method and present the global convergence properties in Section 5. Some numerical results are reported in the last section.


## 2. The Fraction of Cauchy Decrease and the Composite SQP Step

Consider the following unconstraint minimization optimization problem:(1)minx∈Rnf(x),
where f:Rn→R is a continuously differentiable function. A trust region algorithm for solving the above problem is an iterate procedure that computes a trial step as an approximate solution to the following subproblems:
(2)minq(d)=gTd+12dTHd,s.t.∥d∥≤Δ,
where H is the Hessian matrix ∇2f(x) or an approximate to it and Δ>0 is a given trust region radius.To assure the global convergence, the step is required only to satisfy a fraction of Cauchy decrease condition. This means thatd 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.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 [19] for the proof).
Now, we turn to explain the composite SQP step. Given an approximate estimate of the solutionxk at kth iteration, following Dennis Jr. et al. [2] and M. Ulbrich and S. Ulbrich [12], 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. To improve optimality, we seek dkt in the tangential space of the linearized constraints in such a way that it provides sufficient decrease for a quadratic model of the objective function f(x). Let qk(d)=gkTd+(1/2)dTHkd, where Hk is a symmetric approximation of ∇2f(x).
d
k
n is the solution to the subproblem
(5)min12∥ck+AkTdn∥2+ξ2∥dn∥2,s.t.∥dn∥≤Δk,
where Δk is a trust region radius and Ak=∇c(xk)∈Rn×m,ξ>0. In order to improve the value of the objective function, we solve the following subproblem to get dkt:(6)minqk(dkn+dt),s.t.AkTdt=0mmmm∥dt∥≤Δk.
Then we get the current trial stepdk=dkn+dkt. Let dkt=Wkd-kt, where d-kt∈Rn-m and Wk∈Rn×(n-m) denote a matrix whose columns form a basis of the null space of AkT. We refer to [2] for a more detailed discussion of this issue.
In usual way that impose a trust region in step-decomposition methods, the quasi-normal stepdkn and the tangential step dkt are required to satisfy
(7)∥dn∥≤κΔk,∥dkn+dt∥≤Δk,
where 0<κ<1. Here, to simplify the proof, we only impose a trust region on ∥dn∥≤Δk and ∥dt∥≤Δk, which is natural.
Note thatWkT∇qk(dt) is the reduced gradient of qk in terms of the representation dt=Wks of the tangential step:
(8)∇s(qk(Wks))=WkT∇qk(Wks)=WkT∇qk(dt).
Define(9)g^(x)=W(x)Tg(x).
Then the first order necessary optimality conditions (Karush-Kuhn-Tucker or KKT conditions) at a local solutionx-∈Rn of problem (P) can be written as
(10)c(x-)=0,g^(x-)=0.


## 3. A New Nonmonotone Filter Technique

In filter method, originally proposed by Fletcher and Leyffer [4], the acceptability of iterates is determined by comparing the value of constraint violation and the objective function with previous iterates collected in a filter. Define the violation function h(x) by h(x)=∥c(x)∥22, it is easy to see that h(x)=0 if and only if x is a feasible point, so a trial point should reduce either the value of constraint violation or that of the objective function f.In the process of the algorithm, we need to decide whether the trial pointxk+ is any better than xk as an approximate solution to the problem (P). If we decide that this is the case, we say that the iteration k is successful and choose xk+ as the next iterate. Let us denote by 𝒮 the set of all successful iterations, that is,
(11)𝒮={k|xk+1=xk+}.In traditional filter method, a pointx is called acceptable to the filter if and only if
(12)h(x)≤βhjorf(x)≤fj-γhj,∀(hj,fj)∈ℱ,
where 0<γ<β<1, ℱ denotes the filter set. Define
(13)𝒟(ℱ)={(h,f)|h>hjandf>fj,∃j∈ℱ}.A trial pointxk+ is accepted if and only if (hk+,fk+)∉𝒟(ℱk).Now, similar to the idea of Gould and Toint [15], we give a new modified nonmonotone filter technique. For any (h,f)-pair, define an area that represents its contribution to the area of 𝒟(ℱ), we hope this contribution is positive; that is, the area of 𝒟(ℱ) is increasing. For convenience, we partition the right half-plane [0,+∞]×[-∞,+∞] into four different regions (see Figure 1). Define 𝒟(ℱk)c to be the complement of 𝒟(ℱk). Let
(14)hminℱk=defminj∈ℱkhj,hmaxℱk=defmaxj∈ℱkhj,fminℱk=defminj∈ℱkfj,fmaxℱk=defmaxj∈ℱkfj.Figure 1These four parts are(1)
the dominated part of the filter:NE(ℱk)=def𝒟(ℱk);(2)
the undominated part of lower left corner of the half plane:(15)SW(ℱk)=def𝒟(ℱk)c∩[0,hmaxℱk]×[-∞,fmaxℱk],(3)
the undominated upper left corner:NW(ℱk)=def[0,hminℱk)×(fmaxℱk,+∞];(4)
the undominated lower right corner:SE(ℱk)=def(hmaxℱk,+∞]×[-∞,fminℱk).Consider the trial pointxk+, if the filter is empty, then define its contribution to the area of the filter by
(16)α(xk+,ℱk)=defκF2,
where κF>0 is a constant. If the filter is not empty, then define the contribution of xk+ to the area of the filter by four different formulae.If(hk+,fk+)∈SW(ℱk), assume
(17)α(xk+,ℱk)=defarea(𝒟(ℱk)c∩[hk+,hmaxℱk+κF]×[fk+,fmaxℱk+κF]).If(hk+,fk+)∈NW(ℱk), assume
(18)α(xk+,ℱk)=defκF(hminℱk-hk+).If(hk+,fk+)∈SE(ℱk), assume
(19)α(xk+,ℱk)=defκF(fminℱk-fk+).If(hk+,fk+)∈NE(ℱk)=𝒟(ℱk), assume
(20)α(xk+,ℱk)=def-area(𝒟(ℱk)∩[hk+-hmin𝒫k]×[fk+-fmin𝒫k]),
where 𝒫k={(h,f)∈ℱk|hj<hk+,fj<fk+}, and hmin𝒫k=defminj∈𝒫khj,fmin𝒫k=defminj∈𝒫kfj.Figure2 illustrate the corresponding areas in the filter. Horizontally dashed surfaces indicate a positive contribution and vertically dashed ones a negative contribution. Note that α(x,ℱ) is a continuous function of (h(x),f(x)).Figure 2Next, we should consider the updating of the filter. If(hk,fk)∉𝒟(ℱk), then
(21)ℱk+1⟵ℱk∪(hk,fk).If(hk,fk)∈𝒟(ℱk), then
(22)ℱk+1⟵(ℱk∖𝒫k)∪(hmin𝒫k,fk)∪(hk,fmin𝒫k).We now return to the question of deciding whether a trial pointxk+ is acceptable for the filter or not. We will insist that this is a necessary condition for the iteration k to be successful in the sense that xk+1=xk+. If we consider an iterate xk, there must exist a predecessor iteration such that xp(k)+=xp(k)+1=xk. Under the monotonic situation, a trial point xk+ would be accepted whenever it results in an sufficient increase in the dominated area of the filter, that means xk+ would be accepted whenever
(23)αk≥γℱ(hk+)2,
where αk=defα(xk+,ℱk), γℱ∈(0,1) is a constant. Under the nonmonotonic situation, we relax condition (23) to be
(24)max{αk,∑j=r(k)+1j∈𝒰kλp(j)αp(j)}≥γℱ(hk+)2,
where αp(j)=defα(xj,ℱp(j)),𝒰={k|filterisupdatedfor(hk,fk)}, r(k)≤k is some reference iteration for 𝒰, r(k)∈𝒰, 𝒰⊆𝒮, λp(j)∈[0,1],∑j=r(k)+1,j∈𝒰kλp(j)=1.Compared to condition (2.21) [15], our condition (24) is more flexible if αk is negative.According to condition (24), it is possible to accept xk+ even though it may be dominated. Then xk+ will be accepted if either (23) or (24) holds.


## 4. The New Nonmonotone Filter Trust Region Algorithm

Our algorithm is based on the usual trust region technique; define the predict reduction for the functionqk(x) to be
(25)pred(dk)=qk(0)-qk(dk)
and the actual reduction
(26)ared(dk)=f(xk)-f(xk+).Moreover, letrk=ared(dk)/pred(dk), if there exists a nonzero constant η1 such that rk≥η1 and condition (23) and (24) hold, the trial point xk+ will be called acceptable. Then the next trial point xk+1 is obtained, and for its feasibility, we consider the condition
(27)hk+1≤η3min{μ,α1Δk2+α2}
is true or not, where η3 and μ are all positive constants, if it is not true, then turn to the feasibility restoration phase and define
(28)rkj=∥c(xkj)∥2-∥c(xkj+dkj)∥2∥c(xkj)∥2-∥c(xkj)+A(xkj)Tdkj∥2.
A formal description of the algorithm is given as follows.Algorithm A
S
t
e
p
0. Choose an initial point x0∈Rn, a symmetric matrix H0∈Rn×n, let Δ0>0, ϵt>0,η2,η3∈(0,1),α1,α2∈[0,1],η1>0,0<γ0<γ1<1≤γ2<γ3≤2,0<ξ<1,γℱ∈(0,1),μ>0, compute f(x0),h(x0), let k=0,ℱ0=∅.Step 1.
Computeck,Ak,Wk,fk,hk,gk,g^k=WkTgk.Step 2.
If∥g^k∥+hk≤ϵt, stop.Step 3.
Solve the subproblems (5) and (6) to get the quasi-normal step dkn and the tangential step dkt. Let dk=dkn+dkt,xk+=xk+dk.Step 4.
Ifrk<η1, let xk+1=xk, then go to Step 8.Step 5.
Ifxk+dk is not acceptable to the filter, go to Step 8. Otherwise xk+1=xk+ and update the filter according to (21) and (22), the trust region radius and Hk, then get the corresponding hk+1,fk+1.Step 6.
Ifhk+1≤η3min{μ,α1Δk2+α2}, k=k+1 and go to Step 1, otherwise go to Step 7.Step 7.
By restoration Algorithm B to getdkr, then the trial point xkr=xk+dkr.Step 8.
Update the trust region radius by Algorithm C, letk=k+1 and go to Step 3.
We aim to reduce the value ofh(x) in the restoration Algorithm B, that is to get c(xkr)=0 by Newton-type method.Algorithm B
S
t
e
p
0. Let xk0=xk,Δk0=Δk,j=0,η2,η3∈(0,1),α1,α2∈[0,1],μ>0.Step 1.
Ifh(xkj)≤η3min{hkℱk,α1Δk2+α2} and xkj is acceptable by the filter, then xkr=xkj, stop.Step 2.
Compute(29)min∥c(xkj)+A(xkj)Tdkj∥2,s.t.∥dkj∥≤Δkj
to get dkj, then compute rkj.Step 3.
Ifrkj≤η2, xkj+1=xkj,Δkj+1=Δkj/2,j=j+1 and go to Step 2.Step 4.
Ifrkj>η2, xkj+1=xkj+dkj,Δkj+1=2Δkj,j=j+1, compute Akj+1 and go to Step 1, where hkℱk=min{minj∈ℱk{hj|hj>0},μ}.Algorithm C (updating the trust region radius). Given η1>0,0<γ0<γ1<1≤γ2<γ3≤2, we have the following.(1)
Ifrk<η1 or xk+ is not acceptable to the filter, Δk+1∈[γ0Δk,γ1Δk].(2)
Ifxk+ is acceptable to the filter but does not satisfiy condition (27), Δk+1∈(Δk,γ2Δk).(3)
Ifxk+ is acceptable to the filter and satisfies (27),  Δk+1∈[γ2Δk,γ3Δk].From the description above and the idea of the algorithm, we can see that our algorithm is more flexible. Every successful iterate must be any better than the predecessor one in some degree according to the traditional filter method. But our algorithm relaxes this demand by using the nonmonotone technique and also avoids Maratos effect in a certain degree. Moreover, Algorithm C allows a relatively wide choice of the trust region.


## 5. The Convergence Properties

In this section, to present a proof of global convergence of algorithm, we always assume that the following conditions hold.Assumption(A1)
The objective functionf and the constraint functions ci(i∈I={1,2,…,m}) are twice continuously differentiable.
(A2)
For allk,  xk, and xk+dk all remain in a closed, bounded convex subset Ω⊂Rn.
(A3)
The matrixA(x)=∇c(x) is nonsingular matrix for all x∈Ω.
(A4)
The matrices(A(x)TA(x))-1,W(x),(WTW)-1 are uniformly bounded in Ω, where W(x) denotes a matrix whose columns form a basis of the null space of A(x)T.
(A5)
The matrixHk is uniformly bounded.By the assumptions, we can suppose there exist constantsv0,v1,v2,v3 such that ∥f(x)∥≤v0,∥g(x)∥≤v0,∥c(x)∥≤v0,∥A(x)∥≤v0,∥A(x)TA(x)-1∥≤v1,∥W(x)∥≤v2,∥Hk∥≤v3,∥WkTHk∥≤v3,∥WkTHkWk∥≤v3.By (A1) and (A2), it holds(30)fmin≤fk,0≤hk≤hmax∀k,
where fmin,hmax>0, hence in the (h,f)-plane, the (h,f)-pair lies in the area [0,hmax]×[fmin,+∞].From (A1), (A2), and (A3), it exists a constantν- such that
(31)|f(xk+dk)-qk(dk)|≤ν-Δk2.Lemma 2.
At the current iteratexk, let the trial point component dkn actually be normal to the tangential space. Under the problem assumptions, there exists a constant k1>0 independent of the iterates such that
(32)∥dkn∥≤α1∥ck∥.Proof.
It is similar to the proof of Lemma 2 in [13].Lemma 3.
Under Assumptions, there exist positive constantsk2,k3,k4 independent of the iterates such that
(33)∥ck∥2-∥ck+AkTdkn∥2≥k2∥ck∥min{k3∥ck∥,Δk},qk(dkn)-qk(dk)≥σ2∥WkT∇qk(dkn)∥min{k4∥WkT∇qk(dkn)∥,Δk}.Proof.
The proof is an application of Lemma1 to the two subproblems (5) and (6).Lemma 4.
Suppose that Assumptions hold, then restoration Algorithm B is well defined.Proof.
The conclusion is obvious, ifhkj→0. Otherwise it exists ϵ>0 such that for all j, it holds hkj>ϵ. Consider the set
(34)K={j|rkj=∥ckj∥2-∥c(xkj+dkj)∥2∥ckj∥2-∥ckj+(Akj)Tdkj∥2>η2>0},
where ckj=c(xkj),Akj=A(xkj). By Lemma 3 and the definition of hk, we have
(35)+∞>∑j=1∞(hkj-1-hkj)≥∑j∈K(∥ckj∥2-∥ckj+(Akj)Tdkj∥2)≥η2k2∑j∈K‍∥ck∥min{k3∥ck∥,Δkj}.
Byhkj>ϵ, it holds Δkj→0 for j∈K. From Algorithm B, we can obtain that Δkj→0 for all j.
On the other side,(36)∥ckj∥2-∥c(xkj+dkj)∥2=∥ckj∥2-∥ckj+(Akj)Tdkj∥2+o(Δkj)
for Δkj→0. By the algorithm, the radius Δkj should be satisfied Δkj+1>Δkj, that is contradicted to Δkj→0. The proof is complete.Now, we analyze the impact of the criteria (23) and (24). Once a trial point is accepted as a new iterate, it must be provided some improvement, and we formalize this by saying that iterate xk=xp(k)+1 improves on iterate xi(k). That is the trial point xk is accepted at iterate p(k); it happens under two situations, one is by the criteria (23), that is,
(37)i(k)=p(k)ifp(k)∉𝒜
the other is by the criteria (24), that is,
(38)i(k)=p(k)ifp(k)∉𝒜.Now consider any iteratexk, it improved on xi(k), which was itself accepted because it improved on xi(i(k)), and so on, until back to x0. Hence we may construct a chain of successful iterations indexed by 𝒞k= {l1,l2,…,lq} for each k, such that
(39)xl1=x0,xlq=xk,xlj=xi(lj+1),j=1,2,…,q-1,
where l1 is the smallest index in the chain of successful iterations.Lemma 5.
Suppose that Assumptions hold and Algorithm A does not terminate finitely, apply Algorithm A to the problem(P), then for all k and 𝒞k={l1,l2,…,lq}, it holds
(40)area(𝒟(ℱk))≥γℱ∑j=1q‍hlj2.Proof.
For∀lj∈𝒞k, if p(lj)∈𝒜, by (24),  i(lj)=r(p(lj))=lj-1, then
(41)max{αp(lj),∑i=lj-1+1i∈𝒰ljλp(i)αp(i)}≥γℱhlj2.
Ifmax{αp(lj),∑i=lj-1+1,i∈𝒰ljλp(i)αp(i)}=αp(lj),
(42)αp(lj)≥γℱhlj2.
Ifmax{αp(lj),∑i=lj-1+1,i∈𝒰ljλp(i)αp(i)}=∑i=lj-1+1,i∈𝒰ljλp(i)αp(i),
(43)∑i=lj-1+1i∈𝒰ljαp(i)≥γℱhlj2.
Ifp(lj)∉𝒜,  lj-1=p(lj). By 𝒰⊆𝒮, it holds
(44){lj-1+1,…,lj}∩𝒰⊆{lj-1+1,…,lj}∩𝒮={lj}.
Then from (23), αp(i)≥γℱhlj2. It implies (43). Moreover
(45)area(𝒟(ℱk))≥∑i=0i∈𝒰kαp(i)=∑j=0q‍(∑i=lj-1+1i∈𝒰ljαp(i)).
Together with (42) and (43), the result follows.Lemma 6.
Suppose that Assumptions hold. If Algorithm A does not terminate finitely and the filter contains infinite iterates, thenlimk→∞hk=0.Proof.
Suppose by contradiction that there exists a constantϵ>0 and infinite sequence {ki}⊆𝒮 such that hki≥ϵ for all i. Because there are infinite iterations in the filter, we have |𝒮|=∞, then hlq≥ϵ for ∀q.
(46)area(𝒟(ℱk))≥γℱ·q·ϵ2.
Then by (31), area(𝒟(ℱk)) is upper bounded for each k. That means it exists κℱmax≥0 such that area(𝒟(ℱk))≤κℱmax, so i≤(κℱmax/γℱϵ2). Hence i must be finite, it contradicts to the infinity of {ki}. The proof is complete.Lemma 7.
Suppose that Assumptions hold and Algorithm A terminate finitely, thenhk=0.Proof.
From the Algorithm A and the definition of filter, the conclusion follows.Lemma 8.
For any trial pointxk+1≠xk, there must be one accepted by the filter.Lemma 9.
Suppose that Assumptions hold, there existsk5>0 independent of the iterates such that
(47)qk(0)-qk(dkn)≥-k5∥ck∥.Proof.
By (32), the assumptions and ∥dkn∥≤Δmax, it is obvious that
(48)qk(0)-qk(dkn)=-gkTdkn-12(dkn)THkdkn≥-∥dkn∥(∥gk∥+12∥Hk∥∥dkn∥)≥-k1∥ck∥(ν0+ν3Δmax)=def-k5∥ck∥.
The proof is complete.Lemma 10.
Suppose that Assumptions hold and∥g^k∥≥ϵt, if
(49)Δk≤min{(ϵt2k1ν3η3α1)2/(2+α2),k4ϵt2,(ν0k1ν3η3α1)2/(2+α2),(σϵt16k1ν0η3α1)2/α2}=defδ1
one can deduce
(50)qk(0)-qk(dk)≥σϵt8Δk=defσ-Δk.Proof.
By the assumptions and the definition ofdkn, it holds
(51)∥WkT∇qk(dkn)∥=∥WkT(gk+Hkdkn)∥≥∥g^k∥-∥WkTHkdkn∥≥ϵt-ν3k1∥ck∥≥ϵt-ν3k1η3α1Δk1+(α2/2)≥ϵt2.
From Lemma 3, qk(dkn)-qk(dk)≥(σ/4)ϵtmin{Δk,k4ϵt/2}≥(σϵt/4)Δk. Together with
(52)qk(0)-qk(dkn)=-gkTdkn-12(dkn)THkdkn≥-∥gk∥∥dkn∥-12∥Hk∥∥dkn∥2≥-k1ν0η3α1Δk1+(α2/2)-k12ν3η3α1Δk2+α2≥-2k1ν0η3α1Δk1+(α2/2)≥-σϵt8Δk
then qk(0)-qk(dk)≥-(σϵt/8)Δk+(σϵt/4)Δk=(σϵt/8)Δk=σ-Δk. It is the conclusion.Lemma 11.
Suppose the conditions of Lemma10 hold, if
(53)Δk≤min{δ1,(1-η1)σ-ν-}=defδ2
then rk≥η1.Proof.
From the definition ofrk and Lemma 10, together with (31), we have
(54)|rk-1|=|f(xk+dk)-qk(dk)||qk(0)-qk(dk)|≤ν-Δk2σ-Δk≤1-η1.
It is obvious that rk≥η1.Lemma 12.
Suppose the conditions of Lemmas10 and 11 hold, if
(55)hk≤(η3α1)-1/(1+α2)(η1σ-γℱ)(2+α2)/(1+α2)
then
(56)f(xk+)≤f(xk)-γℱhk.Proof.
By Lemmas3, 10, and 11, together with ∥g^k∥≥ϵt, it holds
(57)f(xk)-f(xk+)≥η1(qk(0)-qk(dk))≥η1σ-Δk.
From the Algorithm, hk≤η3α1Δk2+α2, then
(58)f(xk)-f(xk+)≥η1σ-(hkη3α1)1/(2+α2).
Hence f(xk)-f(xk+)≥γℱhk.Theorem 13.
Suppose the assumptions hold, there must existΔmin>0 such that for each k, it holds
(59)Δk≥Δmin.Proof.
Letk-1 be large enough such that hk-1≤ϵt, it is true by Lemmas 6 and 7. Suppose by contradiction that the index j is the first one after k-1, which satisfies
(60)Δj≤γ0min{δ2,((1-γℱ)hFη3α1)1/(2+α2),Δk-1}=defγ0δ3,
where hF=defmini∈𝒰hi is the smallest value of violation function in filter. Then Δj≤γ0Δk-1. By the above analysis, we know j≥k-1+1, that is j-1≥k-1. From the Algorithm and (60), it concludes
(61)Δj-1≤1γ0Δj≤δ3.
By (60) and (61), (53) can be obtained. In Lemma 11, let j-1 instead of k, it deduces
(62)rj-1≥η1.
Based on Lemma12, together with (60), (61), and the algorithm, we can see
(63)hj-1+≤η3α1Δj-12+α2≤(1-γℱ)hF.
It can be seen that (53) is true for j-1≥k, with (55), we can deduce
(64)fj-1+≤fj-1-γℱhj-1.
That meansxj-1+ can be accepted by the filter. From above and (55), we know Δj≥Δj-1. Hence the index j is not the first one after k-1 which satisfied (60), that is a contradiction. So, for any k>k-1, it holds Δk≥γ0δ3. Define
(65)Δmin=min{Δ0,…,Δk-1,γ0δ3}
we can see that(66)Δk≥Δmin
holds for each k. The proof is complete.Lemma 14.
Suppose that Assumptions hold and Algorithm A does not terminate finitely, thenliminfk→∞∥g^k∥=0.Proof.
Suppose by contradiction that forϵt, there exists a constant k->0 such that ∥g^k∥≥ϵt.
By Assumption (A3) and (A4),∥WkT∇qk(dkn)∥≥∥g^k∥-ν3k1∥ck∥. From Lemma 6, we know hk→0. Hence there exists k~>0 such that
(67)∥ck∥≤2ϵt3ν3k1
for k>k~. Then ∥WkT∇qk(dkn)∥≥(1/3)∥g^k∥≥(1/3)ϵt for k>k^=defmax{k-,k~}.
It is obvious that(68)qk(0)-qk(dk)=qk(0)-qk(dkn)+qk(dkn)-qk(dk).
By the proof of Lemma9, it holds |qk(0)-qk(dkn)|≤ν0∥dkn∥+(1/2)ν3∥dkn∥2. Together with Lemma 6 and the definition of dk, we have
(69)limk→∞(qk(0)-qk(dkn))=0.
By the Algorithm, we can get
(70)+∞>∑k=0∞‍(fk-fk+1)≥η1∑k=0∞‍(qk(0)-qk(dk)).
Then
(71)limk→∞(qk(0)-qk(dk))=0.
By (68), (69), and (71), it deduces
(72)limk→∞(qk(dkn)-qk(dk))=0.
Based on the assumptions, Lemma 3 and Theorem 13, for k>k^, it holds
(73)qk(dkn)-qk(dk)≥σ2∥WkT∇qk(dkn)∥min{Δk,k4∥WkT∇qk(dkn)∥}≥σϵt6min{Δmin,k4ϵt6}>0,
which contradicts (72). The conclusion follows.Theorem 15.
Suppose the assumptions hold, and apply the algorithm to problem(P), then
(74)liminfk→∞(hk+∥g^k∥)=0,
where g^k=WkTgk,gk=∇f(xk),  W(x) denotes a matrix whose columns form a basis of the null space of A(x)T.Proof.
If the algorithm terminates finitely, it is obvious that it holds. Otherwise, by Lemmas6 and 14, the conclusion also can be obtained.Theorem 16.
Suppose the assumptions hold, and{xk} is the infinite sequence obtained by the algorithm, then there must exist a subsequence such that
(75)limj→∞xkj=x*
and x* satisfies the one order KKT condition of (P).Proof.
By Assumption (A1), there exist a subsequence{kj} and x*, such that limj→∞xkj=x*. Together with Assumption (A3) and (A4), it hods limj→∞WkjTgkj=0, which means for large enough j, gkj lies in the space spaned by the columns of AkjT. That is there exists λkj such that
(76)limj→∞gkj+AkjTλkj=0.
The conclusion follows.


## 6. Some Numerical Experiments

(1)
Updating ofHk is done by Hk+1=Hk+(ykTyk/ykTsk)-(HkskskTHk/skTHksk), where yk=θky^k+(1-θk)Hksk(77)θk={1skTy^k≥0.2skTHksk0.8skTHkskskTHksk-skTy^k
and y^k=gk+1-gk+(Ak+1-Ak)ρk, sk=xk+1-xkρk is the multipluser of corresponding quadratic subproblems.
(2)
We assume the error toleration is10-5.
(3)
The algorithm parameters were set as follows:H0=I∈Rn×n, η1=0.25, η2=0.25, η3=0.1, α1=α2=0.5, γ=0.02, ρ=0.5, ξ=10-6, γ0=0.1, γ1=0.5, γ2=2, γF=10-4, Δ0=1. The program is written in Matlab.The numerical results for the test problems are listed in Table1.Table 1
Problem
n
m
NF
NG
L's NF
L's NG
HS6
2
1
11
11
20
12
HS7
2
1
9
3
15
11
HS8
2
2
7
4
—
—
HS9
2
1
6
6
6
6
HS26
3
1
24
24
42
24
HS39
4
2
15
9
26
19
HS40
4
3
7
5
7
5
HS42
4
2
8
8
11
11
HS78
5
3
6
6
8
7In Table1, the problems are numbered in the same way as in Schittkowski [20] and Hock and Schittkowski [21]. For example, “S216” is the problem (216) in Schittkowski [20] and “HS6” is the problem (6) in Hock and Schittkowski [21]. NF, NG represent the numbers of function and gradient calculations and “L's” is the solution in [22]. The numerical results show that the our algorithm is more effective than the L's for most test examples. Moreover, the higher the level of nonmonotonic, the better the numerical results. The results show that the new algorithm is robust and effective, and more flexible for the acceptance of the the trial iterate.



---

*Source: 976509-2013-04-10.xml*