# A Frame-Based Conjugate Gradients Direct Search Method with Radial Basis Function Interpolation Model

Authors: Xiaowei Fang; Qin Ni
Journal: Discrete Dynamics in Nature and Society
 (2017)

---

## Abstract

In this paper, we propose a new hybrid direct search method where a frame-based PRP conjugate gradients direct search algorithm is combined with radial basis function interpolation model. In addition, the rotational minimal positive basis is used to reduce the computation work at each iteration. Numerical results for solving the CUTEr test problems show that the proposed method is promising.


---

## Body

## 1. Introduction

In this paper, we consider the following problem:(1)
min
x
∈
R
n
⁡
f
x
,where function f is assumed to be continuously differentiable from R
n into R, and the derivative information is unavailable or untrustworthy, for example, because of noise and using finite differences. Problem (1) has numerous applications in engineering, such as the helicopter rotor blade design [1, 2], the aeroacoustic shape design [3], groundwater community problems [4], and medical image registration problems [5].There are two main methods for solving (1). The first class of methods is the model based methods, which are constructed by means of multivariate interpolation, including under and overdetermined. These methods were introduced by Powell [6] and Winfield [7] and were developed by [8–11]. The second class of methods is the direct search methods which are based on the comparison rules of objective function values. These methods were pioneered by Hooke and Jeeves [12]. The convergence theory was established by Torczon [13, 14]. Audet and Dennis [15] proposed a general framework for direct search method. Coope and Price [16] extended the PRP method [17, 18] to solve (1) and presented a frame-based conjugate gradients direct search algorithm (Max-PRP for short). In each iteration, Max-PRP employed the fixed maximal positive basis to estimate the first and second gradients; then the search direction is determined by employing the PRP formula. Numerical tests showed that the Max-PRP was effective on a wide variety of unconstrained optimization problem. In addition, some classical and modern direct search methods were introduced by Kolda et al. [19].Generally, model based methods are more efficient than direct search methods in that they are able to exploit structure inherently in the problem. But direct search methods are simpler to code and to parallelize. Therefore, it is natural to try to combine both methods. In 2010, Custódio et al. [20] proposed a hybrid method integrating minimum Frobenius norm quadratic interpolation models in a direct search framework and numerical results showed that the addition of quadratic interpolation models improved the performance of the direct search method. In 2013, Conn and Le Digabel [21] showed that the use of quadratic interpolation models can improve the efficiency of the mesh adaptive direct search method.The above hybrid algorithms were based on the quadratic interpolation models. In 2008, Wild et al. [22] presented a new derivative-free algorithm (ORBIT for short), which employed radial basis function (RBF) interpolation models. The RBF interpolation models allowed ORBIT to interpolate nonlinear functions using fewer function evaluations than the quadratic interpolation models. In 2013, Wild and Shoemaker [23] proved the global convergence of the ORBIT under some mild assumptions. Numerical results showed that the method using RBF interpolation models outperformed methods using quadratic interpolation models.Motivated by the efficiency of the ORBIT, we propose a new hybrid direct search method, which combines the frame-based conjugate gradients strategies with the RBF interpolation models. In each iteration, a minimal positive basis is used to construct the frame. In a maximal positive basis,2
n function values are computed, while, in a minimal positive basis, n
+
1 function values are evaluated. So the computation work in the new hybrid direct search method can be reduced. In addition, when the trial point of RBF interpolation models cannot satisfy the decrease condition, we employ PRP formula to get the search direction, which is similar to the Max-PRP. Furthermore, we rotate the minimal positive basis according to the local topography of objective function, making our method more effective in practice. The convergence is established under some mild conditions. Some numerical results show that the proposed method is promising.This paper is organized a s follows. In Section2, we present some basic notions for positive basis, frame, and describe our method. In Section 3, we prove the convergence of the proposed method. In Section 4, numerical results show the efficiency of method derived in this paper compared to Max-PRP [16]. Concluding remarks are given in Section 5. The default norm used in this paper is Euclidean.


## 2. The New Hybrid Direct Search Method

