# Projected Adaptive Cubic Regularization Algorithm with Derivative-Free Filter Technique for Box Constrained Optimization

Authors: Lingyun He; Peng Wang; Detong Zhu
Journal: Discrete Dynamics in Nature and Society
 (2021)

---

## Abstract

An adaptive projected affine scaling algorithm of cubic regularization method using a filter technique for solving box constrained optimization without derivatives is put forward in the passage. The affine scaling interior-point cubic model is based on the quadratic probabilistic interpolation approach on the objective function. The new iterations are obtained by the solutions of the projected adaptive cubic regularization algorithm with filter technique. We prove the convergence of the proposed algorithm under some assumptions. Finally, experiments results showed that the presented algorithm is effective in detail.


---

## Body

## 1. Introduction

In this passage, we investigate the following optimization:(1)minfys.t.y=y1,y2,…,yn∈Rnli≤yi≤uii=1,2,…,n,where f:Rn⟶R is smooth, but its derivative information is unavailable or unreliable. For each i, li is not greater than ui, and there exists some ik such that lk is less than uk strictly. Define the feasible set and the strict interior by Ω, intΩ, respectively.The structure of this passage is as shown below. The relevant information is reviewed and our algorithm for problem (1) is introduced in Section 2. The corresponding analysis are investigated in Sections 3 and 4, respectively. Then, the numerical experiments are listed in details in Section 5.


## 2. Literature Review

Optimization (1) forms an ordinary but important class in various circumstances. There are lots of researchers using different tools to solve it ([1–4]). In order to complements the algorithm library for solving this kind of optimization, we extent the cubic regularization algorithm (shorted by ARC), which is presented by Cartis et al. in [5, 6], with filter technique to solve (1) by projection measure based on probabilistic models.The numerical results of classical ARC showed excellent performance. In [7], Cartis et al. extended ARC for unconstrained optimizations to finite-difference version. In [8], the authors extended the bound of [5, 6] to nonlinear problems with convex constraints. Gould et al., in [9], updated the parameter in the large-scale least-squares nonlinear optimization. Huang and Zhu, in [3], presented an affine scaling ARC algorithm for derivative-free box constrained minimization using backtracking line search technique to obtain the step size. In the framework of ARC, the authors did not use box constraints’ information; thus, we turn to an affine scaling technique in [10], which usually combine with the methods of trust region [10, 11]. However, for various reasons, there are many examples in computational science and engineering; their (at least some) derivatives were unavailable or unreliable. However, they may still be desirable to get the optimizations. This situation led researchers to look for the way to solve (1). Recently, there are many papers proposing various different techniques for the optimization without derivatives. Algorithms for bound constrained optimization with global convergence results using the trust region derivative-free methods were presented in [12, 13]. Powell, in [14, 15], proposed the NEWUOA algorithm, which employs a quadratic polynomial interpolation for the unconstrained or box constrained optimization with excellent experiment performance. In [16], Conn et al. gave a derivative-free version of the trust region method. The corresponding model was constructed by using the polynomial interpolation techniques. Li and Zhu, in [17], proposed an affine trust region method to solve (1) by using a backtracking relevant condition and a filter technique.Motivated by these ideas, we will try our best to introduce the ARC method using filter technique to solve (1) without derivatives under certain assumptions in this paper. In absence of derivatives, we use probabilistic polynomials’ interpolation to construct models of f. The presented algorithm has two merits. The first merit is that to solve the subproblem which is only needed once at every point under some conditions, but the ARC algorithms need to solve repeatedly in [5, 6], in which solving a subproblem is computationally more expensive than using line search to get the trial step. The other merit is that we take a backing line search technique to make the new iteration strictly feasible.In this paper, unless otherwise noted, we write⋅=⋅2 for brevity.


### 2.1. Notations

There are many constants and notations displayed in the next sections. For convenience, we collect the following:κg is bound on ∇fyκh is bound on ∇2fyκng is bound on ∇my≜gyκH is bound on ∇2my≜HyD affines scaling matrix for fD¯ affines scaling matrix for mκD is bound on D,D¯β¯i are constants related to mκ is projected gradient for fκ¯ is projected gradient for mαk is the step size at ykαk,l is the lth trial step size at yk


## 2.1. Notations

There are many constants and notations displayed in the next sections. For convenience, we collect the following:κg is bound on ∇fyκh is bound on ∇2fyκng is bound on ∇my≜gyκH is bound on ∇2my≜HyD affines scaling matrix for fD¯ affines scaling matrix for mκD is bound on D,D¯β¯i are constants related to mκ is projected gradient for fκ¯ is projected gradient for mαk is the step size at ykαk,l is the lth trial step size at yk


## 3. Development of the Algorithm

