# A Derivative-Free Trust Region Algorithm with Nonmonotone Filter Technique for Bound Constrained Optimization

Authors: Jing Gao; Jian Cao; Yueting Yang
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

We propose a derivative-free trust region algorithm with a nonmonotone filter technique for bound constrained optimization. The derivative-free strategy is applied for special minimization functions in which derivatives are not all available. A nonmonotone filter technique ensures not only the trust region feature but also the global convergence under reasonable assumptions. Numerical experiments demonstrate that the new algorithm is effective for bound constrained optimization. Locally, optimal parameters with respect to overall computational time on a set of test problems are identified. The performance of the best choice of parameter values obtained by the algorithm we presented which differs from traditionally used values indicates that the algorithm proposed in this paper has a certain advantage for the nondifferentiable optimization problems.


---

## Body

## 1. Introduction

Many of the objective functions in mathematical optimization that occur in engineering are obtained from a mass of numerical experiments and have special characteristics such as being nonconvex for which their first-order or second-order derivatives are unavailable. In this paper, we analyze the solution of the nonlinear problem with bound constraints:(1a)minfx(1b)subjecttox∈Ω,where Ω={x∈Rn∣l≤x≤u} and f(x):Ω⊂Rn→R is a twice continuously differentiable function, but its first-order or second-order derivatives are not explicitly available. It mainly emerges in the field of operations research, management science, industrial engineering, applied mathematics, and network transmission [1] and in engineering disciplines that deal with analytical optimization techniques such as banking business and weather analysis. The unavailable first- or second-order derivatives may result in traditional derivative-based methods like quasi-Newton methods and conjugate gradient methods are not work. Therefore, researches focus on derivative-free methods which could effectively avoid the use of derivative information.


### 1.1. Derivative-Free Trust Region Method

Derivative-free technique has been explored to tune parameters of nonlinear optimization methods [2], to automatic error analysis [3, 4] and to design helicopter rotor blade [5, 6] and hydrodynamic [7]. These methods are all special algorithms designed for particular optimizations, but have their usage limitations. In [8–12] another type of derivative-free methods is proposed based on the traditional derivative-based algorithm framework [8, 13–15]. They construct a function with all available derivatives to approximate the original objective function. Conn and Scheinberg and Vicente [8, 13] have already given a derivative-free method under trust region method framework. They construct the trust region subproblem(2)mkxk+p=mkxk+qmkp=mkxk+gkTp+12pTHmkp,where mk(xk) is the function value at kth iteration point, gk is the gradient of mk(xk+p) at kth iteration point, and Hmk is the Hessian. Although the function model and the true objective function are meant to coincide the model gradients and Hessian may be (and typically are) different from the original objective function gradient ∇fk and Hessian Hfk, function (2) defined in [8] is calledfully linear orfully quadratic model, dependent upon the related chosen truncated Taylor series conditions; it must be occasionally updated in order to guarantee that the residual between the approximated and real functions (and more critically, their gradients) is within the related error bounds. In fact, by definition, the function values are essentially the same. We will show the definition offully linear model after a reasonable assumption.Assumption (A1). Suppose that a level set L(x0) and a maximal radius Δmax are given. Suppose furthermore that f is twice continuously differentiable with Lipschitz continuous Hessian in an appropriate open domain containing the Δmax neighborhood ⋃x∈L(x0)B(x,Δmax) of the set L(x0).Definition 1.
Let a functionf, which satisfies assumption (A1), be given. A set of model functions M=m:Rn→R,m∈C2 is called a fully linear class of models if the following hold.
There exist positive constantsκef, κeg, and κblg, such that, for any x∈L(x0), Δ∈(0,Δmax]. There is a model function m(x+p) in M, with Lipschitz continuous gradient and corresponding Lipschitz constant bounded by κblg, such that
(1) the error between the gradient of the model and the original objective function satisfies(3)∇fx+p-∇mx+p≤κegΔ,∀p∈B0,Δ,
(2) the error between the model and the original objective function satisfies(4)fx+p-mx+p≤κefΔ2,∀p∈B0,Δ.Such a model m is called fully linear on B(x,Δ).Remark 2.
For this classM there exists an algorithm which we will call a model-improvement algorithm that, in a finite, uniformly bounded (with respect to x and Δ) number of steps can(1)
either establish that a given modelm∈M is fully linear on B(x,Δ)(we will say that a certificate has been provided and the model is certifiably fully linear)(2)
or find a modelm~∈M that is fully linear on B(x,Δ).


### 1.2. Affine-Scale Trust Region Method for Bound Constrained Optimization

Since we analyze the bound constrained optimization (1a) and (1b), the trust region subproblem is(5)minqmkpsubjecttol≤xk+p≤u,p∞≤Δk.As the solution of subproblem (5), pk induces following decrease:(6)Predkpk=-qmkpk≥κ1χmkmin⁡1,Δk,χmkwith constant κ1>0 independent of k. Hereby, the norm of the projected gradient(7)χmk=xk-PXxk-gk=g^xkis a suitably chosen criticality measurement. In order to obtain a relatively short and elegant convergence result, we describe a concrete implementation by means of a Cauchy step that is defined by an affine-scaled gradient used here have stronger smoothness properties. Similar approaches can be found in [16–18]. Define the diagonal affine-scaling matrix Dmk(x)∈Rn×n as(8)Dmkxii=1,li=-∞andui=+∞,min⁡xi-li+γmax⁡κD,-gki,ui-xi+γmax⁡κD,gki,otherwise,where κD>0 and γ>0 are given constants and (gk)i is the ith component of the gradient of mk(xk+p). Solve the subproblem(9)minqmkpsubjecttop=-tDmkxk2gkt≥0,p∈Xk=l-xk,u-xk∩-Δk,Δkn.Following the idea of [18], we are able to prove that the solution of this quadratic model (9) also satisfies the decrease (6).


### 1.3. Nonmonotone Filter Technique

The filter method was first introduced for constrained nonlinear optimization by Fletcher and Leyffer [19] and then it has a wide range of applications in various optimization problems; see [18, 20–23]. In 2005, the filter method has been extended into a filter trust region method by Gould et al [24] for unconstrained optimization and by Sainvrtu [25] for general box constrained optimization. They indicate that the filter method is a reliable and efficient way for nonlinear optimizations. In this paper, we will make a further study on nonmonotone filter method and propose a new algorithm for (1a) and (1b). The main features of this paper are as follows:(i)
We present a further extension of that filter trust region method by introducing both a suitable nonmonotonicity criterion and a derivative-free strategy for bound constrained optimization.(ii)
The global convergence of the presented derivative-free trust region method with the nonmonotone filter technique for bound constrained optimization is established.(iii)
Numerical results indicate that the new algorithm is effective for problems for which the derivative functions are unavailable.The paper is therefore in the following way: we present our algorithmic scheme in Section2. There we first show that the decrease direction described in this paper satisfies the predicted decrease inequality and recall the nonmonotone trust region method from [18, 26] and then make the necessary modifications for a derivative-free version. The global convergence properties of the derivative-free trust region method with nonmonotone filter technique is shown in Section 3. The corresponding numerical results are reported in Section 4 together with some additional tests. Finally, conclusions and further discussions are given.Notation. Unless otherwise specified, throughout this paper, the norm ‖·‖ is the 2-norm for a vector and the induced 2-norm for a matrix. Let B denote a closed ball in Ω⊂Rn and B(x,Δ) denote the closed ball centered at x, with radius Δ>0. In addition, L(x0)=x∈Ω∣f(x)≤f(x0) is the level set about f. We use the subscript fk and subscript mk to distinguish the relevant information between the original function and the approximate function; for example, χfk is the criticality measurement of f(xk) and χmk is the criticality measurement of mk(xk+p). xk+ is the trial step in kth iteration. gk+ and Hmk+ is the gradient and Hessian of the trial step, respectively.


