# A Fractional Trust Region Method for Linear Equality Constrained Optimization

Authors: Honglan Zhu; Qin Ni; Liwei Zhang; Weiwei Yang
Journal: Discrete Dynamics in Nature and Society
 (2016)

---

## Abstract

A quasi-Newton trust region method with a new fractional model for linearly constrained optimization problems is proposed. We delete linear equality constraints by using null space technique. The fractional trust region subproblem is solved by a simple dogleg method. The global convergence of the proposed algorithm is established and proved. Numerical results for test problems show the efficiency of the trust region method with new fractional model. These results give the base of further research on nonlinear optimization.


---

## Body

## 1. Introduction

In this paper, we consider the linear equality constrained optimization problem:(1)
m
i
n
x
∈
R
n
f
x
,
(2)
s
.
t
.
A
T
x
=
b
,where f
(
x
) are continuously differentiable, A
∈
R
n
×
m, b
∈
R
m, and r
a
n
k
(
A
)
=
m.Trust region methods have the advantage in the theoretical analysis of convergence properties and the practice. Besides, Davidon proposed a conic model which makes use of more incorporate information at each iteration (see [1]). It is believed that combing trust region techniques with a conic model would be appealing. And it has attracted more and more attention of the researchers (see [2–8]).For unconstrained optimization problems, we proposed a new fractional model (see [9]):(3)
ψ
k
s
=
1
+
c
k
T
s
1
-
a
k
T
s
1
-
b
k
T
s
g
k
T
s
+
1
2
1
+
c
k
T
s
2
1
-
a
k
T
s
2
1
-
b
k
T
s
2
s
T
B
k
s
,where a
k
,
b
k
,
c
k
∈
R
n are horizontal vectors, g
k
=
∇
f
(
x
k
)
,
s
∈
R
n, B
k
∈
R
n
×
n is symmetric and an approximate Hessian of f
(
x
) at x
k. Then, the trust region subproblem of the unconstrained optimization problems is(4)
m
i
n
ψ
k
s
,
s
.
t
.
s
⩽
Δ
k
,
1
-
a
k
T
s
1
-
b
k
T
s
⩾
ϵ
0
,where ϵ
0
(
0
<
ϵ
0
<
1
) is a sufficiently small positive number, · refers to the Euclidean norm, and Δ
k
>
0 is a trust region radius. If b
k
=
c
k
=
0, then ψ
k
(
s
) is reduced to the conic model. If a
k
=
b
k
=
c
k
=
0, then ψ
k
(
s
) is the quadratic model. In order to ensure that the fractional model function ψ
k
(
s
) is bounded over the trust region {
s
∣
s
⩽
Δ
k
}, we assume ∃
ϵ
1
∈
(
0
,
1
/
3
):(5)
a
k
Δ
k
⩽
ϵ
1
,
b
k
Δ
k
⩽
ϵ
1
,
c
k
Δ
k
⩽
ϵ
1
.We denote(6)
Δ
~
k
=
m
i
n
Δ
k
,
ϵ
1
a
k
,
ϵ
1
b
k
,
ϵ
1
c
k
;then, (4) reduces to a simplified fractional trust region subproblem:(7)
m
i
n
ψ
s
,
s
.
t
.
s
⩽
Δ
~
k
.However, the subproblem (7) is solved only in quasi-Newton direction in [9]. In this paper, we made a further research, where the subproblem (7) is solved by a generalized dogleg algorithm.For linear equality constraints problem, we focus on the problems which are solved by a trust region method with new fractional model. If the constraints are linear inequality constraints or some constraint functions are nonlinear, then a few difficulties may arise. However, for these cases, the linear equality constraints problem may be as the subproblems of them. For example, the inequality constraints can be removed by an active set technique or a barrier transformation, and then the nonlinear constraints are linearized.In [10], Sun et al. established the algorithm for the problem (1)-(2) and prove the convergence. However, they do not consider the model computation. In [11], Lu and Ni proposed a trust region method with new conic model for solving (1)-(2) and carried out the numerical experiments.In this paper, we use a simple dogleg method to solve fractional model subproblems and present a quasi-Newton trust region algorithm for solving linear equality constrained optimization problems. This is a continuing work of the fractional model (see [9]), where the linear equality constraints (2) are deleted by using null space techniques.This paper is organized as follows. In Section2, we give a description of the fractional trust region subproblem. In Section 3, we give a generalized dogleg algorithm for solving the fractional subproblem. In Section 4, we propose a new quasi-Newton method based on the fractional model for solving linearly constrained optimization problems and prove the global convergence of the proposed method under the reasonable assumptions. The numerical results are presented in Section 5.


## 2. The Fractional Trust Region Subproblem