At first, we review the elements of our presented algorithm.Following the notations proposed by Cartis et al., in [5, 6], we give the ARC subproblem as follows:(2)minψkd=∇fykTd+12dT∇2fykd+13σkd3,where σk is a dynamic positive parameter.Definition 1.
A mappingPC:Rn⟶C is called the projection onto C if(3)PCy=argminx∈Cx−y,where C≠Φ and C is closed. PCy=maxl,miny,u since Ω in (1) is a box. κy=y−PΩy−∇fy is a well-known criticality measure.Definition 2 (see [18, 19]).
Functionm is said fully quadratic of f in Byk,δk if, for all y∈Byk,δk, there exist some positive constants κef,κeg,κeh, such that(4)fy−my≤κefδk3,(5)∇fy−∇my≤κegδk2,(6)∇2fy−∇2my≤κehδk.
Next, random modelsMk will be considered; mk=Mkωk is denoted for their realizations. Xk and Δk will be used for random quantities, while their realizations are denoted by xk=Xkωk and δk=Δkωk, respectively.Definition 3 (see [18, 19]).
A sequenceMk is said p-probabilistically fully quadratic for sequence BXk,Δk if Sk=Mkis a full quadratic on sequenceBXk,Δk satisfy PSk|Fk−1M≥p, in which Fk−1M=σM0,…,Mk−1 is generated by M0,…,Mk−1. The random models are probabilistically fully quadratic if p≥1/2.
Now, we expand (2) to the derivative-free version to solve (1):(7)minφkd=gkTd+dTHkd2+σkd33s.t.l≤xk+d≤u,where gk=∇mykandHk=∇2myk. And, gk≠∇fykandHk≠∇2fyk in the derivative-free case, so κ¯y=defy−PΩy−∇my≠κy.
Filter technique was proposed firstly by Fletcher and Leyffer for constrained nonlinear optimization. The idea of using filter is to interpret the system of (1) as a biobjective optimization with two goals: minimizing fy and minimizing hy, where hy=D¯ygy, D¯y=diagv¯y, and(8)v¯yj=1,iflj=−∞anduj=+∞,minyj−lj+μmax0,−∇myj,uj−yj+μmax0,∇myj,otherwise.
Then, we also definiteDy is the derivative version of D¯y.
In order to ensuref or h decreasing sufficiently, we give such a strategy:(9)1−ηhhyk≥hykαk,l,or(10)fyk−ηfαk,lhyk2≥fykαk,l,where ykαk,l=yk+αk,ldk and ηh,ηf∈0,1 are small positive constants.
If (9) or (10) holds, the current filter ℱ accepts ykαk,l. The filter remains unchanged. Otherwise, neither (9) nor (10) holds; the current filter rejects ykαk,l; the filter can be augmented as(11)ℱk+1=h,f∈Rn:1−ηhhyk≥handfyk−ηfαkhyk2≥f∪ℱk.
At the beginning, initializeℱ0=h,f:h≥h0.
Now, we present a projected adaptive cubic regularization algorithm with filter technique (shorted by PFARC) for the solutions of derivative-free box constraint optimization:


### 3.1. Initialization Step

An initial pointy0∈intΩ=y:l<y<u. Given a positive parameter σ0>0, a radius 1≥δ0>0, and constants γ1,γ2,γ,λ1,λ2, they satisfy that(12)0<γ1≤γ2<1,0<γ<1,0<λ1≤λ2<1.Initialize the filterℱ0. Choose ε∈0,1,ηf,ηh∈0,1,andγ3∈0,1. Set k=0.


### 3.2. Main Step

Step 1: set a interpolation points setXk such that yk∈Xk⊆Byk,δk; then, apply Algorithms 6.1 and 6.3 in [20] to construct the fully quadratic model mk=myk on Byk,δk. Set(13)gk=∇mk,Hk=∇2mk,κ¯k=κ¯yk,hyk=defD¯kgk.Step 2: ifκ¯k=0, stop at yk.Step 3: solve (7) and obtain dk.Step 4: line search.Step 4.1: letl=0 and αk,0=1.Step 4.2: setykαk,l=yk+αk,ldk.Step 4.3: ifℱ accepts ykαk,l, go to Step 4.4, else go to Step 4.6.Step 4.4: if1−ηhhyk≥hykαk,l, yk+αk,ldk∈Ω holds, and accept αk,l and go to Step 4.7, else go to Step 4.5.Step 4.5: iffyk−ηfαk,lhyk2≥fykαk,l, yk+αk,ldk∈Ω holds, and accept αk,l and go to Step 4.7, else go to Step 4.6.Step 4.6: setαk,l+1∈λ1αk,l,λ2αk,l; let l=l+1; then, go to Step 4.2.Step 4.7: setαk=αk,l and(14)sk=αkdk,ifyk+αkdk∈intΩ,θkαkdk,if otherwise,whereθk∈θ0,1, for some 0<θ0<1 and θk−1=Odk.Step 5: letδ˜k=δk. If δ˜k>minκk,sk, set δ˜k=γ3δ˜k, and apply Algorithm 6.1 and 6.3 in [20] to construct fully quadratic model m˜k in Byk,δ˜k. Set g˜k=∇m˜kandH˜k=∇2m˜k. Go to Step 3 to compute d˜k. Until δ˜k≤minκ¯˜k,s˜k. Update mk=m˜k,gk=∇m˜k,Hk=∇2m˜k, κ¯k=κ¯˜k, and sk=s˜k, and compute φksk.Step 6: setyk+1=yk+sk. Compute fk+1,mk+1,gk+1,andHk+1.Step 7: compute ratioρk=fyk−fyk+1/−φksk. Set(15)σk+1=γ−1σk,ifρk<γ1,σk,ifγ2≥ρk≥γ1,γσk,ifρk>γ2.Step 8: if neither (9) nor (10) holds, augment the filter set, else the filter does not change.Step 9: setx0k+1=yk+1andδk+1=δk. Then, the sample set Xk+1=x0k+1,…,xqk+1 is constructed in Byk+1,δk+1. Compute gk+1, Hk+1. Set k=k+1.Remark 1.
Now, we describe a concrete implementation in Step 3 using a Cauchy step which is constructed by an affine scaled gradient [21]. The search direction dk satisfies φkdk≤φkdkC, where(16)dkC=−ζkCD¯k2gk,ζkC=argminζ∈ℝ+φk−ζD¯k2gk,φkd=gkTd+12dTHkd+13σkd3.
As we all know that the computation of Cauchy condition usually is much cheaper than the computation in Step 3, we will give a relationship between the critical measureκ¯ and the affine gradient. Therefore, we can replace the predicted decrease by the Cauchy step at each criticality measure satisfying this relationship.Remark 2.
Similar to Lemma 5.1 in [16], we can prove that Step 5 will terminate in a finite number if κk≠0.Remark 3.
In Step 4, the scalarαk with yk+αkdk∈Ω denotes that(17)αk=defminmaxuj−ykjdkj,lj−ykjdkj,j=1,2,…,n,in which uj,lj,ykj, and dkj represent the jth elements of u,l,yk, and dk, respectively.