## 1.1. Derivative-Free Trust Region Method

Derivative-free technique has been explored to tune parameters of nonlinear optimization methods [2], to automatic error analysis [3, 4] and to design helicopter rotor blade [5, 6] and hydrodynamic [7]. These methods are all special algorithms designed for particular optimizations, but have their usage limitations. In [8–12] another type of derivative-free methods is proposed based on the traditional derivative-based algorithm framework [8, 13–15]. They construct a function with all available derivatives to approximate the original objective function. Conn and Scheinberg and Vicente [8, 13] have already given a derivative-free method under trust region method framework. They construct the trust region subproblem(2)mkxk+p=mkxk+qmkp=mkxk+gkTp+12pTHmkp,where mk(xk) is the function value at kth iteration point, gk is the gradient of mk(xk+p) at kth iteration point, and Hmk is the Hessian. Although the function model and the true objective function are meant to coincide the model gradients and Hessian may be (and typically are) different from the original objective function gradient ∇fk and Hessian Hfk, function (2) defined in [8] is calledfully linear orfully quadratic model, dependent upon the related chosen truncated Taylor series conditions; it must be occasionally updated in order to guarantee that the residual between the approximated and real functions (and more critically, their gradients) is within the related error bounds. In fact, by definition, the function values are essentially the same. We will show the definition offully linear model after a reasonable assumption.Assumption (A1). Suppose that a level set L(x0) and a maximal radius Δmax are given. Suppose furthermore that f is twice continuously differentiable with Lipschitz continuous Hessian in an appropriate open domain containing the Δmax neighborhood ⋃x∈L(x0)B(x,Δmax) of the set L(x0).Definition 1.
Let a functionf, which satisfies assumption (A1), be given. A set of model functions M=m:Rn→R,m∈C2 is called a fully linear class of models if the following hold.
There exist positive constantsκef, κeg, and κblg, such that, for any x∈L(x0), Δ∈(0,Δmax]. There is a model function m(x+p) in M, with Lipschitz continuous gradient and corresponding Lipschitz constant bounded by κblg, such that
(1) the error between the gradient of the model and the original objective function satisfies(3)∇fx+p-∇mx+p≤κegΔ,∀p∈B0,Δ,
(2) the error between the model and the original objective function satisfies(4)fx+p-mx+p≤κefΔ2,∀p∈B0,Δ.Such a model m is called fully linear on B(x,Δ).Remark 2.
For this classM there exists an algorithm which we will call a model-improvement algorithm that, in a finite, uniformly bounded (with respect to x and Δ) number of steps can(1)
either establish that a given modelm∈M is fully linear on B(x,Δ)(we will say that a certificate has been provided and the model is certifiably fully linear)(2)
or find a modelm~∈M that is fully linear on B(x,Δ).


## 1.2. Affine-Scale Trust Region Method for Bound Constrained Optimization

Since we analyze the bound constrained optimization (1a) and (1b), the trust region subproblem is(5)minqmkpsubjecttol≤xk+p≤u,p∞≤Δk.As the solution of subproblem (5), pk induces following decrease:(6)Predkpk=-qmkpk≥κ1χmkmin⁡1,Δk,χmkwith constant κ1>0 independent of k. Hereby, the norm of the projected gradient(7)χmk=xk-PXxk-gk=g^xkis a suitably chosen criticality measurement. In order to obtain a relatively short and elegant convergence result, we describe a concrete implementation by means of a Cauchy step that is defined by an affine-scaled gradient used here have stronger smoothness properties. Similar approaches can be found in [16–18]. Define the diagonal affine-scaling matrix Dmk(x)∈Rn×n as(8)Dmkxii=1,li=-∞andui=+∞,min⁡xi-li+γmax⁡κD,-gki,ui-xi+γmax⁡κD,gki,otherwise,where κD>0 and γ>0 are given constants and (gk)i is the ith component of the gradient of mk(xk+p). Solve the subproblem(9)minqmkpsubjecttop=-tDmkxk2gkt≥0,p∈Xk=l-xk,u-xk∩-Δk,Δkn.Following the idea of [18], we are able to prove that the solution of this quadratic model (9) also satisfies the decrease (6).


## 1.3. Nonmonotone Filter Technique

The filter method was first introduced for constrained nonlinear optimization by Fletcher and Leyffer [19] and then it has a wide range of applications in various optimization problems; see [18, 20–23]. In 2005, the filter method has been extended into a filter trust region method by Gould et al [24] for unconstrained optimization and by Sainvrtu [25] for general box constrained optimization. They indicate that the filter method is a reliable and efficient way for nonlinear optimizations. In this paper, we will make a further study on nonmonotone filter method and propose a new algorithm for (1a) and (1b). The main features of this paper are as follows:(i)
We present a further extension of that filter trust region method by introducing both a suitable nonmonotonicity criterion and a derivative-free strategy for bound constrained optimization.(ii)
The global convergence of the presented derivative-free trust region method with the nonmonotone filter technique for bound constrained optimization is established.(iii)
Numerical results indicate that the new algorithm is effective for problems for which the derivative functions are unavailable.The paper is therefore in the following way: we present our algorithmic scheme in Section2. There we first show that the decrease direction described in this paper satisfies the predicted decrease inequality and recall the nonmonotone trust region method from [18, 26] and then make the necessary modifications for a derivative-free version. The global convergence properties of the derivative-free trust region method with nonmonotone filter technique is shown in Section 3. The corresponding numerical results are reported in Section 4 together with some additional tests. Finally, conclusions and further discussions are given.Notation. Unless otherwise specified, throughout this paper, the norm ‖·‖ is the 2-norm for a vector and the induced 2-norm for a matrix. Let B denote a closed ball in Ω⊂Rn and B(x,Δ) denote the closed ball centered at x, with radius Δ>0. In addition, L(x0)=x∈Ω∣f(x)≤f(x0) is the level set about f. We use the subscript fk and subscript mk to distinguish the relevant information between the original function and the approximate function; for example, χfk is the criticality measurement of f(xk) and χmk is the criticality measurement of mk(xk+p). xk+ is the trial step in kth iteration. gk+ and Hmk+ is the gradient and Hessian of the trial step, respectively.


## 2. The Derivative-Free Trust Region Algorithm with Nonmonotone Filter Technique

