1 Introduction
1.1 Affine-scaling matrix for inequality constraints
1.2 Derivative-free technique for trust-region subproblem
-
We use the derivatives of approximation function \(m(x_{k}+\alpha p)\) to replace the derivatives of objective function \(f(x_{k}+\alpha p)\) to reduce the algorithm’s requirement for gradient and Hessian of the iteration points. We solve an affine-scaling trust-region subproblem to find a feasible search direction in each iteration.
-
In the kth iteration, a feasible search direction p is obtained from an affine-scaling trust-region subproblem. Meanwhile, interior backtracking skill will be applied both for determining stepsize α and for guaranteeing the feasibility of iteration point.
-
We will show that the iteration points generated by the proposed algorithm could converge to the optimal points of (1).
-
Local convergence will be given under some reasonable assumptions.
2 A derivative-free trust region method with interior backtracking technique
3 Main results and discussion
3.1 Error bounds
3.2 Sufficiently descent property
3.3 Global convergence
3.4 Local convergence
4 Numerical experiments
No. | Problem | Dim |
\(x_{0}\)
|
---|---|---|---|
1 | HS21 | 2 | [−1,−1] |
3 | HS25 | 3 | [100,12.5,3] |
5 | HS36 | 3 | [10,10,10] |
7 | HS44 | 4 | [0,0,0,0] |
9 | HS76 | 4 | [0.5,0.5,0.5,0.5] |
11 | HS231 | 2 | [−1.2,1] |
13 | HS224 | 2 | [0.1,0.1] |
15 | HS250 | 3 | [10,10,10] |
17 | HS253 | 3 | [0,2,0] |
19 | HS331 | 2 | [0.5,0.1] |
2 | HS24 | 2 | [1,0.5] |
4 | HS35 | 3 | [0.5,0.5,0.5] |
6 | HS37 | 3 | [10,10,10] |
8 | HS45 | 5 | [2,2,2,2,2] |
10 | HS224 | 2 | [0.1,0.1] |
12 | HS232 | 2 | [2,0.5] |
14 | HS232 | 2 | [2,0.5] |
16 | HS251 | 3 | [10,10,10] |
18 | HS268 | 5 | [1,1,…,1] |
20 | HS340 | 3 | [1,1,1] |
Problem name | Results | ||||||
---|---|---|---|---|---|---|---|
\(\Delta_{\max}=4\)
|
\(\Delta_{\max}=6\)
|
\(\Delta_{\max}=8\)
| |||||
n
|
nf
| CPUt |
nf
| CPUt |
nf
| CPUt | |
HS224 | 2 | 26 | 5.187 | 23 | 3.35 | 23 | 3.35 |
HS231 | 2 | 16 | 2.025 | 18 | 4.018 | F | F |
HS232 | 2 | 8 | 2.387 | 23 | 2.455 | F | F |
HS250 | 3 | 12 | 55 | 17 | 73 | 16 | 61 |
HS251 | 3 | 35 | 3.036 | 32 | 2.022 | 37 | 2.332 |