## 3.1. Initialization Step

An initial pointy0∈intΩ=y:l<y<u. Given a positive parameter σ0>0, a radius 1≥δ0>0, and constants γ1,γ2,γ,λ1,λ2, they satisfy that(12)0<γ1≤γ2<1,0<γ<1,0<λ1≤λ2<1.Initialize the filterℱ0. Choose ε∈0,1,ηf,ηh∈0,1,andγ3∈0,1. Set k=0.


## 3.2. Main Step

Step 1: set a interpolation points setXk such that yk∈Xk⊆Byk,δk; then, apply Algorithms 6.1 and 6.3 in [20] to construct the fully quadratic model mk=myk on Byk,δk. Set(13)gk=∇mk,Hk=∇2mk,κ¯k=κ¯yk,hyk=defD¯kgk.Step 2: ifκ¯k=0, stop at yk.Step 3: solve (7) and obtain dk.Step 4: line search.Step 4.1: letl=0 and αk,0=1.Step 4.2: setykαk,l=yk+αk,ldk.Step 4.3: ifℱ accepts ykαk,l, go to Step 4.4, else go to Step 4.6.Step 4.4: if1−ηhhyk≥hykαk,l, yk+αk,ldk∈Ω holds, and accept αk,l and go to Step 4.7, else go to Step 4.5.Step 4.5: iffyk−ηfαk,lhyk2≥fykαk,l, yk+αk,ldk∈Ω holds, and accept αk,l and go to Step 4.7, else go to Step 4.6.Step 4.6: setαk,l+1∈λ1αk,l,λ2αk,l; let l=l+1; then, go to Step 4.2.Step 4.7: setαk=αk,l and(14)sk=αkdk,ifyk+αkdk∈intΩ,θkαkdk,if otherwise,whereθk∈θ0,1, for some 0<θ0<1 and θk−1=Odk.Step 5: letδ˜k=δk. If δ˜k>minκk,sk, set δ˜k=γ3δ˜k, and apply Algorithm 6.1 and 6.3 in [20] to construct fully quadratic model m˜k in Byk,δ˜k. Set g˜k=∇m˜kandH˜k=∇2m˜k. Go to Step 3 to compute d˜k. Until δ˜k≤minκ¯˜k,s˜k. Update mk=m˜k,gk=∇m˜k,Hk=∇2m˜k, κ¯k=κ¯˜k, and sk=s˜k, and compute φksk.Step 6: setyk+1=yk+sk. Compute fk+1,mk+1,gk+1,andHk+1.Step 7: compute ratioρk=fyk−fyk+1/−φksk. Set(15)σk+1=γ−1σk,ifρk<γ1,σk,ifγ2≥ρk≥γ1,γσk,ifρk>γ2.Step 8: if neither (9) nor (10) holds, augment the filter set, else the filter does not change.Step 9: setx0k+1=yk+1andδk+1=δk. Then, the sample set Xk+1=x0k+1,…,xqk+1 is constructed in Byk+1,δk+1. Compute gk+1, Hk+1. Set k=k+1.Remark 1.
Now, we describe a concrete implementation in Step 3 using a Cauchy step which is constructed by an affine scaled gradient [21]. The search direction dk satisfies φkdk≤φkdkC, where(16)dkC=−ζkCD¯k2gk,ζkC=argminζ∈ℝ+φk−ζD¯k2gk,φkd=gkTd+12dTHkd+13σkd3.
As we all know that the computation of Cauchy condition usually is much cheaper than the computation in Step 3, we will give a relationship between the critical measureκ¯ and the affine gradient. Therefore, we can replace the predicted decrease by the Cauchy step at each criticality measure satisfying this relationship.Remark 2.
Similar to Lemma 5.1 in [16], we can prove that Step 5 will terminate in a finite number if κk≠0.Remark 3.
In Step 4, the scalarαk with yk+αkdk∈Ω denotes that(17)αk=defminmaxuj−ykjdkj,lj−ykjdkj,j=1,2,…,n,in which uj,lj,ykj, and dkj represent the jth elements of u,l,yk, and dk, respectively.


## 4. Global Convergence Analysis