We analyze the behaviors of subproblem (9) with the diagonal matrix defined by (8). Let χmk denote the criticality measurement such that(10)κ2χmk≤Dmkxkgxkholds on Xk for some κ2>0. Fraction of Cauchy decrease condition defined as(11)qmkpk≤αqmkpkc,where α∈(0,1) is a constant and qmk(pkc)=qmk(t∗dk)=min⁡{qmk(tdk):t≤0,tdk∈Xk} with dk=Dmk(xk)gk. It is not difficult to prove that both ‖Dmk(x)g(x)‖ and χmk are criticality measurement, i.e., satisfying that χmk=0 if and only if x is the KKT point of problem (1a) and (1b). Furthermore, if g(x) is bounded and uniformly continuous on (l,u), then ‖Dmk(x)g(x)‖ is uniformly continuous. The proof is similar to Lemma 6.1 and Lemma 6.2 in [18] except that we now have to replace ∇h(x) by the approximated gradient gk. In order to discuss the global convergence we first provide the following lemma to show that the decrease direction pk satisfies the predicted decrease inequality (6).Lemma 3.
Suppose that criticality measurementχmk satisfies (10). If χmk≠0 and if the trial step xk+pk satisfies the fraction of Cauchy decrease condition (11), then (6) holds.Proof.
Considering thatdk=Dmk(xk)gk and qmk(pkc) is defined above, firstly we obtain from following inequality that dk is a decrease direction of qmk(x) at 0, that is,(12)∇qmk0Tdk=gkTdk=-Dmkxkgxk2≤-κ22χmk2<0.In the case that the maximum stepsize is determined by the trust region constraint t‖dk‖≤Δk, we obtain (13)t1=min⁡Δkdki;dki≠0≥ΔkDmkxkiiDmkxkiigk≥ΔkγκDDmkxkgk.In the case that the maximum stepsize is determined by the lower bounds of the set Xk, then(14)t2=min⁡xk-lidki;dki<0=min⁡xk-liDmkxkiiDmkxkgki;gki>0,xki>li≥min⁡xk-limin⁡κD,xi-liDmkxkgk;gki>0,xki>li≥κDDmkxkgk.In the same way, the stepsize t3 admitted by the upper bounds of the set Xk can be estimated:(15)t3=min⁡u-xkidki;dki<0≥κDDmkxkgk.In the case Dmk(xk)HmkDmk(xk)=0, we set t4=+∞. Otherwise, in the case that Dmk(xk)HmkDmk(xk) positive definition as well as ‖Hmk‖ less than a constant κH, the function qm(tdk),t≥0, attains its global minimum at t=t4, where(16)t4=-2gkTdkdkTHmkdk≥2Dmkxkgxk2Dmkxkgxk2DmkxkHmkDmkxk≥2γ2κD2κH.We have t∗=min⁡{t1,t2,t3,t4}. If t∗<t4, then ‖Dmk(xk)g(xk)‖2>1/2‖dkTHmkdk‖, and if dkTHmkdk>0 then(17)qmkt∗dk=-t∗Dmkxkgxk2+t∗22dkTHmkdk<-t∗2Dmkxkgxk2=-min⁡t1,t2,t32Dmkxkgxk2.If dkTHmkdk≤0, then(18)qmkt∗dk=-t∗Dmkxkgxk2+t∗22dkTHmkdk≤-t∗Dmkxkgxk2.If, on the other hand, t∗=t4, then(19)qmkxk=-t42Dmkxkgxk2.Combining with the assumptions (10) and (11), the conclusion is obtained.There are two criteria in the proposed algorithm, to measure if the trial stepxk+=xk+pk is acceptable. One is in the trust region method. The new algorithm is based on a nonmonotone decrease criterion. Nonmonotone trust region methods were investigated by Toint [26] and Ulbrich [18]. Let the increasing sequence (ji)i≥0 enumerate all indices of accepted steps. Moreover,(20)xk=xji,∀ji-1<k≤ji,∀i≥1.Conversely, if k≠ji for all i, then pk was rejected. In the following we introduce the set of all these “successful” indices ji by S:(21)S=ji:i≥0=k;trial  stepxk+pkis  accepted.We follow [18] to choose integer l, m≥0, fix λ∈(0,1/m], and then compare the predicted decrease promised by the trust region model with a relaxation of the actual decrease(22)Raredkpk=max⁡fxk,∑r=0lk-1λkrfxji-r-fxk+,whereλkr≥λ,lk=min⁡i+1,l,r=0,1,…,lk-1and∑r=0lk-1λkr=1for the computation of reduction ratio ρk=Raredk(pk)/Predk(pk) in order to decide whether a step is acceptable or not. The idea behind the update rule (22) is the following: instead of requiring that f(xk+) be smaller than f(xk), it is only required that f(xk+) is either less than f(xk) or less than the weighted mean of the function values at the last lk=min⁡{i+1,l} successful iterates. Of course, if l=1, then Raredk(p)=Aredk(p) and the usual reduction ratio is recovered. Our approach is a slightly stronger requirement than the straightforward idea to replace Aredk(p) with max0≤r<lk⁡f(xji-r)-f(xk+p). Unfortunately, for this latter choice it does not seem be possible to establish all the global convergence results that are available for the monotone case. For our approach, however, this is possible without making the theory substantially more difficult.The other criterion is in the filter step. We prefer a filter mechanism to assess the suitability ofxk+. Our strategy is inspired by that of [24]: we decide that a trial point xk+ is acceptable for the filter F if and only if(23)∀g^l∈F∃j∈1,…,n:g^jxk+<g^l,j-γg^g^l,where γg^∈(0,1/n) is a small positive constant and g^l,j=g^j(xl).Aiming to solve the nonlinear optimization with unavailable first- (or second-) order derivatives and to guarantee reliable and efficient numerical performance, we now state following derivative-free trust region method.Algorithm 4 (a derivative-free trust region method with nonmonotone filter technique).
⁡
Initialization Step. Choose a starting point x0∈Ω and suitable constants Δmax, Δ0, η0,η1, μ0, μ1, τ1, τ2, ζ,ς, ε, μ,β, ω, and ι such that Δmax>0, Δ0∈(0,Δmax], 0≤η0≤η1<1,(η1≠0), μ0∈(0,1/2), μ1∈(0,1), τ1>0, τ2>0, 0<ζ<1<ς, ε>0, μ>β>0, ω∈(0,1), and ι∈(0,1). Set NONCONVEX=0, RESTRICT=0, and k≔0.
Main Step Step 1.
Constructmk(xk+p) as in (2). Get gk and Hmk. Ifmk(xk+p) is nonconvex, set NONCONVEX=1. Step 2.
Ifχmk≤ε and mk(xk+p) is fully linear and Δk≤ιχmk, stop; otherwise, set Δ~k=Δk, implement step 9 to obtain Δ~k, and make mk(xk+p) fully linear. Update Δk=min⁡max⁡{Δ~k,βχ~mk},Δk. Step 3.
Solve the trust region subproblem (5). Step 4.
Compute the trial pointxk+=xk+pk. Obtain mk+(xk++p), gk+ and Hmk+. Step 5.
Evaluate ratio(24)ρk=RaredkpkPredkpk, by formulas (6) and (22). Iff(xk+)>fsup, set xk+1=xk and RESTRICT=1. Go to Step 7. Step 6.
These are tests to accept the trial step by (20) and (23). Ifxk+ is acceptable for the filter F and NONCONVEX=0: set xk+1=xk+ and RESTRICT=0 and add g k + to the filter F if either ρk<η1. Elseifρk≥η1, set xk+1=xk+ and RESTRICT=0; Elseif NONCONVEX=1, setfsup=f(xk+1) and reinitialize the filter F to the empty set; Else setxk+1=xk and RESTRICT=1. Step 7
. Adjust trust regionΔk(25)Δk+1∈min⁡ςΔk,Δmaxifρk≥η1andΔk<ιχmk,Δk,min⁡ςΔk,Δmaxifρk≥η1andΔk≥ιχmk,ζΔkifρk<η1andmkxk+pis  fully  linear,Δkifρk<η1andmkxk+pis  not  fully  linear. Step 8.
Ifρk≥η1, or ρk≤η1 and RESTRICT=0 and mk+(xk++p) is not fully linear on B(xk+1,Δk+1), go to Step 1; else set RESTRICT=1, implement Step 9, and then go to Step 2. Step 9.
Seti=0 and set mk(0)(xk+p)=mk(xk+p). Repeat: increment i by one, Δ~k←ωi-1Δk, and improve mk(i-1)(xk+p) by mk(i)(xk+p) until it is fully linear (i.e., satisfying the error bounds (3) and (4)). SetΔ~k←Δk and m~k(xk+p)=mk(i)(xk+p). UntilΔ~k≤ι(χmk)(i).Remark 5.
At the beginning of every iteration, Step 5 is encountered withi=-1. In this case the sum in (22) is empty and thus we define(26)Raredkp=fxk-fxk+p=Aredkp.Remark 6.
In order to obtain a suitable approximation function, the objective function of the trust region subproblem needs to update if necessary. Step 9 is the model improvement method which has the same principle as the Algorithm 2 proposed in [14, 15].


