# A New Global Optimization Algorithm for Solving a Class of Nonconvex Programming Problems

Authors: Xue-Gang Zhou; Bing-Yuan Cao
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

A new two-part parametric linearization technique is proposed globally to a class of
nonconvex programming problems (NPP). Firstly, a two-part parametric linearization method
is adopted to construct the underestimator of objective and constraint functions, by utilizing
a transformation and a parametric linear upper bounding function (LUBF) and a linear lower
bounding function (LLBF) of a natural logarithm function and an exponential function withe
as the base, respectively. Then, a sequence of relaxation lower linear programming problems, which are
embedded in a branch-and-bound algorithm, are derived in an initial nonconvex programming
problem. The proposed algorithm is converged to global optimal solution by means of a
subsequent solution to a series of linear programming problems. Finally, some examples are
given to illustrate the feasibility of the presented algorithm.


---

## Body

## 1. Introduction

In this paper, we consider a class of nonconvex programming problems as follows:(1)
(
NPP
)
{
min
⁡
f
0
(
x
)
s
.
t
.
A
x
⩽
b
,
f
j
(
x
)
⩽
e
j
,
x
∈
X
0
=
[
x
_
,
x
¯
]
⊂
R
n
,
where
(2)
f
j
(
x
)
=
∑
k
=
1
K
j
‍
f
j
k
(
x
)
=
∑
k
=
1
K
j
‍
t
j
k
∏
m
=
1
K
j
k
‍
(
c
j
k
m
T
x
+
d
j
k
m
)
α
j
k
m
,
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
j
=
0,1
,
…
,
p
,
and b
∈
R
q
,
c
j
k
m
∈
R
n
,
e
j
,
t
j
k
,
d
j
k
m
,
α
j
k
m are real numbers, A is q
×
n matrix, x
_
>
0, and x
_
,
x
¯ are finite. c
j
k
m
T
x
+
d
j
k
m
>
0 for all x
∈
X
0. (NPP) contains various variants such as a sum or product of a finite number of ratios in linear functions, generalized linear multiplicative programs, general polynomial programming, quadratic programming, and generalized geometric programming. So, (NPP) with its special form has attracted considerable attention to the literature because of its large number of practical applications in various fields of study, including transaction cost [1], financial optimization [2], robust optimization [3], VLISI chip design [4], data mining/pattern recognition [5], queueing-location problems [6, 7], bond portfolio optimization [8, 9], and elastic-plastic finite element analysis of metal forming processes [10]. From a researching point of view, (NPP) poses significant theoretical and computational challenges. It follows that it possesses multiple local optima that are not globally optimal. Recently, Jiao [11] and Shen et al. [12] have proposed a branch-and-bound algorithm globally to a class of nonconvex programming problems (NPP). By utilizing tangential hypersurfaces, convex envelope approximations of exponential function, and concave envelope approximations of logarithmic function, a two-stage linear relaxation technique was given. Then, the relaxation linear programming of original problem can be constructed with a branch-and-bound algorithm proposed for globally solving (NPP).For allj
=
0,1
,
…
,
p
,
k
=
1,2
,
…
,
K
j, if α
j
k
m
=
1, (NPP) can be reduced to the linear multiplicative programming (LMP) [15, 16]. When K
j
=
1 for any j
=
0,1
,
…
,
p, (NPP) is called multiplicative programming problems with exponent (MPE) [17, 18]; by utilizing logarithmic property, one can obtain an equivalent problem of (MPE), and a linear relaxation of equivalent problem is received by tangential hypersurfaces and concave envelope approximations. Then, a new branch-and-bound algorithm is given via solving a sequence of linear relaxations over partitioned subsets in order to find a global optimal solution to problem (MPE). If, for all j
=
0,1
,
…
,
p
,
k
=
1,2
,
…
,
K
j,  K
j
>
1 and α
j
k
m
=
1, the problem is called generalized linear multiplicative programs (GLMP) [19]. A greedy branching rule for rectangular branch-and-bound algorithms is proposed for solving problem (GLMP).Assume thatK
j
k
=
2 for all j, k, and, without loss of generality, let α
j
k
1
=
1 and α
j
k
2
=
-
1; (NPP) can be reduced to a linear sum-of-ratios fractional program. It is a global optimization problem; that is, it is known to generally possess multiple local optima that are not globally optimal [20]. Furthermore, it is NP-hard [21], and the objective function is neither quasiconvex nor quasiconcave. A number of algorithms have been proposed for globally solving a linear sum-of-ratios fractional program. They can be classified as follows: parametric simplex methods [22, 23], outer approximation methods [24, 25], the branch-and-bound approaches [13, 26–29], a duality-bounds method [30], an iteratively searching method [31], and so forth. Readers can find the applications, theory, and algorithms of the sum-of-ratios fractional programming in [32]. If there exist some α
j
k
m
<
0 and K
j
k
>
2, (NPP) is called generalized linear fractional programming problems. Shen and Wang [14] used a transformation and a two-part linearization technique to systematically convert the generalized linear fractional program into a series of linear programming problems.Whenα
j
k
m
=
1 for all j, k, and m, (NPP) can be reduced to the general polynomial programming problem earlier investigated in [33–35]. Most recently, Lasserre [36, 37] developed a class of positive semidefinite relaxations for polynomial programming with the property that any polynomial program can be approximated as closely as desired by semidefinite program of this class.In this paper, a new global optimization method is presented to (NPP) by solving a sequence of linear programming problems over partitioned subsets. By using a transformation and a two-part parametric linearization technique, we can systematically convert (NPP) into a series of linear programming problems. The solutions to these converted problems can be sufficiently closed to the global optimum of (NPP) by a successive refinement process. Some examples show that the proposed method can achieve all of the test problems in finding globally optimal solutions within a prespecified tolerance.The organization and content of this paper can be summarized as follows. In Section2, we first discuss parametric linear estimation of the natural logarithm function and the exponential function with e as the base, respectively. Then, two-part parametric linearization method is presented for generating the relaxation lower linear programming of (NPP). In Section 3, the proposed branch-and-bound algorithm in which the relaxed subproblems are embedded is described, and the convergence of the algorithm is established. Some numerical results are reported in Section 4. Finally, concluding remarks are given in Section 5.


## 2. Parametric Linear Relaxation of (NPP)

Now, we derive an equivalent form of the functionf
j
(
x
) by transformation. First, for any x
∈
X
0, since c
j
k
m
T
x
+
d
j
k
m
>
0, we assume that
(3)
c
j
k
m
T
x
+
d
j
k
m
=
exp
⁡
(
y
j
k
m
)
.Then, for allj
=
0,1
,
…
,
p, the function f
j
(
x
) can be rewritten as
(4)
f
j
(
x
)
=
f
j
(
y
j
)
=
∑
k
=
1
K
j
‍
f
j
k
(
y
j
k
)
=
∑
k
=
1
K
j
‍
t
j
k
exp
⁡
(
∑
m
=
1
K
j
k
‍
α
j
k
m
y
j
k
m
)
=
∑
k
=
1
K
j
‍
t
j
k
exp
⁡
(
Y
j
k
)
,
where
(5)
y
j
k
m
=
ln
⁡
(
c
j
k
m
T
x
+
d
j
k
m
)
,
Y
j
k
=
∑
m
=
1
K
j
k
‍
α
j
k
m
y
j
k
m
.In order to construct underestimator of functionf
j
(
x
) for all j, we adopt two-part parametric linearization method. We will firstly derive a linear upper bounding function (LUBF) and a linear lower bounding function (LLBF) of t
j
k
exp
⁡
(
Y
j
k
) about the variable y
j
k, respectively. Then, in the second part, an LUBF about primal variable x will be constructed ultimately.


### 2.1. Parametric Linear Estimation of Logarithm and Exponential Functions

We first construct parametric linear overestimation and underestimation of a natural logarithm function and an exponential function withe as the base in interval vector X
⊆
X
0, respectively.LetX
=
[
x
_
,
x
¯
]
=
{
x
∈
R
n
∣
x
_
⩽
x
⩽
x
¯
}, for
all
x
=
(
x
i
)
n
×
1, where x
_ and x
¯ are called the lower bound and upper bound, respectively. For any x
∈
X, we denote
(6)
x
(
σ
)
=
x
_
+
σ
·
(
x
¯
-
x
_
)
,
where σ
∈
{
0,1
}
n is an n-dimensional vector with components σ
i equal to 0 or 1. For convenience, we denote by 0
∈
{
0,1
}
n the vector with all components equal to 0 and by 1
∈
{
0,1
}
n the vector with all components equal to 1. Then, we have x
(
0
)
=
x
_ and x
(
1
)
=
x
¯. The following theorem illustrates how to construct the lower and upper bound linear functions of natural logarithm function and the exponential function with e as the base, respectively.Theorem 1.
For any interval vectorX, X
⊆
X
0
⊂
R
n, one assumes that the vertices of X are x
(
σ
), in form of (6). Let Φ
(
x
)
=
ln
⁡
(
∑
i
=
1
n
γ
i
x
i
+
d
) or Φ
(
x
)
=
exp
⁡
(
∑
i
=
1
n
γ
i
x
i
+
d
) and its gradient function Φ
′
(
x
)
=
(
(
∂
Φ
(
x
)
/
∂
x
1
)
,
…
,
(
∂
Φ
(
x
)
/
∂
x
n
)
)
T over X. Then there exist vectors z
_
,
z
¯
∈
R
n such that the linear functions
(7)
Φ
l
(
x
;
X
,
σ
)
∶
=
z
(
σ
)
T
·
x
+
Φ
(
x
(
σ
)
)
-
z
(
σ
)
T
·
x
(
σ
)
,
Φ
u
(
x
;
X
,
σ
)
∶
=
z
(
1
-
σ
)
T
·
x
+
Φ
(
x
(
σ
)
)
-
z
(
1
-
σ
)
T
·
x
(
σ
)
satisfy, for all x
∈
X, the inequalities
(8)
Φ
l
(
x
;
X
,
σ
)
⩽
Φ
(
x
)
⩽
Φ
u
(
x
;
X
,
σ
)
,
and moreover
(9)
Φ
l
(
x
(
σ
)
;
X
,
σ
)
=
Φ
u
(
x
(
σ
)
;
X
,
σ
)
=
Φ
(
x
(
σ
)
)
,
where z
(
σ
), in form of (6), are vertices of the interval vector z
∶
=
[
z
_
,
z
¯
], and the functions Φ
l
(
x
;
X
,
σ
),Φ
u
(
x
;
X
,
σ
) show that Φ
l, Φ
u have the argument x and depend on the two parameters X and σ.Proof.
For functionΦ
(
x
)
=
exp
⁡
(
∑
i
=
1
n
γ
i
x
i
+
d
), this result is shown in [38], and for Φ
(
x
)
=
ln
⁡
(
∑
i
=
1
n
γ
i
x
i
+
d
), the proof is similar. However, to provide a self-contained presentation, and because this result is central to this paper, we provide a direct proof for natural logarithm function.
ByX and Φ
′
(
x
) it follows that there exist vectors z
=
(
z
_
1
,
…
,
z
_
n
)
T and z
¯
=
(
z
¯
1
,
…
,
z
¯
n
)
T satisfying
(10)
z
_
⩽
Φ
′
(
x
)
⩽
z
¯
,
for
any
x
∈
X
,
where, for i
=
1,2
,
…
,
n,
(11)
z
_
i
=
min
⁡
{
γ
i
(
∑
j
=
1
n
‍
min
⁡
(
γ
j
x
_
j
,
γ
j
x
¯
j
)
+
d
)
-
1
,
γ
i
(
∑
j
=
1
n
‍
max
⁡
(
γ
j
x
_
j
,
γ
j
x
¯
j
)
+
d
)
-
1
}
,
z
¯
i
=
max
⁡
{
γ
i
(
∑
j
=
1
n
‍
min
⁡
(
γ
j
x
_
j
,
γ
j
x
¯
j
)
+
d
)
-
1
,
γ
i
(
∑
j
=
1
n
‍
max
⁡
(
γ
j
x
_
j
,
γ
j
x
¯
j
)
+
d
)
-
1
}
.
By the mean value theorem, we have, for allx
∈
X,
(12)
Φ
(
x
)
=
Φ
(
x
(
σ
)
)
+
Φ
′
(
ξ
)
T
·
(
x
-
x
(
σ
)
)
,
where ξ
=
μ
x
+
(
1
-
μ
)
x
(
σ
) for some μ
∈
[
0,1
]. Then, (6) and (10) imply that, for σ
=
0, the inequalities
(13)
∂
Φ
(
ξ
)
∂
ξ
i
⩾
z
i
(
σ
)
,
x
i
-
x
i
(
σ
)
⩾
0
,
hhhhhhhh
∀
x
∈
X
,
i
=
1,2
,
…
,
n
,
hold, where x
i
(
σ
) denotes the ith component of x
(
σ
). And for σ
=
1 the inequalities
(14)
∂
Φ
(
ξ
)
∂
ξ
i
⩽
z
i
(
σ
)
,
x
i
-
x
i
(
σ
)
⩽
0
,
hhhhhhhh
∀
x
∈
X
,
i
=
1,2
,
…
,
n
,
are valid.
Consequently, it follows from the mean value theorem that(15)
Φ
(
x
)
=
Φ
(
x
(
σ
)
)
+
∑
i
=
1
n
‍
∂
Φ
(
ξ
)
∂
ξ
i
·
(
x
i
-
x
i
(
σ
)
)
⩾
Φ
(
x
(
σ
)
)
+
∑
i
=
1
n
‍
z
i
(
σ
)
·
(
x
i
-
x
i
(
σ
)
)
=
z
(
σ
)
T
·
x
+
Φ
(
x
(
σ
)
)
-
z
(
σ
)
T
·
x
(
σ
)
.
So,Φ
l
(
x
;
X
,
σ
)
⩽
Φ
(
x
)
,
for
all
x
∈
X, and Φ
l
(
x
(
σ
)
;
X
,
σ
)
=
Φ
(
x
(
σ
)
).
Similarly, we can prove that(16)
Φ
u
(
x
;
X
,
σ
)
⩾
Φ
(
x
)
,
∀
x
∈
X
,
Φ
u
(
x
(
σ
)
;
X
,
σ
)
=
Φ
(
x
(
σ
)
)
.Now, we show how to construct a two-part parametric linearization method to systematically convert (NPP) into a series of linear programming problems by utilizing a transformation and a parametric linear upper bounding function (LUBF) and a linear lower bounding function (LLBF) of a natural logarithm function and an exponential function withe as the base, respectively.


### 2.2. First-Part Parametric Linear Relaxation

In this subsection, we discuss how to obtain the first-stage relaxation LLBF off
j
k
(
y
j
k
)
=
t
j
k
exp
⁡
(
Y
j
k
) about the variable y
j
k by using Theorem 1.LetX denote either the initial rectangle X
0 or some subrectangle of X
0 that is generated by the proposed algorithm. Without loss of generality, let X
=
{
x
∣
x
i
l
⩽
x
i
⩽
x
i
u
,
i
=
1,2
,
…
,
n
}. Denote the lower bound and the upper bound of y
j
k
m by y
j
k
m
l and y
j
k
m
u which can be derived on the presently considered rectangle X in the algorithm. For any j, k, fix a vector σ
∈
{
0,1
}
K
j
k, and for function f
j
k
(
y
j
k
)
=
exp
⁡
(
∑
m
=
1
K
j
k
‍
α
j
k
m
y
j
k
m
) and interval vector Y
j
k
=
[
y
j
k
l
,
y
j
k
u
]
⊆
R
K
j
k, calculate interval vector Z
j
k
=
[
z
j
k
l
,
z
j
k
u
] satisfying inequalities (
7
) of Theorem 1 in [38], where z
j
k
l
=
(
z
j
k
1
l
,
…
,
z
j
k
K
j
k
l
)
T,  z
j
k
u
=
(
z
j
k
1
u
,
…
,
z
j
k
K
j
k
u
)
T. That is, for any j
=
0,1
,
…
,
p
,
k
=
1
,
…
,
K
j, and any x
∈
X, we calculate the following formulas:
(17)
Y
j
k
l
=
∑
m
=
1
K
j
k
‍
min
⁡
(
α
j
k
m
y
j
k
m
l
,
α
j
k
m
y
j
k
m
u
)
,
Y
j
k
u
=
∑
m
=
1
K
j
k
‍
max
⁡
(
α
j
k
m
y
j
k
m
l
,
α
j
k
m
y
j
k
m
u
)
,
z
j
k
m
l
=
min
⁡
{
α
j
k
m
exp
⁡
(
Y
j
k
l
)
,
α
j
k
m
exp
⁡
(
Y
j
k
u
)
}
,
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
m
=
1,2
,
…
,
K
j
k
,
z
j
k
m
u
=
max
⁡
{
α
j
k
m
exp
⁡
(
Y
j
k
l
)
,
α
j
k
m
exp
⁡
(
Y
j
k
u
)
}
,
{
α
j
k
m
(
Y
j
k
l
)
,
α
j
k
m
exp
⁡
(
Y
j
k
u
)
}
m
=
1,2
,
…
,
K
j
k
.Thus, the vertices of the interval vectorsY
j
k
,
Z
j
k refer to
(18)
y
j
k
(
σ
)
=
y
j
k
l
+
∑
m
=
1
K
j
k
‍
σ
m
(
y
j
k
m
u
-
y
j
k
m
l
)
e
m
,
z
j
k
(
σ
)
=
z
j
k
l
+
∑
m
=
1
K
j
k
‍
σ
m
(
z
j
k
m
u
-
z
j
k
m
l
)
e
m
,
respectively, where e
i denotes the ith unit vector. Therefore, by Theorem 1, we can derive parametric linear lower bound functions f
j
k
l
(
y
j
k
) of f
j
k
(
y
j
k
) with respect to Y
j
k as follows:
(19)
f
j
k
l
(
y
j
k
)
=
{
t
j
k
[
z
j
k
(
σ
)
T
·
y
j
k
+
f
j
k
(
y
j
k
(
σ
)
)
-
z
j
k
(
σ
)
T
·
y
j
k
(
σ
)
]
,
if
t
j
k
>
0
,
t
j
k
[
z
j
k
(
1
-
σ
)
T
·
y
j
k
+
f
j
k
(
y
j
k
(
σ
)
)
-
z
j
k
(
1
-
σ
)
T
·
y
j
k
(
σ
)
]
,
if
t
j
k
<
0
.LetX
j
k
=
c
j
k
m
T
x
+
d
j
k
m. So, from (5), if t
j
k
>
0, the first-part LLBF of f
j
k
(
x
) denoted by f
j
k
l
(
x
) about x can get
(20)
f
j
k
l
(
x
)
=
t
j
k
[
∑
m
=
1
K
j
k
‍
z
j
k
m
(
σ
)
·
ln
⁡
(
X
j
k
)
n
(
X
j
k
)
+
f
j
k
(
y
j
k
(
σ
)
)
-
z
j
k
(
σ
)
T
·
y
j
k
(
σ
)
∑
m
=
1
K
j
k
‍
]
,
where z
j
k
m
(
σ
) denotes the mth component of z
j
k
(
σ
). And if t
j
k
<
0,
(21)
f
j
k
l
(
x
)
=
t
j
k
[
∑
m
=
1
K
j
k
‍
z
j
k
m
(
1
-
σ
)
·
ln
⁡
(
X
j
k
)
ln
⁡
(
X
j
)
+
f
j
k
(
y
j
k
(
σ
)
)
-
z
j
k
(
1
-
σ
)
T
·
y
j
k
(
σ
)
∑
m
=
1
K
j
k
‍
]
.


### 2.3. Second-Part Parametric Linear Relaxation

Now, by Theorem1, we construct the second-part LLBF of t
j
k
ln
⁡
(
X
j
k
) about the variable x. For any interval vector X
=
[
x
_
,
x
¯
]
⊆
X
0
⊂
R
n and any x
=
(
x
i
)
n
×
1
∈
X, let ϕ
j
k
m
(
x
)
=
ln
⁡
(
c
j
k
m
T
x
+
d
j
k
m
). For convenience, the following notations and functions of this paper are introduced:
(22)
X
j
k
m
l
=
∑
i
=
1
n
‍
min
⁡
(
c
j
k
m
i
x
_
i
,
c
j
k
m
i
x
¯
i
)
+
d
j
k
m
,
X
j
k
m
u
=
∑
i
=
1
n
‍
max
⁡
(
c
j
k
m
i
x
_
i
,
c
j
k
m
i
x
¯
i
)
+
d
j
k
m
,
w
_
j
k
m
i
=
min
⁡
{
c
j
k
m
i
(
X
j
k
m
l
)
-
1
,
c
j
k
m
i
(
X
j
k
m
u
)
-
1
}
,
w
¯
j
k
m
i
=
max
⁡
{
c
j
k
m
i
(
X
j
k
m
l
)
-
1
,
c
j
k
m
i
(
X
j
k
m
u
)
-
1
}
,
x
(
σ
)
=
x
_
+
∑
i
=
1
n
‍
σ
i
(
x
¯
i
-
x
_
i
)
e
i
,
w
j
k
m
(
σ
)
=
w
_
j
k
m
+
∑
i
=
1
n
‍
σ
i
(
w
¯
j
k
m
i
-
w
_
j
k
m
i
)
e
i
,
where e
i denotes the ith unit vector in R
n. Then, by Theorem 1, for any vector σ
∈
{
0,1
}
n, we define the LLBF of t
j
k
ϕ
j
k
m
(
x
) by t
j
k
ϕ
j
k
m
l
(
x
) below:
(23)
t
j
k
ϕ
j
k
m
l
(
x
)
=
{
t
j
k
[
w
j
k
m
(
σ
)
T
x
+
ϕ
j
k
m
(
x
(
σ
)
)
,
-
w
j
k
m
(
σ
)
T
x
(
σ
)
]
if
t
j
k
>
0
,
t
j
k
[
w
j
k
m
(
1
-
σ
)
T
x
+
ϕ
j
k
m
(
x
(
σ
)
)
,
-
w
j
k
m
(
1
-
σ
)
T
x
(
σ
)
]
if
t
j
k
<
0
.Then, ift
j
k
>
0, we can construct the LLBF of t
j
k
∏
m
=
1
K
j
k
(
c
j
k
m
T
x
+
d
j
k
m
)
α
j
k
m as follows:
(24)
L
F
j
k
1
(
x
)
=
t
j
k
{
∑
m
=
1
K
j
k
‍
z
j
k
m
(
σ
)
hh
×
[
w
j
k
m
(
σ
)
T
x
+
ϕ
j
k
m
(
x
(
σ
)
)
-
w
j
k
m
(
σ
)
T
x
(
σ
)
]
+
f
j
k
(
y
j
k
(
σ
)
)
-
z
j
k
(
σ
)
T
·
y
j
k
(
σ
)
∑
m
=
1
K
j
k
‍
}
=
t
j
k
∑
m
=
1
K
j
k
‍
z
j
k
m
(
σ
)
[
w
j
k
m
(
σ
)
T
x
]
+
t
j
k
[
f
j
k
(
y
j
k
(
σ
)
)
-
z
j
k
(
σ
)
T
·
y
j
k
(
σ
)
]
+
t
j
k
∑
m
=
1
K
j
k
‍
z
j
k
m
(
σ
)
[
ϕ
j
k
m
(
x
(
σ
)
)
-
w
j
k
m
(
σ
)
T
x
(
σ
)
]
.And, fort
j
k
<
0, we can get the LLBF of t
j
k
∏
m
=
1
K
j
k
(
c
j
k
m
T
x
+
d
j
k
m
)
α
j
k
m as
(25)
L
F
j
k
2
(
x
)
=
t
j
k
{
∑
m
=
1
K
j
k
‍
z
j
k
m
(
1
-
σ
)
1
hh
σ
×
[
w
j
k
m
(
1
-
σ
)
T
x
+
ϕ
j
k
m
(
x
(
σ
)
)
1
hh
σ
-
w
j
k
m
(
1
-
σ
)
T
x
(
σ
)
]
+
f
j
k
(
y
j
k
(
σ
)
)
-
z
j
k
(
1
-
σ
)
T
·
y
j
k
(
σ
)
∑
m
=
1
K
j
k
‍
}
=
t
j
k
∑
m
=
1
K
j
k
‍
z
j
k
m
(
1
-
σ
)
[
w
j
k
m
(
1
-
σ
)
T
x
]
+
t
j
k
[
f
j
k
(
y
j
k
(
σ
)
)
-
z
j
k
(
1
-
σ
)
T
·
y
j
k
(
σ
)
]
+
t
j
k
∑
m
=
1
K
j
k
‍
z
j
k
m
(
1
-
σ
)
[
ϕ
j
k
m
(
x
(
σ
)
)
.
t
j
k
∑
m
=
1
K
j
k
‍
z
j
k
m
h
h
h
[
ϕ
j
k
m
(
x
(
σ
)
)
-
w
j
k
m
(
1
-
σ
)
T
x
(
σ
)
]
.Taken together, the LLBF of functionf
j
(
x
) with respect to x can be obtained as
(26)
L
F
j
(
x
)
=
∑
t
j
k
>
0
‍
L
F
j
k
1
(
x
)
+
∑
t
j
k
<
0
‍
L
F
j
k
2
(
x
)
,
j
=
0,1
,
…
,
p
.Obviously, for allx
∈
X
⊆
X
0, j
=
0,1
,
…
,
p
,
L
F
j
(
x
)
⩽
f
j
(
x
).


### 2.4. Approximation Relaxation Linear Programming

Consequently, the approximation relaxation lower linear programming (LLP) of problem (NPP) with the parametric vectorσ in interval vector X
=
[
x
_
,
x
¯
]
⊆
X
0
⊂
R
N is easily obtained like the following:
(27)
(
LLP
)
min
⁡
L
F
0
(
x
)
s
.
t
.
A
x
⩽
b
,
L
F
j
(
x
)
⩽
e
j
,
x
∈
X
.Based on the linear underestimators, every feasible point of (NPP) is feasible in (LLP), and the objective of (LLP) is smaller than or equal to that of (NPP) for all points inX. Thus, (LLP) provides a valid lower bound for the solution of (NPP) over the partition set X. It should be noted that problem (LLP) contains only the necessary constraints to guarantee convergence of the algorithm. The following results are key to the convergence of the proposed algorithm.Lemma 2.
For allj
=
0,1
,
…
,
p
,
k
=
1,2
,
…
,
K
j
,
m
=
1,2
,
…
,
K
j
k, and X
=
[
x
_
,
x
¯
]
⊆
X
0, let
(28)
Δ
j
k
m
1
=
ϕ
j
k
m
(
x
)
-
[
w
j
k
m
(
σ
)
T
x
+
ϕ
j
k
m
(
x
(
σ
)
)
ϕ
h
h
h
j
k
m
(
x
)
-
-
w
j
k
m
(
σ
)
T
x
(
σ
)
]
,
Δ
j
k
m
2
=
[
w
j
k
m
(
1
-
σ
)
T
x
+
ϕ
j
k
m
(
x
(
σ
)
)
-
w
j
k
m
(
1
-
σ
)
T
x
(
σ
)
]
-
ϕ
j
k
m
(
x
)
.
Then one haslim
⁡
∥
x
¯
-
x
_
∥
→
0
⁡
Δ
j
k
m
1
=
lim
⁡
∥
x
¯
-
x
_
∥
→
0
⁡
Δ
j
k
m
2
→
0.Proof.
From Theorem1 and definition of function ϕ
j
k
m
(
x
), for any x
∈
X, it follows that
(29)
0
⩽
Δ
j
k
m
1
=
(
ϕ
j
k
m
′
(
ζ
)
-
w
j
k
m
(
σ
)
)
T
(
x
-
x
(
σ
)
)
,
∀
j
,
k
,
m
,
where ϕ
j
k
m
′ is a gradient function of ϕ
j
k
m,  ζ
=
μ
x
+
(
1
-
μ
x
(
σ
)
) for some μ
∈
[
0,1
], and x
(
σ
)
,
w
j
k
m
(
σ
) are vertices of the interval vectors X and W
j
k
m
:
=
[
w
_
j
k
m
,
w
¯
j
k
m
], respectively. By (6) and proof of Theorem 1, the right-hand side in inequality (29) satisfies for arbitrarily fixed σ
(30)
(
ϕ
j
k
m
′
(
ζ
)
-
w
j
k
m
(
σ
)
)
T
(
x
-
x
(
σ
)
)
⩽
∑
i
=
1
n
‍
|
∂
ϕ
j
k
m
(
ζ
)
∂
ζ
i
-
w
j
k
m
i
(
σ
)
|
·
|
x
i
-
x
i
(
σ
)
|
⩽
∑
i
=
1
n
‍
|
w
j
k
m
i
(
0
)
-
w
j
k
m
i
(
1
)
|
·
|
x
i
-
x
i
(
σ
)
|
=
∑
i
=
1
n
‍
|
w
¯
j
k
m
i
-
w
_
j
k
m
i
|
·
|
x
i
-
x
i
(
σ
)
|
=
∑
i
=
1
n
‍
|
c
j
k
m
i
|
·
|
(
X
j
k
m
l
)
-
1
-
(
X
j
k
m
u
)
-
1
|
·
|
x
i
-
x
i
(
σ
)
|
=
∑
i
=
1
n
‍
|
c
j
k
m
i
|
·
|
x
i
-
x
i
(
σ
)
|
·
(
κ
j
k
m
)
-
1
·
|
X
j
k
m
u
-
X
j
k
m
l
|
⩽
∑
i
=
1
n
‍
|
c
j
k
m
i
|
·
|
x
_
i
-
x
¯
i
|
·
(
κ
j
k
m
)
-
1
·
|
X
j
k
m
u
-
X
j
k
m
l
|
=
(
κ
j
k
m
)
-
1
(
∑
i
=
1
n
‍
|
c
j
k
m
i
|
·
|
x
_
i
-
x
¯
i
|
)
2
⩽
(
κ
j
k
m
)
-
1
(
∑
i
=
1
n
‍
|
c
j
k
m
i
|
)
2
·
∥
x
¯
-
x
_
∥
,
where κ
j
k
m
=
μ
X
j
k
m
l
+
(
1
-
μ
)
X
j
k
m
u for some μ
∈
[
0,1
]. It shows that
(31)
lim
⁡
∥
x
¯
-
x
_
∥
→
0
Δ
j
k
m
1
⟶
0
.
Similarly, we can prove thatlim
⁡
∥
x
¯
-
x
_
∥
→
0
⁡
Δ
j
k
m
2
→
0.Similarly, we have Lemma3 (also see Lemma 1 in [38]).Lemma 3.
For allj
,
k
,
Y
j
k
=
[
y
j
k
l
,
y
j
k
u
]
⊆
R
K
j
k, let
(32)
Δ
j
k
3
=
exp
⁡
(
∑
m
=
1
K
j
k
‍
α
j
k
m
y
j
k
m
)
-
[
z
j
k
(
σ
)
T
·
y
j
k
+
f
j
k
(
y
j
k
(
σ
)
)
[
z
j
k
(
σ
)
T
·
y
j
k
+
f
j
k
(
y
j
k
(
σ
)
)
-
z
j
k
(
σ
)
T
·
y
j
k
(
σ
)
]
,
Δ
j
k
4
=
z
j
k
(
1
-
σ
)
T
·
y
j
k
+
f
j
k
(
y
j
k
(
σ
)
)
-
z
j
k
(
1
-
σ
)
T
·
y
j
k
(
σ
)
-
exp
⁡
(
∑
m
=
1
K
j
k
‍
α
j
k
m
y
j
k
m
)
.
Thenlim
⁡
∥
y
jk
u
-
y
jk
l
∥
→
0
⁡
Δ
j
k
3
=
lim
⁡
∥
y
jk
u
-
y
jk
l
∥
→
0
⁡
Δ
j
k
4
→
0.Theorem 4.
For anyj
,
k
,
m, let δ
j
k
=
y
j
k
u
-
y
j
k
l
,
X
=
[
x
_
,
x
¯
]
⊆
X
0
,
and
Y
j
k
=
[
y
j
k
l
,
y
j
k
u
]
⊆
R
K
j
k. Then, when ∥
x
¯
-
x
_
∥
→
0, for any x
∈
X, the difference of L
F
j
(
x
) and f
j
(
x
) satisfies f
j
(
x
)
-
L
F
j
(
x
)
→
0.Proof.
Firstly, notice that∥
y
j
k
u
-
y
j
k
l
∥
→
0 when ∥
x
¯
-
x
_
∥
→
0. Then, for any x
∈
X, and for any j, let
(33)
Δ
=
f
j
(
x
)
-
L
F
j
(
x
)
=
∑
t
j
k
>
0
‍
(
f
j
(
x
)
-
L
F
j
1
(
x
)
)
+
∑
t
j
k
<
0
‍
(
f
j
(
x
)
-
L
F
j
2
(
x
)
)
,
and let Δ
j
k
1
=
f
j
(
x
)
-
L
F
j
1
(
x
) and Δ
j
k
2
=
f
j
(
x
)
-
L
F
j
2
(
x
). Therefore, we only need to prove Δ
j
k
1
→
0
,
Δ
j
k
2
→
0 as ∥
x
¯
-
x
_
∥
→
0.
We first proveΔ
j
k
1
→
0. Since
(34)
Δ
j
k
1
=
(
f
j
(
x
)
-
f
j
k
l
(
x
)
)
+
(
f
j
k
l
(
x
)
-
L
F
j
k
1
(
x
)
)
=
Δ
j
k
1
1
+
Δ
j
k
2
1
,
it is obvious that we only need to prove Δ
j
k
1
1
→
0
and
Δ
j
k
2
1
→
0. We first consider the difference Δ
j
k
1
1. By the definition of L
F
j
k
1
(
x
)
,
f
j
k
l
(
x
), it follows that
(35)
Δ
j
k
1
1
=
f
j
(
x
)
-
f
j
k
l
(
x
)
=
t
j
k
[
∏
m
=
1
K
j
k
‍
(
c
j
k
m
T
x
+
d
j
k
m
)
α
j
k
m
-
z
j
k
(
σ
)
T
·
y
j
k
z
j
k
(
h
h
h
σ
)
T
-
f
j
k
(
y
j
k
(
σ
)
)
+
z
j
k
(
σ
)
T
·
y
j
k
(
σ
)
∏
m
=
1
K
j
k
‍
]
=
t
j
k
[
exp
⁡
(
∑
m
=
1
K
j
k
‍
α
j
k
m
y
j
k
m
)
-
z
j
k
(
σ
)
T
·
y
j
k
z
j
(
h
h
h
σ
)
-
f
j
k
(
y
j
k
(
σ
)
)
+
z
j
k
(
σ
)
T
·
y
j
k
(
σ
)
∑
m
=
1
K
j
k
‍
]
=
t
j
k
Δ
j
k
3
,
where X
j
k
=
c
j
k
m
T
+
d
j
k
m. Then, by Lemma 2, Δ
j
k
1
1
→
0 as ∥
x
¯
-
x
_
∥
→
0.
Now, the differenceΔ
j
k
2
1
=
f
j
k
l
(
x
)
-
L
F
j
k
1
(
x
) is considered. From the definition of f
j
k
l
(
x
), L
F
j
k
1
(
x
), we can obtain
(36)
Δ
j
k
2
1
=
f
j
k
l
(
x
)
-
L
F
j
k
1
(
x
)
=
t
j
k
∑
m
=
1
K
j
k
‍
z
j
k
m
(
σ
)
[
ln
⁡
(
X
j
k
)
-
w
j
k
m
(
σ
)
T
x
∑
m
=
1
K
j
k
‍
h
[
-
w
j
k
m
(
σ
)
T
x
-
ϕ
j
k
m
(
x
(
σ
)
)
+
w
j
k
m
(
σ
)
T
x
(
σ
)
]
=
t
j
k
∑
m
=
1
K
j
k
‍
z
j
k
m
(
σ
)
·
Δ
j
k
m
1
.
Then, by Lemma3, Δ
j
k
2
1
→
0 as ∥
x
¯
-
x
_
∥
→
0. Therefore, when ∥
x
¯
-
x
_
∥
→
0, we can get
(37)
Δ
j
k
1
=
f
j
(
x
)
-
L
F
j
1
(
x
)
=
Δ
j
k
1
1
+
Δ
j
k
2
1
⟶
0
.
By similar discussion as above, we can get(38)
Δ
j
k
2
=
f
j
(
x
)
-
L
F
j
2
(
x
)
⟶
0
,
as
∥
x
¯
-
x
_
∥
⟶
0
.
It follows from (37) and (38) that f
j
(
x
)
-
L
F
j
(
x
)
→
0 when ∥
x
¯
-
x
_
∥
→
0.Theorem4 shows that as the subhyperrectangle X
⊆
X
0 is small enough, the solution to (LLP)(X) is sufficiently approaching the solution of (NPP)(X) and this guarantees the global convergence of the method.


## 2.1. Parametric Linear Estimation of Logarithm and Exponential Functions

We first construct parametric linear overestimation and underestimation of a natural logarithm function and an exponential function withe as the base in interval vector X
⊆
X
0, respectively.LetX
=
[
x
_
,
x
¯
]
=
{
x
∈
R
n
∣
x
_
⩽
x
⩽
x
¯
}, for
all
x
=
(
x
i
)
n
×
1, where x
_ and x
¯ are called the lower bound and upper bound, respectively. For any x
∈
X, we denote
(6)
x
(
σ
)
=
x
_
+
σ
·
(
x
¯
-
x
_
)
,
where σ
∈
{
0,1
}
n is an n-dimensional vector with components σ
i equal to 0 or 1. For convenience, we denote by 0
∈
{
0,1
}
n the vector with all components equal to 0 and by 1
∈
{
0,1
}
n the vector with all components equal to 1. Then, we have x
(
0
)
=
x
_ and x
(
1
)
=
x
¯. The following theorem illustrates how to construct the lower and upper bound linear functions of natural logarithm function and the exponential function with e as the base, respectively.Theorem 1.
For any interval vectorX, X
⊆
X
0
⊂
R
n, one assumes that the vertices of X are x
(
σ
), in form of (6). Let Φ
(
x
)
=
ln
⁡
(
∑
i
=
1
n
γ
i
x
i
+
d
) or Φ
(
x
)
=
exp
⁡
(
∑
i
=
1
n
γ
i
x
i
+
d
) and its gradient function Φ
′
(
x
)
=
(
(
∂
Φ
(
x
)
/
∂
x
1
)
,
…
,
(
∂
Φ
(
x
)
/
∂
x
n
)
)
T over X. Then there exist vectors z
_
,
z
¯
∈
R
n such that the linear functions
(7)
Φ
l
(
x
;
X
,
σ
)
∶
=
z
(
σ
)
T
·
x
+
Φ
(
x
(
σ
)
)
-
z
(
σ
)
T
·
x
(
σ
)
,
Φ
u
(
x
;
X
,
σ
)
∶
=
z
(
1
-
σ
)
T
·
x
+
Φ
(
x
(
σ
)
)
-
z
(
1
-
σ
)
T
·
x
(
σ
)
satisfy, for all x
∈
X, the inequalities
(8)
Φ
l
(
x
;
X
,
σ
)
⩽
Φ
(
x
)
⩽
Φ
u
(
x
;
X
,
σ
)
,
and moreover
(9)
Φ
l
(
x
(
σ
)
;
X
,
σ
)
=
Φ
u
(
x
(
σ
)
;
X
,
σ
)
=
Φ
(
x
(
σ
)
)
,
where z
(
σ
), in form of (6), are vertices of the interval vector z
∶
=
[
z
_
,
z
¯
], and the functions Φ
l
(
x
;
X
,
σ
),Φ
u
(
x
;
X
,
σ
) show that Φ
l, Φ
u have the argument x and depend on the two parameters X and σ.Proof.
For functionΦ
(
x
)
=
exp
⁡
(
∑
i
=
1
n
γ
i
x
i
+
d
), this result is shown in [38], and for Φ
(
x
)
=
ln
⁡
(
∑
i
=
1
n
γ
i
x
i
+
d
), the proof is similar. However, to provide a self-contained presentation, and because this result is central to this paper, we provide a direct proof for natural logarithm function.
ByX and Φ
′
(
x
) it follows that there exist vectors z
=
(
z
_
1
,
…
,
z
_
n
)
T and z
¯
=
(
z
¯
1
,
…
,
z
¯
n
)
T satisfying
(10)
z
_
⩽
Φ
′
(
x
)
⩽
z
¯
,
for
any
x
∈
X
,
where, for i
=
1,2
,
…
,
n,
(11)
z
_
i
=
min
⁡
{
γ
i
(
∑
j
=
1
n
‍
min
⁡
(
γ
j
x
_
j
,
γ
j
x
¯
j
)
+
d
)
-
1
,
γ
i
(
∑
j
=
1
n
‍
max
⁡
(
γ
j
x
_
j
,
γ
j
x
¯
j
)
+
d
)
-
1
}
,
z
¯
i
=
max
⁡
{
γ
i
(
∑
j
=
1
n
‍
min
⁡
(
γ
j
x
_
j
,
γ
j
x
¯
j
)
+
d
)
-
1
,
γ
i
(
∑
j
=
1
n
‍
max
⁡
(
γ
j
x
_
j
,
γ
j
x
¯
j
)
+
d
)
-
1
}
.
By the mean value theorem, we have, for allx
∈
X,
(12)
Φ
(
x
)
=
Φ
(
x
(
σ
)
)
+
Φ
′
(
ξ
)
T
·
(
x
-
x
(
σ
)
)
,
where ξ
=
μ
x
+
(
1
-
μ
)
x
(
σ
) for some μ
∈
[
0,1
]. Then, (6) and (10) imply that, for σ
=
0, the inequalities
(13)
∂
Φ
(
ξ
)
∂
ξ
i
⩾
z
i
(
σ
)
,
x
i
-
x
i
(
σ
)
⩾
0
,
hhhhhhhh
∀
x
∈
X
,
i
=
1,2
,
…
,
n
,
hold, where x
i
(
σ
) denotes the ith component of x
(
σ
). And for σ
=
1 the inequalities
(14)
∂
Φ
(
ξ
)
∂
ξ
i
⩽
z
i
(
σ
)
,
x
i
-
x
i
(
σ
)
⩽
0
,
hhhhhhhh
∀
x
∈
X
,
i
=
1,2
,
…
,
n
,
are valid.
Consequently, it follows from the mean value theorem that(15)
Φ
(
x
)
=
Φ
(
x
(
σ
)
)
+
∑
i
=
1
n
‍
∂
Φ
(
ξ
)
∂
ξ
i
·
(
x
i
-
x
i
(
σ
)
)
⩾
Φ
(
x
(
σ
)
)
+
∑
i
=
1
n
‍
z
i
(
σ
)
·
(
x
i
-
x
i
(
σ
)
)
=
z
(
σ
)
T
·
x
+
Φ
(
x
(
σ
)
)
-
z
(
σ
)
T
·
x
(
σ
)
.
So,Φ
l
(
x
;
X
,
σ
)
⩽
Φ
(
x
)
,
for
all
x
∈
X, and Φ
l
(
x
(
σ
)
;
X
,
σ
)
=
Φ
(
x
(
σ
)
).
Similarly, we can prove that(16)
Φ
u
(
x
;
X
,
σ
)
⩾
Φ
(
x
)
,
∀
x
∈
X
,
Φ
u
(
x
(
σ
)
;
X
,
σ
)
=
Φ
(
x
(
σ
)
)
.Now, we show how to construct a two-part parametric linearization method to systematically convert (NPP) into a series of linear programming problems by utilizing a transformation and a parametric linear upper bounding function (LUBF) and a linear lower bounding function (LLBF) of a natural logarithm function and an exponential function withe as the base, respectively.


## 2.2. First-Part Parametric Linear Relaxation

In this subsection, we discuss how to obtain the first-stage relaxation LLBF off
j
k
(
y
j
k
)
=
t
j
k
exp
⁡
(
Y
j
k
) about the variable y
j
k by using Theorem 1.LetX denote either the initial rectangle X
0 or some subrectangle of X
0 that is generated by the proposed algorithm. Without loss of generality, let X
=
{
x
∣
x
i
l
⩽
x
i
⩽
x
i
u
,
i
=
1,2
,
…
,
n
}. Denote the lower bound and the upper bound of y
j
k
m by y
j
k
m
l and y
j
k
m
u which can be derived on the presently considered rectangle X in the algorithm. For any j, k, fix a vector σ
∈
{
0,1
}
K
j
k, and for function f
j
k
(
y
j
k
)
=
exp
⁡
(
∑
m
=
1
K
j
k
‍
α
j
k
m
y
j
k
m
) and interval vector Y
j
k
=
[
y
j
k
l
,
y
j
k
u
]
⊆
R
K
j
k, calculate interval vector Z
j
k
=
[
z
j
k
l
,
z
j
k
u
] satisfying inequalities (
7
) of Theorem 1 in [38], where z
j
k
l
=
(
z
j
k
1
l
,
…
,
z
j
k
K
j
k
l
)
T,  z
j
k
u
=
(
z
j
k
1
u
,
…
,
z
j
k
K
j
k
u
)
T. That is, for any j
=
0,1
,
…
,
p
,
k
=
1
,
…
,
K
j, and any x
∈
X, we calculate the following formulas:
(17)
Y
j
k
l
=
∑
m
=
1
K
j
k
‍
min
⁡
(
α
j
k
m
y
j
k
m
l
,
α
j
k
m
y
j
k
m
u
)
,
Y
j
k
u
=
∑
m
=
1
K
j
k
‍
max
⁡
(
α
j
k
m
y
j
k
m
l
,
α
j
k
m
y
j
k
m
u
)
,
z
j
k
m
l
=
min
⁡
{
α
j
k
m
exp
⁡
(
Y
j
k
l
)
,
α
j
k
m
exp
⁡
(
Y
j
k
u
)
}
,
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
m
=
1,2
,
…
,
K
j
k
,
z
j
k
m
u
=
max
⁡
{
α
j
k
m
exp
⁡
(
Y
j
k
l
)
,
α
j
k
m
exp
⁡
(
Y
j
k
u
)
}
,
{
α
j
k
m
(
Y
j
k
l
)
,
α
j
k
m
exp
⁡
(
Y
j
k
u
)
}
m
=
1,2
,
…
,
K
j
k
.Thus, the vertices of the interval vectorsY
j
k
,
Z
j
k refer to
(18)
y
j
k
(
σ
)
=
y
j
k
l
+
∑
m
=
1
K
j
k
‍
σ
m
(
y
j
k
m
u
-
y
j
k
m
l
)
e
m
,
z
j
k
(
σ
)
=
z
j
k
l
+
∑
m
=
1
K
j
k
‍
σ
m
(
z
j
k
m
u
-
z
j
k
m
l
)
e
m
,
respectively, where e
i denotes the ith unit vector. Therefore, by Theorem 1, we can derive parametric linear lower bound functions f
j
k
l
(
y
j
k
) of f
j
k
(
y
j
k
) with respect to Y
j
k as follows:
(19)
f
j
k
l
(
y
j
k
)
=
{
t
j
k
[
z
j
k
(
σ
)
T
·
y
j
k
+
f
j
k
(
y
j
k
(
σ
)
)
-
z
j
k
(
σ
)
T
·
y
j
k
(
σ
)
]
,
if
t
j
k
>
0
,
t
j
k
[
z
j
k
(
1
-
σ
)
T
·
y
j
k
+
f
j
k
(
y
j
k
(
σ
)
)
-
z
j
k
(
1
-
σ
)
T
·
y
j
k
(
σ
)
]
,
if
t
j
k
<
0
.LetX
j
k
=
c
j
k
m
T
x
+
d
j
k
m. So, from (5), if t
j
k
>
0, the first-part LLBF of f
j
k
(
x
) denoted by f
j
k
l
(
x
) about x can get
(20)
f
j
k
l
(
x
)
=
t
j
k
[
∑
m
=
1
K
j
k
‍
z
j
k
m
(
σ
)
·
ln
⁡
(
X
j
k
)
n
(
X
j
k
)
+
f
j
k
(
y
j
k
(
σ
)
)
-
z
j
k
(
σ
)
T
·
y
j
k
(
σ
)
∑
m
=
1
K
j
k
‍
]
,
where z
j
k
m
(
σ
) denotes the mth component of z
j
k
(
σ
). And if t
j
k
<
0,
(21)
f
j
k
l
(
x
)
=
t
j
k
[
∑
m
=
1
K
j
k
‍
z
j
k
m
(
1
-
σ
)
·
ln
⁡
(
X
j
k
)
ln
⁡
(
X
j
)
+
f
j
k
(
y
j
k
(
σ
)
)
-
z
j
k
(
1
-
σ
)
T
·
y
j
k
(
σ
)
∑
m
=
1
K
j
k
‍
]
.


## 2.3. Second-Part Parametric Linear Relaxation

Now, by Theorem1, we construct the second-part LLBF of t
j
k
ln
⁡
(
X
j
k
) about the variable x. For any interval vector X
=
[
x
_
,
x
¯
]
⊆
X
0
⊂
R
n and any x
=
(
x
i
)
n
×
1
∈
X, let ϕ
j
k
m
(
x
)
=
ln
⁡
(
c
j
k
m
T
x
+
d
j
k
m
). For convenience, the following notations and functions of this paper are introduced:
(22)
X
j
k
m
l
=
∑
i
=
1
n
‍
min
⁡
(
c
j
k
m
i
x
_
i
,
c
j
k
m
i
x
¯
i
)
+
d
j
k
m
,
X
j
k
m
u
=
∑
i
=
1
n
‍
max
⁡
(
c
j
k
m
i
x
_
i
,
c
j
k
m
i
x
¯
i
)
+
d
j
k
m
,
w
_
j
k
m
i
=
min
⁡
{
c
j
k
m
i
(
X
j
k
m
l
)
-
1
,
c
j
k
m
i
(
X
j
k
m
u
)
-
1
}
,
w
¯
j
k
m
i
=
max
⁡
{
c
j
k
m
i
(
X
j
k
m
l
)
-
1
,
c
j
k
m
i
(
X
j
k
m
u
)
-
1
}
,
x
(
σ
)
=
x
_
+
∑
i
=
1
n
‍
σ
i
(
x
¯
i
-
x
_
i
)
e
i
,
w
j
k
m
(
σ
)
=
w
_
j
k
m
+
∑
i
=
1
n
‍
σ
i
(
w
¯
j
k
m
i
-
w
_
j
k
m
i
)
e
i
,
where e
i denotes the ith unit vector in R
n. Then, by Theorem 1, for any vector σ
∈
{
0,1
}
n, we define the LLBF of t
j
k
ϕ
j
k
m
(
x
) by t
j
k
ϕ
j
k
m
l
(
x
) below:
(23)
t
j
k
ϕ
j
k
m
l
(
x
)
=
{
t
j
k
[
w
j
k
m
(
σ
)
T
x
+
ϕ
j
k
m
(
x
(
σ
)
)
,
-
w
j
k
m
(
σ
)
T
x
(
σ
)
]
if
t
j
k
>
0
,
t
j
k
[
w
j
k
m
(
1
-
σ
)
T
x
+
ϕ
j
k
m
(
x
(
σ
)
)
,
-
w
j
k
m
(
1
-
σ
)
T
x
(
σ
)
]
if
t
j
k
<
0
.Then, ift
j
k
>
0, we can construct the LLBF of t
j
k
∏
m
=
1
K
j
k
(
c
j
k
m
T
x
+
d
j
k
m
)
α
j
k
m as follows:
(24)
L
F
j
k
1
(
x
)
=
t
j
k
{
∑
m
=
1
K
j
k
‍
z
j
k
m
(
σ
)
hh
×
[
w
j
k
m
(
σ
)
T
x
+
ϕ
j
k
m
(
x
(
σ
)
)
-
w
j
k
m
(
σ
)
T
x
(
σ
)
]
+
f
j
k
(
y
j
k
(
σ
)
)
-
z
j
k
(
σ
)
T
·
y
j
k
(
σ
)
∑
m
=
1
K
j
k
‍
}
=
t
j
k
∑
m
=
1
K
j
k
‍
z
j
k
m
(
σ
)
[
w
j
k
m
(
σ
)
T
x
]
+
t
j
k
[
f
j
k
(
y
j
k
(
σ
)
)
-
z
j
k
(
σ
)
T
·
y
j
k
(
σ
)
]
+
t
j
k
∑
m
=
1
K
j
k
‍
z
j
k
m
(
σ
)
[
ϕ
j
k
m
(
x
(
σ
)
)
-
w
j
k
m
(
σ
)
T
x
(
σ
)
]
.And, fort
j
k
<
0, we can get the LLBF of t
j
k
∏
m
=
1
K
j
k
(
c
j
k
m
T
x
+
d
j
k
m
)
α
j
k
m as
(25)
L
F
j
k
2
(
x
)
=
t
j
k
{
∑
m
=
1
K
j
k
‍
z
j
k
m
(
1
-
σ
)
1
hh
σ
×
[
w
j
k
m
(
1
-
σ
)
T
x
+
ϕ
j
k
m
(
x
(
σ
)
)
1
hh
σ
-
w
j
k
m
(
1
-
σ
)
T
x
(
σ
)
]
+
f
j
k
(
y
j
k
(
σ
)
)
-
z
j
k
(
1
-
σ
)
T
·
y
j
k
(
σ
)
∑
m
=
1
K
j
k
‍
}
=
t
j
k
∑
m
=
1
K
j
k
‍
z
j
k
m
(
1
-
σ
)
[
w
j
k
m
(
1
-
σ
)
T
x
]
+
t
j
k
[
f
j
k
(
y
j
k
(
σ
)
)
-
z
j
k
(
1
-
σ
)
T
·
y
j
k
(
σ
)
]
+
t
j
k
∑
m
=
1
K
j
k
‍
z
j
k
m
(
1
-
σ
)
[
ϕ
j
k
m
(
x
(
σ
)
)
.
t
j
k
∑
m
=
1
K
j
k
‍
z
j
k
m
h
h
h
[
ϕ
j
k
m
(
x
(
σ
)
)
-
w
j
k
m
(
1
-
σ
)
T
x
(
σ
)
]
.Taken together, the LLBF of functionf
j
(
x
) with respect to x can be obtained as
(26)
L
F
j
(
x
)
=
∑
t
j
k
>
0
‍
L
F
j
k
1
(
x
)
+
∑
t
j
k
<
0
‍
L
F
j
k
2
(
x
)
,
j
=
0,1
,
…
,
p
.Obviously, for allx
∈
X
⊆
X
0, j
=
0,1
,
…
,
p
,
L
F
j
(
x
)
⩽
f
j
(
x
).


## 2.4. Approximation Relaxation Linear Programming

Consequently, the approximation relaxation lower linear programming (LLP) of problem (NPP) with the parametric vectorσ in interval vector X
=
[
x
_
,
x
¯
]
⊆
X
0
⊂
R
N is easily obtained like the following:
(27)
(
LLP
)
min
⁡
L
F
0
(
x
)
s
.
t
.
A
x
⩽
b
,
L
F
j
(
x
)
⩽
e
j
,
x
∈
X
.Based on the linear underestimators, every feasible point of (NPP) is feasible in (LLP), and the objective of (LLP) is smaller than or equal to that of (NPP) for all points inX. Thus, (LLP) provides a valid lower bound for the solution of (NPP) over the partition set X. It should be noted that problem (LLP) contains only the necessary constraints to guarantee convergence of the algorithm. The following results are key to the convergence of the proposed algorithm.Lemma 2.
For allj
=
0,1
,
…
,
p
,
k
=
1,2
,
…
,
K
j
,
m
=
1,2
,
…
,
K
j
k, and X
=
[
x
_
,
x
¯
]
⊆
X
0, let
(28)
Δ
j
k
m
1
=
ϕ
j
k
m
(
x
)
-
[
w
j
k
m
(
σ
)
T
x
+
ϕ
j
k
m
(
x
(
σ
)
)
ϕ
h
h
h
j
k
m
(
x
)
-
-
w
j
k
m
(
σ
)
T
x
(
σ
)
]
,
Δ
j
k
m
2
=
[
w
j
k
m
(
1
-
σ
)
T
x
+
ϕ
j
k
m
(
x
(
σ
)
)
-
w
j
k
m
(
1
-
σ
)
T
x
(
σ
)
]
-
ϕ
j
k
m
(
x
)
.
Then one haslim
⁡
∥
x
¯
-
x
_
∥
→
0
⁡
Δ
j
k
m
1
=
lim
⁡
∥
x
¯
-
x
_
∥
→
0
⁡
Δ
j
k
m
2
→
0.Proof.
From Theorem1 and definition of function ϕ
j
k
m
(
x
), for any x
∈
X, it follows that
(29)
0
⩽
Δ
j
k
m
1
=
(
ϕ
j
k
m
′
(
ζ
)
-
w
j
k
m
(
σ
)
)
T
(
x
-
x
(
σ
)
)
,
∀
j
,
k
,
m
,
where ϕ
j
k
m
′ is a gradient function of ϕ
j
k
m,  ζ
=
μ
x
+
(
1
-
μ
x
(
σ
)
) for some μ
∈
[
0,1
], and x
(
σ
)
,
w
j
k
m
(
σ
) are vertices of the interval vectors X and W
j
k
m
:
=
[
w
_
j
k
m
,
w
¯
j
k
m
], respectively. By (6) and proof of Theorem 1, the right-hand side in inequality (29) satisfies for arbitrarily fixed σ
(30)
(
ϕ
j
k
m
′
(
ζ
)
-
w
j
k
m
(
σ
)
)
T
(
x
-
x
(
σ
)
)
⩽
∑
i
=
1
n
‍
|
∂
ϕ
j
k
m
(
ζ
)
∂
ζ
i
-
w
j
k
m
i
(
σ
)
|
·
|
x
i
-
x
i
(
σ
)
|
⩽
∑
i
=
1
n
‍
|
w
j
k
m
i
(
0
)
-
w
j
k
m
i
(
1
)
|
·
|
x
i
-
x
i
(
σ
)
|
=
∑
i
=
1
n
‍
|
w
¯
j
k
m
i
-
w
_
j
k
m
i
|
·
|
x
i
-
x
i
(
σ
)
|
=
∑
i
=
1
n
‍
|
c
j
k
m
i
|
·
|
(
X
j
k
m
l
)
-
1
-
(
X
j
k
m
u
)
-
1
|
·
|
x
i
-
x
i
(
σ
)
|
=
∑
i
=
1
n
‍
|
c
j
k
m
i
|
·
|
x
i
-
x
i
(
σ
)
|
·
(
κ
j
k
m
)
-
1
·
|
X
j
k
m
u
-
X
j
k
m
l
|
⩽
∑
i
=
1
n
‍
|
c
j
k
m
i
|
·
|
x
_
i
-
x
¯
i
|
·
(
κ
j
k
m
)
-
1
·
|
X
j
k
m
u
-
X
j
k
m
l
|
=
(
κ
j
k
m
)
-
1
(
∑
i
=
1
n
‍
|
c
j
k
m
i
|
·
|
x
_
i
-
x
¯
i
|
)
2
⩽
(
κ
j
k
m
)
-
1
(
∑
i
=
1
n
‍
|
c
j
k
m
i
|
)
2
·
∥
x
¯
-
x
_
∥
,
where κ
j
k
m
=
μ
X
j
k
m
l
+
(
1
-
μ
)
X
j
k
m
u for some μ
∈
[
0,1
]. It shows that
(31)
lim
⁡
∥
x
¯
-
x
_
∥
→
0
Δ
j
k
m
1
⟶
0
.
Similarly, we can prove thatlim
⁡
∥
x
¯
-
x
_
∥
→
0
⁡
Δ
j
k
m
2
→
0.Similarly, we have Lemma3 (also see Lemma 1 in [38]).Lemma 3.
For allj
,
k
,
Y
j
k
=
[
y
j
k
l
,
y
j
k
u
]
⊆
R
K
j
k, let
(32)
Δ
j
k
3
=
exp
⁡
(
∑
m
=
1
K
j
k
‍
α
j
k
m
y
j
k
m
)
-
[
z
j
k
(
σ
)
T
·
y
j
k
+
f
j
k
(
y
j
k
(
σ
)
)
[
z
j
k
(
σ
)
T
·
y
j
k
+
f
j
k
(
y
j
k
(
σ
)
)
-
z
j
k
(
σ
)
T
·
y
j
k
(
σ
)
]
,
Δ
j
k
4
=
z
j
k
(
1
-
σ
)
T
·
y
j
k
+
f
j
k
(
y
j
k
(
σ
)
)
-
z
j
k
(
1
-
σ
)
T
·
y
j
k
(
σ
)
-
exp
⁡
(
∑
m
=
1
K
j
k
‍
α
j
k
m
y
j
k
m
)
.
Thenlim
⁡
∥
y
jk
u
-
y
jk
l
∥
→
0
⁡
Δ
j
k
3
=
lim
⁡
∥
y
jk
u
-
y
jk
l
∥
→
0
⁡
Δ
j
k
4
→
0.Theorem 4.
For anyj
,
k
,
m, let δ
j
k
=
y
j
k
u
-
y
j
k
l
,
X
=
[
x
_
,
x
¯
]
⊆
X
0
,
and
Y
j
k
=
[
y
j
k
l
,
y
j
k
u
]
⊆
R
K
j
k. Then, when ∥
x
¯
-
x
_
∥
→
0, for any x
∈
X, the difference of L
F
j
(
x
) and f
j
(
x
) satisfies f
j
(
x
)
-
L
F
j
(
x
)
→
0.Proof.
Firstly, notice that∥
y
j
k
u
-
y
j
k
l
∥
→
0 when ∥
x
¯
-
x
_
∥
→
0. Then, for any x
∈
X, and for any j, let
(33)
Δ
=
f
j
(
x
)
-
L
F
j
(
x
)
=
∑
t
j
k
>
0
‍
(
f
j
(
x
)
-
L
F
j
1
(
x
)
)
+
∑
t
j
k
<
0
‍
(
f
j
(
x
)
-
L
F
j
2
(
x
)
)
,
and let Δ
j
k
1
=
f
j
(
x
)
-
L
F
j
1
(
x
) and Δ
j
k
2
=
f
j
(
x
)
-
L
F
j
2
(
x
). Therefore, we only need to prove Δ
j
k
1
→
0
,
Δ
j
k
2
→
0 as ∥
x
¯
-
x
_
∥
→
0.
We first proveΔ
j
k
1
→
0. Since
(34)
Δ
j
k
1
=
(
f
j
(
x
)
-
f
j
k
l
(
x
)
)
+
(
f
j
k
l
(
x
)
-
L
F
j
k
1
(
x
)
)
=
Δ
j
k
1
1
+
Δ
j
k
2
1
,
it is obvious that we only need to prove Δ
j
k
1
1
→
0
and
Δ
j
k
2
1
→
0. We first consider the difference Δ
j
k
1
1. By the definition of L
F
j
k
1
(
x
)
,
f
j
k
l
(
x
), it follows that
(35)
Δ
j
k
1
1
=
f
j
(
x
)
-
f
j
k
l
(
x
)
=
t
j
k
[
∏
m
=
1
K
j
k
‍
(
c
j
k
m
T
x
+
d
j
k
m
)
α
j
k
m
-
z
j
k
(
σ
)
T
·
y
j
k
z
j
k
(
h
h
h
σ
)
T
-
f
j
k
(
y
j
k
(
σ
)
)
+
z
j
k
(
σ
)
T
·
y
j
k
(
σ
)
∏
m
=
1
K
j
k
‍
]
=
t
j
k
[
exp
⁡
(
∑
m
=
1
K
j
k
‍
α
j
k
m
y
j
k
m
)
-
z
j
k
(
σ
)
T
·
y
j
k
z
j
(
h
h
h
σ
)
-
f
j
k
(
y
j
k
(
σ
)
)
+
z
j
k
(
σ
)
T
·
y
j
k
(
σ
)
∑
m
=
1
K
j
k
‍
]
=
t
j
k
Δ
j
k
3
,
where X
j
k
=
c
j
k
m
T
+
d
j
k
m. Then, by Lemma 2, Δ
j
k
1
1
→
0 as ∥
x
¯
-
x
_
∥
→
0.
Now, the differenceΔ
j
k
2
1
=
f
j
k
l
(
x
)
-
L
F
j
k
1
(
x
) is considered. From the definition of f
j
k
l
(
x
), L
F
j
k
1
(
x
), we can obtain
(36)
Δ
j
k
2
1
=
f
j
k
l
(
x
)
-
L
F
j
k
1
(
x
)
=
t
j
k
∑
m
=
1
K
j
k
‍
z
j
k
m
(
σ
)
[
ln
⁡
(
X
j
k
)
-
w
j
k
m
(
σ
)
T
x
∑
m
=
1
K
j
k
‍
h
[
-
w
j
k
m
(
σ
)
T
x
-
ϕ
j
k
m
(
x
(
σ
)
)
+
w
j
k
m
(
σ
)
T
x
(
σ
)
]
=
t
j
k
∑
m
=
1
K
j
k
‍
z
j
k
m
(
σ
)
·
Δ
j
k
m
1
.
Then, by Lemma3, Δ
j
k
2
1
→
0 as ∥
x
¯
-
x
_
∥
→
0. Therefore, when ∥
x
¯
-
x
_
∥
→
0, we can get
(37)
Δ
j
k
1
=
f
j
(
x
)
-
L
F
j
1
(
x
)
=
Δ
j
k
1
1
+
Δ
j
k
2
1
⟶
0
.
By similar discussion as above, we can get(38)
Δ
j
k
2
=
f
j
(
x
)
-
L
F
j
2
(
x
)
⟶
0
,
as
∥
x
¯
-
x
_
∥
⟶
0
.
It follows from (37) and (38) that f
j
(
x
)
-
L
F
j
(
x
)
→
0 when ∥
x
¯
-
x
_
∥
→
0.Theorem4 shows that as the subhyperrectangle X
⊆
X
0 is small enough, the solution to (LLP)(X) is sufficiently approaching the solution of (NPP)(X) and this guarantees the global convergence of the method.


## 3. Algorithm and Its Convergence

In this section, a branch-and-bound algorithm is developed to solve (NPP) based on the relaxation lower linear programming in Section2. This algorithm needs to solve a sequence of linear programming over partitioned subsets of X in order to find a global optimum. Consequently, this method needs partitioning the set X
0 into subhyperrectangles, each concerned with a node of the branch-and-bound tree, and each node is associated with a relaxation linear subproblem in each subhyperrectangle.First, at any stagek of the algorithm, suppose that we have a collection of active nodes denoted by Q
k, say, each associated with a subhyperrectangle X
⊂
X
0
,
for
all
X
∈
Q
k. For each node X, we will have computed a lower bound of the optimal value of the problem ((NPP)(X)) via solution L
B
(
X
) of problem (LLP) so that the lower bound of optimal value of (NPP) on the whole initial box region X
0 is given by L
B
k
=
min
⁡
{
L
B
(
X
)
∣
∀
X
∈
Q
k
} at stage k. Whenever the lower bounding solution to any node subproblem; that is, the solution to the relaxation linear programming (LLP), turns out to be feasible to (NPP), we update the upper bound of incumbent solution U
B if necessary. Then, the active nodes collection Q
k will satisfy U
B
⩾
L
B
(
X
)
,
for
all
X
∈
Q
k, for each stage k. We now select an active node X
∈
Q
k such that L
B
(
X
)
=
L
B
k for further considering. The active node X is partitioned into two subhyperrectangles according to the following branching rules. For these two subhyperrectangles, the fathoming step is applied in order to identify whether the subhyperrectangles should be eliminated. Finally, we obtain a collection of active nodes for the next stage, and this process is repeated until convergence is obtained.


### 3.1. Branching Rule

The critical element in guaranteeing convergence to a global minimum means the choice of a suitable partitioning strategy. In our paper, we choose a simple and standard bisection rule. This method is sufficient to ensure convergence since it drives all the intervals to zero for the variables that are associated with the term yielding the greatest discrepancy in the employed approximation along with any infinite branch of a branch-and-bound tree.Consider any node subproblem identified by the hyperrectangleX
=
{
x
_
,
x
¯
}
⊆
X
0 and the selection of branching variable x
p and partitioning of X is then done by using the following rule (see also [39, 40]). Let p
=
argmax
{
x
¯
i
-
x
_
i
;
i
=
1,2
,
…
,
n
},  partitioning X by bisectioning the interval [
x
_
p
,
x
¯
p
] into the subintervals [
x
_
p
,
(
x
_
p
+
x
¯
p
)
/
2
] and [
(
x
_
p
+
x
¯
p
)
/
2
,
x
¯
p
].


### 3.2. Algorithmic Statement

The deterministic global optimization algorithm is summarized as follows.Step  0  (initialization).
(0.1)
Initialize the iteration counterk
:
=
0, the set of all active nodes Q
0
=
{
X
0
}, the upper bound β
=
+
∞, and the set of feasible points F
∶
=
∅.
(0.2)
Solve (LLP) withX
=
X
0 in order to find an optimal solution x
0 and the optimal value α
(
X
0
). If x
0 is feasible to (NPP), then set β
=
f
(
x
0
)
,
F
=
F
∪
{
x
0
}, and α
0
=
α
(
X
0
), if necessary.
(0.3)
Ifβ
⩽
α
0
+
ɛ, where ɛ
>
0 is some accuracy tolerance, then stop. x
0 is global ɛ-optimal solution to (NPP). Otherwise, set k
=
1 and proceed to Step 1.Step 1 (partitioning step).
According to the rectangle bisection rule, select a branching variablex
p to partition X
k to get two new subhyperrectangles X
k
,
1
,
X
k
,
2
⊆
R
n. Call the set of new partition rectangles as X
¯
k
=
{
X
k
,
1
,
X
k
,
2
}.Step 2 (feasibility check for (NPP) in subhyperrectangles).
For each new nodeX
=
[
x
_
,
x
¯
]
∈
X
¯
k, for each l
=
1,2
,
…
,
q, compute the lower bound for any linear constraint function ∑
i
=
1
n
‍
a
l
i
x
i only according to the present considered rectangle; that is, compute lower bound ∑
a
l
i
>
0
‍
a
l
i
x
_
i
+
∑
a
l
i
<
0
‍
a
l
i
x
¯
i. If there exists some l
∈
{
1
,
…
,
q
} such that
(39)
∑
a
l
i
>
0
‍
a
l
i
x
_
i
+
∑
a
l
i
<
0
‍
a
l
i
x
¯
i
>
b
l
,
then the corresponding subrectangle X is eliminated from X
¯
k; that is, X
¯
k
=
X
¯
k
∖
{
X
}, and skip to next element of X
¯
k.Step 3 (bounding step).
IfX
¯
k
=
∅, go to Step 5. If X
¯
k
≠
∅, solve LLP(X) to obtain α
(
X
) and x
(
X
) for each X
∈
X
¯
k. If α
(
X
)
>
β, set X
¯
k
=
X
¯
k
∖
{
X
}. Otherwise, if x
(
X
), is feasible to (NPP), then update β and F, if necessary.Step 4 (updating the upper bound).
Select the midpointx
mid of X
k; if x
mid is feasible to (NP)(X
k), then F
∶
=
F
∪
{
x
mid
}. Define the upper bound β
∶
=
min
⁡
x
∈
F
⁡
f
(
x
). If F
≠
ϕ, the best known feasible point is denoted by x
best
∶
=
arg
min
⁡
x
∈
F
⁡
f
(
x
).Step 5 (updating the lower bound).
The partition set remaining is nowQ
k
∶
=
(
Q
k
∖
{
X
k
}
)
∪
X
¯
k and a new lower bound is α
k
∶
=
min
⁡
X
∈
Q
k
⁡
β
(
X
).Step 6 (convergence checking).
SetQ
k
+
1
=
Q
k
∖
{
X
:
β
-
α
k
⩽
ɛ
,
X
∈
Q
k
}. If Q
k
+
1
=
ϕ, then stop with β as the solution of (NPP) and x
best as an optimal solution. Otherwise select an active node X
k
+
1 such that X
k
+
1
=
arg
min
⁡
X
∈
Q
k
+
1
⁡
α
(
X
)
,
x
k
=
x
(
X
k
). Set k
:
=
k
+
1 and go to Step 1.


### 3.3. Convergence of the Algorithm

By Theorem4, global algorithm convergence will be given in Theorem 5.Theorem 5.
The above algorithm either terminates finitely with the incumbent solution being optimal to (NPP) or generates an infinite sequence of iterations such that, along with any infinite branch of the branch-and-bound tree, any accumulation point of sequencex
k will be global solution to (NPP).Proof.
If the above proposed algorithm terminates finitely, obviouslyα is a global optimal value and x
best is optimal solution for the (NPP). If the algorithm is infinite, it generates at least one infinite sequence {
X
k
} such that X
k
+
1
⊂
X
k for any k. Then, from [39, 40], ⋂
k
‍
X
k
=
{
x
^
} for some point x
^
∈
R
n. For every iteration of the algorithm, the following results are true:
(40)
α
k
⩽
min
⁡
x
∈
X
0
f
(
x
)
,
X
k
∈
arg
min
⁡
X
∈
Q
k
α
(
X
)
,
α
k
hh
⩽
x
k
=
x
(
X
k
)
∈
X
k
,
k
=
0,1
,
…
.
Since{
x
k
} is contained in a compact set X
0, there must be one convergent subsequence {
x
s
}
⊆
{
x
k
} and assume lim
⁡
s
→
∞
x
s
=
x
^. Then from the proposed algorithm, there exists a decreasing subsequence {
X
r
}
⊂
{
X
s
} where X
r
∈
Q
r with x
r
∈
X
r
,
α
r
=
α
(
X
r
)
=
L
F
0
(
x
r
), and lim
⁡
r
→
∞
X
r
=
{
x
^
}. According to Theorem 5, we have lim
⁡
r
→
∞
α
r
=
lim
⁡
r
→
∞
L
F
0
(
x
r
)
=
lim
⁡
r
→
∞
f
0
(
x
r
)
=
f
0
(
x
^
).
Then all what remains is to prove thatx
^ is feasible to (NPP)(X
0). First, it is obvious that x
^
∈
X
0 since X
0 is closed. Secondly, by the algorithm, we can obtain that, for all r, x
r is feasible solution to (NPP); that is, A
x
r
⩽
b. Taking limits over r in this inequality yields A
x
^
⩽
b. The remainder of the proof will be by contradiction. Assume that f
j
(
x
^
)
>
e
j for some j
=
1,2
,
…
,
p. Because function L
F
j
(
x
) is continuous and again from Theorem 4, the sequence {
L
F
j
(
x
r
)
} converges to f
j
(
x
^
); then by definition of convergence, there must be r
¯, such that |
L
F
j
(
x
r
)
-
f
j
(
x
^
)
|
<
f
j
(
x
^
)
-
e
j for any r
>
r
¯. Therefore, for any r
>
r
¯, we have f
j
(
x
^
)
>
e
j, which implies that LLP(X
r) is infeasible and violating the assumption that x
r
=
x
(
X
r
). This is a contradiction, and thus the theorem is completed.


## 3.1. Branching Rule

The critical element in guaranteeing convergence to a global minimum means the choice of a suitable partitioning strategy. In our paper, we choose a simple and standard bisection rule. This method is sufficient to ensure convergence since it drives all the intervals to zero for the variables that are associated with the term yielding the greatest discrepancy in the employed approximation along with any infinite branch of a branch-and-bound tree.Consider any node subproblem identified by the hyperrectangleX
=
{
x
_
,
x
¯
}
⊆
X
0 and the selection of branching variable x
p and partitioning of X is then done by using the following rule (see also [39, 40]). Let p
=
argmax
{
x
¯
i
-
x
_
i
;
i
=
1,2
,
…
,
n
},  partitioning X by bisectioning the interval [
x
_
p
,
x
¯
p
] into the subintervals [
x
_
p
,
(
x
_
p
+
x
¯
p
)
/
2
] and [
(
x
_
p
+
x
¯
p
)
/
2
,
x
¯
p
].


## 3.2. Algorithmic Statement

The deterministic global optimization algorithm is summarized as follows.Step  0  (initialization).
(0.1)
Initialize the iteration counterk
:
=
0, the set of all active nodes Q
0
=
{
X
0
}, the upper bound β
=
+
∞, and the set of feasible points F
∶
=
∅.
(0.2)
Solve (LLP) withX
=
X
0 in order to find an optimal solution x
0 and the optimal value α
(
X
0
). If x
0 is feasible to (NPP), then set β
=
f
(
x
0
)
,
F
=
F
∪
{
x
0
}, and α
0
=
α
(
X
0
), if necessary.
(0.3)
Ifβ
⩽
α
0
+
ɛ, where ɛ
>
0 is some accuracy tolerance, then stop. x
0 is global ɛ-optimal solution to (NPP). Otherwise, set k
=
1 and proceed to Step 1.Step 1 (partitioning step).
According to the rectangle bisection rule, select a branching variablex
p to partition X
k to get two new subhyperrectangles X
k
,
1
,
X
k
,
2
⊆
R
n. Call the set of new partition rectangles as X
¯
k
=
{
X
k
,
1
,
X
k
,
2
}.Step 2 (feasibility check for (NPP) in subhyperrectangles).
For each new nodeX
=
[
x
_
,
x
¯
]
∈
X
¯
k, for each l
=
1,2
,
…
,
q, compute the lower bound for any linear constraint function ∑
i
=
1
n
‍
a
l
i
x
i only according to the present considered rectangle; that is, compute lower bound ∑
a
l
i
>
0
‍
a
l
i
x
_
i
+
∑
a
l
i
<
0
‍
a
l
i
x
¯
i. If there exists some l
∈
{
1
,
…
,
q
} such that
(39)
∑
a
l
i
>
0
‍
a
l
i
x
_
i
+
∑
a
l
i
<
0
‍
a
l
i
x
¯
i
>
b
l
,
then the corresponding subrectangle X is eliminated from X
¯
k; that is, X
¯
k
=
X
¯
k
∖
{
X
}, and skip to next element of X
¯
k.Step 3 (bounding step).
IfX
¯
k
=
∅, go to Step 5. If X
¯
k
≠
∅, solve LLP(X) to obtain α
(
X
) and x
(
X
) for each X
∈
X
¯
k. If α
(
X
)
>
β, set X
¯
k
=
X
¯
k
∖
{
X
}. Otherwise, if x
(
X
), is feasible to (NPP), then update β and F, if necessary.Step 4 (updating the upper bound).
Select the midpointx
mid of X
k; if x
mid is feasible to (NP)(X
k), then F
∶
=
F
∪
{
x
mid
}. Define the upper bound β
∶
=
min
⁡
x
∈
F
⁡
f
(
x
). If F
≠
ϕ, the best known feasible point is denoted by x
best
∶
=
arg
min
⁡
x
∈
F
⁡
f
(
x
).Step 5 (updating the lower bound).
The partition set remaining is nowQ
k
∶
=
(
Q
k
∖
{
X
k
}
)
∪
X
¯
k and a new lower bound is α
k
∶
=
min
⁡
X
∈
Q
k
⁡
β
(
X
).Step 6 (convergence checking).
SetQ
k
+
1
=
Q
k
∖
{
X
:
β
-
α
k
⩽
ɛ
,
X
∈
Q
k
}. If Q
k
+
1
=
ϕ, then stop with β as the solution of (NPP) and x
best as an optimal solution. Otherwise select an active node X
k
+
1 such that X
k
+
1
=
arg
min
⁡
X
∈
Q
k
+
1
⁡
α
(
X
)
,
x
k
=
x
(
X
k
). Set k
:
=
k
+
1 and go to Step 1.


## 3.3. Convergence of the Algorithm

By Theorem4, global algorithm convergence will be given in Theorem 5.Theorem 5.
The above algorithm either terminates finitely with the incumbent solution being optimal to (NPP) or generates an infinite sequence of iterations such that, along with any infinite branch of the branch-and-bound tree, any accumulation point of sequencex
k will be global solution to (NPP).Proof.
If the above proposed algorithm terminates finitely, obviouslyα is a global optimal value and x
best is optimal solution for the (NPP). If the algorithm is infinite, it generates at least one infinite sequence {
X
k
} such that X
k
+
1
⊂
X
k for any k. Then, from [39, 40], ⋂
k
‍
X
k
=
{
x
^
} for some point x
^
∈
R
n. For every iteration of the algorithm, the following results are true:
(40)
α
k
⩽
min
⁡
x
∈
X
0
f
(
x
)
,
X
k
∈
arg
min
⁡
X
∈
Q
k
α
(
X
)
,
α
k
hh
⩽
x
k
=
x
(
X
k
)
∈
X
k
,
k
=
0,1
,
…
.
Since{
x
k
} is contained in a compact set X
0, there must be one convergent subsequence {
x
s
}
⊆
{
x
k
} and assume lim
⁡
s
→
∞
x
s
=
x
^. Then from the proposed algorithm, there exists a decreasing subsequence {
X
r
}
⊂
{
X
s
} where X
r
∈
Q
r with x
r
∈
X
r
,
α
r
=
α
(
X
r
)
=
L
F
0
(
x
r
), and lim
⁡
r
→
∞
X
r
=
{
x
^
}. According to Theorem 5, we have lim
⁡
r
→
∞
α
r
=
lim
⁡
r
→
∞
L
F
0
(
x
r
)
=
lim
⁡
r
→
∞
f
0
(
x
r
)
=
f
0
(
x
^
).
Then all what remains is to prove thatx
^ is feasible to (NPP)(X
0). First, it is obvious that x
^
∈
X
0 since X
0 is closed. Secondly, by the algorithm, we can obtain that, for all r, x
r is feasible solution to (NPP); that is, A
x
r
⩽
b. Taking limits over r in this inequality yields A
x
^
⩽
b. The remainder of the proof will be by contradiction. Assume that f
j
(
x
^
)
>
e
j for some j
=
1,2
,
…
,
p. Because function L
F
j
(
x
) is continuous and again from Theorem 4, the sequence {
L
F
j
(
x
r
)
} converges to f
j
(
x
^
); then by definition of convergence, there must be r
¯, such that |
L
F
j
(
x
r
)
-
f
j
(
x
^
)
|
<
f
j
(
x
^
)
-
e
j for any r
>
r
¯. Therefore, for any r
>
r
¯, we have f
j
(
x
^
)
>
e
j, which implies that LLP(X
r) is infeasible and violating the assumption that x
r
=
x
(
X
r
). This is a contradiction, and thus the theorem is completed.


## 4. Numerical Experiments

To verify performance of the proposed global optimization algorithm, some test problems were implemented. The test problems are coded in C++ and the experiments are conducted on a Pentium IV (3.06 GHZ) microcomputer. Setɛ
=
0.000001. The results of Examples 1–5 are summarized in Table 1. In Table 1, the notations have been used for row headers: Iter.: number of algorithm iterations; L
max
⁡: the maximal length of the enumeration tree.Table 1
Computational results of Examples1–5.
Example
Methods
Optimal solution
Optimal value
Iter.
L
max
⁡
Example1
[13]
(0, 0, 1.25)
2.9311923
25
Ours
(0, 0, 1.25)
2.9311923
15
4
Example2
[13]
(0.000, 1.111, 0.000)
4.217
31
Ours
(0.000, 1.111, 0.000)
4.217
20
5
Example3
[14]
(1.5, 1.5, 0)
7.96324
52
3
Ours
(3.0, 4.0, 0)
5.7606445
55
8
Example4
[11]
(1.0, 1.0)
1.3463824
26
4
[12]
(1.0, 1.0)
1.3463824
1
0
Ours
(1.0, 1.0)
1.3463824
24
2
Example5
[11]
(1.0, 1.0)
288.0
43
5
[12]
(1.0, 1.0)
288.0
1
0
Ours
(1.0, 1.0)
288.0
42
5Example 1 (see [13]).
Consider(41)
min
⁡
y
=
3
x
1
+
5
x
2
+
3
x
3
+
50
3
x
1
+
4
x
2
+
5
x
3
+
50
+
3
x
1
+
4
x
2
+
50
4
x
1
+
3
x
2
+
2
x
3
+
50
hhhhhhh
+
4
x
1
+
2
x
2
+
4
x
3
+
50
5
x
1
+
4
x
2
+
3
x
3
+
50
s
.
t
.
6
x
1
+
3
x
2
+
3
x
3
⩽
10
,
10
x
1
+
3
x
2
+
8
x
3
⩽
10
,
hhhhhhhhhhhhhhhhhhhhhhhhhhhhhh
x
1
,
x
2
,
x
3
⩾
0
.Example 2 (see [13]).
Consider(42)
min
⁡
y
=
4
x
1
+
3
x
2
+
3
x
3
+
50
3
x
2
+
3
x
3
+
50
+
3
x
1
+
4
x
3
+
50
4
x
1
+
4
x
2
+
5
x
3
+
50
hhhhhhh
+
x
1
+
2
x
2
+
5
x
3
+
50
x
1
+
5
x
2
+
5
x
3
+
50
+
x
1
+
2
x
2
+
4
x
3
+
50
5
x
2
+
4
x
3
+
50
s
.
t
.
2
x
1
+
x
2
+
5
x
3
⩽
10
,
x
1
+
6
x
2
+
3
x
3
⩽
10
,
5
x
1
+
9
x
2
+
2
x
3
⩽
10
,
9
x
1
+
7
x
2
+
3
x
3
⩽
10
,
hhhhhhhhhhhhhhhhhhhhhhhhhhhhhh
x
1
,
x
2
,
x
3
⩾
0
.Example 3 (see [14]).
Consider(43)
min
⁡
(
13
x
1
+
13
x
2
+
13
37
x
1
+
73
x
2
+
13
)
-
1.4
×
(
63
x
1
-
18
x
2
+
39
13
x
1
+
26
x
2
+
13
)
1.2
-
(
x
1
+
2
x
2
+
5
x
3
+
50
x
1
+
5
x
2
+
5
x
3
+
50
)
0.5
×
(
x
1
+
2
x
2
+
4
x
3
+
50
5
x
2
+
4
x
3
+
50
)
-
2
s
.
t
.
2
x
1
+
x
2
+
5
x
3
⩽
10
,
5
x
1
-
3
x
2
=
3
,
hhhhhhhhhhhhh
1.5
⩽
x
1
⩽
3
,
x
1
,
x
2
,
x
3
⩾
0
.Example 4 (see [11, 12]).
Consider(44)
min
⁡
(
x
1
+
x
2
+
1
x
1
+
x
2
+
2
)
1.1
×
(
x
1
+
x
2
+
3
x
1
+
x
2
+
4
)
1.2
+
(
x
1
+
x
2
+
5
x
1
+
x
2
+
6
)
1.1
×
(
x
1
+
x
2
+
7
x
1
+
x
2
+
8
)
1.2
s
.
t
.
x
1
x
2
2
+
x
1
2
x
2
⩽
10
,
1.0
⩽
x
1
⩽
2.0
,
1.0
⩽
x
2
⩽
2.0
.Example 5 (see [11, 12]).
Consider(45)
min
⁡
(
2
x
1
+
x
2
+
1
)
2
(
2
x
1
+
2
x
2
+
1
)
2
-
(
x
1
+
2
x
2
+
1
)
2
(
x
1
+
3
x
2
+
3
)
s
.
t
.
(
2
x
1
+
2
x
2
+
1
)
(
x
1
+
2
x
2
+
1
)
2
+
2
(
x
1
+
x
2
+
1
)
1.5
(
2
x
1
+
x
2
)
2
⩽
200
,
(
x
1
+
x
2
+
1
)
1.1
(
1.5
x
1
+
x
2
+
2
)
1.2
-
(
2
x
1
+
2
x
2
+
1
)
(
2
x
1
+
x
2
+
3
)
⩽
30
,
hhhhhhhhhhhhhhh
1
⩽
x
1
⩽
3
,
1
⩽
x
2
⩽
3
.Example 6.
In this example, we solve 10 different random instances:(46)
min
⁡
∑
k
=
1
K
‍
t
k
∏
j
=
1
K
k
‍
(
c
k
j
T
x
+
d
k
j
)
α
k
j
s
.
t
.
A
x
⩽
b
,
x
∈
X
0
=
[
x
_
,
x
¯
]
⊂
R
n
,
where K
=
4, K
k
=
3, A is m
×
n matrix, and all elements of t
k
,
c
k
j
,
d
k
j
,
α
k
m
,
A
,
b, x
_, and x
¯ are randomly generated, whose ranges are [
-
2,2
]. Table 2 summarizes our computational results. In Table 2, the following indices characterize performance in algorithm: (m
,
n): the dimensions of the matrix A; Iter.: the average number of iterations; time: the average execution time in seconds.Table 2
Computational results of Example6.
Example
(m, n)
Iter.
Time
1
(10, 10)
41.8
33.7
2
(10, 20)
43.2
35.3
3
(20, 20)
69.1
46.5
4
(20, 30)
75.6
49.9
5
(30, 10)
88.7
57.0
6
(30, 20)
91.8
61.7
7
(40, 10)
118.2
78.4
8
(40, 20)
125.0
82.5
9
(50, 10)
138.6
88.9
10
(50, 20)
146.7
92.0


## 5. Conclusion

In this paper, a global optimization algorithm is presented to a class of nonconvex programming problems (NPP). A transformation and a two-part parametric linearization technique are employed to initial (NPP), and (NPP) is reduced to a parametric relaxation in lower linear programming based on the linear lower bounding of the objective function and nonlinear constraint functions. Thus the initial (NPP) is reduced to a sequence of linear programming problems through the successive refinement in a linear relaxation of feasible region in an objective function. The algorithm can obtain finite convergence to the global minimum through the successive refinement of the feasible region and the subsequent solutions to a series of linear programming problems. The proposed algorithm is applied to several test problems. In all cases, convergence to the global minimum is achieved.



---

*Source: 697321-2014-02-23.xml*