Next, we will present some properties of the algorithm PFARC which will be referenced in analysis of global and local convergence. Denote the indices set of the augmented filter byA. First, we make some assumptions as following.Assumption 1.
The iteratesyk remain in ℒy0, where ℒy0 is the level set of f, ℒy0=y∈Rn|fy0≥fy,y∈Ω.Assumption 2.
Letf:Rn⟶R be twice continuously differentiable and bounded from below, and its gradient is Lipschitz continuous with Lipschitz constants Lg.Assumption 3.
Assume thatDy≤κD, D¯y≤κD, ∇fy≤κg, and ∇2fy≤κh, for all y∈ℒy0, respectively, where κD, κg, and κh are positive constants.
Letdk be a solution to (7); the following equations,(18)Hk+σkdkIdk=−gk,are the first-order necessary conditions of (7).
Consequently, from Assumptions1–3, (5), and the choice of δk in Step 5, we can get that(19)κlf≤fy≤κuf,Hk≤κh+κehδ0=defκH,gk≤∇fyk+∇fyk−gk≤κg+κegδ02=defκng.
Letκ¯ denote any criticality measure for the derivative-free model such that(20)β¯1κ¯y≤hy=defD¯y∇myholds on Ω, for some β¯1>0. Certainly, β¯1κ¯k≤κDκng and a natural choice for κ¯ satisfying (20) is κ¯=hy/β¯1. And, there exist an β1>0 such that β1κy=Dy∇fy. First, we show that hy is a criticality measure, which can be found in [21].Lemma 1.
The functionhyk defined in (20) is a critical measure.Lemma 2.
Letdk satisfy the Cauchy decrease condition in Remark 1. If κ¯k≠0, there is a constant β¯2>0 which only depends on β¯1,κD, and κH such that the following holds:(21)−φkdk≥β¯2κ¯kmin1,κ¯kσk,κ¯k.Proof.
Setdk=−D¯k2gk and hyk=D¯kgk. First, we derive an upper bound to φkdkC=φkζkCdk=minφkζdk;ζ≥0,ζdk∈Ω; then, apply φkdk≤φkdkC. It is easy to see that gkTdk=−hyk2≤−β¯12κ¯k2<0, since, by (20), the maximum step-size ζ1 arrived at the lower bounds to Ω−yk is(22)ζ1=minyk−ljdkj;dkj≤0=minyk−ljD¯kjjhykj;gkj>0,ykj>lj≥minyk−ljminyk−lj,u−ykj+μgkjhyk;gkj>0,ykj>lj≥1hyk.
The step-sizeζ2 arrived at the upper bounds to Ω−yk is calculated in the same way:(23)ζ2=minu−ykjdkj;dkj≥0≥1hyk.
Letak=1/3σkdk3,bk=1/2dkTHkdk,andck=gkTdk. Noting that ak>0 and ck<0, the function φkζdk=ζgkTdk+ζ2/2dkTHkdk+ζ3/3σkdk3=defakζ3+bkζ2+ckζ,ζ≥0 attains its global minimum at ζ=ζ3, where(24)ζ3=−bk+bk2−3akck3ak=−ckbk2−3akck+bk≥11/4κD4κH+σkκD3hxk+1/2κD2κH≥12min1κD2κH,1κDκDσkhxk.
We haveζkC=minζ1,ζ2,ζ3. If ζkC<ζ3, then(25)ζkCbk2−3akck+bk<−ck,and furthermore,(26)ak<ck2+2bkckζkC−3ckζkC2=−ck−2bkζkC3ζkC2.
Then, ifHk is positive semidefinite, that is, bk≥0, we have that(27)2ζkCbk<−ck,ζkC−3akck<−ck.
That is,(28)bk<−ck2ζkC,ak<ck3ζkC2,φkζkCdk=akζkC3+bkζkC2+ckζkC<ck3ζkC2ζkC3−ck2ζkCζk2+ckζkC=−56ζkChxk2.
Otherwise,bk<0, we can get that −3akckζkC/2max−3akck,−2bk<−ck, from −3akckζkC/bk2−3akck−bk<−ck, which is equivalent to (25).
First, assume thatmax−3akck,−2bk=−3akck. Therefore, from (25), we have(29)ζkC5bk2+bk<−ck.
Noting that−bk<0, we can also obtain(30)−bk<−ck5−1ζkC.
By combiningbk<0, (26), and (30), we can get that(31)φkζkC=akζkC3+bkζkC2+ckζkC<23ckζkC−235−1ckζkC<−16ζkChxk2.
Now, assume thatmax−3akck,−2bk=−2bk; then,(32)bk<−ck+3akζkC22ζkC,φkζkCdk=akζkC3+bkζkC2+ckζkC<akζkC3−ck+3akζkC22ζkCζkC2+ckζkC<−12ζkChxk2.
On the contrary,ζkC=ζ3=−bk+bk2−3akck/3ak, and we obtain that(33)akζkC3+23bkζkC2+13ckζkC=0,φkζkCdk=akζkC3+bkζkC2+ckζkC=13bkζkC2+23ckζkC.
Ifbk<0,(34)φkζkCdk<23ckζkC=−23ζkChxk2.
Ifbk≥0, we can have that bk<−ck/ζkC from ζkC=ζ3=−bk+bk2−3akck/3ak, and then,(35)φkζkCdk=13bkζkC2+23ckζkC<13ckζkC=−13ζkChxk2.
Then, combiningφkdk≤φkdkC=φkζkCdk and (20) and (22)–(35), −φkdk≥β¯2κ¯k2 holds, where β¯2>0 is a constant which only depends on β¯1,κD, and κH. The proof is completed.
The following lemma from [5] gives a useful bound on the step dk.Lemma 3.
Ifdk is a solution in Step 3, then(36)dk≤3σkmaxκH,β¯1σkκ¯kκD.Assumption 4.
Suppose that∇dφkdk≤κθmin1,dk⋅gk, where κθ∈0,1.Lemma 4.
Let Assumptions1–4 hold and mk be fully quadratic. If(37)σkκ¯k≥9β¯11−γ1β¯2κDmaxLg+κegδ0+κH,1,κ¯k=defκHB,then ρk≥γ1 and σk≥σk+1.Proof.
From (37), we will get that κ¯k≠0 because, otherwise, the algorithm would have terminated; then, κ¯k=0 will conflict with (37). However,(38)ρk−γ1=fyk+sk−fyk−φksk+1−γ1φkskφksk.
Firstly, using a Taylor expansion, for someξk∈0,1, the first term of the numerator in the fraction above becomes that(39)fyk+sk−fyk−φksk=fyk+∇fyk+ξkskTsk−fyk−gkTsk−12skTHksk−σk3sk3≤∇fyk+ξksk−∇fyk+∇fyk−gk⋅sk+12κHsk2≤θkαkmaxLg+κegδ0+κH,1,κ¯k⋅9β¯1κ¯kκDσk,where Assumption 2, Lemma 3, and (37) are used.
Next, we consider the second term of the numerator in the fraction:(40)1−γ1φksk≤−1−γ1β¯2θkαkκ¯kmin1,κ¯kσk,κ¯k≤37−1−γ1β¯2θkαkκ¯k2⋅1σkκ¯k.
However, the denominatorφksk<0 is from Lemma 2.
Thus, following with (37)–(40), we get that(41)ρk−γ1≥θkαkmaxLg+κegδ0+κH,1,κ¯k9β¯1κ¯k/κDσk−β¯21−γ1αkθkκ¯k2⋅1/σkκ¯kφksk=θkαkκ¯k⋅9β¯1maxLg+κegδ0+κH,1,κ¯k−β¯21−γ1κDσkκ¯kκDσkφksk≥370.
Thus,ρk≥γ1 and σk≥σk+1 are from Step 7.Assumption 5.
Letσk≥σmin>0; then, σk⟶∞ as αk⟶0.
Assumption5, which is reasonable when we use Armijo backing line search or Wolfe condition (ii) for global convergence, is important to promote global convergence.
Ifyk+αkdk satisfies Armijo condition, fyk+αkdk≤fyk+c1αk∇fykTdk, where c1 is in 0,1, we assume that αk=αk,l, where l is the first integer such that αk,l satisfies Armijo condition, and we can get that(42)fyk+αkλ1dk>fyk+αkλ1c1∇fykTdk.
Then, we can get that(43)αkλ1∇fyk+ξkαkλ1dk−∇fykTdk+αkλ11−c1∇fyk−gkTdk+αkλ1c1gkTdk>0,where ξk∈0,1. From Assumption 2 and (5), then(44)αkλ12Lgdk2+αk3λ11−c1κegdk3+αkλ1c1gkTdk>0.
Dividing (44) by αk/λ1 and applying Lemma 2,(45)αkλ1Lgdk2−αk2c1−1κegdk3>c1β¯2κ¯kmin1,κ¯kσk,κ¯k.
Ifκ¯k>ε, using Assumption 3 and the fact that dk is bounded, dk≤3maxκH/σk,β¯1κ¯k/κDσk≤3maxκH/σmin,κng/σmin, we can infer that σk⟶∞ as αk⟶0 from (45).
Then, we show that Assumption5 can be also achieved when ykαk=yk+αkdk satisfies the Wolfe condition (ii):(46)∇fyk+αkdkTdk≥c2∇fykTdk,in whichc2∈0,1.
We rewrite it as(47)∇fyk+αkdk−∇fykTdk+1−c2∇fyk−gkTdk+1−c2gkTdk>0.
From Assumption2 and (5) again, we have that(48)Lgαkdk2+1−c2αk2κegκD2dk3+1−c2gkTdk>0.
Using Lemma2 and Assumption 3, the following inequality,(49)Lgαkdk2+1−c2αk2κegκD2dk3>1−c2β2κ¯k⋅min1,κ¯kσk,κ¯k,holds. Consequently, limαk⟶0σk=∞ if κ¯k>ε.Assumption 6.
Assume thatsigngyj=sign∇fyj∀y∈By∗,δ, when ∇fy∗j=0,j=1,2,…,n.Lemma 5.
Let Assumptions1–6 hold. If A<∞ and after many steps with a KKT points yk of (1), algorithm PFARC does not stop; then, limk⟶∞κ¯k=0.Proof.
Choose an integerK that satisfy that the filter is not augmented in iteration for all iteration k≥K. Step 4 in algorithm PFARC gives that either (9) or (10) holds. If (9) holds for k≥K, then hyk+1≤1−ηhhyk≤⋯≤1−ηhk−KhyK+1 since ηh is in 0,1. Recall that β¯1κ¯k≤hyk, we infer that limk⟶∞κ¯k=0 holds. If (9) does not hold for certain k sufficiently large, algorithm DFFARC implies that, for each k which is greater than K,(50)fyk+1≤fyk−ηfαkhyk2.
Hence, for alli=1,2,…,(51)fyK+i=∑k=KK+i−1fyk+1−fyk+fyK≤−∑k=KK+i−1ηfαkhyk2+fyK.
To have a contradiction, we letκ¯k>ε. Then, hyk≥β¯1κ¯k≥β¯1ε and fyK−fyK+i≥∑k=KK+i−1ηfαkhyk2≥∑k=KK+i−1ηfαkβ¯12ε2. Since fyK+i is bounded from below, the right-hand side series is bounded as i⟶∞; then, limk⟶0αk=0.
Letαk be given in Step 4 with yk+αkdk∈Ω. It is easy to see that(52)∀y∈Ω,Dy∇fy=0⇔∇fyj≥0,ifyj=lj,≤0,ifyj=uj,=0,iflj≤yj≤uj,which is the KKT-conditions of (1). From the continuity of f, Assumption 6, and (5), we can get that gykj has the same sign when yk is close to y; then, αk↛0 as k⟶∞.
Furthermore, ifαk is obtained from the reduced conditions in Step 4, we have that σk⟶∞ from Assumption 5. Recall that κ¯k>ε, we can have that, for sufficiently large k, σkκ¯k>σkε>κHB; then, σk≥σk+1 from Lemma 4. According to the updating role in σk, if σk<σk+1=γ−1σk, then σk≤κHB2/ε<κHB2/γε from Lemma 4. By induction, σ0≤maxσ0,κHB2/γε. Suppose the claim that σk≤maxσ0,κHB2/γε holds. It is obvious that σk+1≤maxσ0,κHB2/γε if σk≥σk+1. If σk<σk+1, then σk≤κHB2/ε; consequently, σk+1≤maxσ0,κHB2/γε since σk+1=γ−1σk≤κHB2/γε. The claim σk≤σmax=maxσ0,κHB2/γε, which contradicts to σk⟶∞. Hence, αk↛0, and our hypothesis κ¯k>ε is impossible. Thus, the conclusion holds.Lemma 6.
Let Assumptions1–6 hold and A=∞. If algorithm PFARC does not stop after finite steps at a KKT points of yk in (1), then(53)limk⟶∞,k∈Aκ¯k=0.Proof.
To get a contradiction, we suppose that, for all largeki, κ¯ki≥ε, where ki is a subsequence of A and ε>0 is a constant. By the definition of ki, the pair of hyki,fyki is augmented to ℱ. Thus, there exists an infinite subsequence kij⊆ki such that κ¯kij⟶0 from the compactness theorem, which contradicts to κ¯ki≥ε. Hence, (53) holds.Lemma 7.
Let Assumptions1–6 hold, and sequence Qk is probabilistically κeh,κeg,κef fully quadratic. Yk is a sequence of random iterates generated by algorithm PFARC. If any limit point y∗ of yk satisfies the strict complementarity, then liminfk⟶∞DYk∇fYk=0 almost surely.Proof.
Combining the affine scaling technique with the proof in Theorem 4.2 in [18], it is easy to derive the conclusion similar to Theorem 4.8 in [19]. We have omitted this section for reasons of length.Theorem 1.
Let Assumptions1–5 hold, and algorithm PFARC does not stop after finite steps at a KKT points of yk in (1); thus,(54)limk⟶∞κ¯k=0.Proof.
From Lemmas5 and 6, we just think about this one case in which there are k1,k2 with k1∈A and k2∉A, and k1,k2 are larger than integer K. If (54) does not hold, there is a subsequence yki such that κ¯ki≥2εandki∉A. From Lemma 6, we also have, for every ki, that κ¯li<ε; the iterate yli is the first iterate after yki such that hyli,fyli is augmented to ℱ, that is, li∈A. Thus,(55)κ¯k≥ε,withki≤k<lifor alli.
Obviously,K=k∈ℕ|ki≤k<li is infinite, where ki and li are defined as above.
For everyk=ki,…,li−1∉A, we have that either (9) or (10) holds. If (9) holds, then 1−ηhhyk≥hyk+1. Since 0<ηh<1 and hyk≤κDκng and hyk+1⟶0, then κ¯k+1⟶0 which contradicts to (55). Then, algorithm PFARC implies that (10) holds. Thus, fyk−ηfαkβ¯12ε2>fyk−ηfαkhyk2≥fyk+1.
Moreover,fyk is monotonically decreasing and fyki+1≥fyli. Consequently,(56)fyki−ηfαkiβ¯12ε2>fyki−ηfαkihyki2>fyki+1≥fyli,∀i.
This ensures thatfyki+1≥fyli,∀K∈ℕ, with some i≥K, because otherwise the inequality above will give that(57)fyki−ηfαkiβ¯12ε2>fyki+1≤fyki−ηfαkihyki2≥fyli>fyki+1,∀i.
Similar to proof of Lemma5, we can to prove that αk∈K1↛0, where K1⊆ℕ. Furthermore, from Assumption 5, we can get σk⟶∞ as αk⟶0. Recall that β¯1κ¯k≤κDκng and dk≤3β¯1κ¯k/κDσk; thus, dk⟶0, and then, θk⟶1, where θk is defined in Step 4, so sk=αkdk. However,(58)−φ¯ksk=−φ¯αkdk≥αkβ¯2κ¯kmin1,κ¯kσk,κ¯k≥αkβ¯2ε⋅κD23β¯12dk=β¯2ε⋅κD23β¯12sk,fyk+sk−fyk−φksk=∇fyk+ξkskTsk−gkTsk−12skTHksk−13σksk3≤∇fyk+ξkdk−∇fykTsk+∇fyk−gkTsk+κHsk2≤Lg+κegsk+κHsk2.
Thus, combining (58) and inequalities above, we can have for sufficiently large k that(59)ρk=1−fyk+sk−fyk−φksk−φksk≥1−3β¯12Lg+κegsk+κHsk2β¯2κD2εsk≥γ2.
Then,(60)fyk−fyk+1=fyk−fyk+sk≥η2−φksk≥η2β¯2κD2ε3β¯1sk.
Consequently,(61)yki−yli≤∑k=kili−1sk≤3β¯1η2β¯2κD2εfyki−fyli.
Sincefyk is convergent, we can get yki−yli⟶0 from (61). However, κ¯ is uniform continuous on ℒx0. Thus, κ¯ki−κ¯li⟶0 holds, which conflicts to the fact that κ¯ki−κ¯li≥ε. Therefore, our assumption is wrong and αk↛0.
Combining (57) with αki↛0, we get that fyki⟶−∞, which conflicts to fyk is bounded below. Thus, there is a subsequence ij⊂i such that(62)fykij+1≥fylij.
Sincekij+1 is not in A and ℱlij⊆ℱkij+1, it follows from (7) and (62) that(63)1−ηhhylij≥hykij+1.
For allj, lij∈li⊆A, Lemma 6 implies limj⟶∞hylij=0. Consequently, from (63), we get that limj⟶∞hykij+1=0; it contradicts to that hykij+1≥β¯1κ¯kij+1≥2β¯1ε since kij+1∉A. Thus, the claim holds.