## 3. Global Convergence for First-Order Critical Points

The purpose of this section is to provide in-depth introduction to the global convergence properties of Algorithm4 in first-order case. We recall or state some reasonable assumptions that are assumed to hold for problem (1a) and (1b) in order to get global convergence of the derivative-free trust region method.Assumptions (A2)
The level setL(x0) is bounded. (A3)
There exist positive constantsκHf and κHm such that ‖Hfk‖≤κHf and ‖Hmk‖≤κHm, respectively, for all xk∈L(x0). And set κH=max⁡{κHf,κHm+1}.The global convergence property is described by following Theorem7 which indicates that there exist at less one accumulation point of a sequence generated by the derivative-free trust region method from Algorithm 4 with filter technique which is still a stationary point of the optimization problem (1a) and (1b).Theorem 7.
Suppose that Assumptions (A1)-(A3), the error bounds (3) and (4), and the fact that Δk is bounded by Δmax hold. Suppose furthermore that mk(xk+p) is fully linear on B(xk,Δk). Then(27)liminfk→+∞χfk=0.In order to obtain Theorem7, the remainder of this section will derive Lemmas 8–15 as support.Lemma 8.
Suppose that Assumptions (A1)-(A3), the error bounds (3) and (4), and the fact that Δk is bounded by Δmax hold. mk(xk+p) is the fully linear function on B(xk,Δk). Then step 3 of Algorithm 4 will terminate in a finite number of improvement step, if χfk≠0.Proof.
We prove this result by contradiction. Assume that the loop in Step 9 is infinite. We will show thatχfk must be zero in this case.
If Step 9 is implemented, we notice that we do not have a certifiably fully linear modelmk(xk+p) and that the radius Δk exceeds ιχmk. Then set mk(0)(xk+p)=mk(xk+p) and improve the model until it is fully linear on B(xk,ω(0)Δk). If χmk(1) of the resulting model mk(1)(xk+p) satisfies ιχmk(1)≥ω(0)Δk, the procedure stops with Δ~k=ω(0)Δk≤ιχmk(1).
Otherwise, that is,ιχmk(1)<ω(0)Δk improve the model until it is fully linear on B(xk,ωΔk). Then, estimate whether the procedure stops or not. If not, the radius should be multiplied by ω again, and go on.
The only way for this procedure to be infinite is if(28)ιχmki<ωi-1Δkfor  alli≥1.This construction implies(29)limi→+∞χmki=0.
Since each modelmk(i)(xk+p) was fully linear on B(xk,ωi-1Δk), the bound (3) provides(30)χfki=xk-PXxk-∇fk≤PXxk-∇fk-PXxk-gki+xk-PXxk-gki≤∇fk-gki+χmki≤κegΔmax+1ιωi-1Δkfor  alli≥1.
The choice ofω∈(0,1) in Algorithm 4 implies that(31)χfk=0.Lemma 9.
Suppose that Assumptions (A1)-(A3), the error bounds (3) and (4), and the fact that Δk is bounded by Δmax hold. mk(xk+p) is the fully linear function on B(xk,Δk). Suppose furthermore that xk, pk, Δk, etc. are generated by Algorithm 4, then for all computed indices i≥1 holds,(32)fxji<fx0-η1λ∑r=0i-2Predjrpjr-η1Predji-1pji-1.Proof.
We note from (6) that Predk(pk)>0. The proof is by induction. For i=1 we have by (20) and using ρj0(pj0)>η1(33)fxj1=fxj0+1=fxj0-Aredj0pj0<fxj0-η1Predj0pj0=fx0-η1Predj0pj0.Now assume that (32) holds for 1,…,i. If Raredji(pji)=Aredji(pji) then, using (32) and λ≤1,(34)fxji+1=fxji+1=fxji-Aredjipji=fxji-Raredjipji<fx0-η1λ∑r=0i-2Predjrpjr-η1Predji-1pji-1-η1Predjipji≤fx0-η1λ∑r=0i-1Predjrpjr-η1Predjipji.If Raredji(pji)≠Aredji(pji) then Raredji(pji)>Aredji(pji), and with q=min⁡{i,l-1} we obtain(35)fxji+1=fxji+1=∑t=0qλjitfxji-t-Raredjipji<∑t=0qλjitfx0-η1λ∑r=0i-t-2Predjrpjr-η1Predji-t-1pji-t-1-η1Predjipji.Using {0,…,q}×{0,…,i-t-2}⊂{(t,r);0≤p≤t,0≤r≤i-t-2},λji0+⋯+λjit=1, and λjit≥λ, we can proceed as follows:(36)fxji+1<fx0-η1λ∑r=0i-t-2∑t=0qλjitPredjrpjr-η1λ∑t=0qPredji-t-1pji-t-1-η1Predjipji<fx0-η1λ∑r=0i-t-2Predjrpjr-η1λ∑r=i-t-1i-1Predjrpjr-η1Predjipji=fx0-η1λ∑r=0i-1Predjrpjr-η1Predjipji.Lemma9 provides the sufficiently descent property at the kth iteration of Algorithm 4.Lemma 10.
Suppose that Assumptions (A1)-(A3), the error bounds (3) and (4), and the fact that Δk is bounded by Δmax hold. Suppose furthermore that xk, pk, Δk, etc. are generated by Algorithm 4, that mk(xk+p) is fully linear on B(xk,Δk), and that(37)Δk≤min⁡1,χmk,κ11-η1χmk2κef.Then for arbitrary x∈L(x0) with χmk≠0, the kth iteration is successful.Proof.
Sinceχmk≠0 and Δk≤min⁡1,χmk, we obtain from the decrease condition (6)(38)Predkpk=-qmkpk≥κ1χmkmin⁡1,Δk,χmk≥κ1χmkΔk.On the other hand, since the current model is fully linear on B(xk,Δk), then from the bound (3) on the error between the function and the model and from (38), if Raredk(pk)=Aredk(pk), then we have(39)ρk-1=RaredkpkPredkpk-1=fxk-fxk+pkPredkpk-1≤fxk=mkxkmkxk+pk-fxk+pkPredkpk≤2κefΔk2κ1χmkΔk≤1-η1where we have used the assumption Δk≤κ1(1-η1)χmk/(2κef) to deduce the inequality.
IfRaredk(pk)>Aredk(pk), then we have, with appropriate xk′∈[xk,xk+pk],(40)Aredkpk=fxk-fxk+pk=-∇fxk′Tpk=-qmkpk+gk-∇fxk′Tpk+12pkTHmkpk.Since ∇f continuous, there exists δ′>0 such that(41)∇fxk′-∇fxk1≤1-η1κ1-κeg-12κHΔmaxχmk,for all xk′∈Xk with ‖xk′-xk‖<δ. Hence, for these indices k,(42)gk-∇fxk′+12pkTHmkpk1≤gk-∇fxk+∇fxk′-∇fxk1+12κHΔk2≤1-η1κ1χmk.At the same time, we get from (5) and (38) that(43)pk∞≤Δk≤1κ1χmkPredkpk.This inequality implies that(44)gk-∇fxk′Tpk+12pkTHmkpk≤1-η1κ1χmkpk∞≤1-η1Predkpk.This means that(45)Raredkpk≥Aredkpk≥Predkpk-gk-∇fxk′Tpk+12pkTHmkpk≥η1Predkpk.For either case, we obtain the conclusion that ρk≥η1; that is, the kth iteration is successful.Lemma 11.
Suppose that Assumptions (A1)-(A3), the error bounds (3) and (4), and the fact that Δk is bounded by Δmax hold. Suppose furthermore that mk(xk+p) is fully linear on B(xk,Δk) and that there exists a constant κlbg>0 such that χmk≥κlbg for all k. Then there is a constant κubd>0 such that Δk≥κubd for all k.Proof.
The proof is the same as for Lemma 5.3 in [8] when ‖pk‖∞≤Δk except that we now have to replace ‖gk‖ by the criticality measurement χmk and use (38) instead of the model decrease defined in [8].Lemma 12.
Suppose that Assumptions (A1)-(A3), the error bounds (3) and (4), and the fact that Δk is bounded by Δmax hold. Suppose furthermore that mk(xk+p) is fully linear on B(xk,Δk) and that there exists a constant κlbg>0 such that χmk≥κlbg for all k. Then there can be only finitely many successful nonconvex iterations in the course of the algorithm, i.e., |S∩N|<+∞.Proof.
Suppose, for the purpose of obtaining a contradiction, that there are infinitely many successful nonconvex iterations, which we index byS∩N={ki}. It follows from the fact of S∩N=D∩N that the algorithm also guarantees that ρk≥η1 for all iteration in S∩N, where D={k∣ρk≥η1} is the set of sufficient descent iterations, which in turn implies with (6) that, for k∈S∩N,(46)Raredkpk≥η1mkxk-mkxk+pk≥η1κ1χmkmin⁡1,Δk,χmk≥η1κ1κlbgmin⁡1,Δk,κlbgwhere we have used Lemma 8, (A3) and our lower bound on the gradient norm to obtain the last inequality. Combining now this bound with (3), we deduce that(47)fx0-fxk+1≥∑j=0,j∈S∩NkRaredkpk≥∑j=0,j∈S∩Nkmax⁡fxk,∑r=0lk-1λkrfxji-1-fxk+1≥ςkη1κ1κlbgmin⁡1,Δk,κlbgwhere ςk=|{1,…,k}∩S∩N|. As we have supposed that there are infinitely many successful nonconvex iterations, we have that limk→∞⁡ςk=+∞, and |f(x0)-f(xk+1)| is unbounded above, which contradicts the fact that the objective function is bound below; as stated in assumption A1, our initial assumption must then be false and the set S∩N of successful nonconvex iteration must be finite.Lemma 13.
Suppose that Assumptions (A1)-(A3), the error bounds (3) and (4), and the fact that Δk is bounded by Δmax hold. Suppose furthermore that mk(xk+p) is fully linear on B(xk,Δk) and that there are only finitely many successful iterations, i.e., |S|<+∞. Then limk→∞χmk=0.Proof.
Letk0 be the index of the last successful iteration. Then x∗=xk0+1=xk0+j and(48)ρk0+j<η1for  allj>1.Now observe that Restrict is set by the algorithm in the course of every unsuccessful iteration. This flag must thus be set at the beginning of every iteration of index k0+j+1 for j>0. As a consequence, ‖pk0+j+2‖≤Δk0+j+2 for all j>0. This, (48), and the mechanism of step 7 of the algorithm then imply that(49)limk→∞Δk=0.Assume now, for the purpose of establishing a contradiction, that χmk0+1≥ε for some ε>0. Then Lemma 12 implies that (49) is impossible and we deduce that(50)χmk0+j=0,for  allj>0.Lemma 14.
Suppose that Assumptions (A1)-(A3), the error bounds (3) and (4), and the fact that Δk is bounded by Δmax hold. Suppose furthermore that mk(xk+p) is fully linear on B(xk,Δk) and that |A|=|S|=+∞. Then liminfk→∞χmk=0.Proof.
Assume for the purpose of obtaining a contradiction that, for allk large enough,(51)χmk≥κlbgfor some κlbg>0 and define {ki}=A. The bound (51) and the Lemma 12 then imply that |S∩N| is finite and therefore that the filter is no longer reset to the empty set for k sufficiently large. Moreover, since our assumptions imply that {χmki+1} is bounded above and away form zero, there must exist a subsequence kl⊆ki+1 such that(52)liml→∞χmkl=χm∞withχm∞≥κlbg.By definition of {kl}, xkl is acceptable for the filter in each iteration l-1. This implies, since the filter is not reset for l large enough, that, for each l sufficiently large, there exists an index jl∈{1,…,n} such that(53)g^kl,jl-g^kl-1,jl≤-γg^g^kl-1.But (51) implies that ‖g^kl-1‖≥κlbg for all l sufficiently large. Hence we deduce from (53) that(54)g^kl,jl-g^kl-1,jl≤-γg^κlbg.for all l sufficiently large. But the left-hand side of this inequality tends to zero when l tends to infinity because of (52), yielding the desired contradiction. Hence the conclusion holds.We now consider the similar conclusion of Lemma 5.7 in [8] that if the model criticality measurement χmk converges to 0 on a subsequence, then so does the true criticality measurement χfk.Lemma 15.
For any subsequenceki such that(55)limi→+∞χmki=0it also holds that(56)limi→+∞χfki=0.Combining both Lemmas14 and 15, a global convergent property immediately will be given as Theorem 7, which also illustrates that the criticality step plays an important role in ensuring a subsequence of the iterations being close to the first-order stationarity.