We first state the definition about positive basis, which can be found in [24].Definition 1.
Positive basisV in R
n is a set of vectors with the following two properties: (i)
Every vector inR
n is a nonnegative linear combination of the members of V.
(ii)
No proper subset ofV satisfies (i).It is easy to know that cardinality of any positive basisV satisfies n
+
1
≤
|
V
|
≤
2
n. Two famous and simple examples of positive bases are (2)
V
m
i
n
=
v
1
,
…
,
v
n
,
-
∑
i
=
1
n
v
i
,
V
m
a
x
=
v
1
,
…
,
v
n
,
-
v
1
,
…
,
-
v
n
,where v
1
,
…
,
v
n is a basis for R
n, V
m
i
n represents the minimal positive basis, and V
m
a
x represents the maximal positive basis.In addition, we give some concepts about frames, which were proposed by Coope and Price [25, 26].Definition 2.
A frame can be defined as(3)
Φ
=
x
+
h
v
:
v
∈
V
,where x
∈
R
n is a central point of a frame, h
>
0 is frame size, and V is a positive basis in R
n.Definition 3.
A frameΦ is a minimal frame, if and only if (4)
f
x
≤
f
y
,
∀
y
∈
Φ
.Definition 4.
A frameΦ is a quasi minimal frame if and only if (5)
f
x
≤
f
y
+
ϵ
,
∀
y
∈
Φ
,where ϵ
=
h
1
+
μ, μ is a positive constant, and the corresponding central point x is called a quasi minimal point.Letx
k be kth iterate. We will discuss the strategy of RBF interpolation model, search direction, and rotation of positive basis in detail below.


### 2.1. RBF Interpolation Model

Choose a positive basisV
k
=
v
1
k
,
v
2
k
,
…
,
v
q
k
q
≥
n
+
1 and obtain a set of interpolate data points Y
=
y
1
,
y
2
,
…
,
y
n
q
∈
R
n
n
q
≥
q
+
1, where y
1
=
x
k, y
2
=
x
k
+
h
k
v
1
k
,
…
,
y
q
+
1
=
x
k
+
h
k
v
q
k, h
k
>
0 is the frame size, and the other points of set Y are chosen in the subset of previously evaluated points.RBF interpolation model is a popular model for optimization, and some theory and implementations can be found in [27]. Corresponding to the set of interpolate data points Y, we get the following RBF interpolation model:(6)
m
^
k
x
=
∑
i
=
1
n
q
λ
i
ϕ
x
-
y
i
+
∑
j
=
1
r
γ
j
p
j
x
,where ϕ
:
R
+
→
R is a radial basis function and λ
1
,
…
,
λ
n
q
,
γ
1
,
…
,
γ
r
∈
R are parameters to be determined. p
1
,
…
,
p
r are polynomial tails used in the context of RBF interpolation models, which most frequently are linear.In addition, coefficientsλ
1
,
…
,
λ
n
q are required to satisfy(7)
∑
i
=
1
n
q
λ
i
p
j
y
i
=
0
,
j
=
1
,
…
,
r
.These, in conjunction withn
q interpolation conditions m
^
k
(
y
l
)
=
f
(
y
l
), l
=
1
,
…
,
n
q
.We define the linear system:(8)
Φ
P
P
T
0
Λ
Γ
=
f
0
,where Λ
=
λ
1
,
…
,
λ
n
q
T, Γ
=
γ
1
,
…
,
γ
r
T, f
=
f
y
1
,
…
,
f
y
n
q
T, and Φ
l
i
=
ϕ
y
l
-
y
i for l
,
i
∈
1
,
…
,
n
q, P
i
j
=
p
j
y
i for i
∈
1
,
…
,
n
q, j
∈
1
,
…
,
r. We employ null-space method to solve system (8), which is similar to the approach of [22].Then, we minimize the RBF interpolation model by solving the following problem:(9)
min
x
∈
B
x
k
;
Δ
k
⁡
m
^
k
x
,where B
(
x
k
;
Δ
k
)
=
x
∈
R
n
:
x
-
x
k
≤
Δ
k, Δ
k
=
δ
k
h
k
max
⁡
v
1
k
,
…
,
v
q
k, and δ
k is the radius factor parameter.


### 2.2. PRP Direction

Consider the following linear model:(10)
m
-
k
x
=
f
x
k
+
g
k
T
x
-
x
k
,where g
k
∈
R
n. The coefficients can be determined by q regression interpolation conditions:(11)
m
¯
k
x
k
+
h
k
v
l
k
=
f
x
k
+
h
k
v
l
k
,
l
=
1
,
…
,
q
.Then, we have that(12)
f
x
k
+
h
k
v
l
k
=
f
x
k
+
h
k
g
k
T
v
l
k
,
l
=
1
,
…
,
q
.This system can be solved by the method of least squares. For example, if we choose the positive basis V
k as V
m
i
n, and v
i
=
e
i
(
i
=
1
,
…
,
n
), where e
i is ith unit vector, then ith element of g
k is calculated according to the following formula:(13)
g
k
i
=
1
h
k
f
x
k
+
h
k
e
i
-
f
x
k
-
h
k
e
+
∑
j
=
1
n
f
x
k
+
h
k
e
j
n
+
1
,where e
=
∑
j
=
1
n
e
j. The PRP direction is obtained by(14)
d
k
=
-
g
k
if
k
=
0
-
g
k
+
max
⁡
0
,
g
k
T
g
k
-
g
k
-
1
g
k
-
1
2
d
k
-
1
if
k
>
0
.