In order to solve the problem (1)-(2), we assume that A is column full rank and constraints are consistent. That is, the current point x
k always satisfies A
T
x
k
=
b. Obviously, the constrained condition is equivalent to A
T
s
=
0 if x
=
x
k
+
s. Therefore, combing with (1)–(4), we can obtain that the trial step s
k is computed by the following subproblem:(8)
m
i
n
ψ
k
s
,
(9)
s
.
t
.
A
T
s
=
0
,
(10)
1
-
a
k
T
s
1
-
b
k
T
s
⩾
ϵ
0
,
(11)
s
⩽
Δ
k
.It can be found that our trust region subproblem (8)–(11) is the minimization of a fractional function subject to the trust region constraint and the linear constraints.In order to solve (8)–(11), firstly we consider removing the constraint (10) by the same assumption as in [9]. That is, we assume the parameters a
k, b
k, and c
k satisfied (5); then, subproblem (8)–(11) can be rewritten as the following reduced subproblem:(12)
m
i
n
ψ
k
s
(13)
s
.
t
.
A
T
s
=
0
,
(14)
s
⩽
Δ
~
k
,where Δ
~
k is defined as (6).The null space technology (see [4, 12, 13]) is an important technique for solving equality constraints programming problems. In the following, we use this technology to eliminate constraint (13). Since A has full column rank, then there exist an orthogonal matrix Q
∈
R
n
×
n and a nonsingular upper triangular matrix R
∈
R
m
×
m such that(15)
A
=
Q
R
=
Q
1
Q
2
R
1
0
=
Q
1
R
1
,where Q
1
∈
R
n
×
m, Q
2
∈
R
n
×
(
n
-
m
), and R
1
∈
R
m
×
m. Then, (13) can be rewritten as (16)
R
1
T
Q
1
T
s
=
0
.Therefore, the feasible point for (13) can be presented by(17)
s
=
Q
2
u
,for any u
∈
R
n
-
m, where Q
2
u lies in the null space of A. Then, the subproblem (12)–(14) becomes(18)
m
i
n
ψ
~
k
u
=
1
+
c
~
k
T
u
g
~
k
T
u
1
-
a
~
k
T
u
1
-
b
~
k
T
u
+
1
+
c
~
k
T
u
2
u
T
B
~
k
u
2
1
-
a
~
k
T
u
2
1
-
b
~
k
T
u
2
,
(19)
s
.
t
.
u
⩽
Δ
~
k
,where a
~
k, b
~
k, and c
~
k are reduced horizontal vectors, g
~
k is the reduced gradient, B
~
k is Hessian approximation, and(20)
g
~
k
=
Q
2
T
g
k
,
B
~
k
=
Q
2
T
B
k
Q
2
,
a
~
k
=
Q
2
T
a
k
,
b
~
k
=
Q
2
T
b
k
,
c
~
k
=
Q
2
T
c
k
.It can be seen that this subproblem has the same form as the subproblem (7) of the unconstrained optimization problems and it can be considered as the subproblem of the unconstrained minimization over u. Therefore, we can find a solution of (18)-(19) by the dogleg method. Besides, it is easy to find that s
=
Q
2
u
⩽
Δ
~
k is equivalent to u
⩽
Δ
~
k due to Q
2
T
Q
2
=
I.


## 3. The Dogleg Method of Fractional Trust Region Subproblem