## 4. Numerical Experiment

In this section, we examine the practical performance of the derivative-free trust region method on two aspects. The comparisons of the numerical results between the proposed derivative-free trust region method and traditional gradient algorithm are firstly given in order to illustrate the effectiveness of Algorithm4 in solving the general optimization problems. And then the derivative-free trust region algorithm with nonmonotone filter technique to parameter estimation is presented to show the performance of Algorithm 4 to derivative-free optimization problems. All routines are written in Matlab R2009a and run on a PC with 2.66GHz Intel(R) Core(TM)2 Quad CPU and 4G DDR2.


### 4.1. Numerical Results of the Derivative-Free Trust Region Algorithm with Nonmonotone Filter Technique

The Hock [27] test set is frequently used to test derivative-free algorithms on moderate-size problems. For running the proposed derivative-free trust region algorithm with nonmonotone filter technique, the bound constraints of each problem define the set Ω and linear (not bound) constraints of the original problem were processed by projections. We test 27 simple bound constrained optimization problems (List in Table 1) from Test examples for Nonlinear Programming Codes [27–29]. The values Δ0=2, η0=0.25, η1=0.75, ζ=0.4, ς=2, ι=0.5, β=0.3, ε=10-8, and ω=0.5 are used. At the same time, we introduce two different algorithms traditional quasi-Newton method and conjugate gradient method [30] into this section to measure the objective algorithm efficiency through the tested problems. We denote the two algorithms as Algorithm 1.1 and Algorithm 1.2.Table 1
Test problems.
Problem Dim x0 Problem Dim x0 HS1 2 [ - 2,1 ] HS2 2 [ - 2,1 ] HS3 2 [ 10,1 ] HS4 2 [ 1.125,0.125 ] HS5 2 [ 0,0 ] HS21 2 [ - 1 , - 1 ] HS24 2 [ 1,0.5 ] HS25 3 [ 100,12.5,3 ] HS35(Beale’s problem) 3 [ 0.5,0.5,0.5 ] HS38(Colville No.4) 4 [ - 3 , - 1 , - 3 , - 1 ] HS45 5 [ 2,2 , 2,2 , 2 ] HS110 10 [ 9,9 , … , 9 ] HS119(Colville No.7) 16 [ 10,10 , … , 10 ] HS224 2 [ 0.1,0.1 ] HS232 2 [ 2,0.5 ] HS247(Helical vally) 3 [ - 1,0 , 0 ] HS250(Rosenbrock’s-Post-office-prob.) 3 [ 10,10,10 ] HS251 3 [ 10,10,10 ] HS253 3 [ 0,2 , 0 ] HS257 4 [ - 3 , - 1 , - 3 , - 1 ] HS262 4 [ 0,0 , 0,0 ] HS279 8 [ 0,0 , … , 0 ] HS280 10 [ 0,0 , … , 0 ] HS299 100 [ - 1,2 , … , - 1,2 ] HS328(Gear train of minimum inertia) 2 [ 0.5,0.5 ] HS340(Pascal problem) 3 [ 1,1 , 1 ] HS368(Gear train of minimum inertia) 8 [ 1,1 , … , 1 ]We use the tool of Dolan and More [31] to analyze the efficiency of the given three algorithms. Figures 1 and 2 show that the performance of Algorithm 4 is feasible and has the robust property among those three methods. It is not difficult to see from Figure 1 that Algorithm 4 has a huge lead among those three methods in the CPU time for solving each test problems. Simultaneously, Figure 2 illustrates that Algorithm 4 more quickly to optimal performance in terms of the number of function evaluations than other two algorithms.Figure 1
Profile comparing the CPU time required performance of different methods.Figure 2
Profile comparing the numbers of function evaluations performance of different methods.To measure the efficiency of the proposed algorithm for large-scale optimizations, in this section, we compare this method with Algorithm 2.1 in [32] using three characteristics “NI,” “NF,” and “CPU,” where “NI” presents the number of iterations, “NF” is the calculation frequency of the function, and “CPU” is the time of the process in addressing the tested problems. The numerical results with the corresponding problem are listed in Table 2.Table 2
Numerical results.
Problem Dim Algorithm4 Algorithm 2.1 NI NF CPU NI NF CPU Broyden Tridiagonal Function 9000 23 87 14.322854 13 54 9.718862 Extended Powell Function 9000 7 37 0.2094377 9 45 0.218401 Extended Penalty Function 9000 43 193 0.355428 65 252 0.421203 Extended Wood Function 9000 17 73 0.396603 13 50 0.124801 Extended Quadratic Penalty QP1 Function 9000 15 57 0.0953941 18 63 0.124801Although we only list the data of dimension of 9000, obviously, the objective algorithm (Algorithm4) is more effective for large-scale optimizations since the iteration number and CPU time which are two essential aspects to measure the efficiency of an algorithm are less than Algorithm 2.1.