## 5. Properties of the Local Convergence

We can know that any limit pointy∗ of (1) is a KKT point from Theorem 1. In the following section, we consider the local convergence of algorithm PFARC, where the following assumptions are required.Assumption 7.
Assume thatlimk⟶∞∇2fyk−Hkdk/dk=0 as limk⟶∞κ¯k=0.Assumption 8.
Assume thaty∗ satisfies(64)∃κc>0such thatdT∇2fy∗d≥2κcd2,∀d≠0.
Noting thatDy∗2∇fy∗=0 is equivalent to Dy∗∇fy∗=0, then Dk2∇fyk⟶0 is equivalent to the fact Dk∇fyk⟶0. Let h1y=D¯y2gy. From (5), the fact h1yk⟶0 is equivalent to the fact hyk⟶0, as k⟶∞. To illustrate the properties of the local convergence, we substitute hyk for h1yk in Step 4.4. That is, we accept the trial step αk,l if(65)h1ykαk,l≤1−ηhh1ykwithyk+αk,ldk∈Ωholds in Step 4.4 in the following sections.Theorem 2.
Assume that Assumptions1–8 hold and algorithm PFARC does not stop finite step at a KKT points yk of (1); then, dk⟶0,αk≡1 for large k and all iterations eventually satisfy ρk>γ2,σk is bounded from above as k⟶∞.Proof.
Theorem1 gives that limk⟶0κ¯k⟶0 from the assumptions in Theorem 2. Consequently, Assumption 7 implies that limk⟶∞∇2fyk−Hkdk/dk=0.
Thus, for largek,(66)dkT∇2fyk−Hkdk≤κcdk2,in which κc appears in Assumption 8. And, we also have that dkT∇2fykdk≥2κcdk2 for large k from Assumptions 2 and 8. Then, we can infer that 2κcdk2≤dkT∇2fykHkdk+dkTHkdk≤κcdk2+dkTHkdk. As a consequence, dkTHkdk≥κcdk2. So, Hk is positive definite. And,(67)κcdk2≤dkTHkdk≤dkTHk+σkdkIdk=18−gkTdk≤gk⋅dk.
Sincedk≠0, the first and last terms above give(68)dk≤gkκc.
Otherwise,−φkdk=0, from Lemma 2. This, however, contradicts −φkdk>0 since χ¯k≠0. Recall that(69)D¯kgk=0⇔gyj≥0,ifyj=li,≤0,ifyj=ui,=0,iflj≤yj≤uj,and we can get gk⟶0, from κ¯k⟶0. Thus, (68) gives that dk⟶0. Furthermore, θk⟶1, in which θk appears in Step 4. Then, sk=αkdkands^k=αkd^k for large k.
Assumption6 provides that signgkj and sign∇fykj is the same for large k if ∇fy∗j=0. On the other side, (5) gives that signgkj and sign∇fxkj are also the same for large k if ∇fy∗j≠0 for some j. Thus, Dk=D¯k for large k.
Now let us think aboutσk. From Step 7, ρk=1−fyk+sk−fyk−φksk/−φksk.
However, using a Taylor expansion, for someξk∈0,1,(70)fyk+sk−fyk−φksk=∇fykTsk+12skT∇2fyk+ξksksk−gkTsk−12skTHksk−13σksk3≤∇fyk−gkTsk+12skT∇2fyk+ξksksk−12skTHksk≤κDκegκ¯ksk2+12κD2sk2⋅∇2fyk+ξksk−∇2fxk+12sk2∇2fyk−Hksksk,φksk=gkTsk+12skTHksk+13σksk3=18−skTHk+σkskIsk+12skTHksk+13σksk3=−12skTHksk−23σksk3≤−12skTHksk≤−κc2sk2.
Together with the inequalities above, for largek,(71)ρk≥1−κDκegκ¯k+1/2κD2∇2fyk+ξksk−∇2fyk+1/2∇2fykHksk/skκc/2>γ2,where the last inequality is from κ¯k⟶0 and Assumptions 2 and 7. Recall the updating role in σk in Step 7, and we get that(72)σk>σk+1=γσk,0<γ<1,ksufficiently large.
Thus,σk is bounded from above and σkdk⟶0. Clearly, h1yk=D¯k2gk≠0. Set εk=1−ηh/2δ1h1yk, where δ1 is sufficiently small such that(73)h1yk+∇h1ykdk=D¯k2gk+D¯k2Hk+D¯kdiaggkJ¯kdk≤18σkκD2dk2+D¯kgk⋅dk≤κD2σkdk+β1κ¯kdk≤εkdk,whenever dk≤δ1. Let ωk=1−ηh/2δ2h1yk, where δ2 is sufficiently small such that(74)h1yk+dk−h1yk−∇h1ykdk≤ωkdk,whenever dk≤δ2. Such δ2 exists by Lemma 1.2 in [22].
Then, it follows that(75)|h1yk+dk≤h1yk+dk−h1yk−∇h1ykdk+h1yk+∇h1ykdk≤ωkdk+εkdk≤1−ηhδh1yk⋅dk≤1−ηhh1yk,whenever dk≤δ, where δ=minδ1,δ2.
Letαk be given by yk+αkdk∈Ω in Step 4. Similar to the proof of Lemma 5, we can also get that αk↛0. Therefore, αk≡1 for large k.Corollary 1.
Under the conditions of Theorem2, then(76)Dk+12∇fyk+1Dk2∇fyk⟶0,ask⟶∞,(77)yk+1−y∗yk−y∗⟶0,ask⟶∞.Proof.
Recalling (5) and Dk=D¯k for large k, we obtain the following inequalities:(78)Dk+1∇fyk+1≤Dk+1∇fyk+1−hyk+1+hyk+1≤κDκegκ¯k+1+β¯1⋅κ¯k+1,Dk∇fyk≥hyk−hyk−Dk∇fyk≥β¯1−κDκegκ¯k⋅κ¯k.
Hence,(79)Dk+1∇fyk+1Dk∇fyk≤κDκegκ¯k+1+β¯1⋅κ¯k+1β¯1−κDκegκ¯k⋅κ¯k⟶0,as k⟶∞. The limit in (79) is from (75). In fact, (75) gives that h1yk+1=oh1yk since dk⟶0. Thus, hyk+1=ohyk, Furthermore, κ¯k+1=oκ¯k. Noting that Dk2∇fyk⟶0 is equivalently to Dk∇fyk⟶0, we have that (76) holds.
Sincey∗ is the limit point of yk, there exist positive scales β3,β4,β5,β6, such that(80)β3yk+1−y∗≤Dk+1−2∇fyk+1≤β4yk−y∗,β5yk+1−y∗≤Dk−2∇fyk≤β6yk−y∗.
Consequently, (77) holds from the inequalities above and (76).