Now we consider calculating the trial stepu
k of the new subproblem (18)-(19) by a simple dogleg method. Firstly, we need to recall the choice of the Newton point u
N as the following subalgorithm (see [9]).Subalgorithm  3.1. Given B
k
>
0,(21)
ϵ
1
∈
0
,
1
3
.Step 1.
Calculatea
~
k, b
~
k, c
~
k, g
~
k, and B
~
k as defined in (20) and(22)
ξ
a
=
c
~
k
T
B
~
k
-
1
g
~
k
+
a
~
k
T
B
~
-
1
g
~
k
b
~
k
T
B
~
k
-
1
g
~
k
,
ξ
b
=
a
~
k
T
B
~
k
-
1
g
~
k
+
b
~
k
T
B
~
k
-
1
g
~
k
-
1
.Step 2.
Ifξ
a
<
0, then u
N
=
-
τ
N
B
~
k
-
1
g
~
k, where(23)
τ
N
=
ξ
b
+
ξ
b
2
+
-
4
ξ
a
-
2
ξ
a
.Step 3.
Ifξ
a
⩾
0, then set b
~
k
=
c
~
k
=
0. If |
a
~
k
T
B
~
k
-
1
g
~
k
|
⩽
ϵ
1, then u
N
=
-
B
~
k
-
1
g
~
k
/
(
1
-
a
~
k
T
B
~
k
-
1
g
~
k
). If |
a
~
k
T
B
~
k
-
1
g
~
k
|
>
ϵ
1, then set a
~
k
=
0 and u
N
=
-
B
~
k
-
1
g
~
k.
In the following, we consider determining the steepest descent point of (18)-(19), where the steepest descent point is defined by Definition 1. Let u
=
-
τ
g
~
k
(
g
~
k
≠
0
) and from (18) we have(24)
ψ
^
τ
=
ψ
~
k
-
τ
g
~
k
;then, (18)-(19) becomes(25)
m
i
n
ψ
^
τ
,
s
.
t
.
0
⩽
τ
⩽
τ
Δ
,where(26)
ψ
^
τ
=
τ
1
-
τ
c
~
k
T
g
~
k
-
2
v
τ
g
~
k
T
g
~
k
+
τ
1
-
τ
c
~
k
T
g
~
k
g
~
k
T
B
~
k
g
~
k
2
v
τ
2
,
(27)
v
τ
=
1
+
τ
a
~
k
T
g
~
k
1
+
τ
b
~
k
T
g
~
k
,
τ
Δ
=
Δ
~
k
g
~
k
.Definition 1.
Letτ
c
p be the solution of (25). Then, u
c
p
=
-
τ
c
p
g is called a steepest descent point of (18)-(19).In order to discuss the stationary points ofψ
^
(
τ
), by computation we have that the derivative of ψ
^
(
τ
) is(28)
ψ
^
′
τ
=
φ
τ
φ
~
τ
v
τ
3
,where(29)
φ
τ
=
a
τ
τ
2
+
b
τ
τ
+
g
~
k
T
g
~
k
,
(30)
φ
~
τ
=
a
~
τ
τ
2
+
2
c
~
k
T
g
~
k
τ
-
1
,
(31)
a
τ
=
c
~
k
T
g
~
k
g
~
k
T
B
~
k
g
~
k
+
a
~
k
T
g
~
k
b
~
k
T
g
~
k
g
~
k
T
g
~
k
,
(32)
b
τ
=
a
~
k
T
g
~
k
g
~
k
T
g
~
k
+
b
~
k
T
g
~
k
g
~
k
T
g
~
k
-
g
~
k
T
B
~
k
g
~
k
,
(33)
a
~
τ
=
c
~
k
T
g
~
k
a
~
k
T
g
~
k
+
c
~
k
T
g
~
k
b
~
k
T
g
~
k
+
a
~
k
T
g
~
k
b
~
k
T
g
~
k
.By direct calculating, we have(34)
a
τ
=
a
~
τ
g
~
k
T
g
~
k
-
b
τ
c
~
k
T
g
~
k
.During the analysis, we find that ifb
τ
⩾
0 and c
~
k
T
g
~
k
⩽
0, then (29) and (30) may have no positive real zero points in most of the cases, respectively. Thus, in order to simplify the discussion, we assume(35)
b
τ
<
0
,
c
~
k
T
g
~
k
>
0
.In order to discuss the feasible stationary points ofφ
τ and φ
~
τ, we first define the sets T
φ and T
φ
~ which contain all the positive extremum points of φ
τ and φ
~
τ, respectively, and these extremum points should be inside the feasible region [
0
,
τ
Δ
]. It is easy to obtain that(36)
T
φ
=
∅
,
i
f
a
τ
>
0
,
τ
^
1
,
i
f
a
τ
=
0
,
τ
2
,
o
t
h
e
r
w
i
s
e
,
T
φ
~
=
τ
3
,
i
f
a
~
τ
>
0
,
τ
^
3
,
i
f
a
~
τ
=
0
,
τ
3
,
τ
4
,
i
f
-
c
~
k
T
g
~
k
2
<
a
~
τ
<
0
,
∅
,
o
t
h
e
r
w
i
s
e
,where(37)
τ
^
1
=
g
~
k
T
g
~
k
-
b
τ
,
τ
1
=
-
b
τ
+
Δ
τ
2
a
τ
,
τ
2
=
-
b
τ
-
Δ
τ
2
a
τ
,
(38)
τ
^
3
=
1
2
c
~
k
T
g
~
k
,
τ
3
=
-
c
~
k
T
g
~
k
+
Δ
~
τ
a
~
τ
,
τ
4
=
-
c
~
k
T
g
~
k
-
Δ
~
τ
a
~
τ
,
(39)
Δ
τ
=
b
τ
2
-
4
a
τ
g
~
k
T
g
~
k
,
Δ
~
τ
=
c
~
k
T
g
~
k
2
+
a
~
τ
.Now, we have the the following conclusions.Remark 2.
Suppose that (5) and (35) hold. (i) If a
~
τ
⩾
0, then from (34) we know that a
τ
>
0. (ii) If -
(
c
~
k
T
g
~
k
)
2
⩽
a
~
τ
<
0
,
a
τ
=
0, then τ
^
1
>
τ
Δ. From (37) and (33), we have(40)
1
-
τ
^
1
c
~
k
T
g
~
k
=
a
~
τ
+
c
~
k
T
g
~
k
2
a
~
τ
⩽
0
,where τ
^
1 is defined in (37). However, from (37) and (35) we have τ
^
1
>
0. We assume τ
^
1
∈
(
0
,
τ
Δ
]; then, from (5) and (27) we have (41)
1
-
τ
^
1
c
~
k
T
g
~
k
⩾
1
-
τ
Δ
c
~
k
g
~
k
⩾
1
-
ϵ
1
>
0
,where the last inequality is obtained by (21) and this conflicts with (40). Therefore, τ
^
1
>
τ
Δ.
Similarly, we can prove that if-
(
c
~
k
T
g
~
k
)
2
⩽
a
~
τ
<
0
,
a
τ
<
0, then τ
2
>
τ
Δ.
Then, combining with (36) and Remark 2., we define a set(42)
T
=
τ
3
,
i
f
a
~
τ
>
0
,
τ
^
3
,
i
f
a
~
τ
=
0
,
τ
3
,
τ
4
,
i
f
-
c
~
k
T
g
~
k
2
<
a
~
τ
<
0
,
τ
^
1
,
i
f
a
~
τ
<
-
c
~
k
T
g
~
k
2
,
a
~
τ
=
0
,
τ
2
,
i
f
a
~
τ
<
-
c
~
k
T
g
~
k
2
,
a
~
τ
<
0
,
∅
,
o
t
h
e
r
w
i
s
e
,where τ
^
1, τ
2, τ
^
3, τ
3, and τ
4 are determined by (37)–(39).Hence, it is easy to get the following theorems.Theorem 3.
Suppose that (5) and (35) hold. Then, the solution of (25) is(43)
τ
c
p
=
a
r
g
m
i
n
ψ
^
τ
,
τ
∈
T
∗
,where(44)
T
∗
=
T
∩
0
,
τ
Δ
∪
0
,
τ
Δand T is defined by (36).Therefore, the steepest descent pointu
c
p
=
-
τ
c
p
g is an approximate solution of the fractional trust region subproblem (18)-(19), where τ
c
p is defined by (43).Similarly, the fractional trust region subproblem (18)-(19) has the following property. The proof of this theorem is similar to Theorem 3.1 in [14], so we omit its proof.Theorem 4.
Suppose that (5) and (35) hold, where ϵ
1
∈
(
0
,
1
/
3
). If u
N
>
Δ
~
k, then the optimal solution of (18)-(19) must be on the boundary of trust region, where u
N is defined in Subalgorithm  3.1.In order to propose a generalized dogleg method of (18)-(19), we set(45)
u
t
=
t
u
N
+
1
-
t
u
c
pand calculate t
∗ such that u
(
t
∗
)
=
Δ
~
k. Denote(46)
d
=
u
N
-
u
c
p
2
,
e
=
u
N
-
u
c
p
T
u
c
p
,
f
=
u
c
p
2
-
Δ
~
k
2
.If u
c
p
<
Δ
~
k, then there exist two real roots t
1 and t
2:(47)
t
1
=
-
e
+
e
2
-
d
f
d
,
t
2
=
-
e
-
e
2
-
d
f
d
,where 0
<
t
1
<
1 and t
2
<
0 (see [14, 15]).Based on the preceding theorems and analysis, we now give a generalized dogleg algorithm for solving (18)-(19).Algorithm 5.
Step  1. Compute u
N by Subalgorithm  3.1.
Step  2. If u
N
⩽
Δ
~
k, then u
k
=
u
N, and stop.
Step  3. If ξ
a
<
0, then compute b
τ as defined in (32), and go to Step  4. Otherwise, go to Step  5.
Step  4. If b
τ
⩾
0 or c
~
k
T
g
~
k
⩽
0, go to Step  5. Otherwise, compute u
c
p
=
-
τ
c
p
g
~
k, where τ
c
p is defined by (43). If τ
c
p
=
τ
Δ, where τ
Δ is defined by (27), then u
k
=
u
c
p, and stop. If τ
c
p
=
0, go to Step  5. Otherwise, go to Step  6.
Step  5. Set b
~
k
=
c
~
k
=
0 and compute(48)
c
a
g
=
g
~
k
T
B
~
k
g
~
k
-
a
~
k
T
g
~
k
g
~
k
T
g
~
k
,
τ
~
c
p
=
g
~
k
T
g
~
k
c
a
g
,
u
d
=
-
τ
~
∗
g
~
k
,where(49)
τ
~
∗
=
τ
Δ
,
i
f
c
a
g
⩽
0
,
m
i
n
τ
Δ
,
τ
~
c
p
,
i
f
c
a
g
>
0
.If τ
~
∗
=
τ
Δ, then u
k
=
u
d, and stop. Otherwise, calculate u
c
p
=
-
τ
~
c
p
g
~
k, go to Step  6.
Step  6. Calculate t
1 and t
2 as defined in (47); then,(50)
t
∗
=
a
r
g
m
i
n
ψ
~
k
u
0
,
ψ
~
k
u
t
1
,
ψ
~
k
u
t
2
,where u
(
t
) is defined by (45). u
k
=
u
(
t
∗
), and stop.
Then, we give the predicted decent bound in each iteration, which is the lower bound of the predicted reduction in each iteration:(51)
p
r
e
d
k
u
=
ψ
~
k
0
-
ψ
~
k
u
,where ψ
~
k
(
u
) is defined by (18).Theorem 6.
Suppose that (5) and (35) hold, where ϵ
1
∈
(
0
,
1
/
3
). If u
k is obtained by Algorithm 5, then(52)
p
r
e
d
u
k
⩾
1
2
g
~
k
B
~
k
m
i
n
g
~
k
,
ξ
Δ
~
k
B
~
k
-
1
,where ξ
=
(
1
-
ϵ
1
)
/
(
1
+
ϵ
1
)
2.This theorem is similar to that in [9] and its proof is omitted.