### 4.2. The Derivative-Free Trust Region Algorithm to Parameter Estimation

Algorithm 16 (basic trust region method).
⁡
Step 0. An initial point x0∈Rn and an initial trust region radius Δ0>0 are given, as well as parameters 0≤η0<η1<1 and 0<ζ<1<ς. Compute f(x0) and set k=0.
Step 1. Solve a trust region subproblem and compute a step pk which satisfies the sufficient decrease conditions.
Step 2. Compute f(xk+pk) and ρk=f(xk)-f(xk+pk)/mk(xk)-mk(xk+pk). If η0≤ρk, then set xk+1=xk+αkpk; otherwise, set xk+1=xk.
Step 3. Set(57)Δk+1=ζpkifρk<η0Δkifη0<ρk<η1max⁡ςpk,Δkifη1≤ρk.Increment k by one, and go to Step 1.Trust region methods generate steps with the help of a quadratic model of the objective function, but they use this model in different ways from line search methods. Trust region methods define a region around the current iterate within which the trust the model to be an adequate representation of the objective function and then choose the step to be the approximate minimizer of the model in this region. The size of the trust region is critical to the effectiveness of each step. There are four parameters found in a trust region update process (57); namely, η0,η1,ζ,ς are used to adjust the size of the trust region radius. The values are arbitrary and that much better options are available. The classical parameter values(58)sc=0.25,0.75,0.5,2are recommended in the literature [30], but they may not be the best choice if we consider the total CPU time or the overall number of function evaluations which was necessary to solve a set of optimization problems. This is a derivative-free optimization problem. In this section, an objective is to identify four optimal parameters found in a trust-region update using the proposed Algorithm 4 in this paper. Next we describe the specific representation of this parameter estimation problem.LetP be a set of optimization problems, Ω={s∈R4∣0≤η0<η1<1and0<ζ<1<ς}, τi(s) be the CPU time which is necessary to solve the problem pi∈P with the parameter values s, and ϕi(s) be the number of function evaluations. Thus the small-dimensional nondifferentiable optimization problem measuring by the overall CPU time ψCPU(s) or the overall number of function evaluations ψfeval(s) is written as(59)minp∈ΩψCPUs=∑i∈Pτisorminp∈Ωψfevals=∑i∈PϕisWe consider to minimize the total computing time ψCPU(·). The test problems in P and their dimension are list in Table 3. The initial point chosen for Algorithm 4 is sc. Thus, the best set of parameters given by Algorithm 4 is(60)s∗=0.238721,0.923489,0.352533,2.304294.Table 3 shows the results on the test problems. Timings τi(·) are in seconds. The measure ϕi(·) is the number of function evaluations in each case. Failures occur when ϕi(·)=1001. Table 3 demonstrates that this strategy allowed the improvement if the truth initial value from ψCPU(sc)=71.04 to ψCPU(s∗)=64.4 seconds, i.e., an improvement of approximately 10.31 %. The total number of function evaluations is improved from ψfeval(sc)=14221 to ψfeval(s∗)=12752, i.e., an improvement of approximately 11.52 %.Table 3
Numerical results of the parameter estimation.
Problem name n τ i ( s c ) τ i ( s ∗ ) ϕ i ( s c ) ϕ i ( s ∗ ) 3PK 30 0.14 0.04 71 55 ARGLINA 200 0.64 0.34 3 3 BIGGS6 6 0.12 0.02 24 23 BOX3 3 0.02 0.02 6 6 BROWNAL 200 0.12 0.17 4 7 BROWNBS 2 0.22 0.32 23 27 BROWNDEN 4 0.02 0.02 10 9 CHNROSNB 50 0.32 0.43 66 70 CLIFF 2 0.20 0.02 27 19 CUBE 2 0.02 0.02 45 40 DECONVU 61 1.34 0.93 90 38 DENSCHND 3 0.55 0.22 31 29 DIXMAANK 15 0.10 0.02 9 9 DJTL 2 0.02 0.02 168 147 ERRINROS 50 0.22 0.11 71 73 GENROSE 500 23.37 19.55 461 413 GROWTHLS 3 0.82 0.47 179 157 GULF 3 0.03 0.02 54 49 HAIRY 2 0.04 0.09 78 51 HEART6LS 6 0.25 0.25 1001 1001 HEART8LS 8 0.25 0.18 259 178 HIELOW 3 3.09 1.29 11 6 HIMMELBF 4 0.44 0.62 201 174 HUMPS 2 0.44 0.41 1001 613 LOGHAIRY 2 0.44 0.44 1001 1001 MANCINO 100 21.33 16.79 20 24 MARATOSB 2 0.03 0.37 1001 1001 MEYER3 3 0.42 0.49 1001 472 OSBORNEA 5 0.06 0.04 69 77 OSBORNEB 11 0.11 0.16 20 53 PALMER1C 8 0.54 0.94 1001 874 PALMER1D 7 0.02 0.02 49 69 PALMER2C 8 0.71 0.71 1001 1001 PALMER3C 8 0.31 0.26 646 983 PALMER4C 8 0.03 0.06 80 548 PALMER6C 8 0.07 0.15 229 145 PALMER7C 8 0.36 0.84 1001 1001 PALMER8C 8 0.55 1.09 268 233 PENALTY2 200 0.99 0.77 13 15 PFIT1LS 3 0.23 0.65 625 368 PFIT2LS 3 0.01 0.37 242 176 PFIT3LS 3 0.27 0.49 275 377 PFIT4LS 3 0.21 0.43 510 269 SENSORS 100 8.77 11.77 22 20 SISSER 2 0.02 0.02 10 12 SNAIL 2 0.06 0.06 75 81 TOINTGOR 50 0.08 0.10 7 9 TOINTPSP 50 0.05 0.05 16 20 TOINTQOR 50 0.02 0.02 16 10 VARDIM 200 0.09 0.22 26 71 VAREIGVL 50 0.03 0.03 20 15 VIBRBEAM 8 1.63 0.95 1001 533 WATSON 12 0.77 0.48 11 4 YFITU 3 0.05 0.05 72 93  Total ψ 71.04 64.40 14221 12752The function which characterizes the performance profile of parameter valuessc and s∗ is the same as [2]. The performance of the computing time τi(·) required to solve each optimization problem in the problem set P, with the parameter values sc, can be visualized in the profile of Figure 3 which compares the CPU time with the parameter values s∗. The profile of Figure 4 presents a similar comparison, using the number of function evaluations. Both Figures 3 and 4 illustrate that Algorithm 4 has advantage in solving nondifferentiable optimization problems.Figure 3
Profile comparing the CPU time required performance when using different parameter values.Figure 4
Profile comparing the total numbers of function evaluations performance when using different parameter values.


