# A Novel Optimization Method for Nonconvex Quadratically Constrained Quadratic Programs

Authors: Hongwei Jiao; Yong-Qiang Chen; Wei-Xin Cheng
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

This paper presents a novel optimization method for effectively solving nonconvex quadratically constrained quadratic programs (NQCQP) problem. By applying a novel parametric linearizing approach, the initial NQCQP problem and its subproblems can be transformed into a sequence of parametric linear programs relaxation problems. To enhance the computational efficiency of the presented algorithm, a cutting down approach is combined in the branch and bound algorithm. By computing a series of parametric linear programs problems, the presented algorithm converges to the global optimum point of the NQCQP problem. At last, numerical experiments demonstrate the performance and computational superiority of the presented algorithm.


---

## Body

## 1. Introduction

The nonconvex quadratically constrained quadratic programs problems have attracted the attention of practitioners and researchers for 30 years. During the past 10 years, curiosity in these problems has been especially intense. In part, this is because the NQCQP problems have a large number of practical applications, for example, pooling problems in petrochemistry [1], modularization of product subassemblies [2], chance-constrained optimization problems, production planning or portfolio optimization [3–5], the fuel mixture problem encountered in oil industry [6], and also placement and layout problems appeared in integrated circuit design (see [7, 8]). In addition, many nonlinear optimization problems can be transformed into the form, for example, special classes of structured stochastic games [9] can be interpreted as quadratic programs problems, the packing problem contained in the unit square can be formulated as concave quadratic constraints quadratic programs problem, {
0,1
} variable in 0-1 programming may be also represented by concave quadratic constraints, and minmax location problems [4] also lead to quadratic programs problems with quadratic constraints. Another cause for the strong attention in the NQCQP problems is that, from a research point of view, the class of problems put forward significant theoretical and computational defiance. This is mainly because these problems are global optimization problem; that is, they are well known to generally own multiple local optimum points that are not globally optimum point. Therefore, it is very essential to put forward a good global optimization method for solving the NQCQP problems.In this paper, we will investigate the following NQCQP problems:(
NQCQP
)
min
⁡
G
0
(
x
)
=
x
T
A
0
x
+
(
d
0
)
T
x
s
.
t
.
lh
G
i
(
x
)
=
x
T
A
i
x
+
(
d
i
)
T
x
≤
b
i
,
s
.
t
.
G
i
(
x
)
=
l
l
l
l
l
x
T
A
i
x
+
i
=
1
,
…
,
m
,
h
h
h
h
x
∈
X
0
=
{
x
∈
R
n
:
l
0
≤
x
≤
u
0
}
,
where A
i
=
(
a
j
k
i
)
n
×
n
∈
R
n
×
n
(
i
=
0,1
,
…
,
m
) are all symmetric matrices, d
0
,
d
i
∈
R
n, b
i
∈
R, i
=
1
,
…
,
m, and l
0
=
(
l
1
0
,
…
,
l
n
0
)
T, u
0
=
(
u
1
0
,
…
,
u
n
0
)
T.In last several decades, some algorithms have been exploited for globally solving the special case or general case of the NQCQP problems. For example, based on a novel reformulation-linearization/convexification approach, Sherali and Tuncbilek [10] proposed a global optimization algorithm for linearly constrained nonconvex quadratic programs problems. Based on outer approximation and branch and bound scheme by solving linear programs subproblems, Al-Khayyal et al. [7] presented an algorithm for computing the approximate global optimal solutions of the NQCQP problems. Based on Lagrangian underestimation method to compute lower bounds and utilize the Interval Newton method to facilitate the convergence of algorithm in the neighborhood of the global optimum point, Van Voorhis [11] developed a branch and bound algorithm for globally solving the NQCQP problems. By partitioning the feasible region into the Cartesian product of two-dimensional triangles and rectangles and by utilizing the convex and concave envelopes of bilinear functions over triangles and rectangles, a simplicial branch and bound algorithm [12] was presented for solving globally the NQCQP problems. Based on semidefinite relaxations and finite KKT-branching method, Burer and Vandenbussche [13] presented a finite branch and bound algorithm for globally solving the NQCQP problems. In [14], Zheng et al. presented a decomposition-approximation method for constructing convex relaxations of the NQCQP problems, which can be used to offer a tighter lower bound for solving the problems (
NQCQP
). Using duality bounds approach, Thoai [15] presented a branch and bound algorithm for solving the NQCQP problems. Based on linear relaxation approximation technique and linearity-based range deleting tactics, Gao et al. [16] presented a rectangle branch and reduce method for the linearly constrained quadratic programs problems; by utilizing linearizing technique and quadratic constraint-based range compressing technique, Gao et al. [17] presented a branch and reduce approach for globally solving the NQCQP problems. By utilizing the special structure of quadratic function and linearization technique, Shen et al. [18] and Shen and Liu [19] proposed two effective global optimization algorithms for computing the NQCQP problems. By making use of linear relaxation approximation technique, Qu et al. [20] and Jiao and Chen [21] proposed two deterministic algorithms for calculating the NQCQP problems. Except for the above reviewed references, several algorithms for solving generalized geometric programming problem presented in [22–30] can be also used to solve the NQCQP problems. For an excellent review of recent advances in global optimization, the reader is referred to Floudas and Gounaris [31].In this paper, by combing a parametric linearizing approach with a cutting down approach, we will present a novel global optimization method for solving the NQCQP problems. The main characteristics of the presented approach are expounded as follows. Firstly, a novel linear relaxation approximation technique, that is, a parametric linearizing approach, is constructed for inconsistently transforming the NQCQP problems into a sequence of parametric linear programs relaxation problems, and by subsequently subdividing the initial hyperrectangle the optimal point of parametric linear programs relaxation problems can infinitely approach the global optimum point of the problem(
NQCQP
). Secondly, the proposed parametric linear programs relaxation problems are putted into a branch and bound framework without adding any new variables and constraint functions and which can be easily calculated by any effective linear programs algorithm procedure. Thirdly, a cutting down approach is exploited to eliminate a large part of the currently investigated subhyperrectangle which does not contain the global optimum point of the problem (
NQCQP
). Combing the parametric linear programs relaxation problem with the cutting down approach in a branch and bound procedure, a new optimization method is displayed for globally solving the NQCQP problems. At last, numerical results indicate that the proposed method can be employed to obtain the global optimum point of the problem (
NQCQP
).The remainder of this paper is composed as follows. The next section describes a novel parametric linearizing approach and the parametric linear programs relaxation of the problem(
NQCQP
) is constructed. In Section 3 a cutting down approach is presented. Section 4 combines the cutting down approach within a branch and bound scheme; an optimization algorithm and its global convergence are described. In Section 5 some test examples and their results are reported to demonstrate the feasibility and superiority of the presented algorithm. At last, some concluding remarks are described.


## 2. Parametric Linear Relaxation