## 4. New Quasi-Newton Algorithm and Its Global Convergence

In this section, we propose a quasi-Newton method with a fractional model for linearly equality constrained optimization and prove its convergence under some reasonable conditions. In order to solve problem (1)-(2), we consider the fractional model approximation for f
(
x
) about u
=
0; that is(53)
m
k
u
=
f
k
+
ψ
~
k
u
,where x
=
x
k
+
s
=
x
k
+
Q
2
u, f
k
=
f
(
x
k
), and ψ
~
k
(
u
) is defined as (18). Thus, m
k
(
0
)
=
f
k, g
~
k, and B
~
k are the corresponding gradient and Hessian approximations of the function at the kth iteration. We choose u
k to minimize m
k
(
u
). There is a unique minimizer if and only if B
~
k is positive definite. In the following, we give our algorithm. If the current iteration is the feasible point x
k, then an equivalent form of (1)-(2) is to solve the reduced unconstrained problem(54)
m
i
n
u
∈
R
n
-
m
f
~
u
=
f
x
k
+
Q
2
u
.In the following, we consider the choice of the parameter vectorsa
~
k, b
~
k, and c
~
k. We choose these vectors such that (53) satisfies the following conditions:(55)
m
k
0
=
f
~
k
,
∇
m
k
0
=
g
~
k
,
(56)
m
k
-
u
k
-
1
=
f
~
k
-
1
,
∇
m
k
-
u
k
-
1
=
g
~
k
-
1
,where(57)
x
k
=
x
k
-
1
+
s
k
-
1
=
x
k
-
1
+
Q
2
u
k
-
1
,
f
~
k
=
f
~
0
=
f
x
k
=
f
k
,
f
~
k
-
1
=
f
~
-
u
k
-
1
=
f
x
k
-
1
=
f
k
-
1
,
g
~
k
-
1
=
Q
2
T
g
k
-
1
.Obviously, (55) holds. Then, from (56), we have(58)
f
k
-
1
=
f
k
-
1
-
c
~
k
T
u
k
-
1
g
~
k
T
u
k
-
1
v
~
k
-
1
+
1
-
c
~
k
T
u
k
-
1
2
u
k
-
1
T
B
~
k
u
k
-
1
2
v
~
k
-
1
2
,
(59)
g
~
k
-
1
=
1
v
~
k
-
1
3
Q
~
k
-
1
v
~
k
-
1
g
~
k
-
1
-
c
~
k
T
u
k
-
1
B
~
k
u
k
-
1
,where v
~
k
-
1
=
(
1
+
a
~
k
T
u
k
-
1
)
(
1
+
b
~
k
T
u
k
-
1
) and(60)
Q
~
k
-
1
=
1
-
c
~
k
T
u
k
-
1
v
~
k
-
1
I
-
c
~
k
v
~
k
-
1
+
1
-
c
~
k
T
u
k
-
1
a
~
k
1
+
b
~
k
T
u
k
-
1
+
b
~
k
1
+
a
~
k
T
u
k
-
1
u
k
-
1
T
.If we choose(61)
a
~
k
=
k
1
g
~
k
-
1
,
b
~
k
=
k
2
B
~
k
-
1
u
k
-
1
,
c
~
k
=
k
3
g
~
k
,then these unknown parameters k
1, k
2, and k
3 can be obtained from (58)-(59). In the following, we give the derivation process of k
1, k
2, and k
3. First, we define some notations:(62)
α
k
=
g
~
k
-
1
T
u
k
-
1
,
α
~
k
=
g
~
k
-
1
T
ξ
1
,
α
^
k
=
g
~
k
-
1
T
ξ
2
,
β
k
=
u
k
-
1
T
B
~
k
-
1
u
k
-
1
,
β
~
k
=
u
k
-
1
T
B
~
k
-
1
ξ
1
,
β
^
k
=
u
k
-
1
T
B
~
k
-
1
ξ
2
,
ζ
k
=
u
k
-
1
T
B
~
k
u
k
-
1
,
ζ
~
k
=
u
k
-
1
T
B
~
k
ξ
1
,
ζ
^
k
=
u
k
-
1
T
B
~
k
ξ
2
,
γ
k
=
g
~
k
T
u
k
-
1
,
γ
~
k
=
g
~
k
T
ξ
1
,
γ
^
k
=
g
~
k
T
ξ
2
,where the vectors ξ
1 and ξ
2 are chosen to satisfy(63)
α
~
k
=
γ
~
k
=
ζ
^
k
=
γ
^
k
=
0
.For convenience, we omit the index k of α
k
,
α
~
k
,
α
^
k
,
β
k
,
…
,
γ
~
k and γ
^
k.On one hand, from (58) we have(64)
1
-
c
~
k
T
u
k
-
1
=
η
v
~
k
-
1
,where(65)
η
=
γ
+
γ
2
+
2
ζ
f
~
k
-
1
-
f
~
k
ζ
.If the sequence f
~
k is monotonically decreasing and B
~
k is positive definite, then we know that η
>
0 and (64) becomes(66)
1
-
k
3
γ
=
η
1
+
k
1
α
1
+
k
2
β
.On the other hand, by left-multiplyingξ
1
T on (59) and combining with (63), we have(67)
1
-
k
3
γ
k
2
β
~
ζ
-
β
ζ
~
-
ζ
~
-
1
+
k
1
α
1
+
k
2
β
k
2
β
~
γ
=
0
.Then, from (66), we have(68)
k
2
=
η
ζ
~
γ
¨
,where(69)
γ
¨
=
η
β
~
ζ
-
η
β
ζ
~
-
β
~
γ
.Similarly, by left multiplying ξ
2
T on (59), from (63) and (66) we have(70)
k
1
=
-
α
^
β
+
ι
~
η
β
^
k
2
+
α
^
α
α
^
β
+
ι
~
η
α
^
β
+
α
β
^
k
2
+
α
α
^
+
α
^
ι
~
η
,where ι
~
=
γ
-
η
ζ. Substituting (68) into the above equation, we have(71)
k
1
=
-
ι
˙
γ
˙
,where(72)
ι
˙
=
ι
~
α
^
β
~
-
η
2
ζ
~
β
^
,
γ
˙
=
α
ι
^
+
η
α
^
β
~
ι
~
2
.And then from (66), we have(73)
k
3
=
1
-
η
1
+
k
1
α
1
+
k
2
β
γ
.Now we give the new quasi-Newton algorithm based on the fractional model (53).Algorithm 7.
Step  0. Choose x
0
∈
R
n
,
ϵ
1
∈
(
0
,
1
/
3
)
,
ε
>
0
,
Δ
m
a
x
>
0
,
0
<
ι
1
<
ι
2
<
1
,
0
<
δ
1
<
1
<
δ
2, 0
<
ι
<
1, B
~
0
=
I, and the initial trust region radius Δ
0
∈
(
0
,
Δ
m
a
x
]. Compute Q
2 as defined in (15). Set k
=
0.
Step  1 (stopping criterion). Compute f
k
=
f
(
x
k
), g
k
=
∇
f
(
x
k
), and g
~
k
=
Q
2
T
g
k. If g
~
k
⩽
ε, then x
∗
=
x
k, and stop. If k
=
0, go to Step  3.
Step  2. Compute y
k
-
1
=
g
~
k
-
g
~
k
-
1. Update B
~
k by(74)
B
~
k
=
B
~
k
-
1
-
B
~
k
-
1
u
k
-
1
u
k
-
1
T
B
~
k
-
1
u
k
-
1
T
B
~
k
-
1
u
k
-
1
+
z
k
-
1
z
k
-
1
T
z
k
-
1
T
u
k
-
1
,where (75)
z
k
-
1
=
θ
y
k
-
1
+
1
-
θ
B
~
k
-
1
u
k
-
1
,
θ
∈
0,1
,
θ
=
1
,
i
f
y
k
-
1
T
u
k
-
1
⩾
0.2
u
k
-
1
T
B
~
k
-
1
u
k
-
1
,
0.8
u
k
-
1
T
B
~
k
-
1
u
k
-
1
u
k
-
1
T
B
~
k
-
1
u
k
-
1
-
y
k
-
1
T
u
k
-
1
,
o
t
h
e
r
w
i
s
e
.
Step  3. If k
⩽
1, then set a
~
k
=
b
~
k
=
c
~
k
=
0, B
~
k
=
Q
2
T
B
k
Q
2, and d
k
=
-
B
~
k
-
1
g
~
k, compute α
k such that Wolfe-Powell conditions are satisfied, and set x
k
+
1
=
x
k
+
s
k
=
x
k
+
α
k
d
k and u
k
=
Q
2
T
s
k, k
=
k
+
1, and go to Step  1.
Step  4. By the parameters g
~
k
-
1, g
~
k, and B
~
k
u
k
-
1 get ξ
1 and ξ
2.
Step  5. Compute α
,
α
~
,
α
^
,
…
,
γ
,
γ
~ and γ
^ as defined in (62). If γ
=
0, then set b
~
k
=
c
~
k
=
0. Calculate(76)
ρ
k
=
f
~
k
-
1
-
f
~
k
2
-
g
~
k
-
1
T
u
k
-
1
g
~
k
T
u
k
-
1
,
β
˙
=
f
~
k
-
1
-
f
~
k
+
ρ
k
-
g
~
k
-
1
T
u
k
-
1
,
i
f
ρ
k
⩾
0
,
1
,
o
t
h
e
r
w
i
s
eand set(77)
a
~
k
=
1
-
β
˙
g
~
k
-
1
T
u
k
-
1
g
~
k
-
1
.Otherwise, compute γ
˙ and γ
¨ as defined in (72) and (69). If γ
˙
=
0 or γ
¨
=
0, then set a
~
k
=
b
~
k
=
c
~
k
=
0. Otherwise, calculate a
~
k, b
~
k, and c
~
k, where k
1, k
2, and k
3 in (61) are determined by (71), (68), and (73).
Step  6. If a
~
k
>
ϵ
1
/
Δ
~
k, then a
~
k
=
ϵ
1
a
k
/
Δ
~
k
a
k. Update b
~
k and c
~
k with the same way such that (5) are satisfied.
Step  7. By the parameters a
~
k, b
~
k, c
~
k, g
~
k, and Δ
~
k, solve the subproblem (18)-(19) by Algorithm 5 to get u
k. Set s
k
=
Q
2
u
k.
Step  8. Compute(78)
ρ
k
=
A
r
e
d
u
k
P
r
e
d
u
k
,where(79)
A
r
e
d
u
k
=
A
r
e
d
s
k
=
f
x
k
-
f
x
k
+
s
k
,
(80)
P
r
e
d
u
k
=
m
k
0
-
m
k
u
k
=
-
ψ
~
k
u
k
.
Step  9. Update the trust region radius:(81)
Δ
~
k
+
1
=
δ
1
Δ
~
k
,
i
f
ρ
k
⩽
ι
1
,
m
i
n
δ
2
Δ
~
k
,
Δ
m
a
x
,
i
f
ρ
k
⩾
ι
2
,
u
k
=
Δ
~
k
,
Δ
~
k
,
o
t
h
e
r
w
i
s
e
.
Step  10. If ρ
k
⩾
ι
1, then x
k
+
1
=
x
k
+
s
k. Set k
=
k
+
1, and go to Step  1. Otherwise, x
k
+
1
=
x
k, k
=
k
+
1, and go to Step  6.Next we present the global convergence theorem which says the reduced gradients converge to zero.Theorem 8.
Assume that (5) and (35) hold, where ϵ
1
∈
(
0
,
1
/
3
). If f is continuously differentiable and bounded below in some set containing all iterations generated by Algorithm 7, the sequences {
g
~
k
} and {
B
~
k
} are uniformly bounded. Then, (82)
l
i
m
i
n
f
k
→
∞
g
~
k
=
0
.Proof.
Assume that the theorem is false and there isε
¯
>
0 such that g
~
k
⩾
ε
¯ for all k. From the assumption, we can assume that(83)
a
~
k
⩽
a
¯
,
b
~
k
⩽
b
¯
,
c
~
k
⩽
c
¯
,
g
~
k
⩽
g
¯
,
0
<
B
~
k
⩽
B
¯
,
0
<
B
~
k
-
1
⩽
B
~hold for all k. From (52) and the assumptions in the theorem, we have(84)
p
r
e
d
s
k
⩾
ε
¯
2
B
¯
m
i
n
ε
¯
,
ξ
Δ
~
k
B
~
⩾
c
1
min
⁡
Δ
~
k
,
c
2
,where c
1 and c
2 are some positive constants. Then, from Step  10 of Algorithm 7, we have(85)
f
k
-
f
k
+
1
⩾
ι
1
p
r
e
d
s
k
⩾
ι
1
c
1
min
⁡
Δ
~
k
,
c
2
.Since f
(
x
) is bounded from below and f
k
+
1
<
f
k for all k, we have that ∑
k
=
1
∞
min
⁡
{
Δ
~
k
,
c
2
} is convergent, and Δ
~
k
→
0 as k
→
∞.
On the other hand, whenΔ
~
k
→
0, u
k
→
0. From Step  6 of Algorithm 7, we have(86)
a
~
k
T
u
k
⩽
a
~
k
Δ
~
k
⩽
ϵ
1
,
b
~
k
T
u
k
⩽
ϵ
1
,where ϵ
1
∈
(
0
,
1
/
3
). Thus, we have(87)
1
1
-
a
~
k
T
u
k
=
1
+
a
~
k
T
u
k
+
o
u
k
,
1
1
-
b
~
k
T
u
k
=
1
+
b
~
k
T
u
k
+
o
u
k
.By computing, we obtain(88)
1
+
c
~
k
T
u
k
g
~
k
T
u
k
1
-
a
~
k
T
u
k
1
-
b
~
k
T
u
k
=
g
k
T
u
k
+
O
u
k
2
,
1
+
c
~
k
T
u
k
2
u
k
T
B
~
k
u
k
1
-
a
~
k
T
u
k
2
1
-
b
~
k
T
u
k
2
=
u
k
T
B
~
k
u
k
+
o
u
k
2
,
A
r
e
d
u
k
=
-
g
k
T
u
k
-
u
k
T
B
~
k
u
k
+
o
u
k
2
.Then, from (80), we have(89)
P
r
e
d
u
k
=
A
r
e
d
u
k
+
O
Δ
~
k
2
,which indicates that(90)
lim
k
→
∞
⁡
ρ
k
=
1
.By the updating in Step  9 of Algorithm 7, we have Δ
~
k
+
1
⩾
Δ
~
k, which is a contradiction to Δ
~
k
→
0. The theorem is proved.