## 4.1. Numerical Results of the Derivative-Free Trust Region Algorithm with Nonmonotone Filter Technique

The Hock [27] test set is frequently used to test derivative-free algorithms on moderate-size problems. For running the proposed derivative-free trust region algorithm with nonmonotone filter technique, the bound constraints of each problem define the set Ω and linear (not bound) constraints of the original problem were processed by projections. We test 27 simple bound constrained optimization problems (List in Table 1) from Test examples for Nonlinear Programming Codes [27–29]. The values Δ0=2, η0=0.25, η1=0.75, ζ=0.4, ς=2, ι=0.5, β=0.3, ε=10-8, and ω=0.5 are used. At the same time, we introduce two different algorithms traditional quasi-Newton method and conjugate gradient method [30] into this section to measure the objective algorithm efficiency through the tested problems. We denote the two algorithms as Algorithm 1.1 and Algorithm 1.2.Table 1
Test problems.
Problem Dim x0 Problem Dim x0 HS1 2 [ - 2,1 ] HS2 2 [ - 2,1 ] HS3 2 [ 10,1 ] HS4 2 [ 1.125,0.125 ] HS5 2 [ 0,0 ] HS21 2 [ - 1 , - 1 ] HS24 2 [ 1,0.5 ] HS25 3 [ 100,12.5,3 ] HS35(Beale’s problem) 3 [ 0.5,0.5,0.5 ] HS38(Colville No.4) 4 [ - 3 , - 1 , - 3 , - 1 ] HS45 5 [ 2,2 , 2,2 , 2 ] HS110 10 [ 9,9 , … , 9 ] HS119(Colville No.7) 16 [ 10,10 , … , 10 ] HS224 2 [ 0.1,0.1 ] HS232 2 [ 2,0.5 ] HS247(Helical vally) 3 [ - 1,0 , 0 ] HS250(Rosenbrock’s-Post-office-prob.) 3 [ 10,10,10 ] HS251 3 [ 10,10,10 ] HS253 3 [ 0,2 , 0 ] HS257 4 [ - 3 , - 1 , - 3 , - 1 ] HS262 4 [ 0,0 , 0,0 ] HS279 8 [ 0,0 , … , 0 ] HS280 10 [ 0,0 , … , 0 ] HS299 100 [ - 1,2 , … , - 1,2 ] HS328(Gear train of minimum inertia) 2 [ 0.5,0.5 ] HS340(Pascal problem) 3 [ 1,1 , 1 ] HS368(Gear train of minimum inertia) 8 [ 1,1 , … , 1 ]We use the tool of Dolan and More [31] to analyze the efficiency of the given three algorithms. Figures 1 and 2 show that the performance of Algorithm 4 is feasible and has the robust property among those three methods. It is not difficult to see from Figure 1 that Algorithm 4 has a huge lead among those three methods in the CPU time for solving each test problems. Simultaneously, Figure 2 illustrates that Algorithm 4 more quickly to optimal performance in terms of the number of function evaluations than other two algorithms.Figure 1
Profile comparing the CPU time required performance of different methods.Figure 2
Profile comparing the numbers of function evaluations performance of different methods.To measure the efficiency of the proposed algorithm for large-scale optimizations, in this section, we compare this method with Algorithm 2.1 in [32] using three characteristics “NI,” “NF,” and “CPU,” where “NI” presents the number of iterations, “NF” is the calculation frequency of the function, and “CPU” is the time of the process in addressing the tested problems. The numerical results with the corresponding problem are listed in Table 2.Table 2
Numerical results.
Problem Dim Algorithm4 Algorithm 2.1 NI NF CPU NI NF CPU Broyden Tridiagonal Function 9000 23 87 14.322854 13 54 9.718862 Extended Powell Function 9000 7 37 0.2094377 9 45 0.218401 Extended Penalty Function 9000 43 193 0.355428 65 252 0.421203 Extended Wood Function 9000 17 73 0.396603 13 50 0.124801 Extended Quadratic Penalty QP1 Function 9000 15 57 0.0953941 18 63 0.124801Although we only list the data of dimension of 9000, obviously, the objective algorithm (Algorithm4) is more effective for large-scale optimizations since the iteration number and CPU time which are two essential aspects to measure the efficiency of an algorithm are less than Algorithm 2.1.


## 4.2. The Derivative-Free Trust Region Algorithm to Parameter Estimation