### 2.3. Rotation of the Positive Basis

In order to modify the positive basis such that at least one of the new directions is more closely conformed to the local behavior of the function, we rotate the positive basis at each step. This idea is similar to that in [28].Suppose that(15)
V
k
=
v
1
k
,
…
,
v
n
k
,
…
,
v
q
k
,where {
v
1
k
,
…
,
v
n
k
} is a basis for R
n. Denote(16)
δ
x
=
x
k
+
1
-
x
k
=
δ
x
1
,
…
,
δ
x
n
T
,where δ
x
i
∈
R
i
=
1
,
…
,
n describe the movements performed along the vectors v
i
k
i
=
1
,
…
,
n in previous iterations.We get positive basisV
k
+
1 by rotating V
k. Firstly, we obtain n linearly independent vectors according to V
k:(17)
v
¯
i
k
+
1
=
v
i
k
if
δ
x
i
=
0
∑
l
=
i
n
δ
x
l
v
l
k
if
δ
x
i
≠
0
,where v
¯
i
k
+
1 represents the sum of all the movements made in the directions v
l
k for l
=
i
,
…
,
n
. The lemma  8.5.4 of [29] proved that v
¯
1
k
+
1
,
…
,
v
¯
n
k
+
1 is linearly independent.Secondly, we use the Gram-Schmidt orthogonalization method to get a class of standard orthogonal basis:(18)
v
1
k
+
1
,
…
,
v
n
k
+
1
.Finally, we can get(19)
V
k
+
1
=
v
1
k
+
1
,
…
,
v
n
k
+
1
,
v
n
+
1
k
+
1
,
…
,
v
q
k
+
1
,where v
n
+
1
k
+
1
,
…
,
v
q
k
+
1 is combined with v
1
k
+
1
,
…
,
v
n
k
+
1 according to the same combination principal as V
k.For instance, ifq
=
n
+
1, we obtain(20)
V
k
+
1
=
v
1
k
+
1
,
…
,
v
n
k
+
1
,
-
∑
i
=
1
n
v
i
k
+
1
.Supposing thatz
m is the sequence of quasi minimal iteration points, then the above process can be summarized as the following algorithm.Algorithm 5.
Step  0 (initializations). Choose initial point x
0
∈
R
n, positive basis V
0, step length h
0, and radius factor parameter δ
0. Choose λ
>
1, μ
>
0, ϵ
k
=
h
k
1
+
μ. Set k
=
0, m
=
0.
Step  1 (checking the stopping condition). If the stopping condition is not met, then go to Step  2, otherwise output the lowest known point and stop.
Step  2 (determining the frame). Create a frame Φ
k at iterate x
k according to the positive basis V
k and step length h
k, and calculate the corresponding function values.
Step  3 (building the RBF interpolation model). Evaluate the RBF model parameters according to formula (8), and get solution x
^
k
+
1 of subproblem (9). If f
(
x
k
)
-
f
(
x
^
k
+
1
)
>
ϵ
k, then set x
k
+
1
=
x
^
k
+
1 and go to Step  6, otherwise go to Step  4.
Step  4 (obtaining the PRP direction). Obtain the search direction d
k using (14), execute the line search process to find β
k, and set x
¯
k
+
1
=
x
k
+
β
k
h
k
d
k
/
d
k. If f
(
x
k
)
-
f
(
x
¯
k
+
1
)
>
ϵ
k, then set x
k
+
1
=
x
¯
k
+
1 and go to Step  6, otherwise go to Step  5.
Step  5 (updating the current iteration point). Let x
k
+
1 be defined by the following rule:(21)
f
x
k
+
1
=
min
v
k
∈
V
k
⁡
f
x
k
,
f
x
^
k
+
1
,
f
x
¯
k
+
1
,
f
x
k
+
h
k
v
k
.
Step  6 (rotating the positive basis and updating the some parameters). Obtain V
k
+
1 according to (15)–(19) and compute δ
k
+
1. If frame Φ
k is a quasi minimal frame, then set h
k
+
1
=
h
k
/
λ, m
=
m
+
1, z
m
=
x
k, otherwise set h
k
+
1
=
h
k. In addition, increment k by one and go to Step  1.Remark 6.
In Step  3, we setp
1
,
…
,
p
r as linear polynomial tails, and ϕ
x
-
y
i
=
x
-
y
i
3 in (8).


## 2.1. RBF Interpolation Model