The principal composition in the configuration of a branch and bound algorithm for globally solving the problem(
NQCQP
) is the computation of lower bounds of the problem (
NQCQP
) and its divided subproblems. The lower bounds of the global minimum values of the problem (
NQCQP
) and its divided subproblems can be calculated by solving a series of parametric linear programs relaxation problem (
PLPRP
). In order to construct the PLPRP, the proposed approach is to replace each quadratic function G
i
(
x
) by a parametric linear function.LetX
=
(
X
j
)
n
×
1
⊆
X
0 with X
j
=
[
l
j
,
u
j
]
(
j
=
1
,
…
,
n
). For each i
=
0,1
,
…
,
m, define x
(
θ
i
)
=
l
+
θ
i
(
u
-
l
), where θ
i
∈
{
0,1
}, l
T
=
{
l
1
,
l
2
,
…
,
l
n
}, u
T
=
{
u
1
,
u
2
,
…
,
u
n
}, x
(
0
)
=
l, and x
(
1
)
=
u. For convenience in expression, for all x
∈
X
⊆
X
0, for each i
=
0,1
,
…
,
m, some symbols are given as follows:
(1)
Z
_
i
=
2
×
(
∑
k
=
1
,
a
1
k
i
>
0
n
‍
a
1
k
i
l
k
+
∑
k
=
1
,
a
1
k
i
<
0
n
‍
a
1
k
i
u
k
∑
k
=
1
,
a
2
k
i
>
0
n
‍
a
2
k
i
l
k
+
∑
k
=
1
,
a
2
k
i
<
0
n
‍
a
2
k
i
u
k
⋮
∑
k
=
1
,
a
n
k
i
>
0
n
‍
a
n
k
i
l
k
+
∑
k
=
1
,
a
n
k
i
<
0
n
‍
a
n
k
i
u
k
)
,
Z
¯
i
=
2
×
(
∑
k
=
1
,
a
1
k
i
>
0
n
‍
a
1
k
i
u
k
+
∑
k
=
1
,
a
1
k
i
<
0
n
‍
a
1
k
i
l
k
∑
k
=
1
,
a
2
k
i
>
0
n
‍
a
2
k
i
u
k
+
∑
k
=
1
,
a
2
k
i
<
0
n
‍
a
2
k
i
l
k
⋮
∑
k
=
1
,
a
n
k
i
>
0
n
‍
a
n
k
i
u
k
+
∑
k
=
1
,
a
n
k
i
<
0
n
‍
a
n
k
i
l
k
)
,
f
i
(
x
)
=
x
T
A
i
x
,
Z
i
(
θ
i
)
=
Z
_
i
+
θ
i
(
Z
¯
i
-
Z
_
i
)
,
Z
i
(
1
-
θ
i
)
=
Z
_
i
+
(
1
-
θ
i
)
(
Z
¯
i
-
Z
_
i
)
,
f
i
l
(
x
,
X
,
θ
i
)
=
Z
i
(
θ
i
)
T
x
+
x
(
θ
i
)
T
A
i
x
(
θ
i
)
-
Z
i
(
θ
i
)
T
x
(
θ
i
)
,
f
i
u
(
x
,
X
,
θ
i
)
=
Z
i
(
1
-
θ
i
)
T
x
+
x
(
θ
i
)
T
A
i
x
(
θ
i
)
-
Z
i
(
1
-
θ
i
)
T
x
(
θ
i
)
.Obviously, we have(2)
Z
i
(
0
)
=
Z
_
i
,
Z
i
(
1
)
=
Z
¯
i
.Theorem 1.
For anyx
∈
X
⊆
X
0, for each i
=
0,1
,
…
,
m, consider the function f
i
(
x
)
,
f
i
l
(
x
,
X
,
θ
i
) and f
i
u
(
x
,
X
,
θ
i
); then the following conclusions hold:(i)
f
i
l
(
x
,
X
,
θ
i
)
≤
f
i
(
x
)
≤
f
i
u
(
x
,
X
,
θ
i
);
(ii)
∥
f
i
u
(
x
,
X
,
θ
i
)
-
f
i
(
x
)
∥
→
0 and ∥
f
i
(
x
)
-
f
i
l
(
x
,
X
,
θ
i
)
∥
→
0 as ∥
u
-
l
∥
→
0.Proof.
(i) The gradient function of the functionf
i
(
x
)
=
x
T
A
i
x
,
i
=
0,1
,
…
,
m, can be expressed as follows:
(3)
∂
f
i
(
x
)
∂
x
=
2
A
i
x
=
2
×
(
∑
k
=
1
n
‍
a
1
k
i
x
k
∑
k
=
1
n
‍
a
2
k
i
x
k
⋮
∑
k
=
1
n
‍
a
n
k
i
x
k
)
.
Obviously, we have
(4)
Z
_
i
≤
∂
f
i
(
x
)
∂
x
=
2
A
i
x
≤
Z
¯
i
.
By the mean value theorem, for anyx
∈
X, there exists a point ξ
=
α
x
+
(
1
-
α
)
x
(
θ
i
), where α
∈
[
0,1
], such that
(5)
f
i
(
x
)
=
f
i
(
x
(
θ
i
)
)
+
(
∂
f
i
(
ξ
)
∂
ξ
)
T
(
x
-
x
(
θ
i
)
)
=
x
(
θ
i
)
T
A
i
x
(
θ
i
)
+
(
∂
f
i
(
ξ
)
∂
ξ
)
T
(
x
-
x
(
θ
i
)
)
.
If θ
i
=
0, then we have
(6)
∂
f
i
(
ξ
)
∂
ξ
≥
Z
_
i
=
Z
i
(
θ
i
)
,
x
-
x
(
θ
i
)
=
x
-
l
≥
0
,
for
any
x
∈
X
.
If θ
i
=
1, it follows that
(7)
∂
f
i
(
ξ
)
∂
ξ
≤
Z
¯
i
=
Z
i
(
θ
i
)
,
x
-
x
(
θ
i
)
=
x
-
u
≤
0
,
for
any
x
∈
X
.
Therefore, we can get that
(8)
f
i
(
x
)
=
x
(
θ
i
)
T
A
i
x
(
θ
i
)
+
(
∂
f
i
(
ξ
)
∂
ξ
)
T
(
x
-
x
(
θ
i
)
)
≥
x
(
θ
i
)
T
A
i
x
(
θ
i
)
+
Z
i
(
θ
i
)
T
(
x
-
x
(
θ
i
)
)
=
f
i
l
(
x
,
X
,
θ
i
)
.
Analogously, ifθ
i
=
0, then it follows that
(9)
∂
f
i
(
ξ
)
∂
ξ
≤
Z
¯
i
=
Z
i
(
1
-
θ
i
)
,
x
-
x
(
θ
i
)
=
x
-
l
≥
0
,
for
any
x
∈
X
.
If θ
i
=
1, the following inequalities hold:
(10)
∂
f
i
(
ξ
)
∂
ξ
≥
Z
_
i
=
Z
i
(
1
-
θ
i
)
,
x
-
x
(
θ
i
)
=
x
-
u
≤
0
,
for
any
x
∈
X
.
Hence, it follows as above that
(11)
f
i
(
x
)
=
x
(
θ
i
)
T
A
i
x
(
θ
i
)
+
(
∂
f
i
(
ξ
)
∂
ξ
)
T
(
x
-
x
(
θ
i
)
)
≤
x
(
θ
i
)
T
A
i
x
(
θ
i
)
+
Z
i
(
1
-
θ
i
)
T
(
x
-
x
(
θ
i
)
)
=
f
i
u
(
x
,
X
,
θ
i
)
.
The conclusion (i) is followed.
(ii) Consider∥
f
i
(
x
)
-
f
i
l
(
x
,
X
,
θ
i
)
∥, we have
(12)
∥
f
i
(
x
)
-
f
i
l
(
x
,
X
,
θ
i
)
∥
=
∥
x
T
A
i
x
-
[
Z
i
(
θ
i
)
T
x
+
x
(
θ
i
)
T
A
i
x
(
θ
i
)
-
Z
i
(
θ
i
)
T
x
(
θ
i
)
]
∥
=
∥
[
x
(
θ
i
)
T
A
i
x
(
θ
i
)
+
(
∂
f
i
(
ξ
)
∂
ξ
)
T
(
x
-
x
(
θ
i
)
)
]
h
h
h
-
[
Z
i
(
θ
i
)
T
x
+
x
(
θ
i
)
T
A
i
x
(
θ
i
)
-
Z
i
(
θ
i
)
T
x
(
θ
i
)
]
(
∂
f
i
(
ξ
)
∂
ξ
)
T
∥
=
∥
(
∂
f
i
(
ξ
)
∂
ξ
)
T
(
x
-
x
(
θ
i
)
)
-
[
Z
i
(
θ
i
)
T
x
-
Z
i
(
θ
i
)
T
x
(
θ
i
)
]
∥
=
∥
(
∂
f
i
(
ξ
)
∂
ξ
-
Z
i
(
θ
i
)
)
T
(
x
-
x
(
θ
i
)
)
∥
≤
∥
∂
f
i
(
ξ
)
∂
ξ
-
Z
i
(
θ
i
)
∥
∥
x
-
x
(
θ
i
)
∥
≤
∥
Z
¯
i
-
Z
_
i
∥
∥
x
-
x
(
θ
i
)
∥
≤
∥
Z
¯
i
-
Z
_
i
∥
∥
u
-
l
∥
,
where ξ
=
α
x
+
(
1
-
α
)
x
(
θ
i
) with α
∈
[
0,1
].
Since∥
Z
¯
i
-
Z
_
i
∥
∥
u
-
l
∥
→
0 as ∥
u
-
l
∥
→
0, thus we can get that
(13)
∥
f
i
(
x
)
-
f
i
l
(
x
,
X
,
θ
i
)
∥
⟶
0
as
∥
u
-
l
∥
⟶
0
.
Similarly, we can prove that
(14)
∥
f
i
u
(
x
,
X
,
θ
i
)
-
f
i
(
x
)
∥
⟶
0
as
∥
u
-
l
∥
⟶
0
.
The conclusion is complete.By Theorem1, for any x
∈
X, for each i
=
0,1
,
…
,
m, we define
(15)
G
i
L
(
x
,
X
,
θ
i
)
=
Z
i
(
θ
i
)
T
x
+
x
(
θ
i
)
T
A
i
x
(
θ
i
)
-
Z
i
(
θ
i
)
T
x
(
θ
i
)
+
(
d
i
)
T
x
,
G
i
U
(
x
,
X
,
θ
i
)
=
Z
i
(
1
-
θ
i
)
T
x
+
x
(
θ
i
)
T
A
i
x
(
θ
i
)
-
Z
i
(
1
-
θ
i
)
T
x
(
θ
i
)
+
(
d
i
)
T
x
.Theorem 2.
For anyx
∈
X
⊆
X
0, for each i
=
0,1
,
…
,
m, the following conclusions hold:(i)
G
i
L
(
x
,
X
,
θ
i
)
≤
G
i
(
x
)
≤
G
i
U
(
x
,
X
,
θ
i
);
(ii)
∥
G
i
U
(
x
,
X
,
θ
i
)
-
G
i
(
x
)
∥
→
0 and ∥
G
i
(
x
)
-
G
i
L
(
x
,
X
,
θ
i
)
∥
→
0 as ∥
u
-
l
∥
→
0.Proof.
(i) By the definitions ofG
i
L
(
x
,
X
,
θ
i
)
,
G
i
(
x
) and G
i
U
(
x
,
X
,
θ
i
) and the conclusion (i) of Theorem 1, we have
(16)
G
i
L
(
x
,
X
,
θ
i
)
=
Z
i
(
θ
i
)
T
x
+
x
(
θ
i
)
T
A
i
x
(
θ
i
)
-
Z
i
(
θ
i
)
T
x
(
θ
i
)
+
(
d
i
)
T
x
=
f
i
l
(
x
,
X
,
θ
i
)
+
(
d
i
)
T
x
≤
f
i
(
x
)
+
(
d
i
)
T
x
=
G
i
(
x
)
≤
f
i
u
(
x
,
X
,
θ
i
)
+
(
d
i
)
T
x
=
Z
i
(
1
-
θ
i
)
T
x
+
x
(
θ
i
)
T
A
i
x
(
θ
i
)
-
Z
i
(
1
-
θ
i
)
T
x
(
θ
i
)
+
(
d
i
)
T
x
=
G
i
U
(
x
,
X
,
θ
i
)
.
Therefore, the conclusion (i) is followed.
(ii) By the expressions ofG
i
L
(
x
,
X
,
θ
i
), G
i
(
x
), G
i
U
(
x
,
X
,
θ
i
), f
i
l
(
x
,
X
,
θ
i
), f
i
(
x
), and f
i
u
(
x
,
X
,
θ
i
), we can get that
(17)
∥
G
i
(
x
)
-
G
i
L
(
x
,
X
,
θ
i
)
∥
=
∥
[
x
T
A
i
x
+
(
d
i
)
T
x
]
-
[
(
d
i
)
T
Z
i
(
θ
i
)
T
x
+
x
(
θ
i
)
T
A
i
x
(
θ
i
)
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
-
Z
i
(
θ
i
)
T
x
(
θ
i
)
+
(
d
i
)
T
x
]
∥
=
∥
x
T
A
i
x
-
[
Z
i
(
θ
i
)
T
x
+
x
(
θ
i
)
T
A
i
x
(
θ
i
)
-
Z
i
(
θ
i
)
T
x
(
θ
i
)
]
∥
=
∥
f
i
(
x
)
-
f
i
l
(
x
,
X
,
θ
i
)
∥
,
∥
G
i
U
(
x
,
X
,
θ
i
)
-
G
i
(
x
)
∥
=
∥
[
(
d
i
)
T
Z
i
(
1
-
θ
i
)
T
x
+
x
(
θ
i
)
T
A
i
x
(
θ
i
)
-
Z
i
(
1
-
θ
i
)
T
x
(
θ
i
)
h
h
h
h
h
+
(
d
i
)
T
x
]
-
[
x
T
A
i
x
+
(
d
i
)
T
x
]
∥
=
∥
[
Z
i
(
1
-
θ
i
)
T
x
+
x
(
θ
i
)
T
A
i
x
(
θ
i
)
h
h
h
h
h
-
Z
i
(
1
-
θ
i
)
T
x
(
θ
i
)
]
-
x
T
A
i
x
(
1
-
θ
i
)
T
∥
=
∥
f
i
u
(
x
,
X
,
θ
i
)
-
f
i
(
x
)
∥
.
By the proof of Theorem1 (ii), we can get
(18)
∥
G
i
U
(
x
,
X
,
θ
i
)
-
G
i
(
x
)
∥
=
∥
f
i
u
(
x
,
X
,
θ
i
)
-
f
i
(
x
)
∥
⟶
0
as
∥
u
-
l
∥
⟶
0
,
∥
G
i
(
x
)
-
G
i
L
(
x
,
X
,
θ
i
)
∥
=
∥
f
i
(
x
)
-
f
i
l
(
x
,
X
,
θ
i
)
∥
⟶
0
as
∥
u
-
l
∥
⟶
0
.
The conclusion is complete.By Theorem2, we can construct the underestimating approximation parametric linear programs relaxation problem (
PLPRP
) of the problem (
NQCQP
) over subhyperrectangle X as follows:
(
PLPRP
)
min
⁡
G
0
L
(
x
,
X
,
θ
0
)
,
s
.
t
.
iiihi
G
i
L
(
x
,
X
,
θ
i
)
≤
b
i
,
i
=
1
,
…
,
m
,
h
h
h
h
h
x
∈
X
=
{
x
:
l
≤
x
≤
u
}
⊆
X
0
,
where
(19)
G
i
L
(
x
,
X
,
θ
i
)
=
Z
i
(
θ
i
)
T
x
+
x
(
θ
i
)
T
A
i
x
(
θ
i
)
-
Z
i
(
θ
i
)
T
x
(
θ
i
)
+
(
d
i
)
T
x
.Based on the above parametric linearizing approach, every feasible point of the problem(
NQCQP
) is feasible to the problem (
PLPRP
) over the subhyperrectangle X, and the objective function value of the problem (
PLPRP
) at each feasible point is less than or equal to that of the problem (
NQCQP
) over the subhyperrectangle X. Thus, the optimal value of the problem (
PLPRP
) offers a valid lower bound for the optimal value of the problem (
NQCQP
) over the subhyperrectangle X.