## 5. Numerical Tests

In this section, Algorithm7 (abbreviated as FTR) is tested with some test problems which are chosen from [16, 17]. These test problems are listed in Table 1. We choose linear constrained problems HS9, HS48, HS49, HS50, Chen 3.3.1, and Chen 3.3.2. Moreover, in order to test Algorithm 7 more generally, we designed some problems where the objective functions are Pro. 7–18 (see [14, 18]) and the linear equality constraints are Pro. 1–6. If b
~
k
=
c
~
k
=
0 in Algorithm 7, we can obtain the conic model algorithm and call this algorithm CTR. We solve the following 18 test problems by FTR and CTR and compare their results.Table 1
Test functions.
Pro.
Function name
1
HS 9
2
HS 48
3
HS 49
4
HS 50
5
Chen 3.3.1
6
Chen 3.3.2
7
Cube
8
Penalty-I
9
Beale
10
Conic
11
Extended Powell
12
Broyden Tridiagonal
13
Rosenbrock
14
Chained Freudenstein and Roth
15
Extended Trigonometric
16
Penalty-III
17
Troesch
18
Cragg and LevyAll the computations are carried out in Matlab R2012b on a microcomputer in double precision arithmetic. These tests use the same stopping criteriong
~
k
⩽
1
0
-
4. The columns in the tables have the following meanings: Pro. denotes the numbers of the test problems; n is the dimension of the test problems; Iter is the number of iterations; nf and ng are the numbers of function and gradient evaluations, respectively; g
~ is the Euclidean norm of the final reduced gradient; CPU(s) denotes the total iteration time of the algorithm in seconds. The parameters in these algorithms are (91)
B
0
=
I
,
ϵ
1
=
0.33
,
Δ
0
=
1
,
Δ
m
a
x
=
10
,
l
=
0.15
,
μ
=
0.85
,
ι
1
=
0.25
,
ι
2
=
0.75
,
δ
2
=
4
.The numerical comparison for 18 small-scale test problems is listed in Table2. We can see that FTR is better than CTR for 15 tests in the number of iterations and the remaining 3 tests are similar. Because FTR needs some extra algebra computation for some parameters, FTR takes more time than CTR for small problems.Table 2
The numerical results of Algorithm7 for some test problems.
Pro.
n
Starting point
Algorithm
Iter
nf/ng
‖
g
‖
CPU (s)
1
6
(0, 0, 0, 0, 0, 0)
CTR
6
7/8
7.559746(−5)
0.084639
FTR
5
6/6
1.693174(−5)
0.161438
2
5
(3, 5, −3, 2, −2)
CTR
13
14/9
1.637781(−5)
0.094287
FTR
8
9/9
2.148387(−6)
0.098268
3
5
(2, 2, −9, 3, 3)
CTR
27
28/21
5.815109(−5)
0.110429
FTR
25
26/17
4.996278(−5)
0.149000
4
10
(0, −6, 6, 0, 0,
CTR
12
13/13
3.889891(−5)
0.100359
0, −6, 6, 0, 0)
FTR
8
9/9
2.397640(−5)
0.152117
5
8
(0, 3, −1, −2
CTR
16
17/14
7.255223(−5)
0.099120
0, 3, −1, −2)
FTR
16
17/17
1.249467(−5)
0.129272
6
8
(7/3, 11/3, −1, −1
CTR
22
23/19
3.128858(−6)
0.101571
7/3, 11/3, −1, −1)
FTR
21
22/19
2.865070(−7)
0.167233
7
6
(3, 4, 3, 4, 3, 4)
CTR
8
9/9
2.208537(−7)
0.093060
FTR
8
9/9
1.765690(−8)
0.139521
8
6
(3, 4, 3, 4, 3, 4)
CTR
14
15/11
8.493218(−7)
0.095873
FTR
12
13/10
1.155176(−5)
0.166608
9
6
(6, 8, 6, 8, 6, 8)
CTR
21
22/18
1.208648(−6)
0.094048
FTR
19
20/18
3.705893(−5)
0.170549
10
6
−(1.5, 2, 1.5, 2, 1.5, 2)
CTR
13
14/10
1.789828(−6)
0.104145
FTR
9
10/7
4.017095(−6)
0.158877
11
8
(0.3, 0.4, …, 0.3, 0.4)
CTR
15
16/13
3.013621(−5)
0.087370
FTR
7
8/8
7.252083(−5)
0.121116
12
6
(0.3, 0.4, …, 0.3, 0.4)
CTR
26
27/16
5.317180(−5)
0.1160001
FTR
24
25/14
5.917188(−5)
0.187447
13
6
(1.5, 2, 1.5, 2, 1.5, 2)
CTR
6
7/7
8.707409(−5)
0.081667
FTR
6
7/7
5.998420(−5)
0.115520
14
6
(6, 8, 6, 8, 6, 8)
CTR
34
35/20
3.185767(−5)
0.106515
FTR
22
23/23
4.845919(−6)
0.158603
15
8
(0.3, 0.4, …, 0.3, 0.4)
CTR
10
11/9
1.738762(−5)
0.092062
FTR
9
10/8
5.005195(−5)
0.146342
16
6
(0.3, 0.4, …, 0.3, 0.4)
CTR
13
14/12
3.409181(−5)
0.083445
FTR
12
13/12
9.332787(−5)
0.164178
17
6
(0.3, 0.4, …, 0.3, 0.4)
CTR
29
30/17
1.845528(−6)
0.088997
FTR
19
20/17
5.983264(−6)
0.159851
18
8
(0.3, 0.4, …, 0.3, 0.4)
CTR
12
13/9
7.722466(−7)
0.087020
FTR
9
10/9
4.353866(−7)
0.149733The numerical results of some large-scale problems are presented in Table3. From Table 3, we find that for large-scale problems the CPU time of FTR is approximately the same as that of CTR but it has fewer number of iterations. From the above comparison, we see that FTR is slightly more effective and robust for these large-scale test problems.Table 3
The numerical results of Algorithm7 for some test problems (
n
=
3000
).
Pro.
Starting point
Algorithm
Iter
nf/ng
‖
g
‖
CPU (s)
7
(6, 8, …, 6, 8)
CTR
25
26/26
3.737202(−9)
28.5976
FTR
21
22/22
3.849243(−9)
26.2795
8
(6, 8, …, 6, 8)
CTR
12
13/12
8.930053(−6)
13.8295
FTR
12
13/11
3.113077(−7)
14.7506
9
(6, 8, …, 6, 8)
CTR
25
26/26
3.388081(−6)
28.4904
FTR
24
25/25
1.176732(−6)
30.7385
10
(6, 8, …, 6, 8)
CTR
12
13/13
1.226943(−7)
14.9229
FTR
10
11/11
6.842114(−6)
14.9369
11
(6, 8, …, 6, 8)
CTR
18
19/19
2.718913(−8)
21.4796
FTR
4
5/5
5.738665(−5)
8.48251The fractional model in Algorithm7 is the extension of conic model. By using more information of function and gradient from the previous iterations and choosing parameters flexibly, the fractional model can be more approximate to the original problem. And the global convergence of the proposed quasi-Newton trust region algorithm is also proved. Numerical experiment shows the algorithm is effective and robust, including for large-scale test problems. The theoretical results and the numerical results lead us to believe that the method is worthy of further study. For example, we can consider using fractional model to solve the nonlinear equality constrained optimization problem.



---

*Source: 8676709-2016-07-14.xml*