Choose a positive basisV
k
=
v
1
k
,
v
2
k
,
…
,
v
q
k
q
≥
n
+
1 and obtain a set of interpolate data points Y
=
y
1
,
y
2
,
…
,
y
n
q
∈
R
n
n
q
≥
q
+
1, where y
1
=
x
k, y
2
=
x
k
+
h
k
v
1
k
,
…
,
y
q
+
1
=
x
k
+
h
k
v
q
k, h
k
>
0 is the frame size, and the other points of set Y are chosen in the subset of previously evaluated points.RBF interpolation model is a popular model for optimization, and some theory and implementations can be found in [27]. Corresponding to the set of interpolate data points Y, we get the following RBF interpolation model:(6)
m
^
k
x
=
∑
i
=
1
n
q
λ
i
ϕ
x
-
y
i
+
∑
j
=
1
r
γ
j
p
j
x
,where ϕ
:
R
+
→
R is a radial basis function and λ
1
,
…
,
λ
n
q
,
γ
1
,
…
,
γ
r
∈
R are parameters to be determined. p
1
,
…
,
p
r are polynomial tails used in the context of RBF interpolation models, which most frequently are linear.In addition, coefficientsλ
1
,
…
,
λ
n
q are required to satisfy(7)
∑
i
=
1
n
q
λ
i
p
j
y
i
=
0
,
j
=
1
,
…
,
r
.These, in conjunction withn
q interpolation conditions m
^
k
(
y
l
)
=
f
(
y
l
), l
=
1
,
…
,
n
q
.We define the linear system:(8)
Φ
P
P
T
0
Λ
Γ
=
f
0
,where Λ
=
λ
1
,
…
,
λ
n
q
T, Γ
=
γ
1
,
…
,
γ
r
T, f
=
f
y
1
,
…
,
f
y
n
q
T, and Φ
l
i
=
ϕ
y
l
-
y
i for l
,
i
∈
1
,
…
,
n
q, P
i
j
=
p
j
y
i for i
∈
1
,
…
,
n
q, j
∈
1
,
…
,
r. We employ null-space method to solve system (8), which is similar to the approach of [22].Then, we minimize the RBF interpolation model by solving the following problem:(9)
min
x
∈
B
x
k
;
Δ
k
⁡
m
^
k
x
,where B
(
x
k
;
Δ
k
)
=
x
∈
R
n
:
x
-
x
k
≤
Δ
k, Δ
k
=
δ
k
h
k
max
⁡
v
1
k
,
…
,
v
q
k, and δ
k is the radius factor parameter.


## 2.2. PRP Direction

Consider the following linear model:(10)
m
-
k
x
=
f
x
k
+
g
k
T
x
-
x
k
,where g
k
∈
R
n. The coefficients can be determined by q regression interpolation conditions:(11)
m
¯
k
x
k
+
h
k
v
l
k
=
f
x
k
+
h
k
v
l
k
,
l
=
1
,
…
,
q
.Then, we have that(12)
f
x
k
+
h
k
v
l
k
=
f
x
k
+
h
k
g
k
T
v
l
k
,
l
=
1
,
…
,
q
.This system can be solved by the method of least squares. For example, if we choose the positive basis V
k as V
m
i
n, and v
i
=
e
i
(
i
=
1
,
…
,
n
), where e
i is ith unit vector, then ith element of g
k is calculated according to the following formula:(13)
g
k
i
=
1
h
k
f
x
k
+
h
k
e
i
-
f
x
k
-
h
k
e
+
∑
j
=
1
n
f
x
k
+
h
k
e
j
n
+
1
,where e
=
∑
j
=
1
n
e
j. The PRP direction is obtained by(14)
d
k
=
-
g
k
if
k
=
0
-
g
k
+
max
⁡
0
,
g
k
T
g
k
-
g
k
-
1
g
k
-
1
2
d
k
-
1
if
k
>
0
.


## 2.3. Rotation of the Positive Basis