## 3. Cutting Down Approach

To enhance the computational speed of the investigated algorithm, based on the above parametric linear relaxation problem, a novel cutting down approach is described in the following Theorem3. At the k-th iteration of the proposed algorithm, we will judge whether or not the subhyperrectangle X contains a global optimum point of the problem (
NQCQP
). The cutting down approach can be used to reject a part of the subhyperrectangle X or the whole X without deleting any global optimum point of the problem (
NQCQP
). For convenience, for any x
∈
X
=
(
X
j
)
n
×
1 with X
j
=
[
l
j
,
u
j
]
(
j
=
1
,
…
,
n
), without loss of generality, we express the G
i
L
(
x
,
X
,
θ
i
) in the problem (
PLPRP
) over the subhyperrectangle X as the following form:
(20)
G
i
L
(
x
,
X
,
θ
i
)
=
∑
j
=
1
n
‍
γ
i
j
(
θ
i
)
x
j
+
η
i
(
θ
i
)
,
i
=
0,1
,
…
,
m
.Assume thatU
B
k is the currently known upper bound of the proposed branch and bound algorithm, and for any fixed θ
i
,
i
=
0,1
,
…
,
m, let
(21)
PLR
B
i
(
θ
i
)
=
∑
j
=
1
n
‍
min
⁡
{
γ
i
j
(
θ
i
)
l
j
,
γ
i
j
(
θ
i
)
u
j
}
+
η
i
(
θ
i
)
,
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
i
=
0,1
,
…
,
m
,
β
p
(
θ
0
)
=
U
B
k
-
PLR
B
0
(
θ
0
)
+
min
⁡
{
γ
0
p
(
θ
0
)
l
p
,
γ
0
p
(
θ
0
)
u
p
}
,
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
p
=
1
,
…
,
n
,
λ
i
p
(
θ
i
)
=
b
i
-
PLR
B
i
(
θ
i
)
+
min
⁡
{
γ
i
p
(
θ
i
)
l
p
,
γ
i
p
(
θ
i
)
u
p
}
,
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
l
p
=
1
,
…
,
n
,
i
=
1
,
…
,
m
.And defineY
¯
¯
=
(
Y
¯
¯
j
)
n
×
1
,
Y
_
=
(
Y
_
j
)
n
×
1
,
Y
~
=
(
Y
~
j
)
n
×
1, and Y
^
=
(
Y
^
j
)
n
×
1, where
(22)
Y
~
j
=
{
X
j
,
j
≠
p
,
j
=
1
,
…
,
n
,
(
λ
i
p
(
θ
i
)
γ
i
p
(
θ
i
)
,
u
p
]
⋂
‍
X
p
,
j
=
p
;
Y
^
j
=
{
X
j
,
j
≠
p
,
j
=
1
,
…
,
n
,
[
l
p
,
λ
i
p
(
θ
i
)
γ
i
p
(
θ
i
)
)
⋂
‍
X
p
,
j
=
p
;
Y
¯
¯
j
=
{
X
j
,
j
≠
p
,
j
=
1
,
…
,
n
,
(
β
p
(
θ
0
)
γ
0
p
(
θ
0
)
,
u
p
]
⋂
‍
X
p
,
j
=
p
;
Y
_
j
=
{
X
j
,
j
≠
p
,
j
=
1
,
…
,
n
,
[
l
p
,
β
p
(
θ
0
)
γ
0
p
(
θ
0
)
)
⋂
‍
X
p
,
j
=
p
.Theorem 3.
For any subhyperrectangleX
⊆
X
0, one has the following results.(i)
IfP
L
R
B
0
(
θ
0
)
>
U
B
k, then the subhyperrectangle X does not contain the global optimum point of the problem (
NQCQP
).
(ii)
IfP
L
R
B
0
(
θ
0
)
≤
U
B
k, then for any p
∈
{
1,2
,
…
,
n
}, if γ
0
p
(
θ
0
)
>
0, then the subhyperrectangle Y
¯
¯
=
(
Y
¯
¯
j
)
n
×
1 does not contain the global optimum point of the problem (
NQCQP
); if γ
0
p
(
θ
0
)
<
0, then the subhyperrectangle Y
_
=
(
Y
_
j
)
n
×
1 does not contain the global optimum point of the problem (
NQCQP
).
(iii)
If there exists somei
∈
{
1
,
…
,
m
} such that P
L
R
B
i
(
θ
i
)
>
b
i, then the subhyperrectangle X does not contain the global optimum point of the problem (
NQCQP
).
(iv)
IfP
L
R
B
i
(
θ
i
)
≤
b
i for all i
=
1
,
…
,
m, then for each p
∈
{
1,2
,
…
,
n
}, if γ
i
p
(
θ
i
)
>
0, then the subhyperrectangle Y
~
=
(
Y
~
j
)
n
×
1 does not contain the global optimum point of the problem (
NQCQP
); if γ
i
p
(
θ
i
)
<
0, then the subhyperrectangle Y
^
=
(
Y
^
j
)
n
×
1 does not contain the global optimum point of the problem (
NQCQP
).Proof.
(i) IfPLR
B
0
(
θ
0
)
>
U
B
k, then for all x
∈
X, by the Theorem 2 we have
(23)
G
0
(
x
)
≥
G
0
L
(
x
,
X
,
θ
0
)
≥
∑
j
=
1
n
‍
min
⁡
{
γ
0
j
(
θ
0
)
l
j
,
γ
0
j
(
θ
0
)
u
j
}
+
η
0
(
θ
0
)
=
PLR
B
0
(
θ
0
)
>
U
B
k
.
Hence, the X does not contain the global optimum point of the problem (
NQCQP
).
(ii) IfPLR
B
0
(
θ
0
)
≤
U
B
k, then for any p
∈
{
1
,
…
,
n
}, if γ
0
p
(
θ
0
)
>
0, for all x
∈
Y
¯
¯, we have x
p
>
β
p
(
θ
0
)
/
γ
0
p
(
θ
0
); that is, γ
0
p
(
θ
0
)
x
p
>
U
B
k
-
PLR
B
0
(
θ
0
)
+
min
⁡
{
γ
0
p
(
θ
0
)
l
p
,
γ
0
p
(
θ
0
)
u
p
}. Thus, we have
(24)
G
0
L
(
x
,
Y
¯
¯
,
θ
0
)
=
∑
j
=
1
,
j
≠
p
n
‍
γ
0
j
(
θ
0
)
x
j
+
γ
0
p
(
θ
0
)
x
p
+
η
0
(
θ
0
)
≥
∑
j
=
1
,
j
≠
p
n
‍
min
⁡
{
γ
0
j
(
θ
0
)
l
j
,
γ
0
j
(
θ
0
)
u
j
}
+
η
0
(
θ
0
)
+
γ
0
p
(
θ
0
)
x
p
>
∑
j
=
1
,
j
≠
p
n
‍
min
⁡
{
γ
0
j
(
θ
0
)
l
j
,
γ
0
j
(
θ
0
)
u
j
}
+
η
0
(
θ
0
)
hhhhhh
+
U
B
k
-
PLR
B
0
(
θ
0
)
+
min
⁡
{
γ
0
p
(
θ
0
)
l
p
,
γ
0
p
(
θ
0
)
u
p
}
=
PLR
B
0
(
θ
0
)
+
U
B
k
-
PLR
B
0
(
θ
0
)
=
U
B
k
.
Therefore, by the above inequality and Theorem 2, we get that
(25)
G
0
(
x
)
≥
G
0
L
(
x
,
Y
¯
¯
,
θ
0
)
>
U
B
k
.
Hence, the rectangle Y
¯
¯ does not contain the global optimum point of the problem (
NQCQP
).
Similarly, ifγ
0
p
(
θ
0
)
<
0, we can prove that the subhyperrectangle Y
_ does not contain the global optimum point of the problem (
NQCQP
).
Using similar proving method as the above, we can draw the conclusions (iii) and (iv).By Theorem3, by making use of the above cutting down approach to reject a part of the investigated subhyperrectangle which does not contain the global minimum point of the problem (
NQCQP
), thus we can enhance the computational speed of the proposed branch and bound algorithm.


## 4. Algorithm and Its Convergence

In this section, based on the former parametric linear programs relaxation problem, we present a novel optimization method for globally solving the problem(
NQCQP
). There are three fundamental compositions in the presented method: a branching approach, an updating upper bounds approach, and an updating lower bounds approach.The branching approach iteratively subdivides the investigated hyperrectangleX
k into two subhyperrectangles, which produces a more refined partition for computing the global optimum point of the problem (
NQCQP
). In this paper we select a simple partitioning approach, which is enough to guarantee the global convergence of the presented branch and bound algorithm. For any selected subhyperrectangle X
k
=
[
l
k
,
u
k
]
⊆
X
0, the selected partitioning approach is described as follows.(a)
Letη
=
arg
max
⁡
{
u
i
k
-
l
i
k
:
i
=
1
,
…
,
n
}.
(b)
Let(26)
X
k
,
1
=
{
x
∈
R
n
∣
l
i
k
≤
x
i
≤
u
i
k
,
i
≠
η
,
l
η
k
≤
x
η
≤
l
η
k
+
u
η
k
2
}
,
X
k
,
2
=
{
x
∈
R
n
∣
l
i
k
≤
x
i
≤
u
i
k
,
i
≠
η
,
l
η
k
+
u
η
k
2
≤
x
η
≤
u
η
k
}
.By making use of this branching approach, the selected hyperrectangle X
k is subdivided into two subhyperrectangles X
k
,
1 and X
k
,
2.The updating lower bounds approach needs to compute a sequence of parametric linear programs relaxation problems by using the simplex approach. The updating upper bounds approaches need to calculate the objective function value of the feasible point of the problem(
NQCQP
), where the feasible point can be found by solving the parametric linear programs relaxation problem and probing the feasibility of the midpoint of the investigated subhyperrectangle X
k, respectively.


### 4.1. Novel Optimization Algorithm

LetLB
(
X
k
) and x
k
=
x
(
X
k
) be the optimal value and the optimal solution of the problem (
PLPRP
) over subhyperrectangle X
k, respectively. Combining the former parametric linear programs relaxation problem with the cutting down approach in a branch and bound framework, a novel global optimization method for the problem (
NQCQP
) is described as follows.Algorithm StepsStep 1 (initializing).
Initialize the iteration counterk
:
=
0, the collection of all active node Ω
0
=
{
X
0
}, the feasible solution set F
=
∅, the convergence error ϵ
>
0, and the upper bound U
B
0
=
+
∞.
Solve the problem(
PLPRP
) over the hyperrectangle X
0 to compute L
B
0
:
=
LB
(
X
0
) and x
0
:
=
x
(
X
0
). For all i
=
1
,
…
,
m, if G
i
(
x
0
)
≤
b
i, then let F
=
{
x
0
} and U
B
0
=
G
0
(
x
0
).
IfU
B
0
-
L
B
0
≤
ϵ, then algorithm terminates with x
0 as the global optimum point of the problem (
NQCQP
). Otherwise, go to Step 2.Step 2 (partitioning hyperrectangle).
Utilizing the proposed branching approach, select a branching variablex
η to partition X
k into two new subhyperrectangles, and still let the new collection of partitioned subhyperrectangles by X
¯
k.Step 3 (cutting down region).
For each subhyperrectangleX
∈
X
¯
k, for any fixed parameter vector θ
=
(
θ
0
,
θ
1
,
…
,
θ
m
), compute PLR
B
i
(
θ
i
)
(
i
=
0,1
,
…
,
m
), β
p
(
θ
0
)
(
p
=
1
,
…
,
n
), and λ
i
p
(
θ
i
)
(
i
=
1
,
…
,
m
,
p
=
1
,
…
,
n
).
For eachi
∈
{
1
,
…
,
m
}, if PLR
B
i
(
θ
i
)
>
b
i, let X
=
∅; elseifγ
i
p
(
θ
i
)
>
0 and λ
i
p
(
θ
i
)
/
γ
i
p
(
θ
i
)
<
u
p for some p
∈
{
1
,
…
,
n
}, then let u
p
=
λ
i
p
(
θ
i
)
/
γ
i
p
(
θ
i
).
else ifγ
i
p
(
θ
i
)
<
0 and λ
i
p
(
θ
i
)
/
γ
i
p
(
θ
i
)
>
l
p for some p
∈
{
1
,
…
,
n
}, then let l
p
=
λ
i
p
(
θ
i
)
/
γ
i
p
(
θ
i
).
IfPLR
B
0
(
θ
0
)
>
U
B
k, then let X
=
∅; elseifγ
0
p
(
θ
0
)
>
0 and β
p
(
θ
0
)
/
γ
0
p
(
θ
0
)
<
u
p for some p
∈
{
1
,
…
,
n
}, then let u
p
=
β
p
(
θ
0
)
/
γ
0
p
(
θ
0
),
else ifγ
0
p
(
θ
0
)
<
0 and β
p
(
θ
0
)
/
γ
0
p
(
θ
0
)
>
l
p for some p
∈
{
1
,
…
,
n
}, then let l
p
=
β
p
(
θ
0
)
/
γ
0
p
(
θ
0
).
At last, still let the remaining subhyperrectangle beX, and let the remaining partitioned set be X
¯
k.Step 4 (feasibility fathoming).
For each new subhyperrectangleX
∈
X
¯
k, compute the lower bounds LB
(
X
) and x
(
X
) by solving the problem (
PLPRP
) over X.
IfLB
(
X
)
>
U
B
k, set X
¯
k
:
=
X
¯
k
∖
X; otherwise, if the midpoint x
mid of X satisfies G
i
(
x
mid
)
≤
b
i for all i
=
1
,
…
,
m, then let F
:
=
F
∪
{
x
mid
}, and if x
(
X
) satisfies G
i
(
x
(
X
)
)
≤
b
i for all i
=
1
,
…
,
m, then let F
:
=
F
∪
{
x
(
X
)
},Step 5 (renewing bound).
Renew the upper boundU
B
k
:
=
min
⁡
x
∈
F
G
0
(
x
). If F
≠
∅, the best known feasible solution is denoted by x
k
:
=
arg
mi
n
x
∈
F
G
0
(
x
). Let Θ
k
:
=
(
Θ
k
∖
X
k
)
∪
X
¯
k, and renew the lower bound L
B
k
:
=
inf
⁡
X
∈
Θ
k
LB
(
X
).Step 6 (convergence fathoming).
IfU
B
k
-
L
B
k
≤
ϵ, then algorithm stops, and we get that U
B
k is the global ϵ-minimum value of the problem (
NQCQP
), and x
k is a global ϵ-optimum point. Otherwise, k
:
=
k
+
1, and select a new subhyperrectangle X
k such that X
k
=
arg
mi
n
X
∈
Θ
k
LB
(
X
), and return to Step 2.


### 4.2. Global Convergence of the Algorithm

The global convergence of the presented algorithm is described as follows.Theorem 4.
If the proposed algorithm stops finitely at thek-th iteration, then when the algorithm stops, x
k is the global optimum point of the problem (
NQCQP
); else it will bring about an infinite sequence {
x
k
} of iteration, such that any accumulation point x
* of the sequence {
x
k
} will be the global optimum point of the problem (
N
Q
C
Q
P
), and the sequence {
U
B
k
} is nonincreasing and the sequence {
L
B
k
} is nondecreasing; moreover they meet lim
⁡
k
→
∞
U
B
k
=
lim
⁡
k
→
∞
L
B
k
=
v
*, where v
* is the global minimum value of the problem (
NQCQP
).Proof.
(i) If the proposed algorithm stops finitely at thek-th iteration, then when it stops, we get that U
B
k
=
v
*
=
L
B
k. Thus, by the characteristic of the proposed branch and bound algorithm, we get the global optimum point x
k of the problem (
NQCQP
). If the proposed algorithm is infinite, then it must bring about an infinite subhyperrectangle sequence {
X
k
}, since the used branching approach is exhaustive, we get that the subhyperrectangle sequence {
X
k
} converges to a point. By the branch and bound characteristic of the algorithm we get that the sequence {
U
B
k
} is nonincreasing, and the sequence {
L
B
k
} is nondecreasing; therefore the sequence {
U
B
k
-
L
B
k
} is a positive and nonincreasing sequence. From Theorem 2, we know that the sequence {
U
B
k
-
L
B
k
} must be convergent to zero. Also L
B
k
≤
v
*
≤
U
B
k for each k indicate that lim
⁡
k
→
∞
U
B
k
=
lim
⁡
k
→
∞
L
B
k
=
v
*. Since x
k is always a feasible solution of the problem (
NQCQP
) and the upper bound U
B
k
=
G
0
(
x
k
), any cluster point x
* of the sequence {
x
k
} must be feasible to the problem (
NQCQP
) with objective function value v
*
=
G
0
(
x
*
). Therefore, the conclusion is followed.


## 4.1. Novel Optimization Algorithm

LetLB
(
X
k
) and x
k
=
x
(
X
k
) be the optimal value and the optimal solution of the problem (
PLPRP
) over subhyperrectangle X
k, respectively. Combining the former parametric linear programs relaxation problem with the cutting down approach in a branch and bound framework, a novel global optimization method for the problem (
NQCQP
) is described as follows.Algorithm StepsStep 1 (initializing).
Initialize the iteration counterk
:
=
0, the collection of all active node Ω
0
=
{
X
0
}, the feasible solution set F
=
∅, the convergence error ϵ
>
0, and the upper bound U
B
0
=
+
∞.
Solve the problem(
PLPRP
) over the hyperrectangle X
0 to compute L
B
0
:
=
LB
(
X
0
) and x
0
:
=
x
(
X
0
). For all i
=
1
,
…
,
m, if G
i
(
x
0
)
≤
b
i, then let F
=
{
x
0
} and U
B
0
=
G
0
(
x
0
).
IfU
B
0
-
L
B
0
≤
ϵ, then algorithm terminates with x
0 as the global optimum point of the problem (
NQCQP
). Otherwise, go to Step 2.Step 2 (partitioning hyperrectangle).
Utilizing the proposed branching approach, select a branching variablex
η to partition X
k into two new subhyperrectangles, and still let the new collection of partitioned subhyperrectangles by X
¯
k.Step 3 (cutting down region).
For each subhyperrectangleX
∈
X
¯
k, for any fixed parameter vector θ
=
(
θ
0
,
θ
1
,
…
,
θ
m
), compute PLR
B
i
(
θ
i
)
(
i
=
0,1
,
…
,
m
), β
p
(
θ
0
)
(
p
=
1
,
…
,
n
), and λ
i
p
(
θ
i
)
(
i
=
1
,
…
,
m
,
p
=
1
,
…
,
n
).
For eachi
∈
{
1
,
…
,
m
}, if PLR
B
i
(
θ
i
)
>
b
i, let X
=
∅; elseifγ
i
p
(
θ
i
)
>
0 and λ
i
p
(
θ
i
)
/
γ
i
p
(
θ
i
)
<
u
p for some p
∈
{
1
,
…
,
n
}, then let u
p
=
λ
i
p
(
θ
i
)
/
γ
i
p
(
θ
i
).
else ifγ
i
p
(
θ
i
)
<
0 and λ
i
p
(
θ
i
)
/
γ
i
p
(
θ
i
)
>
l
p for some p
∈
{
1
,
…
,
n
}, then let l
p
=
λ
i
p
(
θ
i
)
/
γ
i
p
(
θ
i
).
IfPLR
B
0
(
θ
0
)
>
U
B
k, then let X
=
∅; elseifγ
0
p
(
θ
0
)
>
0 and β
p
(
θ
0
)
/
γ
0
p
(
θ
0
)
<
u
p for some p
∈
{
1
,
…
,
n
}, then let u
p
=
β
p
(
θ
0
)
/
γ
0
p
(
θ
0
),
else ifγ
0
p
(
θ
0
)
<
0 and β
p
(
θ
0
)
/
γ
0
p
(
θ
0
)
>
l
p for some p
∈
{
1
,
…
,
n
}, then let l
p
=
β
p
(
θ
0
)
/
γ
0
p
(
θ
0
).
At last, still let the remaining subhyperrectangle beX, and let the remaining partitioned set be X
¯
k.Step 4 (feasibility fathoming).
For each new subhyperrectangleX
∈
X
¯
k, compute the lower bounds LB
(
X
) and x
(
X
) by solving the problem (
PLPRP
) over X.
IfLB
(
X
)
>
U
B
k, set X
¯
k
:
=
X
¯
k
∖
X; otherwise, if the midpoint x
mid of X satisfies G
i
(
x
mid
)
≤
b
i for all i
=
1
,
…
,
m, then let F
:
=
F
∪
{
x
mid
}, and if x
(
X
) satisfies G
i
(
x
(
X
)
)
≤
b
i for all i
=
1
,
…
,
m, then let F
:
=
F
∪
{
x
(
X
)
},Step 5 (renewing bound).
Renew the upper boundU
B
k
:
=
min
⁡
x
∈
F
G
0
(
x
). If F
≠
∅, the best known feasible solution is denoted by x
k
:
=
arg
mi
n
x
∈
F
G
0
(
x
). Let Θ
k
:
=
(
Θ
k
∖
X
k
)
∪
X
¯
k, and renew the lower bound L
B
k
:
=
inf
⁡
X
∈
Θ
k
LB
(
X
).Step 6 (convergence fathoming).
IfU
B
k
-
L
B
k
≤
ϵ, then algorithm stops, and we get that U
B
k is the global ϵ-minimum value of the problem (
NQCQP
), and x
k is a global ϵ-optimum point. Otherwise, k
:
=
k
+
1, and select a new subhyperrectangle X
k such that X
k
=
arg
mi
n
X
∈
Θ
k
LB
(
X
), and return to Step 2.


## 4.2. Global Convergence of the Algorithm

The global convergence of the presented algorithm is described as follows.Theorem 4.
If the proposed algorithm stops finitely at thek-th iteration, then when the algorithm stops, x
k is the global optimum point of the problem (
NQCQP
); else it will bring about an infinite sequence {
x
k
} of iteration, such that any accumulation point x
* of the sequence {
x
k
} will be the global optimum point of the problem (
N
Q
C
Q
P
), and the sequence {
U
B
k
} is nonincreasing and the sequence {
L
B
k
} is nondecreasing; moreover they meet lim
⁡
k
→
∞
U
B
k
=
lim
⁡
k
→
∞
L
B
k
=
v
*, where v
* is the global minimum value of the problem (
NQCQP
).Proof.
(i) If the proposed algorithm stops finitely at thek-th iteration, then when it stops, we get that U
B
k
=
v
*
=
L
B
k. Thus, by the characteristic of the proposed branch and bound algorithm, we get the global optimum point x
k of the problem (
NQCQP
). If the proposed algorithm is infinite, then it must bring about an infinite subhyperrectangle sequence {
X
k
}, since the used branching approach is exhaustive, we get that the subhyperrectangle sequence {
X
k
} converges to a point. By the branch and bound characteristic of the algorithm we get that the sequence {
U
B
k
} is nonincreasing, and the sequence {
L
B
k
} is nondecreasing; therefore the sequence {
U
B
k
-
L
B
k
} is a positive and nonincreasing sequence. From Theorem 2, we know that the sequence {
U
B
k
-
L
B
k
} must be convergent to zero. Also L
B
k
≤
v
*
≤
U
B
k for each k indicate that lim
⁡
k
→
∞
U
B
k
=
lim
⁡
k
→
∞
L
B
k
=
v
*. Since x
k is always a feasible solution of the problem (
NQCQP
) and the upper bound U
B
k
=
G
0
(
x
k
), any cluster point x
* of the sequence {
x
k
} must be feasible to the problem (
NQCQP
) with objective function value v
*
=
G
0
(
x
*
). Therefore, the conclusion is followed.


## 5. Numerical Experiments

To validate the performance and computational efficiency of the presented optimization method, several common test examples in literatures are put into effect on microcomputer, the algorithm program is coded in C++, the simplex approach is applied to solve a series of parametric linear programs relaxation problems, and the termination tolerance error is set toϵ
=
1
0
-
6. These test examples are described and their numerical results are listed as follows. In the following Tables 1, 2, and 3, number of algorithm iteration and computational time in seconds are denoted by “Iter” and “Time,” respectively.Table 1
Numerical results for Examples1–3.
Example
Refs.
(θ
0
,
…
,
θ
m)
Optimal solution
Optimal value
Iter
Time (s)
1
our1
(0, 0, 0)
(5.0, 1.0)
−16.000000000
3
0.00190359
our2
(0, 0, 1)
(5.0, 1.0)
−16.000000000
2
0.000975264
our3
(0, 1, 1)
(5.0, 1.0)
−16.000000000
2
0.000958502
our4
(1, 1, 1)
(5.0, 1.0)
−16.000000000
3
0.00115294
our5
(1, 0, 0)
(5.0, 1.0)
−16.000000000
4
0.0013566
our6
(1, 0, 1)
(5.0, 1.0)
−16.000000000
3
0.00114037
our7
(1, 1, 0)
(5.0, 1.0)
−16.000000000
4
0.00142281
our8
(0, 1, 0)
(5.0, 1.0)
−16.000000000
3
0.00108701
[32]
(5.0, 1.0)
−16.0
20
0.175
[21]
(5.0, 1.0)
−16.0
5
0.00184588
2
our1
(0, 0)
(2.0, 1.666666667)
6.777778018
32
0.00662822
our2
(0, 1)
(2.0, 1.666666667)
6.777778233
32
0.00665057
our3
(1, 1)
(2.0, 1.666666667)
6.777778517
33
0.00698972
our4
(1, 0)
(2.0, 1.666666667)
6.777778743
32
0.00685227
[19]
(2.0, 1.666666667)
6.777782016
40
0.032
[22]
(2.00003, 1.66665)
6.7780
44
0.18
3
our1
(0, 0, 0)
(0.5, 0.5)
0.500000000
25
0.0065648
our2
(0, 0, 1)
(0.5, 0.5)
0.500000000
25
0.00733278
our3
(0, 1, 1)
(0.5, 0.5)
0.500000600
26
0.00686791
our4
(1, 1, 1)
(0.5, 0.5)
0.500000600
26
0.00691568
our5
(1, 0, 0)
(0.5, 0.5)
0.500000000
25
0.00735261
our6
(1, 0, 1)
(0.5, 0.5)
0.500000000
25
0.00736742
our7
(1, 1, 0)
(0.5, 0.5)
0.500000600
26
0.00769232
our8
(0, 1, 0)
(0.5, 0.5)
0.500000600
26
0.00921374
[19]
(0.5, 0.5)
0.500004627
34
0.056
[21]
(0.5, 0.5)
0.500000442
37
0.0192625
[22]
(0.5, 0.5)
0.5
91
0.85Table 2
Numerical results for Examples4–6.
Example
Refs.
(θ
0
,
…
,
θ
m)
Optimal solution
Optimal value
Iter
Time (s)
4
our1
(0, 0, 0)
(2.0, 1.0)
−1.000000
0
0.00071504
our2
(0, 0, 1)
(2.0, 1.0)
−1.000000000
1
0.00165866
our3
(0, 1, 1)
(2.0, 1.0)
−1.000000000
2
0.00169589
our4
(1, 1, 1)
(2.0, 1.0)
−1.000000000
2
0.00156529
our5
(1, 0, 0)
(2.0, 1.0)
−1.000000000
2
0.00153087
our6
(1, 0, 1)
(2.0, 1.0)
−1.000000000
2
0.00159881
our7
(1, 1, 0)
(2.0, 1.0)
−1.000000000
2
0.00158519
our8
(0, 1, 0)
(2.0, 1.0)
−1.000000
0
0.00066607
[21]
(2.0, 1.0)
−0.999999410
21
0.00849446
[23]
(2.0, 1.0)
−1.0
24
0.0116923
5
our1
(0, 0)
(2.555409888, 3.130613160)
118.383672050
49
0.0271463
our2
(0, 1)
(2.555676683, 3.130286407)
118.383672115
51
0.0287108
our3
(1, 1)
(2.555800904, 3.130134268)
118.383672231
61
0.0350215
our4
(1, 0)
(2.555775920, 3.130164866)
118.383671937
55
0.030462
[17]
(2.555779370, 3.130164640)
118.383756475
210
0.78
[21]
(2.555745855, 3.130201688)
118.383671904
59
0.0385038
6
our1
(0, 0, 0)
(1.0, 0.181818247, 0.983332154)
−11.363635387
141
0.110562
our2
(0, 0, 1)
(1.0, 0.181818217, 0.983332160)
−11.363636364
240
0.198587
our3
(0, 1, 1)
(1.0, 0.181818196, 0.983332163)
−11.363635785
260
0.213692
our4
(1, 1, 1)
(1.0, 0.181818133, 0.983332175)
−11.363635682
229
0.18844
our5
(1, 0, 0)
(1.0, 0.181783067, 0.983338664)
−11.363635889
80
0.0669022
our6
(1, 0, 1)
(1.0, 0.181818133, 0.983332175)
−11.363635715
213
0.176459
our7
(1, 1, 0)
(1.0, 0.181818301, 0.983332144)
−11.363635516
149
0.131391
our8
(0, 1, 0)
(1.0, 0.181818133, 0.983332175)
−11.363636364
133
0.105004
[21]
(1.0, 0.181818470, 0.983332113)
−11.363636364
420
0.284541
[25]
(0.998712, 0.196213, 0.979216)
−10.35
1648
0.3438Table 3
Numerical comparisons with Refs. [16, 21] for Example 9.
Refs.
Number of variable
n
=
5
n
=
10
n
=
20
n
=
30
Ours
Computational time (s)
0.0124692
0.215709
3.69194
27.4522
Iteration Number
12
31
86
204
Ref. [16]
Computational time (s)
10.11
21.86
47.00
106.33
Iteration Number
141
283
651
965
Ref. [21]
Computational time (s)
0.0181791
0.302157
6.01095
44.4965
Iteration Number
12
32
88
206Example 1 (see [21, 32]).
Consider(27)
min
⁡
-
x
1
2
+
x
1
+
x
2
2
-
2
x
2
+
x
1
x
2
s
.
t
.
hh
x
1
+
x
2
≤
6
,
hhhhh
-
2
x
1
2
+
x
2
2
+
2
x
1
+
x
2
≤
-
4
,
hhhhiii
1
≤
x
1
,
x
2
≤
6
.Example 2 (see [19, 21, 22]).
Consider(28)
min
⁡
x
1
2
+
x
2
2
s
.
t
.
h
-
0.3
x
1
x
2
≤
-
1
,
hhhhh
2
≤
x
1
≤
5
,
1
≤
x
2
≤
3
.Example 3 (see [19, 21, 22]).
Consider(29)
min
⁡
x
1
s
.
t
.
h
4
x
2
-
4
x
1
2
≤
1
,
h
h
h
h
h
x
1
+
x
2
≥
1
,
hhhhh
0.01
≤
x
1
,
x
2
≤
15
.Example 4 (see [21, 23]).
Consider(30)
min
⁡
x
1
x
2
-
2
x
1
+
x
2
+
1
s
.
t
.
h
8
x
2
2
-
6
x
1
-
16
x
2
≤
-
11
,
hhhh
-
x
2
2
+
3
x
1
+
2
x
2
≤
7
,
hhhhi
1
≤
x
1
≤
2.5
,
1
≤
x
2
≤
2.225
.Example 5 (see [17, 21]).
Consider(31)
min
⁡
6
x
1
2
+
4
x
2
2
+
5
x
1
x
2
s
.
t
.
h
-
6
x
1
x
2
≤
-
48
,
0
≤
x
1
,
x
2
≤
10
.Example 6 (see [21, 25]).
Consider(32)
min
⁡
-
4
x
2
+
(
x
1
-
1
)
2
+
x
2
2
-
10
x
3
2
min
⁡
6
x
1
2
+
4
x
2
2
+
5
x
1
x
2
hhhhh
(
x
1
-
2
)
2
+
x
2
2
+
x
3
2
≤
2
,
hhhhh
2
-
2
≤
x
1
≤
2
,
0
≤
x
2
,
x
3
≤
2
.Example 7 (see [33, 34]).
Consider(33)
min
⁡
x
1
+
x
2
+
x
3
s
.
t
.
h
833.33252
x
-
1
x
4
x
-
6
+
100.0
x
6
-
1
hhhh
-
83333.333
x
1
-
1
x
6
-
1
≤
1
,
hhhhi
1250.0
x
2
-
1
x
5
x
7
-
1
+
1.0
x
4
x
7
-
1
hhhh
-
1250.0
x
2
-
1
x
4
x
7
-
1
≤
1
,
hhhhi
1250000.0
x
3
-
1
x
8
-
1
+
1.0
x
5
x
8
-
1
hhhh
-
2500.0
x
3
-
1
x
5
x
8
-
1
≤
1
,
hhhhi
0.0025
x
4
+
0.0025
x
6
≤
1
,
hhhh
-
0.0025
x
4
+
0.0025
x
5
hhhh
+
0.0025
x
7
≤
1
,
hhhhi
0.001
x
8
-
0.001
x
5
≤
1
,
h
h
h
h
(
100,1000,1000,10,10,10,10,10
)
hhhh
≤
(
x
1
,
x
2
,
x
3
,
x
4
,
x
5
,
x
6
,
x
7
,
x
8
)
,
h
h
h
h
(
x
1
,
x
2
,
x
3
,
x
4
,
x
5
,
x
6
,
x
7
,
x
8
)
hhhh
≤
(
10000,10000,10000,1000
,
h
h
h
h
h
h
h
h
1000,1000,1000,1000
)
.
This problem is from the heat exchanger design problem; solve this problem by the proposed method, with the given convergence errorϵ
=
1
0
-
6 and parameter vector θ
i
=
0, i
=
0,1
,
…
,
6, and a global ϵ-optimal solution
(34)
(
x
1
,
…
,
x
8
)
T
=
(
579.307,1359.971,5109.971,182.018
,
h
h
h
h
295.601,217.982,286.417,395.6
)
is found after 18377 iterations with objective function value 7049.248020529, and computational time is 11.475 s.
Using the proposed approach in Floudas et al. [33], a global optimal solution, under the given convergence tolerance ϵ
=
1
0
-
4,
(35)
(
x
1
,
…
,
x
8
)
T
=
(
579.31,1359.97,5109.97,182.01
,
h
h
h
h
295.60,217.98,286.42,395.6
)
is found with global optimal value 7049.25000.
Using the proposed approach in Lin and Tsai [34], under the convergence tolerance ϵ
=
1
0
-
6, a global optimal solution
(36)
(
x
1
,
…
,
x
8
)
T
=
(
578.973,1359.573,5110.701,181.99
,
h
h
h
h
295.572,218.01,286.418,395.572
)
is found with global optimization value 7049.24692.Example 8 (see [24]).
Consider(37)
min
⁡
5.3578
x
3
2
+
0.8357
x
1
x
5
+
37.2392
x
1
s
.
t
.
h
0.00002584
x
3
x
5
-
0.00006663
x
2
x
5
hhhh
-
0.0000734
x
1
x
4
≤
1
,
hhhiii
0.000853007
x
2
x
5
+
0.00009395
x
1
x
4
hhhh
-
0.00033085
x
3
x
5
≤
1
,
hhhhi
1330.3294
x
2
-
1
x
5
-
1
-
0.42
x
1
x
5
-
1
hhhh
-
0.30586
x
2
-
1
x
3
2
x
5
-
1
≤
1
,
hhhhi
0.00024186
x
2
x
5
+
0.00010159
x
1
x
2
hhhh
+
0.00007379
x
3
2
≤
1
,
hhhhi
2275.1327
x
3
-
1
x
5
-
1
-
0.2668
x
1
x
5
-
1
hhhh
-
0.40584
x
4
x
5
-
1
≤
1
,
hhhhi
0.00029955
x
3
x
5
+
0.00007992
x
1
x
3
hhhh
+
0.00012157
x
3
x
4
≤
1
,
hhhhi
78.0
≤
x
1
≤
102.0
,
33.0
≤
x
2
≤
45.0
,
hhhhi
27.0
≤
x
3
≤
45.0
,
hhhhi
27.0
≤
x
4
≤
45.0
,
27.0
≤
x
5
≤
45.0
.
This test problem has a relative high degree of difficulty, and it contains both negative and positive terms. By using the proposed algorithm in this paper, initializing the parameterθ
i
=
1, i
=
0,1
,
…
,
6, with the given convergence error ϵ
=
1
0
-
6, the global ϵ-optimal solution
(38)
(
x
1
,
x
2
,
…
,
x
5
)
T
=
(
78.0,33.739811424,30.594417922
,
h
h
h
h
44.991210938,35.288085938
)
can be obtained after the 51 iterations.
But using the proposed algorithm in [24], with the given convergence error ϵ
=
1
0
-
6, the global ϵ-optimal solution
(39)
(
x
1
,
x
2
,
…
,
x
5
)
T
=
(
78.0,32.99999946,29.995510365
,
h
h
h
h
44.999998630,36.77517397
)
can be obtained after the 523 iterations.Example 9 (see [16, 21]).
Consider(40)
min
⁡
-
∑
i
=
1
n
‍
x
i
2
s
.
t
.
hh
∑
i
=
1
j
‍
x
i
≤
j
,
j
∈
{
1,2
,
…
,
n
}
,
hhhhhh
x
i
≥
0
,
i
∈
{
1,2
,
…
,
n
}
.
Using the proposed algorithm in this paper, initializing the parameterθ
i
=
0, i
=
0,1
,
…
,
n, the numerical results are compared with those in [16, 21] and are illustrated in Table 3.
From the numerical results for Examples1–9, our algorithm is competitive.


## 6. Concluding Remarks

In this paper, a novel optimization method based on the parametric linear programs relaxation problem is proposed for globally solving the NQCQP problem. The parametric linear programs relaxation problem is constructed by underestimating each quadratic function with a parametric linear function. By making use of the currently known upper bound and the parametric linear programs relaxation of the problem(
NQCQP
), a cutting down approach is constructed and used to enhance the computational speed of the branch and bound algorithm. The algorithm is convergent to the global optimum point by subdividing the initial hyperrectangle and solving sequences of parametric linear programs relaxation problems. Numerical experimental results are reported to demonstrate that the presented method can be employed to effectively solve the problem (
NQCQP
).



---

*Source: 698489-2014-04-27.xml*