# A Nonmonotone Adaptive Trust Region Method Based on Conic Model for Unconstrained Optimization

Authors: Zhaocheng Cui
Journal: Journal of Optimization
 (2014)

---

## Abstract

We propose a nonmonotone adaptive trust region method for unconstrained optimization problems which combines a conic model and a new update rule for adjusting the trust region radius. Unlike the traditional adaptive trust region methods, the subproblem of the new method is the conic minimization subproblem. Moreover, at each iteration, we use the last and the current iterative information to define a suitable initial trust region radius. The global and superlinear convergence properties of the proposed method are established under reasonable conditions. Numerical results show that the new method is efficient and attractive for unconstrained optimization problems.


---

## Body

## 1. Introduction

In this paper, we consider the following unconstrained optimization problem:(1)min⁡x∈Rnf(x),
where f: Rn→R is a continuously differentiable function.Trust region method is effective for solving (1). In 1970s, Powell [1] established the convergence result of trust region method. Yuan [2], Nocedal, and Yuan [3] proposed various trust region methods for optimization problems. It calculates a trial step by solving the subproblem
(2)min⁡ϕk(d)=gkTd+12dTBkd,s.t.∥d∥≤Δk,
where gk=∇xf(xk) is the gradient of the objective function at xk, Bk∈Rn×n is a symmetric matrix which is either the Hessian matrix of f at xk or an approximation to it, ∥·∥ refers to the Euclidean norm, and Δk>0 is the radius of an area, called the trust region, where the model is trusted. Let dk be the solution of (2). The actual reduction of the objective function is defined by
(3)Aredk=fk-f(xk+dk),
and the predicted reduction of f(x) is defined by
(4)Predk=ϕk(0)-ϕk(dk).
The ratio between these two reductions is defined by
(5)rk=AredkPredk=fk-f(xk+dk)ϕk(0)-ϕk(dk),
and it is normally used to test whether the trial step dk is accepted or the trust region radius needs to be adjusted. The next iterate xk+1 is chosen by the following formula:
(6)xk+1={xk+dkifrk≥η0,xkotherwise,
where η0∈[0,1) is a constant. The next trust region radius is chosen as
(7)Δk+1={c0Δkifrk<η1,c1Δkifrk>η2,Δkotherwise,
where 0≤η1<η2<1, 0<c0<1<c1 are constants. In comparison with quasi-Newton methods, trust region methods converge to a point which not only is a stationary point but also satisfies second-order necessary conditions. Trust region method has strong convergence and robustness, so many authors have studied it; see [4–7]. Conn et al. [8], Nocedal and Wright [9], and Yuan and Sun [10] presented the complete introduction.Recently, Grippo et al. [11] presented the nonmonotone line search method for unconstrained optimization problems. Due to its high efficiency of nonmonotone method, this technique has been combined with trust region methods; we can see [12–16].Sartenaer [17] presented a strategy for determining automatically an initial trust region radius. Fan and Yuan [18] proposed a trust region method with the trust region radius converging to zero. Recently, Zhang et al. [19] gave an adaptive trust region method, and they solve the subproblem (2) with Δk=cp∥gk∥∥B^k-1∥,0<c<1, and p is a nonnegative integer. B^k is a safely positive definite matrix based on Schnabal and Eskow modified Cholesky factorization. Therefore, instead of adjusting Δk, one adjusts p at each iteration. Based on [19] and a simple subproblem model, Sang and Sun [20] proposed another adaptive trust region method with line search. The numerical results show that the adaptive trust region algorithms [21–24] are more effective than traditional trust region methods for unconstrained optimization problems.The adaptive trust region methods listed above are based on quadratic model; however, when the objective function has strong nonquadratic behavior, the quadratic model methods often produce a poor prediction of the minimizer of the function. In 1980, Davidon [25] proposed the conic model methods for unconstrained optimization problems. A typical conic trust region subproblem is as follows:
(8)min⁡φk(s)=gkTs1-αkTs+12sTBks(1-αkTs)2,s.t.1-αkTs>0,∥s∥≤Δk,
where φk(s) is called conic model which is an approximation to f(xk+sk)-f(xk). The vector αk is the associated vector for the collinear scaling in the kth iteration, and it is normally called the horizontal vector. If αk=0, the conic model reduces to a quadratic model. Also, one can see that φk(s) is quadratic along any direction s∈Rn satisfying αkTs=0. Recently, trust region methods based on conic model have been presented and studied; see [26–32]. Numerical results show the efficiency of the conic trust region methods.In the traditional trust region methods, the next trust region radius is updated by the current ratiork, which is reasonable if the matrix Bk is exactly as the Hessian Hk and if the trust region subproblem (2) is solved exactly. However, in practical computations, the matrix Bk is often obtained approximately and the subproblem is solved approximately. In such a case, it may be more reasonable to adjust the next trust region Δk+1 according to not only rk but also the previous ratios {rk-q,…,rk}, where q is some nonnegative integer.In order to measure the agreement between the model function and the objective function, we define the following ratio:(9)r^k=∑i=0min⁡{k,q}‍ωkirk-i,
where ωki∈[0,1] is the weight of rk-i, such that
(10)∑i=0min⁡{k,q}‍ωki=1.In this paper, we propose a new adaptive trust region method which combines the conic model and nonmonotone technique which was given in [33] and a new update rule for adjusting the trust region radius. Our method is different from other adaptive trust region methods in three points. First, the subproblem is conic model which can produce a better prediction of the minimizer of the function than quadratic model methods when the objective function has strong nonquadratic behavior. Second, at each iteration, our method generates a suitable trust region radius automatically based on the current and last iterative information. Last, we use a new update rule (8) to adjust the next trust region radius. The new trust region model is more consistent with the objective function at the current iterative point. According to the nonmonotone technique in [33], our method constructs an iterative series {xk} such that the sequence {f(xk)} is not monotonic, which can accelerate the convergence rate of the minimization process, especially in the narrow curved valley. The global and superlinear convergence properties of the proposed method are proved under reasonable conditions. The numerical results show that the new method is more effective than other trust region methods.The rest of this paper is organized as follows. In next section, we describe a new nonmonotone adaptive trust region method based on conic model for unconstrained optimization problems. In Sections3 and 4, we prove the global and superlinear convergence properties of the proposed method under reasonable conditions, respectively. Some numerical results are given in Section 5. Conclusions are summarized in Section 6.


## 2. Algorithm Description

In this section, we describe a new nonmonotone adaptive trust region method based on conic model for unconstrained optimization problems.We obtain the trial stepsk by solving the following subproblem:
(11)min⁡φk(s)=gkTs1-αkTs+12sTBks(1-αkTs)2,s.t.1-αkTs>0,∥s∥≤Δk,
where Δk=μk(∥sk-1∥2/sk-1TB^ksk-1)∥gk∥, Δ0=μ0∥g0∥, μ0>0. μk is updated according to (8), sk-1 is the solution of the last subproblem. B^k is generated by the procedure sk-1TB^ksk-1=sk-1TBksk-1+i∥sk-1∥2 and i is the smallest nonnegative integer such that
(12)sk-1TB^ksk-1=sk-1TBksk-1+i∥sk-1∥2>0.
The new reduction of f(x) is defined by
(13)Aredk=Mk-f(xk+sk),
where
(14)Mk=max⁡{f(xk),∑r=0m(k)-1‍λkrf(xk-r)},λ∈(0,1],m≥1 is a positive integer. We define m(k)=min⁡{k+1,m} and choose
(15)λkr≥λ,r=0,1,…,m(k)-1,∑r=0m(k)-1‍λkr=1.
The predicted reduction of f(x) is
(16)Predk=-gkTsk1-αkTsk-12skTBksk(1-αkTsk)2.
The new ratio rk is defined by
(17)rk=AredkPredk.In what follows, we describe our new nonmonotone adaptive trust region method based on conic model.Algorithm 1 (nonmonotone adaptive trust region method based on conic model).
Consider the following.
Step
0
. Given x0∈Rn, B0∈Rn×n is a symmetric positive definite matrix, ɛ>0, μ0>0, Δ0=μ0∥g0∥, 0<λ≤1, 0<η0<η1<1, 0<c0<1<c1, and an integer constant m≥1; set m(0)=0, k:=0.
Step
1
. Compute gk. If ∥gk∥<ɛ, then stop. Otherwise, go to Step 2.
Step
2
. Solve the subproblem (11) and let sk be an approximate solution of the subproblem (11).
Step
3
. Compute Aredk,Predk, and rk.
Step
4
. If rk<η0, set μk:=c0μk and go to Step 2. Otherwise, go to Step 5.
Step
5
. Choose ωki∈[0,1] that satisfying (9). Compute r^k and, by (8), set xk+1=xk+sk and
(18)μk+1={c1μkifη1≤r^k,μkifη0≤r^k<η1.
Step
6
. Update αk+1,m(k+1), and the symmetric matrix Bk+1. Let Δk+1=μk+1(∥dk∥2/dkTB^k+1dk)∥gk+1∥ and set k:=k+1 and go to Step 1.Remark 2.
In Algorithm1, we define a new reduction of f(x) which is different from the actual reduction fk-f(xk+sk) in other methods. Instead of requiring fk+1 to be smaller than fk, it is only required that fk+1 is either less than fk or less than the weighted mean of the function values at the last m(k) iterates.Remark 3.
How to choose the horizontal vectorαk and the approximate Hessian matrix Bk is one of the crucial issues of a conic model method. More details for generating αk and Bk can be found in [25]. If αk=0, Algorithm 1 reduces to the quadratic model trust region method. If we choose m=1, we obtain a monotonic adaptive trust region method. Hence, Algorithm 1 is a generalization and development of quadratic model trust region method and monotonic trust region method.Remark 4.
“Step 2-Step 3-Step 4" are called the internal circulation.


## 3. Convergence Analysis

In this section we discuss the global convergence of Algorithm1. Before we address some theoretical issues, we would like to give the following assumptions.Assumption 5.
(
i
) The level set L(x0)={x∈Rn∣f(x)≤f(x0)} is bounded for any given x0∈Rn and f(x) is twice continuously differentiable in L(x0). (ii) The sequences {Bk} and {αk} are uniformly bounded; that is, there exist two positive scalars M1,M2 such that ∥Bk∥≤M1 and ∥αk∥≤M2 hold for all k.  (iii) There exists a positive constant σ∈(0,1), such that ∥αk∥Δk≤σ.
It is similar to Theorem  3.1 in [28], and we can prove the following lemma.Lemma 6.
Suppose that Assumption5 holds. Then, there exists a scalar β∈(0,1) such that
(19)Predk≥β∥gk∥min⁡{Δk,∥gk∥∥Bk∥}≥β∥gk∥min⁡{∥sk∥,∥gk∥∥Bk∥}
holds for all k, where sk is an inexact solution of the subproblem (11).Lemma 7.
Suppose that Assumption5 holds. Then,
(20)|f(xk)-f(xk+sk)-Predk|≤O(∥sk∥2),
where sk is the solution of (11) and is sufficiently close to zero.Proof.
Since{∥αk∥} is bounded, we can have 1/(1-αkTsk)=1+O(∥sk∥). Then, from the boundedness of {∥gk∥} and {∥Bk∥}, we obtain
(21)gkTsk1-αkTsk=gkTsk+O(∥sk∥2),skTBksk(1-αkTsk)2=skTBksk+O(∥sk∥2).
By f(x) which is twice continuously differentiable in L(x0), there exists M3>0 such that ∥H(x)∥≤M3 holds for all Hessian H(x) and all x∈L(x0).
Therefore, we have that(22)|f(xk)-f(xk+sk)-Predk|=|f(xk)-f(xk+sk)+gkTsk1-αkTsk+12skTBksk(1-αkTsk)2|=|-gkTsk-12skTH(xk+θksk)sk+gkTsk+12skTBksk+O(∥sk∥2)|≤12(M1+M3)∥sk∥2+O(∥sk∥2)=O(∥sk∥2).
This completes the proof.Lemma 8.
Suppose that Assumption5 holds. Then, Algorithm 1 is well defined; that is, Algorithm 1 can not cycle infinitely in the internal circulation.Proof.
Suppose that Algorithm1 cycles infinitely many times between Steps 2 and 4 at the current point xk. We denote the solution of the conic model (11) by sk(i) and the corresponding predicted reduction by Predk(i) with the cycling index i. Then, we have
(23)rk(i)<η0,i=0,1,2,…(24)Δk(i)=c0iΔk⟶0,i⟶∞.
From Lemmas6 and 7, we can have
(25)|fk-f(xk+sk(i))Predk(i)-1|=|fk-f(xk+sk(i))-Predk(i)Predk(i)|≤O(∥sk(i)∥2)Predk(i)≤O(Δk(i)2)β∥gk∥min⁡{Δk(i),∥gk∥/∥Bk∥}⟶0,asi⟶∞.
Hence, the following
(26)fk-f(xk+sk(i))Predk(i)≥η0
holds for i sufficiently large. From Mk≥fk, we obtain that
(27)rk(i)=Mk-f(xk+sk(i))Predk(i)≥η0,
holds for i sufficiently large, which contradicts with (23). The proof is completed.In the next lemma, an important decrease property of the function valuef(xk) is established.Lemma 9.
Suppose that Assumption5 holds and {xk} is generated by Algorithm 1. Then, there exists a constant τ>0 such that the following
(28)f(xk)≤f(x0)-τλ∑r=0k-2‍∥gr∥min⁡{Δr,∥gr∥∥Br∥}-τ∥gk-1∥min⁡{Δk-1,∥gk-1∥∥Bk-1∥}
holds for k≥1.Proof.
We prove it by induction. For simplicity, we denote(29)βk=∥gk∥min⁡{Δk,∥gk∥∥Bk∥}.
(
1
) If k=1, by r0≥η0, M0=f0, and Lemma 6, we have
(30)f(x1)≤f(x0)-η0(φ0(0)-φ0(s0))≤f(x0)-η0β∥g0∥min⁡{Δ0,∥g0∥∥B0∥}=f(x0)-τ∥g0∥min⁡{Δ0,∥g0∥∥B0∥},
where τ=η0β.
(
2
) Now, we assume that it holds for 1,2,…,k, and we consider two cases.Case 1.
IfMk=f(xk), by rk+1≥η0, 0<λ≤1, and Lemma 6, then we have
(31)f(xk+1)=f(xk+sk)≤f(xk)-η0(φk(0)-φk(sk))≤f(x0)-τλ∑r=0k-2‍βr-τβk-1-η0ββk≤f(x0)-τλ∑r=0k-1‍βr-τβk.Case 2.
M
k
=
∑
r
=
0
m
(
k
)
-
1
‍
λ
k
r
f
(
x
k
-
r
). Let q=min⁡[k,m-1], by rk+1≥η0, 0<λ≤1, and Lemma 6. Then, we have
(32)f(xk+1)=f(xk+sk)≤∑p=0q‍λkpf(xk-p)-η0(φk(0)-φk(sk))≤∑p=0q‍λkp(f(x0)-τλ∑r=0k-p-2‍βr-τβk-p-1)-η0(φk(0)-φk(sk)).
Using (0,1,2,…,q)×(0,1,2,…,k-p-2)⊂{(p,r);0≤p≤q,0≤r≤k-p-2}, λkp≥λ, ∑p=0q‍λkp=1, we have
(33)f(xk+1)≤f(x0)-τλ∑r=0k-q-2‍(∑p=0q‍λkp)βr-τ∑p=0q‍λkpβk-p-1-τβk≤f(x0)-τλ∑r=0k-q-2‍βr-τλ∑r=k-q-1k-1‍βr-τβk≤f(x0)-τλ∑r=0k-1‍βr-τβk.Lemma 10.
Suppose that the conditions in Lemma9 hold. Then, {xk}⊂L(x0).Proof.
By Lemma9, f(xk)≤f(x0)-τλ∑r=0k-1‍∥gr∥min⁡{Δr,∥gr∥/∥Br∥}≤f(x0), the conclusion holds obviously.
Now, we prove the global convergence of Algorithm1.Theorem 11.
Suppose that Assumption5 holds. If ɛ=0, Algorithm 1 either terminates in finite iterations or generates an infinite sequence {xk} which satisfies
(34)liminf⁡k→∞∥gk∥=0.Proof.
If Algorithm1 terminates in finite iterations, the theorem is obviously true. Assume that Algorithm 1 generates an infinite sequence {xk} in the following proof.
If (34) is not true, then there exists a positive constant ε0, such that
(35)∥gk∥≥ε0,∀k.
From Lemma 9, 0<λ≤1, and ∥gk∥≥ε0, we can have
(36)f(xk)≤f(x0)-τλε0∑r=0k-1‍min⁡{Δr,ε0∥Br∥}.
By Assumption 5(ii), we can obtain
(37)τλε0∑r=0k-1‍min⁡{Δr,ε0M1}≤f(x0)-f(xk).
Therefore, by Assumption 5(i), we have
(38)∑k=0∞‍Δk<∞.
Thus, we can obtain
(39)lim⁡k→∞Δk=0.
By Assumption 5(ii), then ∥B^k∥≤2M1+1. From Algorithm 1, we know that
(40)Δk=μk∥sk-1∥2sk-1TB^ksk-1∥gk∥≥μk∥sk-1∥2(2M1+1)∥sk-1∥2ε0=μkε02M1+1.
By (39) and (40), we obtain
(41)lim⁡k→∞μk=0.
On the other hand, we have from Lemma6 that
(42)|fk-f(xk+sk)Predk-1|=O(∥sk∥)+O(∥sk∥2∥Bk∥)Predk≤O(∥sk∥)+O(∥sk∥2∥Bk∥)β∥gk∥min⁡{Δk,∥gk∥/∥Bk∥}≤O(∥sk∥)Δk⟶0.
The above inequality implies that
(43)rk=Mk-f(xk+sk)Predk≥fk-f(xk+sk)Predk≥η0
holds for k sufficiently large. Hence, there exists a positive constant μ* such that
(44)μk≥μ*.
holds for all sufficiently large k, which contradicts with (41). The proof is completed.


## 4. Superlinear Convergence

In general, the superlinear convergence property of Algorithm1 requires further assumptions, we give the assumptions and the superlinear convergence property in the following theorem.Theorem 12.
Suppose that Assumption5 holds and Algorithm 1 generates an infinite sequence {xk} which converges to x*, where H(x*) is positive definite and H(x) is Lipschitz continuous in a neighborhood of x*. If the following condition holds
(45)lim⁡k→∞∥gk+H(x*)sk∥∥sk∥=0,
then the rate of convergence is superlinear; that is, ∥xk+1-x*∥=o(∥xk-x*∥).Proof.
Fromxk→x*, we can have lim⁡k→∞∥sk∥=0. By the Taylor expansion, we can obtain
(46)gk+1=gk+∇2f(xk+θksk)sk=gk+H(x*)sk+(∇2f(xk+θksk)-H(x*))sk,
where θk∈(0,1).
So,(47)∥gk+1∥≤∥gk+H(x*)sk∥+∥∇2f(xk+θksk)-H(x*)∥·∥sk∥.
Dividing both sides by ∥sk∥, we get
(48)∥gk+1∥∥sk∥≤∥gk+H(x*)sk∥∥sk∥+∥∇2f(xk+θksk)-H(x*)∥.
By (45), ∥sk∥→0, and Lipschitz continuous property of H(x), we can have
(49)lim⁡k→∞∥gk+1∥∥sk∥=0.
ByH(x*) which is positive definite, and f which is a twice continuously differentiable function, there exists β>0, such that
(50)β∥xk+1-x*∥≤∥gk+1∥
for sufficiently large k.
By (49) and (50), it follows that
(51)∥gk+1∥∥sk∥≥β∥xk+1-x*∥∥sk∥≥β∥xk+1-x*∥∥xk+1-xk∥≥β∥xk+1-x*∥∥xk+1-x*∥+∥xk-x*∥=β∥xk+1-x*∥/∥xk-x*∥1+(∥xk+1-x*∥/∥xk-x*∥),
and thus
(52)lim⁡k→∞∥xk+1-x*∥∥xk-x*∥=0,
which implies that the sequence {xk} converges to x* superlinear.


## 5. Numerical Results

In this section, we compare the performance of Algorithm1, denoted by NACTR, with NAQTR if αk=0 for all k in Algorithm 1, MACTR if m=1 in Algorithm 1, CTR method which is a conic trust region algorithm without adaptive technique, and QTR method which is the traditional trust region method without adaptive technique. All programs are written in MATLAB with double precision.For these methods, the trial stepsk is computed approximately by the algorithm proposed by Lu and Ni in [34] for solving the subproblem (11). B0 is chosen as the identity matrix. The parameters in our algorithm are chosen as η0=0.25, η1=0.7, c0=0.25, c1=1.5, λkr=1/m(k), (r=0,1,…,m(k)-1), m=4, and α0=0. In our implementation, we prefer the following choice
(53)r^k=0.85rk+0.15r^k-1,
where r^0=r0.The stopping condition is(54)∥gk∥≤10-4.The iteration is also terminated if the number of evaluations exceeds 300.We provide the results of our tests in Table1. The numerical results are given in the form of Ni,Nf, where Ni,Nf denote the numbers of iterations and function evaluations, respectively. We chose the test problems from [35]. From Table 1, we can see that, in most of the problems considered, the numbers Ni and Nf for the conic model methods are considerably smaller than those required for the quadratic model methods, especially for those functions with strong nonquadratic behavior. This means that the conic model methods are very effective to many unconstrained optimization. Compared with the methods without adaptive technique, the adaptive trust region methods are more attractive. Hence, our new nonmonotone adaptive conic trust region method is an improvement of the existing trust region methods.Table 1
Numerical comparisons.
Problems
QTR
CTR
NAQTR
MACTR
NACTR
N
i
/
N
f
N
i
/
N
f
N
i
/
N
f
N
i
/
N
f
N
i
/
N
f
Helical Valley
62/74
43/53
56/61
32/45
29/42
Gaussian
7/12
3/8
3/5
3/5
3/5
Box 3-D
41/45
33/37
36/41
30/35
30/33
Var. Dimen.
17/26
11/11
18/27
12/18
13/21
Waston
72/78
66/73
62/81
54/98
48/86
Penalty I
18/21
16/17
18/24
15/20
15/18
Penalty II
21/26
21/24
23/31
17/26
16/25
Brown-Dennis
62/66
78/84
62/75
55/67
53/58
Gulf R.D.
88/83
96/98
66/46
38/42
46/47
Trigonometric
46/52
38/39
45/48
32/39
34/36
Ex. Ros.
91/124
Failed
48/62
33/46
35/48


## 6. Conclusions

In this paper, we propose a new nonmonotone adaptive conic model trust region method for unconstrained optimization. The global and superlinear convergence properties of the new method are proved under reasonable conditions. Our method is attractive in the following aspects. First, the subproblem is conic model which can produce a better prediction of the minimizer of the function than quadratic model methods when the objective function has strong nonquadratic behavior. Second, at each iteration, our method generates a suitable trust region radius automatically based on the current and last iterative information. Last, we use a new update rule (8) to adjust the next trust region radius. According to the nonmonotone technique in [33], our method constructs an iterative series {xk} such that the sequence {f(xk)} is not monotonic, which can accelerate the convergence rate of the minimization process, especially in the narrow curved valley. Numerical results show that the new method is efficient for unconstrained optimization problems.



---

*Source: 237279-2014-01-27.xml*