In order to modify the positive basis such that at least one of the new directions is more closely conformed to the local behavior of the function, we rotate the positive basis at each step. This idea is similar to that in [28].Suppose that(15)
V
k
=
v
1
k
,
…
,
v
n
k
,
…
,
v
q
k
,where {
v
1
k
,
…
,
v
n
k
} is a basis for R
n. Denote(16)
δ
x
=
x
k
+
1
-
x
k
=
δ
x
1
,
…
,
δ
x
n
T
,where δ
x
i
∈
R
i
=
1
,
…
,
n describe the movements performed along the vectors v
i
k
i
=
1
,
…
,
n in previous iterations.We get positive basisV
k
+
1 by rotating V
k. Firstly, we obtain n linearly independent vectors according to V
k:(17)
v
¯
i
k
+
1
=
v
i
k
if
δ
x
i
=
0
∑
l
=
i
n
δ
x
l
v
l
k
if
δ
x
i
≠
0
,where v
¯
i
k
+
1 represents the sum of all the movements made in the directions v
l
k for l
=
i
,
…
,
n
. The lemma  8.5.4 of [29] proved that v
¯
1
k
+
1
,
…
,
v
¯
n
k
+
1 is linearly independent.Secondly, we use the Gram-Schmidt orthogonalization method to get a class of standard orthogonal basis:(18)
v
1
k
+
1
,
…
,
v
n
k
+
1
.Finally, we can get(19)
V
k
+
1
=
v
1
k
+
1
,
…
,
v
n
k
+
1
,
v
n
+
1
k
+
1
,
…
,
v
q
k
+
1
,where v
n
+
1
k
+
1
,
…
,
v
q
k
+
1 is combined with v
1
k
+
1
,
…
,
v
n
k
+
1 according to the same combination principal as V
k.For instance, ifq
=
n
+
1, we obtain(20)
V
k
+
1
=
v
1
k
+
1
,
…
,
v
n
k
+
1
,
-
∑
i
=
1
n
v
i
k
+
1
.Supposing thatz
m is the sequence of quasi minimal iteration points, then the above process can be summarized as the following algorithm.Algorithm 5.
Step  0 (initializations). Choose initial point x
0
∈
R
n, positive basis V
0, step length h
0, and radius factor parameter δ
0. Choose λ
>
1, μ
>
0, ϵ
k
=
h
k
1
+
μ. Set k
=
0, m
=
0.
Step  1 (checking the stopping condition). If the stopping condition is not met, then go to Step  2, otherwise output the lowest known point and stop.
Step  2 (determining the frame). Create a frame Φ
k at iterate x
k according to the positive basis V
k and step length h
k, and calculate the corresponding function values.
Step  3 (building the RBF interpolation model). Evaluate the RBF model parameters according to formula (8), and get solution x
^
k
+
1 of subproblem (9). If f
(
x
k
)
-
f
(
x
^
k
+
1
)
>
ϵ
k, then set x
k
+
1
=
x
^
k
+
1 and go to Step  6, otherwise go to Step  4.
Step  4 (obtaining the PRP direction). Obtain the search direction d
k using (14), execute the line search process to find β
k, and set x
¯
k
+
1
=
x
k
+
β
k
h
k
d
k
/
d
k. If f
(
x
k
)
-
f
(
x
¯
k
+
1
)
>
ϵ
k, then set x
k
+
1
=
x
¯
k
+
1 and go to Step  6, otherwise go to Step  5.
Step  5 (updating the current iteration point). Let x
k
+
1 be defined by the following rule:(21)
f
x
k
+
1
=
min
v
k
∈
V
k
⁡
f
x
k
,
f
x
^
k
+
1
,
f
x
¯
k
+
1
,
f
x
k
+
h
k
v
k
.
Step  6 (rotating the positive basis and updating the some parameters). Obtain V
k
+
1 according to (15)–(19) and compute δ
k
+
1. If frame Φ
k is a quasi minimal frame, then set h
k
+
1
=
h
k
/
λ, m
=
m
+
1, z
m
=
x
k, otherwise set h
k
+
1
=
h
k. In addition, increment k by one and go to Step  1.Remark 6.
In Step  3, we setp
1
,
…
,
p
r as linear polynomial tails, and ϕ
x
-
y
i
=
x
-
y
i
3 in (8).


## 3. Convergence Analysis

