# A Nonmonotone Trust Region Algorithm Based on the Average of the Successive Penalty Function Values for Nonlinear Optimization

Authors: Zhensheng Yu; Jinhong Yu
Journal: ISRN Operations Research
 (2013)

---

## Abstract

We present a nonmonotone trust region algorithm for nonlinear equality constrained optimization problems. In our algorithm, we use the average of the successive penalty function values to rectify the ratio of predicted reduction and the actual reduction. Compared with the existing nonmonotone trust region methods, our method is independent of the nonmonotone parameter. We establish the global convergence of the proposed algorithm and give the numerical tests to show the efficiency of the algorithm.


---

## Body

## 1. Introduction

In this paper, we consider the equality constrained optimization problem as follows:(1)minf(x),s.t.c(x)=0,
where f(x):Rn→R, c(x)=(c1(x),c2(x),…,cm(x))T, ci(x):Rn→Rm, (i=1,2,…,m), and (m≤n) are assumed to be twice continuously differentiable.Trust region method is one of the well-known methods for solving problem (1). Due to its strong convergence and robustness, trust region methods have been proved to be efficient for both unconstrained and constrained optimization problems [1–9].Most traditional trust region methods are of descent type methods; namely, they accept only a trial point as the next iterate if its associated merit function value is strictly less than that of the current iterate. However, just as pointed out by Toint [10], the nonmonotone techniques are helpful to overcome the case that the sequence of iterates follows the bottom of curved narrow valleys, a common occurrence in difficult nonlinear problems. Hence many nonmonotone algorithms are proposed to solve the unconstrained and constrained optimization problems [11–20]. Numerical tests show that the performance of the nonmonotone technique is superior to those of the monotone cases.The nonmonotone technique was originally proposed by Grippo, Lampariello and Lucidi [13] for unconstrained optimization problems based on Newton’s method, in which the stepsize αk satisfies the following condition:
(2)f(xk+αkdk)≤max0≤j≤mkf(xk-j)+βαk∇f(xk)Tdk,
where β∈(0,1), 0≤mk≤min{mk-1+1,M}, and M is a prefixed nonnegative integer.Although the nonmonotone technique based on (2) works well in many cases, there are some drawbacks. Firstly, a good function value generated in any iteration is essentially discarded due to the maximum in (2). Secondly, in some cases, the numerical performance is heavily dependent on the choice of M (see, e.g., [16, 21]). To overcome these drawback, Zhang and Hager [21] proposed another nonmonotone algorithm, and they used the average of function values to replace the maximum function value in (2). The numerical tests show that their nonmonotone line search algorithm used fewer function and gradient evaluations, on average, than either the monotone or the traditional nonmonotone scheme. Recently, Mo and Zhang [16] extended Zhang and Hager’s nonmonotone technique to unconstrained optimization with trust region global scheme and discussed the global and local convergence of the proposed algorithm.In this paper, we further extend the nonmonotone technique [16, 21] to equality constrained optimization. To design our algorithm, we first introduce some notations as follows: denote g(x)=∇f(x) and A(x)=(∇c1(x),∇c2(x),…,∇cm(x))∈Rn×m. Assuming that A(x) has full column rank, we define the projective matrix
(3)Z(x)=I-A(x)(A(x)TA(x))-1A(x)T∈Rn×n
and the Lagrange function
(4)L(x,λ)=f(x)+λTc(x),
where λ is a projective version of the multiplier vector as follows:
(5)λ(x)=(A(x)TA(x))-1A(x)Tg(x).For convenience, we denote the previous quantities atxk by fk, ck, gk, Ak, Zk, and λk. At each iteration, we calculate the trust region trial step as follows (see [22]): firstly, we calculate
(6)ν(xk)=-αkA(x)[A(xk)TA(xk)]-1c(xk),
where
(7)αk={1,ck=0,min{1,Δk∥Ak[A(xk)TA(x)]-1ck∥},otherwise.
Then we solve the trust region subproblem
(8)min(Zkgk)Tω+(12)ωT(ZkBkZk)ωs.t.∥ω∥≤Δk,
where Bk denotes the Hessian matrix of the Lagrange function L(xk,λk), Δk>0 is the trust region radius. Let ωk be the solution of (8) and
(9)hk=Zkωk.
The trust region trial step is taken as
(10)dk=hk+νk.
To test whether the point xk+dk can be accepted as the next iteration, we use the Fletcher’s exact penalty function as the merit function as follows:
(11)ψ(x,λ,σ)=f(x)+λTc(x)+σ∥c(x)∥2,
where σ>0 is the penalty parameter.To define our nonmonotone algorithm, we define(12)Fk={ψ(xk,λk,σk),ifk=0,(ηk-1Qk-1Fk-1+ψ(xk,λk,σk))Qk,ifk≥1,
where
(13)Qk={1,ifk=0,ηk-1Qk-1+1,ifk≥1,
where ηk-1∈[ηmin,ηmax], ηmin∈[0,1], ηmax∈[ηmin,1), and ηmin,ηmax are two chosen parameters.From (12) and (13), we observe that Fk is a convex combination of the function values
(14)ψ(x0,λ0,σ0),ψ(x1,λ1,σ1),…,ψ(xk,λk,σk),
so Fk is regarded as the weighted average of the merit function values.The paper is organized as follows. We describe our algorithm in Section2 and analyze the global convergence in Section 3. The numerical tests are given in Section 4, and the conclusion is presented in Section 5.


## 2. Algorithm

In this section, we give the details of the nonmonotone trust region algorithm. We first recall the definition of a stationary point of problem (1). A point x is called a stationary point of problem (1) if it satisfies
(15)∥Z(x)Tg(x)∥+∥c(x)∥=0.
We define the actual reduction from xk to xk+dk by
(16)Aredk=ψ(xk,λk,σk)-ψ(xk+dk,λk+1,σk)
and the nonmonotone actual reduction by
(17)NAredk=Fk-ψ(xk+dk,λk+1,σk).
The predicted reduction is defined as
(18)Predk=-gkTdk-(12)dkTBkdk-∇λkT(ck+AkTdk)-λkTAkTdk+σk(∥ck∥2-∥ck+AkTdk∥2).
Furthermore, we define the monotone ratio by
(19)rk=AredkPredk
and the nonmonotone ratio by
(20)Nrk=NAredkPredk,
where Fk is computed by (12) and (13).The description of the algorithm is given as follows.Algorithm 1.
Step 0. Set x0∈ℝn, Δ0>0, σ0>0, μ∈(0,1), 0<c1<c2<1, c3>0, a symmetric matrix B0∈ℝn×n, parameters ηmin∈[0,1) and ηmax∈[ηmin,1), and k:=0.
Step 1. If ∥ZkTgk∥+∥ck∥=0, stop; otherwise, go to Step 2.
Step 2. Compute the trust region trial step dk.
Step 3. Set σk=σk, if Predk≥(1/2)σk(∥ck∥2-∥ck+AkTdk∥2), and then set(21)σk=max{σk,2gkTdk+(1/2)dkTBkdk+∇λkT(ck+AkTdk)+λkTAkTdk∥k∥2-∥c-k+AkTdk∥2}.
Step 4. Compute Fk by (12) and (13), and compute the Nrk by (20).
Step 5. Set
(22)xk+1={xk+dk,Nrk≥μ,xk,otherwise.
Step 6. Update Δk+1 as
(23)Δk+1:{∈[c1∥dk∥,c2Δk],ifNrk<μ,=Δk,ifNrk≥μ,∥dk∥<Δk,∈[Δk,c3Δk],ifNrk≥μ,∥dk∥=Δk,
go to Step 3.
Step 7. Update Bk, and choose ηk∈[ηmin,ηmax]. Set k:=k+1; go to Step 1.


## 3. Global Convergence

In this section, we discuss the global convergence of Algorithm1. The following assumptions are needed in our convergence analysis:Assumptions
(A1)
The sequence{xk} and {xk+dk} are contained in a compact set Ω.
(A2)
There exists a positive constantM>0 such that for all k, ∥Bk∥≤M.
(A3)
For allx∈Ω, A(x) is of column full rank. We define two index sets as follows:
(24)I={k:Nrk≥μ},J={k:Nrk≤μ}.
The following lemmas (Lemmas 2–5) are helpful to analyze the convergence of the Algorithm 1, and the proofs are similar to [4].Lemma 2.
Assume that (A1)–(A3) hold, and then there exists a positive constantK1 such that
(25)∥ck∥2-∥ck+AkTdk∥2≥K1∥ck∥2min{∥ck∥2,Δk},Predk≥(12)σkK1∥ck∥min{∥ck∥,Δk}.Lemma 3.
Letζk(d)=gkTd+(1/2)dTBkd, and assume that (A1)–(A3) hold. Then there exists a positive constant K2 such that
(26)ζk(dk)≤ζk(vk)-K2∥Zk(gk+Bkvk)∥×min{∥Zk(gk+Bkvk)∥M+1,Δk}.Lemma 4.
Assume that (A1)–(A3) hold. Then there exists a positive constantK3 such that
(27)|Aredk-Predk|≤K3σk∥dk∥2.Lemma 5.
Assume that (A1)–(A3) holds. Then there exists a positive constantK4 such that
(28)Predk≥K2∥Zk(gk+Bkvk)∥min{∥Zk(gk+Bkvk)∥M+1,Δk}-K4∥ck∥+σk(∥ck∥2-∥ck+AkTdk∥2).The following lemma shows the monotonicity property of the function sequence{Fk}.Lemma 6.
Suppose that{xk} is generated by Algorithm 1. Then the following inequality holds for all k:
(29)ψk+1≤Fk+1≤Fk.Proof.
We first prove that (29) holds for all k∈I; that is,
(30)ψk+1≤Fk+1≤Fk,∀k∈I.
For k∈I, according to Lemma 2, Assumptions (A1) and (A2), we obtain
(31)ψk+1≤Fk-(12)σkK1∥ck∥min{∥ck∥,Δk}.
According to (8)–(13), we have the following inequality:
(32)Fk+1=ηkQkFk+ψk+1Qk+1≤ηkQkFk+Fk-(1/2)σkK1∥ck∥min{∥ck∥,Δk}Qk+1=Fk-(1/2)σkK1∥ck∥min{∥ck∥,Δk}ηkQk.
By (12) and (13), if ηk=0, we have
(33)Fk+1=ψk+1.
Otherwise, if ηk≠0, we have
(34)Fk+1-Fk=ψk+1-Fk+1Qk+1.
So, from (32) to (34), we know that (30) holds.
Next, we prove that (29) holds for all k∈J. From Step 4 of Algorithm 1, we get xk+1=xk and ψk+1=ψk for k∈J. Firstly, we prove that ψk+1≤Fk+1.
We consider two cases.
Case 1 (k-1∈I). According to (8), we have ψk≤Fk. Then it follows from (12) and (13) and ψk+1=ψk that
(35)Fk+1≥ηkQkψk+ψk+1Qk+1=ηkQkψk+1+ψk+1Qk+1=ψk+1.
Case 2 (k-1∈J). In this situation, let K={i∣1<i≤k,k-i∈I}. If K=∅, from Step 4 of Algorithm 1, we have F0=Fk-j=Fk+1, j=0,1,…,k-1. Consequently, it follows from (12) and (13) that
(36)Fk+1=Fk=ψk+1.
We suppose that K≠∅ and set m=min{i:i∈K}, and then we have
(37)ψk-j=ψk=ψk+1,j=0,1,…,m-1.
By (12), we obtain
(38)QkFk=ηk-1Qk-1Fk-1+ψk,k≥1.
According to (38) repeatedly, we can get
(39)ηkQkFk+ψk+1=∏i=0m-1‍ηk-iQk-m+1Fk-m+1+∑j=0m-2‍∏i=0j‍ηk-iψk-j+ψk+1.
Using the definition of K and m, we know that k-m∈I and Fk-m+1≥ψk-m+1 through (8).
From (37) and (39), it follows that
(40)ηkQkFk+Ψk+1≥∏i=0m-1‍ηk-iQk-m+1ψk-m+1+∑j=0m-2‍∏i=0j‍ηk-iψk-j+ψk+1=(∏i=0m-1‍ηk-iQk-m+1+∑j=0m-2‍∏i=0j‍μk-i+1)ψk+1=Qk+1ψk+1.
From (12) and (40) we know that
(41)Fk+1=ηkQkFk+ψk+1Qk+1≥Qk+1ψk+1Qk+1=ψk+1
By (35), (36), and (42), we get
(42)ψk+1≤Fk+1,∀k∈J.
Now we prove that Fk+1≤Fk. If ηk≠0, from (34) and (42), the conclusion is obvious. If ηk=0, then by (12), (13) and k∈J, we have Fk+1=Fk. Thus (29) holds for all k∈J. The proof is completed.Theorem 7.
Suppose that the Assumptions (A1)–(A3) hold and the sequence{xk} is generated by Algorithm 1. Then the algorithm is well defined.Proof.
Since the algorithm does not stop in Step 2, then we have either∥ck∥≠0 or ∥ZkTgk∥≠0. We prove the conclusion by contradiction; if the conclusion is not true, by the algorithm, we have xk+1=xk, but
(43)Nrk<μ,limk→∞Δk=0.
Case 1 (∥ck∥≠0). Then from Lemmas 2 and 4, we have
(44)limk→∞|rk-1|=limk→∞|Aredk-PredkPredk|≤limk→∞2K3σk∥Δk∥2σkK1∥ck∥min{∥ck∥,Δk}≤limk→∞2K3σk∥Δk∥2σkK1∥ck∥Δk=0,
which means that rk>μ for k large enough, according to Lemma 6, and we have that NAredk,i=F(xk+dk)-ψ(xk+dk)>Aredk, so Nrk≥rk>μ, which contradicts (43).
Case 2 (∥ck∥=0). In this case, we have ∥vk∥=0 and ∥ZkTgk∥≠0, By Lemma 3, and we can have
(45)Predk=-ζ(dk)≥K2∥Zk(gk+Bkvk)∥×min{∥Zk(gk+Bkvk)∥M+1,Δk}=K2∥Zkgk∥Δk.
Combining with Lemma 4, we have
(46)limk→∞|rk-1|=limk→∞|Aredk-PredkPredk|≤limk→∞K3σk∥Δk∥2K2∥Zkgk∥Δk=0.
Then similar to Case 1, we can get a contradiction. Combining Cases 1 and 2, we can get the conclusion.Similar to Lemma  7.11 in [4], we get the proposition of the penalty parameter as follows.Lemma 8.
Under Assumption (A1), if∥ZkTgk∥+∥ck∥≠0, then there exist a integer k0 and a positive constant σ⋆ such that for all k≥k0, σk=σ⋆.Without loss of generality, we assume thatσk=σ⋆ for all k. The following theorem gives the convergence proposition of the constraint sequence {∥ck∥}.Theorem 9.
Under the Assumptions (A1)–(A3), we have(47)limk→∞∥ck∥=0.Proof.
First, we prove that(48)liminfk→∞∥ck∥=0.
Assume by contradiction that (48) does not hold, then there exists a constant ε>0 such that ∥ck∥≥ε for all k. According to Lemma 6, we have
(49)Fk+1≤Fk-PredkQk+1,Fk-Fk+1≥PredkQk+1,Fk-1-Fk≥PredkQk,Fk-2-Fk-1≥PredkQk-1,⋮F1-F2≥PredkQ2.
By using (13), we can prove that
(50)Qk+1=1+∑j=0k‍∏i=0j‍ηk-i≤1+∑j=0k‍ηmaxj+1≤∑j=0∞‍ηmaxj=11-ηmax.
Adding all the previous inequalities and by Lemma 2, we have
(51)F1-Fk+1≥∑i=1k+1‍PrediQi+1≥12(1-ηmax)∑i=1k+1‍σiK1∥ci∥min{∥ci∥,Δi}.
By Assumption (A1), we know that F1-Fk+1 is bounded, let k→∞, and we have
(52)+∞>F1-Fk+1≥12(1-ηmax)∑k=1∞‍σ*K1∥ck∥min{∥ck∥,Δk}.
Since ∥ck∥≥ε for all k, we have limk→∞Δk=0. But similar to the proof of Theorem 7, we get Nrk>μ, and therefore we have Δk+1>Δk, which contradicts to limk→∞Δk=0. This contradiction shows that (48) holds.
Next we prove (47). Assume that (47) does not hold, then there exist a subsequence {mj} and a positive constant ε1 such that
(53)∥cmj∥≥ε1.
On the other hand, according to (48) we know that there exists another subsequence {li} such that for ε2=ε1/2, we have
(54)∥ck∥≥ε2mj≤k≤lj,∥clj∥≤ε2.
We define 𝒦={k∣mj≤k≤lj}.  According to Lemma 2, we get the following inequality:
(55)F1-Fk+1≥12(1-ηmax)∑k∈𝒦‍σkK1∥ck∥min{ε2,Δk}.
By Assumption (A1), Fk is bounded, so we have that min{ε2/2,Δj}=ε2/2 can be true only finite number of times. Thus there exists k1>0 such that for j>k1, we have min{ε2/2,Δj}=Δj. Hence for j>k1, we have
(56)∑j∈𝒦,j=k1k‍Δj≤2(1-ηmax)K1K2ε22[F1-minx∈ΩF(x)]<∞.
Then we know that
(57)∑j∈𝒦,j=k∞‍Δj⟶0(k⟶∞).
Now, for large j,
(58)∥xlj-xmj∥≤∑k=mjlj-1‍∥xk+1-xk∥≤∑k=mjlj-1‍Δk<∑k=mj∞‍Δk⟶0.
Since c(x) is continuous, thus for j large enough we have ∥cmj-clj∥<ε2,
(59)∥cmj∥≤∥cmj-clj∥+∥clj∥<2ε2,
and this contradicts to the assumption ∥cmj∥≥2ε2, which means that (47) holds.Theorem 10.
If (A1) holds, we have(60)liminfk→∞∥ZkTgk∥=0.Proof.
Similar to the proof of Theorem  4 in [18].Based on Theorems9 and 10, we get the following global convergence result.Theorem 11.
Under Assumptions (A1)–(A3), we have(61)liminfk→∞∥ZkTgk∥+∥ck∥=0.


## 4. Numerical Tests

In this section, we test our algorithm for some typical problems. The program code was written in MATLAB and run in MATLAB 7.1 environment. The parameters in our algorithm are taken as follows:Δ0=0.1, σ0=1, μ=0.1, c1=0.2, c2=0.8, c3=1.2, ηk≡0.75, and B0=I, and Bk is updated by BFGS formulas as follows:
(62)Bk+1={Bk,ifδkTyk≤0,Bk+ykykTykTδk-BkδkδkTBkδkTBkδk,ifδkTyk>0,
where δk=xk+1-xk, yk=(∇f(xk+1)-A(xk+1)λ(xk+1)-(∇f(xk)-A(xk)λ(xk)). For deciding when to stop the execution of the algorithm declaring convergence we used the criterion ∥ZkTgk∥+∥ck∥≤10-5. We also stop the execution when 500 iterations were completed without achieving convergence and denoted by fail. Our test problems are chosen from [23], and the problems are numbered in the same way as in [23]. For example, HS28 is the problem  28 in [23]. To test the efficiency of our algorithm, we compare our algorithm with the algorithms in [15, 18], where we choose the nonmonotone parameter M=5.The test results are given in Table1: here we use No. to denote the number of the test problems, Ig and If denote the number of gradient estimation and the function value estimation, and Time denotes the CPU time when the algorithm is terminated.Table 1
Test results for our method and the methods in [15, 18].
No.
Our method
The method in [18]
The method in [15]
I
t
/
I
g
Time
I
t
/
I
g
Time
I
t
/
I
g
Time
H28
11/13
0.3438
13/24
0.2652
13/24
0.1404
H39
59/61
1.4688
24/37
0.3432
64/126
0.2625
H42
45/73
0.8281
133/195
0.2652
fail
H47
17/21
0.5625
63/121
0.5460
60/118
0.2964
H48
7/10
0.3125
14/26
0.2340
14/26
0.7488
H49
100/197
2.3750
118/234
0.4524
118/234
0.3144
H50
23/27
0.7344
63/124
0.9360
63/124
0.4212
H51
143/223
2.6094
57/88
0.6084
57/88
1.0764
H52
426/658
7.4844
50/100
0.8112
149/188
1.9812
H63
18/20
0.5469
15/27
0.5928
15/27
0.1404
H77
11/15
0.4063
25/48
1.2324
109/132
3.4788From Table1, we see that our algorithm spend more CPU time than algorithms [15, 18], but we use less function value estimation and gradient value estimation for most of the test problem. These numerical tests show that our algorithm works quiet well.


## 5. Conclusion

In this paper, we presented a nonmonotone trust region method based on the weighted average of the successive penalty values for equality constrained optimization. Compared with the existing nonmonotone trust region methods for constrained optimization, our method is independent on the nonmonotone parameterM. The numerical comparison with some nonmonotone trust region methods shows the efficiency of our proposed method. How to obtain the local fast convergence of our method deserves further study, and we leave it as the future work.



---

*Source: 495378-2013-05-23.xml*