## 6. Numerical Analysis

The main task of this section is to test the algorithm PFARC constructed in this paper by solving actual test problems. We use MATLAB 2014a to program the algorithm, solve all the test problems in Table1, and record the corresponding results. The initial parameters given by the algorithm PFARC are as follows:(81)σ0=1,δ0=0.5,γ1=0.3,γ2=0.7,γ=0.6,λ1=0.1,λ2=0.7,ηf=0.8,ηh=0.8,γ3=0.5.Table 1
The information of test problems.
ProblemsnluHS052[−1.5, −3][4, 3]HS182[2, 0][50, 50]HS192[13, 0][100, 100]HS212[2, −50][50, 50]HS233[−50, −50][50, 50]HS303[1, −10, −10][10, 10, 10]HS313[−10, 1, −10][10, 10, 1]HS343[0, 0, 0][100, 100, 100]HS363[0, 0, 0][20, 11, 42]HS373[0, 0, 0][42, 42, 42]HS384[−10, −10, −10, −10][10, 10, 10, 10]HS414[0, 0, 0, 0][1, 1, 1, 2]HS455[0, 0, 0, 0, 0][1, 2, 3, 4, 5]HS535[−10, …, −10][10, …, 10]HS592[0, 0][75, 65]HS603[−10, −10, −10][10, 10, 10]HS623[0, 0, 0][1, 1, 1]HS653[−5, −5, −5][5, 5, 5]HS663[0, 0, 0][100, 100, 1]HS684[0.0001, 0, 0, 0][100, 100, 2, 2]HS714[1, 1, 1, 1][5, 5, 5, 5]HS805[−2.3, −2.3, −3.2, −3.2, −3.2][2.3, 2.3, 3.2, 3.2, 3.2]HS835[78, 33, 27, 27, 27][102, 45, 45, 45, 45]HS11010[2.001, …, 2.001][9.999, …, 9.999]In this paper, the termination precision of PFARC is set toε=10−5.In the following table, every test problem comes from [23], where n represents the dimension of the problems and l and u represent the lower bound and upper bound of the problems, respectively.Next, we will use PFARC and BOBYQA to solve the same problems in Table1, respectively, and the results are recorded in Table 2, where INTR1 and INTR2 represent the number of iterations in PFARC and BOBYQA, respectively.Table 2
The calculation results.
ProblemsnINTR1INTR2HS0524145HS182276HS21222467HS232268HS253240HS303385HS313399HS3434148HS3634171HS3735270HS38417385HS4142158HS4552189HS5354168HS59210387HS6033271HS6233233HS6533152HS6637311HS6846298HS7148176HS805373HS83514692HS1101014771From the comparison results in Table2, we can easily see that our algorithm PFARC can use a few iterations to get the optimal solution when solving the test problem given in Table 1, while BOBYQA algorithm needs a large number of iterations, which shows that PFARC has advantages in calculating the given test problems in Table 1.In order to further test our algorithm, we will use PFARC given by this paper to calculate the problems given in [3], and the comparison results are recorded in Table 3. In Table 3, n represents the dimension of the problems, INTR3 represents the number of iterations in PFARC, and INTR4 represents the number of iterations for the algorithm given in [3]. In addition, the questions in Table 3 are from [24].Table 3
The calculation results.
ProblemsnINTR3INTR4S201224S203257S206235S207267S212359S21331227S240313S25641016S26141212S283101034From the results in Table3, it can be seen that the same problem is solved by the ARC method using the interpolation technology without derivative. The number of iterations required by PFARC is less than the number of iterations in [3]. The import reason is that filter technique implemented in PFARC has two goals: minimization of f and h, but a line search technique in [3] only performed the minimization of f. Therefore, our algorithm PFARC is more effective for solving bounded constrained derivative-free optimization problems.In this paper, we propose a new algorithm PFARC for solving box constrained optimization problems without derivatives, which further complements the algorithm library for solving this kind of optimization. Since box constrained optimization is a classical problem, the proposed algorithm is an evolution of the existing algorithms, which further improved the existing ones. Box constrained optimization can be used in many fields, such as finance, science and technology, and military industry. Because the derivative information observed often is unavailable or unreliable, the derivative-free algorithm we proposed is closer to the reality. In the future, we can use the idea of this algorithm PFARC to solve other optimization problems, which is what we are going to do later.



---

*Source: 1496048-2021-10-30.xml*