Now we have the following convergent property of Algorithm5.Theorem 7.
Supposing that the sequence of function valuef
x
k is bounded, then the sequence z
m is infinite.Proof.
Assume thatz
m is finite; let z
M be the final quasi minimal point and z
M
=
x
k
~.
From Steps  3, 4, and 5 of Algorithm5, we know that(22)
f
x
k
~
+
1
<
f
x
k
~
-
ϵ
k
~
,or(23)
f
x
k
~
+
1
≤
min
v
k
~
∈
V
k
~
⁡
f
x
k
~
,
f
x
k
~
+
h
k
~
v
k
~
,where ϵ
k
~
=
h
k
~
1
+
μ
(
μ
>
0
) is a positive constant, h
k
~, V
k
~ are frame size and positive basis corresponding to iterate x
k
~, respectively. Supposing that Φ
k
~ is the frame corresponding to quasi minimal iterate x
k
~, then the frame Φ
k
~
+
1 is not quasi minimal. From Definition 4, it follows that there exists at least a vector v
l
k
~
v
l
k
~
∈
V
k
~, such that(24)
f
x
k
~
+
h
k
~
v
l
k
~
<
f
x
k
~
-
ϵ
k
~
.
By (22), (23), and (24), we have(25)
f
x
k
~
+
1
<
f
x
k
~
-
ϵ
k
~
.Then, we have(26)
f
x
k
~
+
r
<
f
x
k
~
+
r
-
1
-
ϵ
k
~
+
r
-
1
<
f
x
k
~
+
r
-
2
-
∑
i
=
k
~
+
r
-
2
k
~
+
r
-
1
ϵ
i
<
⋯
<
f
x
k
~
+
1
-
∑
i
=
k
~
+
1
k
~
+
r
-
1
ϵ
i
,where r is a positive integer and r
≥
3.
Because frameΦ
k
~ is the final quasi minimal frame, by Step  6 of Algorithm 5, we know that h
k is a positive constant for k
>
k
~; that is,(27)
h
k
~
+
1
=
h
k
~
+
2
=
⋯
=
h
k
~
+
r
-
1
,
(28)
ϵ
k
~
+
1
=
ϵ
k
~
+
2
=
⋯
=
ϵ
k
~
+
r
-
1
.
By (25), (26), and (28), we have(29)
f
x
k
~
+
r
<
f
x
k
~
+
1
-
∑
i
=
k
~
+
1
k
~
+
r
-
1
ϵ
i
<
f
x
k
~
-
r
-
1
ϵ
k
~
+
1
-
ϵ
k
~
.If we ignore the stopping condition and let r
→
+
∞, then f
(
x
k
~
+
r
)
→
-
∞, which contradicts the condition that f
x
k is bounded. The proof of this theorem is complete.Theorem 8.
Assume the following conditions are satisfied:
(A1)f is continuously differentiable.
(A2)v
l
k
≤
M for l
=
1
,
…
,
q and k
=
0,1
,
…, where M is a positive constant and v
l
k is the lth vector in V
k.
Then each cluster point ofz
m is a stationary point of f.Proof.
Letz
∞ be an arbitrary cluster point of z
m and the subsequence z
m
K converge to z
∞, where K is an infinite subset of natural numbers. Assume z
m
ˇ
∈
z
m
K, and z
m
ˇ
=
x
k
ˇ. According to Taylor expansion and (A1), we have(30)
f
z
m
ˇ
+
h
m
ˇ
v
l
m
ˇ
=
f
z
m
ˇ
+
h
m
ˇ
∇
f
z
m
ˇ
T
v
l
m
ˇ
+
o
h
m
ˇ
v
l
m
ˇ
,for all v
l
m
ˇ
∈
V
m
ˇ, where h
m
ˇ, V
m
ˇ are frame size and positive basis corresponding to the iteration point z
m
ˇ, respectively, and v
l
m
ˇ is lth vector of V
m
ˇ. From Definition 4, we have(31)
f
z
m
ˇ
+
h
m
ˇ
v
l
m
ˇ
≥
f
z
m
ˇ
-
h
m
ˇ
1
+
μ
,
∀
v
l
m
ˇ
∈
V
m
ˇ
.
Combining (30) and (31) with (A2), we obtain(32)
∇
f
z
m
ˇ
T
v
l
m
ˇ
≥
-
o
h
m
ˇ
h
m
ˇ
M
-
h
m
ˇ
μ
,
∀
v
l
m
ˇ
∈
V
m
ˇ
.
Letm
ˇ
→
+
∞, then z
m
ˇ
→
z
∞, v
l
m
ˇ
→
v
l
∞, h
m
ˇ
→
h
∞. According to Step  6 of Algorithm 5, we have h
∞
→
0. Combining these with (32) and (A1), we have(33)
∇
f
z
∞
T
v
l
∞
≥
0
,
∀
v
l
∞
∈
V
∞
.
Let the numbers ofV
m
ˇ be v
1
m
ˇ
,
…
,
v
q
m
ˇ, then there exist q nonnegative coefficients η
i
i
=
1
,
…
,
q such that(34)
-
∇
f
z
∞
=
∑
i
=
1
q
η
i
v
i
∞
.Combining (33) and (34), we have(35)
0
≥
-
∇
f
z
∞
T
∇
f
z
∞
=
∑
i
=
1
q
η
i
v
i
∞
T
∇
f
z
∞
≥
0
,which yields ∇
f
z
∞
=
0. The proof of this theorem is complete.Remark 9.
Although Theorem8 needs the assumed condition (A1), in practice, we do not solve derivative-free problems that accurately. So we only assure that f is continuously differentiable near the stationary point.


## 4. Numerical Experiments