Algorithm 16 (basic trust region method).
⁡
Step 0. An initial point x0∈Rn and an initial trust region radius Δ0>0 are given, as well as parameters 0≤η0<η1<1 and 0<ζ<1<ς. Compute f(x0) and set k=0.
Step 1. Solve a trust region subproblem and compute a step pk which satisfies the sufficient decrease conditions.
Step 2. Compute f(xk+pk) and ρk=f(xk)-f(xk+pk)/mk(xk)-mk(xk+pk). If η0≤ρk, then set xk+1=xk+αkpk; otherwise, set xk+1=xk.
Step 3. Set(57)Δk+1=ζpkifρk<η0Δkifη0<ρk<η1max⁡ςpk,Δkifη1≤ρk.Increment k by one, and go to Step 1.Trust region methods generate steps with the help of a quadratic model of the objective function, but they use this model in different ways from line search methods. Trust region methods define a region around the current iterate within which the trust the model to be an adequate representation of the objective function and then choose the step to be the approximate minimizer of the model in this region. The size of the trust region is critical to the effectiveness of each step. There are four parameters found in a trust region update process (57); namely, η0,η1,ζ,ς are used to adjust the size of the trust region radius. The values are arbitrary and that much better options are available. The classical parameter values(58)sc=0.25,0.75,0.5,2are recommended in the literature [30], but they may not be the best choice if we consider the total CPU time or the overall number of function evaluations which was necessary to solve a set of optimization problems. This is a derivative-free optimization problem. In this section, an objective is to identify four optimal parameters found in a trust-region update using the proposed Algorithm 4 in this paper. Next we describe the specific representation of this parameter estimation problem.LetP be a set of optimization problems, Ω={s∈R4∣0≤η0<η1<1and0<ζ<1<ς}, τi(s) be the CPU time which is necessary to solve the problem pi∈P with the parameter values s, and ϕi(s) be the number of function evaluations. Thus the small-dimensional nondifferentiable optimization problem measuring by the overall CPU time ψCPU(s) or the overall number of function evaluations ψfeval(s) is written as(59)minp∈ΩψCPUs=∑i∈Pτisorminp∈Ωψfevals=∑i∈PϕisWe consider to minimize the total computing time ψCPU(·). The test problems in P and their dimension are list in Table 3. The initial point chosen for Algorithm 4 is sc. Thus, the best set of parameters given by Algorithm 4 is(60)s∗=0.238721,0.923489,0.352533,2.304294.Table 3 shows the results on the test problems. Timings τi(·) are in seconds. The measure ϕi(·) is the number of function evaluations in each case. Failures occur when ϕi(·)=1001. Table 3 demonstrates that this strategy allowed the improvement if the truth initial value from ψCPU(sc)=71.04 to ψCPU(s∗)=64.4 seconds, i.e., an improvement of approximately 10.31 %. The total number of function evaluations is improved from ψfeval(sc)=14221 to ψfeval(s∗)=12752, i.e., an improvement of approximately 11.52 %.Table 3
Numerical results of the parameter estimation.
Problem name n τ i ( s c ) τ i ( s ∗ ) ϕ i ( s c ) ϕ i ( s ∗ ) 3PK 30 0.14 0.04 71 55 ARGLINA 200 0.64 0.34 3 3 BIGGS6 6 0.12 0.02 24 23 BOX3 3 0.02 0.02 6 6 BROWNAL 200 0.12 0.17 4 7 BROWNBS 2 0.22 0.32 23 27 BROWNDEN 4 0.02 0.02 10 9 CHNROSNB 50 0.32 0.43 66 70 CLIFF 2 0.20 0.02 27 19 CUBE 2 0.02 0.02 45 40 DECONVU 61 1.34 0.93 90 38 DENSCHND 3 0.55 0.22 31 29 DIXMAANK 15 0.10 0.02 9 9 DJTL 2 0.02 0.02 168 147 ERRINROS 50 0.22 0.11 71 73 GENROSE 500 23.37 19.55 461 413 GROWTHLS 3 0.82 0.47 179 157 GULF 3 0.03 0.02 54 49 HAIRY 2 0.04 0.09 78 51 HEART6LS 6 0.25 0.25 1001 1001 HEART8LS 8 0.25 0.18 259 178 HIELOW 3 3.09 1.29 11 6 HIMMELBF 4 0.44 0.62 201 174 HUMPS 2 0.44 0.41 1001 613 LOGHAIRY 2 0.44 0.44 1001 1001 MANCINO 100 21.33 16.79 20 24 MARATOSB 2 0.03 0.37 1001 1001 MEYER3 3 0.42 0.49 1001 472 OSBORNEA 5 0.06 0.04 69 77 OSBORNEB 11 0.11 0.16 20 53 PALMER1C 8 0.54 0.94 1001 874 PALMER1D 7 0.02 0.02 49 69 PALMER2C 8 0.71 0.71 1001 1001 PALMER3C 8 0.31 0.26 646 983 PALMER4C 8 0.03 0.06 80 548 PALMER6C 8 0.07 0.15 229 145 PALMER7C 8 0.36 0.84 1001 1001 PALMER8C 8 0.55 1.09 268 233 PENALTY2 200 0.99 0.77 13 15 PFIT1LS 3 0.23 0.65 625 368 PFIT2LS 3 0.01 0.37 242 176 PFIT3LS 3 0.27 0.49 275 377 PFIT4LS 3 0.21 0.43 510 269 SENSORS 100 8.77 11.77 22 20 SISSER 2 0.02 0.02 10 12 SNAIL 2 0.06 0.06 75 81 TOINTGOR 50 0.08 0.10 7 9 TOINTPSP 50 0.05 0.05 16 20 TOINTQOR 50 0.02 0.02 16 10 VARDIM 200 0.09 0.22 26 71 VAREIGVL 50 0.03 0.03 20 15 VIBRBEAM 8 1.63 0.95 1001 533 WATSON 12 0.77 0.48 11 4 YFITU 3 0.05 0.05 72 93  Total ψ 71.04 64.40 14221 12752The function which characterizes the performance profile of parameter valuessc and s∗ is the same as [2]. The performance of the computing time τi(·) required to solve each optimization problem in the problem set P, with the parameter values sc, can be visualized in the profile of Figure 3 which compares the CPU time with the parameter values s∗. The profile of Figure 4 presents a similar comparison, using the number of function evaluations. Both Figures 3 and 4 illustrate that Algorithm 4 has advantage in solving nondifferentiable optimization problems.Figure 3
Profile comparing the CPU time required performance when using different parameter values.Figure 4
Profile comparing the total numbers of function evaluations performance when using different parameter values.


## 5. Conclusion

This paper proposes a derivative-free trust region algorithm with nonmonotone filter technique for bound constrained optimization.(i)
This algorithm is mainly designed to solve the unavailable derivatives optimization problems in engineering. The proposed algorithm possesses the trust region property and adopts nonmonotone filter technique for bound constrained optimization.(ii)
The global convergence is provided under the definition of fully linear model. The sufficient descent property is able to make the objective function value descend, and then the iteration sequence{xk} converges to the global limit point if the problems are convex.(iii)
The preliminary numerical results compared with traditional quasi-Newton method and conjugate gradient method turn out the proposed algorithm is feasible for those of the unavailable derivative functions. Large-scale problems are done by the given problems, which shows that the new algorithms are very effective.(iv)
Finally, optimal parameters with respect to overall computational time on a set of test problems are identified. We use the proposed algorithm to get a best choice of parameter values which differ from traditionally used values and compare the numerical results affected by two different parameters from the two aspects of the CPU time and the number of function evaluations.



---

*Source: 5049027-2018-10-23.xml*