In this section, we discuss numerical test results for Algorithm5. Our tests are performed on a PC with Intel Core Duo CPU (I5-3470@3.20 GHz, 3.60 GHz) and 8 GB RAM, using MATLAB 7.12.0.To compare our algorithm to Max-PRP, we choose to work with the performance profiles [30] and data profiles [31] for derivative-free optimization. The performance profile is the following fraction: (36)
ρ
s
α
=
1
P
p
∈
P
:
t
p
,
s
min
⁡
t
p
,
s
:
s
∈
S
≤
α
,where P is the set of benchmark problems, S is the set of optimization solvers, t
p
,
s is the number of function evaluations required to satisfy the convergence test for problem p
∈
P on solver s
∈
S.The data profile is defined that(37)
d
s
κ
=
1
P
p
∈
P
:
t
p
,
s
n
p
+
1
≤
κ
,where n
p is the number of variables in p
∈
P.We use the following convergence condition:(38)
f
x
≤
f
L
+
τ
f
x
0
-
f
L
,where x
0 is the initial point for the test problem, τ
>
0 is tolerance, f
L is the best function value achieved by any solvers within μ
f function evaluations, and μ
f is a positive integer.The benchmark problems setP in our experiments is proposed in [32, 33] and CUTEr test problem set [34]. The problems set P includes 78 nonlinear least squares problems P
1 and 60 normal nonlinear programming problems P
2. Tables 1 and 2 show some information about test problems, where n
p is the number of variables and m
p is the number of components. The problems of Table 1 are defined by (39)
f
x
=
∑
k
=
1
m
p
f
k
x
2
.The problems of Table 2 are defined by (40)
f
x
=
∑
k
=
1
m
p
f
k
x
.Table 1
The information about benchmark problems setP
1.
Problem
n
p
m
p
(1) Linear (full rank)
9
45
(2) Linear (rank 1)
7
35
(3) Linear (rank 1 with 0 columns & rows)
7
35
(4) Rosenbrock
2
2
(5) Helical valley
3
3
(6) Powell singular
4
4
(7) Freudenstein and Roth
2
2
(8) Bard
3
15
(9) Meyer
3
16
(10) Watson
6
31
(11) Waston
9
31
(12) Waston
12
31
(13) Waston
31
31
(14) Box  3-dimensional
3
10
(15) Jennrich and Sampson
2
10
(16) Brown and Dennis
4
20
(17) Chebyquad
6
6
(18) Chebyquad
7
7
(19) Chebyquad
8
8
(20) Chebyquad
9
9
(21) Brown almost-linear
10
10
(22) Bdqrtic
8
8
(23) Bdqrtic
10
12
(24) Bdqrtic
11
14
(25) Bdqrtic
12
16
(26) Cube
5
5
(27) Cube
6
6
(28) Cube
8
8
(29) Mancino
5
5
(30) Mancino
8
8
(31) Mancino
10
10
(32) Mancino
12
12
(33) Penalty II
4
8
(34) Penalty II
6
12
(35) Penalty II
8
16
(36) Penalty II
10
20
(37) Penalty II
12
24
(38) Variably dimensioned
8
10
(39) Variably dimensioned
9
11
(40) Variably dimensioned
10
12
(41) Variably dimensioned
11
13
(42) Variably dimensioned
12
14
(43) Broyden tridiagonal
6
6
(44) Broyden tridiagonal
7
7
(45) Broyden tridiagonal
8
8
(46) Broyden tridiagonal
9
9
(47) Broyden tridiagonal
10
10
(48) Broyden tridiagonal
11
11
(49) Broyden tridiagonal
12
12
(50) Broyden banded
4
4
(51) Broyden banded
7
7
(52) Broyden banded
9
9
(53) Broyden banded
10
10
(54) Broyden banded
11
11
(55) Linear (full rank)
100
200
(56) Linear (full rank)
200
400
(57) Linear (rank 1)
100
200
(58) Linear (rank 1)
200
400
(59) Linear (rank 1 with 0 columns & rows)
100
200
(60) Linear(rank 1 with 0 columns & rows)
200
400
(61) Chebyquad
100
100
(62) Chebyquad
200
200
(63) Brown almost-linear
100
100
(64) Brown almost-linear
200
200
(65) Bdqrtic
100
200
(66) Bdqrtic
200
400
(67) Cube
100
100
(68) Cube
200
200
(69) Mancino
100
100
(70) Mancino
200
200
(71) Penalty II
100
200
(72) Penalty II
200
400
(73) Variably dimensioned
100
102
(74) Variably dimensioned
200
202
(75) Broyden tridiagonal
100
100
(76) Broyden tridiagonal
200
200
(77) Broyden banded
100
100
(78) Broyden banded
200
200Table 2
The information about benchmark problems setP
2.
Problem
n
p
m
p
(1) Raydan 1
10
10
(2) Raydan 1
20
20
(3) Raydan 1
100
100
(4) Raydan 2
10
10
(5) Raydan 2
20
20
(6) Raydan 2
100
100
(7) Diagonal 1
10
10
(8) Diagonal 1
20
20
(9) Diagonal 1
100
100
(10) Diagonal 2
10
10
(11) Diagonal 2
20
20
(12) Diagonal 2
100
100
(13) Diagonal 3
10
10
(14) Diagonal 3
20
20
(15) Diagonal 3
100
100
(16) Diagonal 4
10
5
(17) Diagonal 4
20
10
(18) Diagonal 4
100
50
(19) Diagonal 5
10
10
(20) Diagonal 5
20
20
(21) Diagonal 5
100
100
(22) Diagonal 6
10
10
(23) Diagonal 6
20
20
(24) Diagonal 6
100
100
(25) Hager
10
10
(26) Hager
20
20
(27) Hager
100
100
(28) Extended TET
10
5
(29) Extended TET
20
10
(30) Extended TET
100
50
(31) Extended Maratos
10
5
(32) Extended Maratos
20
10
(33) Extended Maratos
100
50
(34) Extended Cliff
10
5
(35) Extended Cliff
20
10
(36) Extended Cliff
100
50
(37) ARWHEAD
10
9
(38) ARWHEAD
20
19
(39) ARWHEAD
100
99
(40) ENGVAL1
10
9
(41) ENGVAL1
20
19
(42) ENGVAL1
100
99
(43) GENHUMPS
10
9
(44) GENHUMPS
20
19
(45) GENHUMPS
100
99
(46) MCCORMCK
10
9
(47) MCCORMCK
20
19
(48) MCCORMCK
100
99
(49) COSINE
10
9
(50) COSINE
20
19
(51) COSINE
100
99
(52) SINE
10
9
(53) SINE
20
19
(54) SINE
100
99
(55) HIMMELBG
10
5
(56) HIMMELBG
20
10
(57) HIMMELBG
100
50
(58) HIMMELH
10
5
(59) HIMMELH
20
10
(60) HIMMELH
100
50In all problems, we have(41)
2
≤
n
p
≤
200
,
p
=
1
,
…
,
138
.In addition, we define the maximum computational budget as 150 simplex gradients, where the computational budget of a simplex gradients is equal to n
p
+
1 function evaluations, so μ
f
=
30150.The parameters of our numerical experiments are listed as follows:h
0
=
1, V
0
=
V
m
i
n, v
i
0
=
e
i
(
i
=
1
,
…
,
n
p
), λ
=
4, μ
=
0.5, δ
0
=
1, and δ
k takes value 2 if the previous iteration was successful, or 1 otherwise.In the RBF interpolation model of (8), we set p
1
,
…
,
p
r as linear polynomial tails and ϕ
x
-
y
i
=
x
-
y
i
3. In addition, we set p
m
a
x
=
3
n as the maximum number of points considered in the interpolate data points Y
=
y
1
,
y
2
,
…
,
y
n
q. All the previously evaluated points are used to compute the RBF interpolation model when its number is lower than p
m
a
x. Similar to [20], whenever there are more previously evaluated points than p
m
a
x for building the RBF interpolation model, 80% of the desired points are selected as the ones nearest to the current iterate and the last 20% are chosen as the ones further away from the current iterate. This strategy is adopted in order to preserve the geometry and diversify the information used in the RBF interpolation model.In Figure1, we show the performance profiles related to Algorithm 5 and Max-PRP. As we can see, Algorithm 5 outperforms Max-PRP when τ
=
1
0
-
3, and the difference is significantly large as the performance ratio α decreases. In addition, Algorithm 5 guarantees better results than Max-PRP when τ
=
1
0
-
5. For example, Algorithm 5 can solve about 90% test problems, while Max-PRP only solves no more than 85%, if performance ratio α
=
16.Figure 1
Performance profilesρ
s
(
α
) for problems P.The data profiles of Algorithm5 and Max-PRP are reported in Figure 2. When the number of simplex gradients κ is larger than 40, Algorithm 5 performs better than Max-PRP as it solves a higher percentage of problems. For example, with a budget of 400 simplex gradients and τ
=
1
0
-
5, Algorithm 5 solves almost 90% of the problems, while Max-PRP solves roughly 85% of the problems.Figure 2
Data profilesd
s
(
κ
) for problems P.


## 5. Conclusion

The computational results which are presented in this paper show that Algorithm5 appears quite competitive. The performance profiles and the data profiles of numerical results indicate that Algorithm 5 often reduces the number of function evaluations which is required to reach stationary point and is superior to Max-PRP.



---

*Source: 4082432-2017-01-19.xml*