# A Global Optimization Approach for Solving Generalized Nonlinear Multiplicative Programming Problem

Authors: Lin-Peng Yang; Pei-Ping Shen; Yong-Gang Pei
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

This paper presents a global optimization algorithm for solving globally the generalized nonlinear multiplicative programming (MP) with a nonconvex constraint set. The algorithm uses a branch and bound scheme based on an equivalently reverse convex programming problem. As a result, in the computation procedure the main work is solving a series of linear programs that do not grow in size from iterations to iterations. Further several key strategies are proposed to enhance solution production, and some of them can be used to solve a general reverse convex programming problem. Numerical results show that the computational efficiency is improved obviously by using these strategies.


---

## Body

## 1. Introduction

Consider the following generalized nonlinear multiplicative programming problem:(1)
(
MP
)
{
min
⁡
f
0
(
y
)
s
.
t
.
f
j
(
y
)
≤
1
,
j
=
1
,
…
,
p
,
f
p
+
1
(
y
)
≥
1
,
y
∈
Ω
0
=
{
y
∣
0
<
y
i
L
≤
y
i
≤
y
i
U
<
∞
,
m
m
m
m
m
m
i
=
1
,
…
,
n
y
i
L
y
i
L
}
,
where
(2)
f
j
(
y
)
=
∏
k
=
1
T
j
‍
{
∑
l
=
1
m
j
‍
β
j
k
l
∏
i
=
1
n
‍
y
i
α
j
k
l
i
}
γ
j
k
,
h
h
h
h
h
h
h
h
h
h
h
h
j
=
0,1
,
…
,
p
+
1
,
and γ
j
k, β
j
k
l, and α
j
k
l
i are all real numbers with γ
j
k
>
0 and β
j
k
l
>
0.Problem (MP) is worth studying because it frequently appears in many applications, including engineering design [1–6], economics and statistics [7–12], manufacturing [13, 14], chemical equilibrium [15, 16], financial optimization [17], plant layout design [18]. On the other hand, many other nonlinear problems, such as quadratic programming (QP), bilinear programming (BLP), linear multiplication programming (LMP), polynomial programming, and generalized geometric programming, fall into the category of (MP).Problem (MP) usually poses significant theoretical and computational difficulties; that is, it is known to generally possess multiple local optima that are not globally optimal. For example, the problems (LMP), (BLP), and (QP) are multiextremal. Both (LMP) and (MP) are known to be NP-hard problems [19, 20] and global optimization ones. So, it evoked interest of researchers and practitioners. During the past years, many solution algorithms have been proposed to solve special forms of the problem (MP). The methods can be classified as parameter-based methods [21–23], branch-and-bound methods [24–28], outer-approximation methods [29, 30], mixed branch-and-bound and outer-approximation method [31], vertex enumeration methods [32, 33], outcome-space cutting plane methods [34], and heuristic methods [35, 36].Up to now, although there has been significant progress in the development of deterministic algorithms for finding global optimal solutions of generalized linear multiplicative programming problem, to our knowledge, little work has been done for globally solving generalized nonlinear multiplicative programming (MP). The purpose of this paper is to develop a reliable and effective algorithm for solving problem (MP). In the algorithm, by making use of a variable transformation the original problem (MP) is first equivalently reformulated as a reverse convex programming (RCP). Then, a linear relaxation programming is generated for a lower bound of the optimal value to problem (RCP) in the branch-and-bound search by using the exponent and logarithmic functions. Compared with other methods reviewed above, the mathematical model considered in this paper is an important extension for the model given in [24, 26, 37], and the presented linear relaxation technique can be looked upon as an extension application for the one proposed in [24, 26, 37]. Moreover, an upper bound updating strategy is given to provide a better bound than the standard branch-and-bound methods (e.g., [24, 26–28, 37]) based on the proposed global solution location rule. Also, the reduction cut given in this paper offers a possibility to cut away a large part of the currently investigated region in which the globally optimal solution of (MP) does not exist. And finally, the numerical results show that the proposed algorithm is feasible and the computational advantages are indicated.The content of this paper is as follows. In Section2, we present the problem (RCP) that is equivalent to problem (MP). The four key strategies of the algorithm are detailed in Section 3. A precise algorithm statement and its convergence are given in Section 4. Section 5 reports the numerical results of some sample problems by using the algorithm. Some concluding remarks are given in Section 6.


## 2. Equivalent Reformulation

In this section, we show that any (MP) problem can be transformed into an equivalent reverse convex programming problem with one reverse convex constraint. To see how such a reformulation is possible, some notations will be introduced as follows:(3)
I
=
{
1
,
…
,
n
}
,
J
=
{
0,1
,
…
,
p
+
1
}
,
b
j
k
l
=
ln
⁡
(
β
j
k
l
)
,
∀
j
∈
J
,
k
=
1
,
…
,
T
j
,
l
=
1
,
…
,
m
j
,
x
i
=
ln
⁡
(
y
i
)
,
i
∈
I
,
L
i
=
ln
⁡
⁡
(
y
i
L
)
,
U
i
=
ln
⁡
⁡
(
y
i
U
)
,
∀
i
∈
I
,
exp
⁡
⁡
(
z
)
=
exp
⁡
⁡
(
z
1
)
+
⋯
+
exp
⁡
⁡
(
z
m
j
)
,
∀
z
=
(
z
1
,
…
,
z
m
j
)
T
∈
R
m
j
.
Thus, one can convert (MP) into the following equivalent reverse convex programming problem (RCP):
(4)
(
RCP
)
{
min
⁡
F
0
(
x
)
s
.
t
.
F
j
(
x
)
≤
0
,
j
=
1
,
…
,
p
,
F
p
+
1
(
x
)
≥
0
,
x
∈
Ω
-
=
{
x
∣
L
-
i
≤
x
i
≤
U
-
i
,
i
∈
I
}
,
where for each j
∈
J,
(5)
F
j
(
x
)
=
∑
k
=
1
T
j
‍
γ
j
k
ln
⁡
(
∑
l
=
1
m
j
‍
exp
⁡
(
∑
i
=
1
n
‍
α
j
k
l
i
x
i
+
b
j
k
l
)
)
are all convex functions. Furthermore, let A
j
k
∈
R
m
j
×
n be a matrix with
(6)
A
j
k
≜
[
α
j
k
11
α
j
k
12
⋯
α
j
k
1
n
α
j
k
21
α
j
k
22
⋯
α
j
k
2
n
⋯
⋯
⋯
⋯
α
j
k
m
j
1
α
j
k
m
j
2
⋯
α
j
k
m
j
n
]
≜
(
d
j
k
1
d
j
k
2
⋮
d
j
k
m
j
)
,
and let b
j
k
∈
R
n be a vector with b
j
k
=
(
ln
⁡
(
β
j
k
1
)
,
ln
⁡
(
β
j
k
2
)
,
…
,
ln
⁡
(
β
j
k
m
j
)
T
). Then, by using (3) F
j
(
y
) can be rewritten in the form
(7)
F
j
(
x
)
=
∑
k
=
1
T
j
‍
γ
j
k
ln
⁡
(
∑
l
=
1
m
j
‍
exp
⁡
(
d
j
k
l
x
+
b
j
k
l
)
)
=
∑
k
=
1
T
j
‍
γ
j
k
ln
⁡
(
exp
⁡
(
A
j
k
x
+
b
j
k
)
)
,
j
∈
J
.
The key equivalent result for problems (MP) and (RCP) is given by the following theorem.Theorem 1.
Ifx
* is a global optimal solution to problem (RCP), then y
* with y
i
*
=
exp
⁡
(
x
i
*
)
,
∀
i
∈
I, is a global optimal solution for problem (MP). If y
* is a global optimal solution for problem (MP), then x
* with x
i
*
=
ln
⁡
(
y
i
*
)
,
∀
i
∈
I, is a global optimal solution for problem (RCP).Proof.
The proof of this theorem follows easily from the definitions of problems (MP) and (RCP); therefore, it is omitted.


## 3. Key Strategies of the Algorithm

From Theorem1, to globally solve problem (MP), the branch-and-bound algorithm to be presented concentrates on globally solving the equivalent problem (RCP). To present the algorithm, we first explain several processes: branching, lower and upper bounding, and reduction cut.The branching process consists in a successive rectangular partition of the initial boxΩ
-
=
[
L
-
,
U
-
] following in an exhaustive subdivision rule; that is, any infinite nested sequence of partition sets generated through the algorithm shrinks to a singleton. A strategy called the bisection of ratio α will be used in the branching process.The lower bounding process consists in deriving a linear relaxation programming of problem (RCP) via a two-part linearization method. A lower bound for the objective function valueF
0
(
x
) can be found by solving the linear relaxation programming.The upper bounding process consists in estimating an upper boundU
* for the objective function value F
0
(
x
) by adopting a new method in this paper. This method is different from the general method, which is to update the upper bound U
* by enclosing all feasible points x
k found while computing the lower bounds of the optimum of the primal problem (RCP).The reduction cut process consists in applying valid cuts (referred to as reduction cuts) to reduce the size of the current partition setΩ
=
[
L
,
U
]
⊆
Ω
-
=
[
L
-
,
U
-
]. The cuts aim at tightening the box containing the feasible portion currently still of interest.Next, we will give the four key strategies for forming the corresponding processes, respectively.


### 3.1. Bisection of Ratioα

The algorithm performs a branching process inR
n that iteratively subdivides the n-dimensional rectangle Ω
- of problem (RCP) into smaller rectangles that are also of dimension n. This process helps the algorithm identify a location in Ω
- of a point that is a global optimal solution for problem (RCP). At each stage of the process, the subdivision yields a more refined partition [28] of a portion of Ω
- that is guaranteed to contain a global optimal solution. The initial partition Q
0 consists simply of Ω
-.During a typical iterationk of the algorithm, k
≥
1, a rectangle Ω
k
-
1 available from iteration k
-
1, is subdivided into two n-dimensional rectangles by a process called bisection of ratio α, where α is a prechosen parameter that satisfies 0.0
<
α
≤
0.5. Let Ω
k
-
1
=
{
x
∈
R
n
∣
L
i
k
-
1
≤
x
i
≤
U
i
k
-
1
,
i
∈
I
}, where L
i
k
-
1
<
U
i
k
-
1 for all i
∈
I. The procedure for forming a bisection of ratio α of Ω
k
-
1 into two subrectangles Ω
-
k
-
1 and Ω
-
-
2
k
-
1 can be described as follows.(1)
Let(8)
j
=
argmax
{
U
i
k
-
1
-
L
i
k
-
1
,
i
∈
I
}
.
(2)
Lett
j satisfy
(9)
min
⁡
{
t
j
-
L
j
k
-
1
,
U
j
k
-
1
-
t
j
}
=
α
(
U
j
k
-
1
-
L
j
k
-
1
)
,
0
<
α
≤
0.5
.
(3)
Let(10)
Ω
-
k
-
1
=
{
x
∈
R
n
∣
L
i
k
-
1
≤
x
i
≤
U
i
k
-
1
,
m
m
m
m
m
i
≠
j
,
L
j
k
-
1
≤
x
j
≤
t
j
,
i
∈
I
{
x
∈
R
n
∣
L
i
k
-
1
≤
x
i
≤
U
i
k
-
1
,
}
,
Ω
-
-
k
-
1
=
{
x
∈
R
n
∣
L
i
k
-
1
≤
x
i
≤
U
i
k
-
1
,
m
m
m
m
m
i
≠
j
,
t
j
≤
x
j
≤
U
j
k
-
1
,
i
∈
I
}
.Clearly, if α
=
0.5, then the bisection of ratio α is the standard bisection rule.


### 3.2. Linearization Strategy

For each rectangleΩ
=
{
x
∈
R
n
∣
L
i
≤
x
i
≤
U
i
,
i
∈
I
}
⊆
R
n created by the branching process, the purpose of this linearization strategy is to obtain a lower bound LB
(
Ω
) for the optimal value of the problem (
RCP
(
Ω
)
).For each rectangleΩ created by the branching process, the lower bound LB
(
Ω
) is found by solving a single linear relaxation programming (
LRP
(
Ω
)
) of problem (
RCP
(
Ω
)
). To derive the (
LRP
(
Ω
)
), we adopt two-part linearization method. In the first part, we will derive the lower bounding functions and the upper bounding function of each function ln
⁡
(
exp
⁡
(
A
j
k
x
+
b
j
k
)
). Then, in the second part, we will derive the linear lower bounding function (LLBF) and linear upper bounding function (LUBF) for each sum term of exp
⁡
(
d
j
k
l
x
+
b
j
k
l
). All the details of this procedure will be given below.First-part linearization: it is well known that the functionln
⁡
(
Y
) is a concave function about the single variable Y
∈
[
Y
_
,
Y
¯
]. Let L
(
ln
⁡
(
Y
)
) and U
(
ln
⁡
(
Y
)
) denote the (LLBF) and (LUBF) of ln
⁡
(
Y
) over the interval [
Y
_
,
Y
¯
], respectively. Then, from the concavity of ln
⁡
(
Y
), it follows that
(11)
L
(
ln
⁡
(
Y
)
)
=
K
1
(
Y
-
Y
_
)
+
ln
⁡
(
Y
_
)
≤
ln
⁡
(
Y
)
,
(12)
U
(
ln
⁡
(
Y
)
)
=
K
1
Y
-
1
-
ln
⁡
K
1
≥
ln
⁡
(
Y
)
,
where K
1
=
(
ln
⁡
Y
¯
-
ln
⁡
Y
_
)
/
(
Y
¯
-
Y
_
).Next, to help to derive the (LLBF) and the (LUBF) of each functionF
j
(
x
), we need to introduce some notations. For any x
∈
Ω, let
(13)
Y
j
k
l
Ω
=
d
j
k
l
x
+
b
j
k
l
with d
j
k
l
T
=
(
a
j
k
l
i
,
…
,
a
j
k
l
n
)
T
∈
R
n; then we have Y
j
k
l
Ω
∈
[
Y
_
j
k
l
Ω
,
Y
¯
j
k
l
Ω
], where
(14)
Y
_
j
k
l
Ω
=
∑
i
=
1
n
‍
min
⁡
{
a
j
k
l
i
L
i
,
a
j
k
l
i
U
i
}
+
b
j
k
l
,
Y
¯
j
k
l
Ω
=
∑
i
=
1
n
‍
max
⁡
{
a
j
k
l
i
L
i
,
a
j
k
l
i
U
i
}
+
b
j
k
l
.
Moreover, let
(15)
η
j
k
Ω
=
∑
l
=
1
m
j
‍
exp
⁡
(
Y
j
k
l
Ω
)
=
exp
⁡
(
A
j
k
x
+
b
j
k
)
;
this will imply η
j
k
Ω
∈
[
η
_
j
k
Ω
,
η
¯
j
k
Ω
], where η
_
j
k
Ω
=
∑
l
=
1
m
j
exp
⁡
(
Y
_
j
k
l
Ω
) and η
¯
j
k
Ω
=
∑
l
=
1
m
j
exp
⁡
(
Y
¯
j
k
l
Ω
). Denote
(16)
K
j
k
Ω
=
ln
⁡
η
¯
j
k
Ω
-
ln
⁡
η
_
j
k
Ω
η
¯
j
k
Ω
-
η
_
j
k
Ω
.
Thus, from (11), it follows that the lower bounding function of ln
⁡
(
exp
⁡
(
A
j
k
x
+
b
j
k
)
) over Ω, denoted as L
j
k
L
(
x
), has the following form:
(17)
L
j
k
L
(
x
)
=
K
j
k
Ω
(
exp
⁡
(
A
j
k
x
+
b
j
k
)
-
η
_
j
k
Ω
)
+
ln
⁡
(
η
_
j
k
Ω
)
=
K
j
k
Ω
(
∑
l
=
1
m
j
‍
exp
⁡
(
d
j
k
l
x
+
b
j
k
l
)
-
η
_
j
k
Ω
)
+
ln
⁡
(
η
_
j
k
Ω
)
.
Similarly, from (12) the upper bounding function of ln
⁡
(
exp
⁡
(
A
j
k
x
+
b
j
k
)
) over Ω, denoted as L
j
k
U
(
x
), is as follows:
(18)
L
j
k
U
(
x
)
=
K
j
k
Ω
exp
⁡
(
A
j
k
x
+
b
j
k
)
-
1
-
ln
⁡
(
K
j
k
Ω
)
=
K
j
k
Ω
∑
l
=
1
m
j
‍
exp
⁡
(
d
j
k
l
x
+
b
j
k
l
)
-
1
-
ln
⁡
(
K
j
k
Ω
)
.
Based on the previous results, we have
(19)
L
j
k
L
(
x
)
≤
ln
⁡
(
exp
⁡
(
A
j
k
x
+
b
j
k
)
)
≤
L
j
k
U
(
x
)
,
∀
x
∈
Ω
.
Therefore, for each j
∈
{
0,1
,
…
,
p
}, the first-part lower bounding function of F
j
(
x
) in (7), denoted by L
j
(
x
), can be given by
(20)
L
j
(
x
)
=
∑
k
=
1
T
j
‍
γ
j
k
[
K
j
k
Ω
(
∑
l
=
1
m
j
‍
exp
⁡
(
d
j
k
l
x
+
b
j
k
l
)
-
η
_
j
k
Ω
)
m
m
m
m
+
ln
⁡
(
η
_
j
k
Ω
)
∑
l
=
1
m
j
‍
]
,
and the first-part upper bounding function of F
p
+
1
(
x
) in (7), denoted by U
p
+
1
(
x
), is as follows:
(21)
U
p
+
1
(
x
)
=
∑
k
=
1
T
p
+
1
‍
γ
p
+
1
,
k
[
K
p
+
1
,
k
Ω
∑
l
=
1
m
p
+
1
‍
exp
⁡
(
d
p
+
1
,
k
l
x
+
b
p
+
1
,
k
l
)
mmmmmm
-
1
-
ln
⁡
(
K
p
+
1
,
k
Ω
)
∑
l
=
1
m
p
+
1
‍
]
.Second-part linearization: with a similar method, we can derive the corresponding (LLBF) and (LUBF) of the functionexp
⁡
(
Y
) over the interval [
Y
L
,
Y
U
] such that
(22)
K
2
(
1
+
Y
-
ln
⁡
K
2
)
≤
exp
⁡
(
Y
)
≤
K
2
(
Y
-
Y
L
)
+
exp
⁡
(
Y
L
)
,
where
(23)
K
2
=
exp
⁡
(
Y
U
)
-
exp
⁡
(
Y
L
)
Y
U
-
Y
L
.
From (22), we can derive the (LLBF) and (LUBF) of exp
⁡
(
Y
j
k
l
) over Ω as follows:
(24)
exp
⁡
(
Y
j
k
l
)
=
exp
⁡
(
d
j
k
l
x
+
b
j
k
l
)
≥
B
j
k
l
Ω
(
1
-
ln
⁡
(
B
j
k
l
Ω
)
+
d
j
k
l
x
+
b
j
k
l
)
,
exp
⁡
(
Y
j
k
l
)
=
exp
⁡
(
d
j
k
l
x
+
b
j
k
l
)
≤
C
j
k
l
Ω
+
B
j
k
l
Ω
(
d
j
k
l
x
+
b
j
k
l
)
,
where
(25)
B
j
k
l
Ω
=
exp
⁡
(
Y
¯
j
k
l
Ω
)
-
exp
⁡
(
Y
_
j
k
l
Ω
)
Y
¯
j
k
l
Ω
-
Y
_
j
k
l
Ω
,
C
j
k
l
Ω
=
Y
¯
j
k
l
Ω
exp
⁡
(
Y
_
j
k
l
Ω
)
-
Y
_
j
k
l
Ω
exp
⁡
(
Y
¯
j
k
l
Ω
)
Y
¯
j
k
l
Ω
-
Y
_
j
k
l
Ω
.
Then, for each j
∈
{
0,1
,
…
,
p
}, substitute each term exp
⁡
(
d
j
k
l
x
+
b
j
k
l
) in (20) by B
j
k
l
Ω
(
1
-
ln
⁡
(
B
j
k
l
Ω
)
+
d
j
k
l
x
+
b
j
k
l
). We may derive the (LLBF) of F
j
(
x
) over Ω, denoted as LF
j
(
x
), being the following form:
(26)
LF
j
(
x
)
=
∑
k
=
1
T
j
‍
γ
j
k
{
K
j
k
Ω
[
∑
l
=
1
m
j
‍
B
j
k
l
Ω
(
1
-
ln
⁡
(
B
j
k
l
Ω
)
+
d
j
k
l
x
+
b
j
k
l
)
]
m
m
m
m
m
m
-
K
j
k
Ω
η
_
j
k
Ω
+
ln
⁡
(
η
_
j
k
Ω
)
∑
l
=
1
m
j
‍
}
,
and it follows that LF
j
(
x
)
≤
F
j
(
x
) for all x
∈
Ω
,
j
=
0,1
,
…
,
p.Ifj
=
p
+
1, substitute the terms exp
⁡
(
d
p
+
1
,
k
l
x
+
b
p
+
1
,
k
l
) in (21) by C
p
+
1
,
k
l
Ω
+
B
p
+
1
,
k
l
Ω
(
d
p
+
1
,
k
l
x
+
b
p
+
1
,
k
l
). We can get the (LUBF) of F
p
+
1
(
x
) over Ω, denoted as UF
p
+
1
(
x
), as follows:
(27)
UF
p
+
1
(
x
)
=
∑
k
=
1
T
p
+
1
‍
γ
p
+
1
,
k
m
m
m
m
×
[
K
p
+
1
,
k
Ω
∑
l
=
1
m
p
+
1
‍
(
C
p
+
1
,
k
l
Ω
+
B
p
+
1
,
k
l
Ω
(
d
p
+
1
,
k
l
x
+
b
p
+
1
,
k
l
)
)
m
m
m
m
m
m
mmmmm
-
1
-
ln
⁡
(
K
p
+
1
,
k
Ω
)
∑
l
=
1
m
p
+
1
‍
]
,
and it follows that UF
p
+
1
(
x
)
≥
F
p
+
1
(
x
) for all x
∈
Ω.From the above discussion for the two kinds of constraints, respectively, we can construct the corresponding linear relaxation programming(
LRP
(
Ω
)
) of problem (
RCP
(
Ω
)
) as follows:
(28)
(
LRP
(
Ω
)
)
{
min
⁡
LF
0
(
x
)
s
.
t
.
LF
j
(
x
)
≤
0
,
j
=
1
,
…
,
p
,
UF
p
+
1
(
x
)
≥
0
,
x
∈
Ω
=
{
x
∣
L
i
≤
x
i
≤
U
i
,
i
∈
I
}
.
Obviously, after the functions are replaced by the corresponding linear functions, the feasible region of problem (
RCP
(
Ω
)
) will be contained in the new feasible region of the (
LRP
(
Ω
)
), and we can have the following lemma.Lemma 2.
Assume thatL
B
(
Ω
) is the minimum of the problem (
L
R
P
(
Ω
)
); then L
B
(
Ω
) provides a lower bound for the optimal value of the problem (
R
C
P
(
Ω
)
).


### 3.3. Global Solution Location and Upper Bound Updating

As is known, in the general branch-and-bound algorithm, to update the upper boundU
* of the optimal value for problem (RCP), the usual method is enclosing all feasible points found while computing the lower bounds of the optimum of the primal problem (RCP). In this paper, we will adopt a new method to update the upper bounds, which is different from the usual method. Toward this end, firstly, we will give the global solution location.LetS
=
{
x
∣
F
j
(
x
)
≤
0
,
j
=
1
,
…
,
p
} and G
=
{
x
∣
F
p
+
1
(
x
)
<
0
}. Since the function F
j
(
x
)
,
j
=
1
,
…
,
p
+
1, are all convex, both sets S and G are convex. It is clear that the feasible region of the problem (RCP) lies in the set S
∖
G. In the problem (RCP), there are two cases at the global solution denoted by x
*.Case 1.
We haveF
p
+
1
(
x
*
)
>
0.Case 2.
We haveF
p
+
1
(
x
*
)
=
0.In the case 1, the reverse convex constraint at the global solutionx
* is called a nonactive constraint; this nonactive constraint can vanish in the primal problem, so the problem (RCP) is equivalent to the following problem:
(29)
(
RCP
1
)
{
min
⁡
F
0
(
x
)
s
.
t
.
F
j
(
x
)
≤
0
,
j
=
1
,
…
,
p
,
x
∈
Ω
-
=
{
x
∣
L
-
i
≤
x
i
≤
U
-
i
,
i
∈
I
}
,
which is a convex programming and can be solved by many effective algorithms. Obviously, if the optimal solution x
* to the above problem satisfies the constraint F
p
+
1
(
x
*
)
≥
0, then it will solve (RCP).In the case 2, the problem (RCP) is equivalent to the following problem:(30)
(
RCP
2
)
{
min
⁡
F
0
(
x
)
s
.
t
.
F
j
(
x
)
≤
0
,
j
=
1
,
…
,
p
,
F
p
+
1
(
x
)
=
0
,
x
∈
Ω
-
=
{
x
∣
L
-
i
≤
x
i
≤
U
-
i
,
i
∈
I
}
.
In this case, we will always have the following assumption.Assumption 1.
A pointx
′ is available such that x
′
∈
S, F
p
+
1
(
x
′
)
<
0, F
0
(
x
′
)
<
min
⁡
{
F
0
(
x
)
:
x
∈
S
∖
G
}.Clearly, if pointx
′ does not exist, then we only need to solve the problem (RCP1) to obtain the solution of the primal problem (RCP).In this paper, we will make our efforts to solve the problem in Case2. It is expedient to indicate some immediate consequences of the above assumption which will locate the solution of (RCP).Let∂
G denote the bounding of G; that is, ∂
G
=
{
x
∣
F
p
+
1
(
x
)
=
0
}.For everyx
∈
(
S
∩
Ω
)
∖
G, we can find the point x
^ where the line segment [
x
′
;
x
] meets ∂
G. Clearly it is as follows: x
^
=
t
x
+
(
1
-
t
)
x
′ with t
∈
(
0,1
], which can be determined from the following equation:
(31)
F
p
+
1
(
x
^
)
=
0
,
that
is
F
p
+
1
(
t
x
+
(
1
-
t
)
x
′
)
=
0
.Because of the convexity ofS, and both the points x and x
′ are in the set S, x
^ is in the set S too.Lemma 3.
For everyx
∈
S
∩
Ω such that F
p
+
1
(
x
)
>
0, one has F
0
(
x
^
)
<
F
0
(
x
).Proof.
SinceF
0
(
x
′
)
<
0, and x
^
=
t
x
+
(
1
-
t
)
x
′, from the convexity of F
0
(
x
) and Assumption 1, we have
(32)
F
0
(
x
^
)
≤
t
F
0
(
x
)
+
(
1
-
t
)
F
0
(
x
′
)
<
t
F
0
(
x
)
+
(
1
-
t
)
F
0
(
x
)
=
F
0
(
x
)
.Corollary 4.
Under Assumption1, if x
* is the optimal solution of problem (RCP), it lies on S
∩
∂
G.According to the discussion of Lemma3 and Corollary 4, we know that the optimal solution must lie on the boundary, so once a feasible point x is found, we will firstly compute the point x
^ which lies on S
∩
∂
G and satisfying F
0
(
x
^
)
<
F
0
(
x
), then the upper bound U
* of the optimal value for problem (RCP) is updated as
(33)
U
*
=
min
⁡
{
U
*
,
F
0
(
x
^
)
}
.
Hence, once a better upper bound U
* is updated, the number of the deleted nodes will increase, and the unnecessary branching and bounding on some regions where the global solution does not exist will decrease greatly.


### 3.4. Reduction Cut

In this subsection, we pay our attention to how to form the bound reduction technique to accelerate the convergence of the proposed global optimization algorithm.Assume thatU
* is a current known upper bound of the optimal objective value of the problem (RCP). For any Ω
=
(
Ω
i
)
n
×
1
⊆
Ω
- with Ω
i
=
[
L
i
,
U
i
], consider the problem (
LRP
(
Ω
)
). For the sake of convenience, let the objective function and linear constraint functions of (
LRP
(
Ω
)
) be expressed as
(34)
LF
0
(
x
)
=
∑
i
=
1
n
‍
c
i
x
i
+
D
,
LF
j
(
x
)
=
∑
i
=
1
n
‍
q
j
i
x
i
-
r
j
,
j
=
1
,
…
,
p
,
-
UF
p
+
1
=
∑
i
=
1
n
‍
q
p
+
1
,
i
x
i
-
r
p
+
1
.
Then, from (26) and (27) it follows that
(35)
(
c
1
,
…
,
c
n
)
T
=
∑
k
=
1
T
0
‍
γ
0
k
K
0
k
Ω
∑
l
=
1
m
0
‍
B
0
k
l
Ω
d
0
k
l
,
D
=
∑
k
=
1
T
0
‍
γ
0
k
{
K
0
k
Ω
[
∑
l
=
1
m
0
‍
B
0
k
l
Ω
(
1
-
ln
⁡
(
B
0
k
l
Ω
)
+
b
0
k
l
)
]
m
m
m
m
m
m
n
-
K
0
k
Ω
η
_
0
k
Ω
+
ln
⁡
(
η
_
0
k
Ω
)
∑
l
=
1
m
0
‍
}
,
r
j
=
∑
k
=
1
T
j
‍
γ
j
k
{
-
K
j
k
Ω
[
∑
l
=
1
m
j
‍
B
j
k
l
Ω
(
1
-
ln
⁡
(
B
j
k
l
Ω
)
+
b
j
k
l
)
]
m
m
m
m
m
m
n
+
K
j
k
Ω
η
_
j
k
Ω
-
ln
⁡
(
η
_
j
k
Ω
)
∑
l
=
1
m
j
‍
}
,
j
=
1
,
…
,
p
,
r
p
+
1
=
∑
k
=
1
T
p
+
1
‍
γ
p
+
1
,
k
[
K
p
+
1
,
k
Ω
∑
l
=
1
m
p
+
1
‍
(
C
p
+
1
,
k
l
Ω
+
B
p
+
1
,
k
l
Ω
b
p
+
1
,
k
l
)
m
m
m
m
m
m
m
m
m
n
-
1
-
ln
⁡
(
K
p
+
1
,
k
Ω
)
∑
l
=
1
m
p
+
1
‍
]
,
(
q
j
1
,
…
,
q
j
n
)
T
=
∑
k
=
1
T
j
‍
γ
j
k
K
j
k
Ω
∑
l
=
1
m
j
‍
B
j
k
l
Ω
d
j
k
l
,
m
m
m
m
m
m
m
m
m
m
m
m
n
j
=
1
,
…
,
p
,
(
q
p
+
1,1
,
…
,
q
p
+
1
,
n
)
T
=
-
∑
k
=
1
T
p
+
1
‍
γ
p
+
1
,
k
K
p
+
1
,
k
Ω
m
m
m
m
m
m
m
m
m
m
m
×
∑
l
=
1
m
p
+
1
‍
B
p
+
1
,
k
l
Ω
d
p
+
1
,
k
l
.In the following, some notations are introduced as follows:(36)
r
C
=
∑
i
=
1
n
‍
min
⁡
{
c
i
L
i
,
c
i
U
i
}
,
r
L
j
=
∑
i
=
1
n
‍
min
⁡
{
q
j
i
L
i
,
q
j
i
U
i
}
,
ρ
i
=
U
*
-
r
C
-
D
+
min
⁡
{
c
i
L
i
,
c
i
U
i
}
,
δ
j
i
=
r
j
-
r
L
j
+
min
⁡
{
q
j
i
L
i
,
q
j
i
U
i
}
,
where j
=
1
,
…
,
p
+
1
,
i
∈
I.Based on the optimality and feasibility of the problem (RCP), we can give two theorems below to determine the region in which it is guaranteed that there is no optimal solution; thus a reduction cut technique is formed from these theorems.Theorem 5.
For any subrectangleΩ
=
(
Ω
i
)
n
×
1
⊆
Ω
- with Ω
i
=
[
L
i
,
U
i
], the following statements hold.(i)
Ifr
C
+
D
>
U
*, then there exists no optimal solution of the problem (RCP) over the subrectangle Ω.
(ii)
Ifr
C
+
D
≤
U
*, consider the following two cases: if there exists some t
∈
I satisfying c
t
>
0 and ρ
t
<
c
t
U
t, then there is no optimal solution of (RCP) over Ω
a
=
(
Ω
a
i
)
n
×
1; conversely, if c
t
<
0 and ρ
t
<
c
t
L
t for some t, then there does not exist global optimal solution of (RCP) over Ω
b
=
(
Ω
b
i
)
n
×
1, where
(37)
Ω
a
i
=
{
Ω
i
,
i
f
i
≠
t
,
(
ρ
t
c
t
,
U
t
]
⋂
‍
Ω
t
,
i
f
i
=
t
,
Ω
b
i
=
{
Ω
i
,
i
f
i
≠
t
,
[
L
t
,
ρ
t
c
t
)
⋂
‍
Ω
t
,
i
f
i
=
t
.Theorem 6.
For anyΩ
=
(
Ω
i
)
n
×
1
⊆
Ω
- with Ω
i
=
[
L
i
,
U
i
], if r
L
j
-
r
j
>
0 for some j
∈
{
1
,
…
,
p
+
1
}, then there exists no optimal solution of problem (RCP) over Ω; otherwise, for each j
∈
{
1
,
…
,
p
+
1
}, consider the following two cases.(i)
If there exists somet
∈
I
a
n
d
j
∈
{
1
,
…
,
p
+
1
} satisfying q
j
t
>
0 and δ
j
t
<
q
j
t
U
t, then there is not optimal solution of the problem (RCP) over Ω
c
=
(
Ω
c
i
)
n
×
1.
(ii)
Ifq
j
t
<
0 and δ
j
t
<
q
j
t
L
t for some t
∈
I
a
n
d
s
o
m
e
j
∈
{
1
,
…
,
p
+
1
}, then no optimal solution of the problem (RCP) over Ω
d
=
(
Ω
d
i
)
n
×
1 exists, where
(38)
Ω
c
i
=
{
Ω
i
,
i
f
i
≠
t
,
(
δ
j
t
q
j
t
,
U
t
]
⋂
‍
Ω
t
,
i
f
i
=
t
,
Ω
d
i
=
{
Ω
i
,
i
f
i
≠
t
,
[
L
t
,
δ
j
t
q
j
t
)
⋂
‍
Ω
t
,
i
f
i
=
t
.Note that the proof of Theorems5 and 6 is similar to the one of Theorems 1 and 2 in [26]; therefore it is omitted.Reduction Cut(S1) Optimality Cut. Compute r
C
+
D. If r
C
+
D
>
U
*, and let Ω
=
∅; otherwise compute c
i
(
i
=
1
,
…
,
n
). If c
t
>
0 and ρ
t
<
c
t
U
t for some t
∈
I, then let U
t
=
ρ
t
/
c
t and Ω
=
(
Ω
i
)
n
×
1 with Ω
i
=
[
L
i
,
U
i
]
(
i
=
1
,
…
,
n
). If c
t
<
0 and ρ
t
<
c
t
L
t for some t
∈
I, then let L
t
=
ρ
t
/
c
t and Ω
=
(
Ω
i
)
n
×
1 with Ω
i
=
[
L
i
,
U
i
]
(
i
=
1
,
…
,
n
).(S2) Feasibility Cut. For any j
=
1
,
…
,
p, compute LF
j
(
x
)
j and -
UF
p
+
1
(
x
). If r
L
j
-
r
j
>
0 for some j
∈
{
1
,
…
,
p
+
1
}, then let Ω
=
∅; otherwise compute q
j
i  (
j
=
1
,
…
,
p
+
1
,
i
=
1
,
…
,
n
). If q
j
t
>
0 and δ
j
t
<
q
j
t
U
t for some j
∈
{
1
,
…
,
p
+
1
} and t
∈
I, then let U
t
=
δ
j
t
/
q
j
t and Ω
=
(
Ω
i
)
n
×
1 with Ω
i
=
[
L
i
,
U
i
]
(
i
=
1
,
…
,
n
). If q
j
t
<
0 and δ
j
t
<
q
j
t
L
t for some j
∈
{
1
,
…
,
p
+
1
} and t
∈
I, then let L
t
=
δ
j
t
/
q
j
t and Ω
=
(
Ω
i
)
n
×
1 with Ω
i
=
[
L
i
,
U
i
]
(
i
=
1
,
…
,
n
).This reduction cut provides the possibility to cut away a large part of subrectangleΩ that is currently investigated by the algorithm procedure.


## 3.1. Bisection of Ratioα

The algorithm performs a branching process inR
n that iteratively subdivides the n-dimensional rectangle Ω
- of problem (RCP) into smaller rectangles that are also of dimension n. This process helps the algorithm identify a location in Ω
- of a point that is a global optimal solution for problem (RCP). At each stage of the process, the subdivision yields a more refined partition [28] of a portion of Ω
- that is guaranteed to contain a global optimal solution. The initial partition Q
0 consists simply of Ω
-.During a typical iterationk of the algorithm, k
≥
1, a rectangle Ω
k
-
1 available from iteration k
-
1, is subdivided into two n-dimensional rectangles by a process called bisection of ratio α, where α is a prechosen parameter that satisfies 0.0
<
α
≤
0.5. Let Ω
k
-
1
=
{
x
∈
R
n
∣
L
i
k
-
1
≤
x
i
≤
U
i
k
-
1
,
i
∈
I
}, where L
i
k
-
1
<
U
i
k
-
1 for all i
∈
I. The procedure for forming a bisection of ratio α of Ω
k
-
1 into two subrectangles Ω
-
k
-
1 and Ω
-
-
2
k
-
1 can be described as follows.(1)
Let(8)
j
=
argmax
{
U
i
k
-
1
-
L
i
k
-
1
,
i
∈
I
}
.
(2)
Lett
j satisfy
(9)
min
⁡
{
t
j
-
L
j
k
-
1
,
U
j
k
-
1
-
t
j
}
=
α
(
U
j
k
-
1
-
L
j
k
-
1
)
,
0
<
α
≤
0.5
.
(3)
Let(10)
Ω
-
k
-
1
=
{
x
∈
R
n
∣
L
i
k
-
1
≤
x
i
≤
U
i
k
-
1
,
m
m
m
m
m
i
≠
j
,
L
j
k
-
1
≤
x
j
≤
t
j
,
i
∈
I
{
x
∈
R
n
∣
L
i
k
-
1
≤
x
i
≤
U
i
k
-
1
,
}
,
Ω
-
-
k
-
1
=
{
x
∈
R
n
∣
L
i
k
-
1
≤
x
i
≤
U
i
k
-
1
,
m
m
m
m
m
i
≠
j
,
t
j
≤
x
j
≤
U
j
k
-
1
,
i
∈
I
}
.Clearly, if α
=
0.5, then the bisection of ratio α is the standard bisection rule.


## 3.2. Linearization Strategy

For each rectangleΩ
=
{
x
∈
R
n
∣
L
i
≤
x
i
≤
U
i
,
i
∈
I
}
⊆
R
n created by the branching process, the purpose of this linearization strategy is to obtain a lower bound LB
(
Ω
) for the optimal value of the problem (
RCP
(
Ω
)
).For each rectangleΩ created by the branching process, the lower bound LB
(
Ω
) is found by solving a single linear relaxation programming (
LRP
(
Ω
)
) of problem (
RCP
(
Ω
)
). To derive the (
LRP
(
Ω
)
), we adopt two-part linearization method. In the first part, we will derive the lower bounding functions and the upper bounding function of each function ln
⁡
(
exp
⁡
(
A
j
k
x
+
b
j
k
)
). Then, in the second part, we will derive the linear lower bounding function (LLBF) and linear upper bounding function (LUBF) for each sum term of exp
⁡
(
d
j
k
l
x
+
b
j
k
l
). All the details of this procedure will be given below.First-part linearization: it is well known that the functionln
⁡
(
Y
) is a concave function about the single variable Y
∈
[
Y
_
,
Y
¯
]. Let L
(
ln
⁡
(
Y
)
) and U
(
ln
⁡
(
Y
)
) denote the (LLBF) and (LUBF) of ln
⁡
(
Y
) over the interval [
Y
_
,
Y
¯
], respectively. Then, from the concavity of ln
⁡
(
Y
), it follows that
(11)
L
(
ln
⁡
(
Y
)
)
=
K
1
(
Y
-
Y
_
)
+
ln
⁡
(
Y
_
)
≤
ln
⁡
(
Y
)
,
(12)
U
(
ln
⁡
(
Y
)
)
=
K
1
Y
-
1
-
ln
⁡
K
1
≥
ln
⁡
(
Y
)
,
where K
1
=
(
ln
⁡
Y
¯
-
ln
⁡
Y
_
)
/
(
Y
¯
-
Y
_
).Next, to help to derive the (LLBF) and the (LUBF) of each functionF
j
(
x
), we need to introduce some notations. For any x
∈
Ω, let
(13)
Y
j
k
l
Ω
=
d
j
k
l
x
+
b
j
k
l
with d
j
k
l
T
=
(
a
j
k
l
i
,
…
,
a
j
k
l
n
)
T
∈
R
n; then we have Y
j
k
l
Ω
∈
[
Y
_
j
k
l
Ω
,
Y
¯
j
k
l
Ω
], where
(14)
Y
_
j
k
l
Ω
=
∑
i
=
1
n
‍
min
⁡
{
a
j
k
l
i
L
i
,
a
j
k
l
i
U
i
}
+
b
j
k
l
,
Y
¯
j
k
l
Ω
=
∑
i
=
1
n
‍
max
⁡
{
a
j
k
l
i
L
i
,
a
j
k
l
i
U
i
}
+
b
j
k
l
.
Moreover, let
(15)
η
j
k
Ω
=
∑
l
=
1
m
j
‍
exp
⁡
(
Y
j
k
l
Ω
)
=
exp
⁡
(
A
j
k
x
+
b
j
k
)
;
this will imply η
j
k
Ω
∈
[
η
_
j
k
Ω
,
η
¯
j
k
Ω
], where η
_
j
k
Ω
=
∑
l
=
1
m
j
exp
⁡
(
Y
_
j
k
l
Ω
) and η
¯
j
k
Ω
=
∑
l
=
1
m
j
exp
⁡
(
Y
¯
j
k
l
Ω
). Denote
(16)
K
j
k
Ω
=
ln
⁡
η
¯
j
k
Ω
-
ln
⁡
η
_
j
k
Ω
η
¯
j
k
Ω
-
η
_
j
k
Ω
.
Thus, from (11), it follows that the lower bounding function of ln
⁡
(
exp
⁡
(
A
j
k
x
+
b
j
k
)
) over Ω, denoted as L
j
k
L
(
x
), has the following form:
(17)
L
j
k
L
(
x
)
=
K
j
k
Ω
(
exp
⁡
(
A
j
k
x
+
b
j
k
)
-
η
_
j
k
Ω
)
+
ln
⁡
(
η
_
j
k
Ω
)
=
K
j
k
Ω
(
∑
l
=
1
m
j
‍
exp
⁡
(
d
j
k
l
x
+
b
j
k
l
)
-
η
_
j
k
Ω
)
+
ln
⁡
(
η
_
j
k
Ω
)
.
Similarly, from (12) the upper bounding function of ln
⁡
(
exp
⁡
(
A
j
k
x
+
b
j
k
)
) over Ω, denoted as L
j
k
U
(
x
), is as follows:
(18)
L
j
k
U
(
x
)
=
K
j
k
Ω
exp
⁡
(
A
j
k
x
+
b
j
k
)
-
1
-
ln
⁡
(
K
j
k
Ω
)
=
K
j
k
Ω
∑
l
=
1
m
j
‍
exp
⁡
(
d
j
k
l
x
+
b
j
k
l
)
-
1
-
ln
⁡
(
K
j
k
Ω
)
.
Based on the previous results, we have
(19)
L
j
k
L
(
x
)
≤
ln
⁡
(
exp
⁡
(
A
j
k
x
+
b
j
k
)
)
≤
L
j
k
U
(
x
)
,
∀
x
∈
Ω
.
Therefore, for each j
∈
{
0,1
,
…
,
p
}, the first-part lower bounding function of F
j
(
x
) in (7), denoted by L
j
(
x
), can be given by
(20)
L
j
(
x
)
=
∑
k
=
1
T
j
‍
γ
j
k
[
K
j
k
Ω
(
∑
l
=
1
m
j
‍
exp
⁡
(
d
j
k
l
x
+
b
j
k
l
)
-
η
_
j
k
Ω
)
m
m
m
m
+
ln
⁡
(
η
_
j
k
Ω
)
∑
l
=
1
m
j
‍
]
,
and the first-part upper bounding function of F
p
+
1
(
x
) in (7), denoted by U
p
+
1
(
x
), is as follows:
(21)
U
p
+
1
(
x
)
=
∑
k
=
1
T
p
+
1
‍
γ
p
+
1
,
k
[
K
p
+
1
,
k
Ω
∑
l
=
1
m
p
+
1
‍
exp
⁡
(
d
p
+
1
,
k
l
x
+
b
p
+
1
,
k
l
)
mmmmmm
-
1
-
ln
⁡
(
K
p
+
1
,
k
Ω
)
∑
l
=
1
m
p
+
1
‍
]
.Second-part linearization: with a similar method, we can derive the corresponding (LLBF) and (LUBF) of the functionexp
⁡
(
Y
) over the interval [
Y
L
,
Y
U
] such that
(22)
K
2
(
1
+
Y
-
ln
⁡
K
2
)
≤
exp
⁡
(
Y
)
≤
K
2
(
Y
-
Y
L
)
+
exp
⁡
(
Y
L
)
,
where
(23)
K
2
=
exp
⁡
(
Y
U
)
-
exp
⁡
(
Y
L
)
Y
U
-
Y
L
.
From (22), we can derive the (LLBF) and (LUBF) of exp
⁡
(
Y
j
k
l
) over Ω as follows:
(24)
exp
⁡
(
Y
j
k
l
)
=
exp
⁡
(
d
j
k
l
x
+
b
j
k
l
)
≥
B
j
k
l
Ω
(
1
-
ln
⁡
(
B
j
k
l
Ω
)
+
d
j
k
l
x
+
b
j
k
l
)
,
exp
⁡
(
Y
j
k
l
)
=
exp
⁡
(
d
j
k
l
x
+
b
j
k
l
)
≤
C
j
k
l
Ω
+
B
j
k
l
Ω
(
d
j
k
l
x
+
b
j
k
l
)
,
where
(25)
B
j
k
l
Ω
=
exp
⁡
(
Y
¯
j
k
l
Ω
)
-
exp
⁡
(
Y
_
j
k
l
Ω
)
Y
¯
j
k
l
Ω
-
Y
_
j
k
l
Ω
,
C
j
k
l
Ω
=
Y
¯
j
k
l
Ω
exp
⁡
(
Y
_
j
k
l
Ω
)
-
Y
_
j
k
l
Ω
exp
⁡
(
Y
¯
j
k
l
Ω
)
Y
¯
j
k
l
Ω
-
Y
_
j
k
l
Ω
.
Then, for each j
∈
{
0,1
,
…
,
p
}, substitute each term exp
⁡
(
d
j
k
l
x
+
b
j
k
l
) in (20) by B
j
k
l
Ω
(
1
-
ln
⁡
(
B
j
k
l
Ω
)
+
d
j
k
l
x
+
b
j
k
l
). We may derive the (LLBF) of F
j
(
x
) over Ω, denoted as LF
j
(
x
), being the following form:
(26)
LF
j
(
x
)
=
∑
k
=
1
T
j
‍
γ
j
k
{
K
j
k
Ω
[
∑
l
=
1
m
j
‍
B
j
k
l
Ω
(
1
-
ln
⁡
(
B
j
k
l
Ω
)
+
d
j
k
l
x
+
b
j
k
l
)
]
m
m
m
m
m
m
-
K
j
k
Ω
η
_
j
k
Ω
+
ln
⁡
(
η
_
j
k
Ω
)
∑
l
=
1
m
j
‍
}
,
and it follows that LF
j
(
x
)
≤
F
j
(
x
) for all x
∈
Ω
,
j
=
0,1
,
…
,
p.Ifj
=
p
+
1, substitute the terms exp
⁡
(
d
p
+
1
,
k
l
x
+
b
p
+
1
,
k
l
) in (21) by C
p
+
1
,
k
l
Ω
+
B
p
+
1
,
k
l
Ω
(
d
p
+
1
,
k
l
x
+
b
p
+
1
,
k
l
). We can get the (LUBF) of F
p
+
1
(
x
) over Ω, denoted as UF
p
+
1
(
x
), as follows:
(27)
UF
p
+
1
(
x
)
=
∑
k
=
1
T
p
+
1
‍
γ
p
+
1
,
k
m
m
m
m
×
[
K
p
+
1
,
k
Ω
∑
l
=
1
m
p
+
1
‍
(
C
p
+
1
,
k
l
Ω
+
B
p
+
1
,
k
l
Ω
(
d
p
+
1
,
k
l
x
+
b
p
+
1
,
k
l
)
)
m
m
m
m
m
m
mmmmm
-
1
-
ln
⁡
(
K
p
+
1
,
k
Ω
)
∑
l
=
1
m
p
+
1
‍
]
,
and it follows that UF
p
+
1
(
x
)
≥
F
p
+
1
(
x
) for all x
∈
Ω.From the above discussion for the two kinds of constraints, respectively, we can construct the corresponding linear relaxation programming(
LRP
(
Ω
)
) of problem (
RCP
(
Ω
)
) as follows:
(28)
(
LRP
(
Ω
)
)
{
min
⁡
LF
0
(
x
)
s
.
t
.
LF
j
(
x
)
≤
0
,
j
=
1
,
…
,
p
,
UF
p
+
1
(
x
)
≥
0
,
x
∈
Ω
=
{
x
∣
L
i
≤
x
i
≤
U
i
,
i
∈
I
}
.
Obviously, after the functions are replaced by the corresponding linear functions, the feasible region of problem (
RCP
(
Ω
)
) will be contained in the new feasible region of the (
LRP
(
Ω
)
), and we can have the following lemma.Lemma 2.
Assume thatL
B
(
Ω
) is the minimum of the problem (
L
R
P
(
Ω
)
); then L
B
(
Ω
) provides a lower bound for the optimal value of the problem (
R
C
P
(
Ω
)
).


## 3.3. Global Solution Location and Upper Bound Updating

As is known, in the general branch-and-bound algorithm, to update the upper boundU
* of the optimal value for problem (RCP), the usual method is enclosing all feasible points found while computing the lower bounds of the optimum of the primal problem (RCP). In this paper, we will adopt a new method to update the upper bounds, which is different from the usual method. Toward this end, firstly, we will give the global solution location.LetS
=
{
x
∣
F
j
(
x
)
≤
0
,
j
=
1
,
…
,
p
} and G
=
{
x
∣
F
p
+
1
(
x
)
<
0
}. Since the function F
j
(
x
)
,
j
=
1
,
…
,
p
+
1, are all convex, both sets S and G are convex. It is clear that the feasible region of the problem (RCP) lies in the set S
∖
G. In the problem (RCP), there are two cases at the global solution denoted by x
*.Case 1.
We haveF
p
+
1
(
x
*
)
>
0.Case 2.
We haveF
p
+
1
(
x
*
)
=
0.In the case 1, the reverse convex constraint at the global solutionx
* is called a nonactive constraint; this nonactive constraint can vanish in the primal problem, so the problem (RCP) is equivalent to the following problem:
(29)
(
RCP
1
)
{
min
⁡
F
0
(
x
)
s
.
t
.
F
j
(
x
)
≤
0
,
j
=
1
,
…
,
p
,
x
∈
Ω
-
=
{
x
∣
L
-
i
≤
x
i
≤
U
-
i
,
i
∈
I
}
,
which is a convex programming and can be solved by many effective algorithms. Obviously, if the optimal solution x
* to the above problem satisfies the constraint F
p
+
1
(
x
*
)
≥
0, then it will solve (RCP).In the case 2, the problem (RCP) is equivalent to the following problem:(30)
(
RCP
2
)
{
min
⁡
F
0
(
x
)
s
.
t
.
F
j
(
x
)
≤
0
,
j
=
1
,
…
,
p
,
F
p
+
1
(
x
)
=
0
,
x
∈
Ω
-
=
{
x
∣
L
-
i
≤
x
i
≤
U
-
i
,
i
∈
I
}
.
In this case, we will always have the following assumption.Assumption 1.
A pointx
′ is available such that x
′
∈
S, F
p
+
1
(
x
′
)
<
0, F
0
(
x
′
)
<
min
⁡
{
F
0
(
x
)
:
x
∈
S
∖
G
}.Clearly, if pointx
′ does not exist, then we only need to solve the problem (RCP1) to obtain the solution of the primal problem (RCP).In this paper, we will make our efforts to solve the problem in Case2. It is expedient to indicate some immediate consequences of the above assumption which will locate the solution of (RCP).Let∂
G denote the bounding of G; that is, ∂
G
=
{
x
∣
F
p
+
1
(
x
)
=
0
}.For everyx
∈
(
S
∩
Ω
)
∖
G, we can find the point x
^ where the line segment [
x
′
;
x
] meets ∂
G. Clearly it is as follows: x
^
=
t
x
+
(
1
-
t
)
x
′ with t
∈
(
0,1
], which can be determined from the following equation:
(31)
F
p
+
1
(
x
^
)
=
0
,
that
is
F
p
+
1
(
t
x
+
(
1
-
t
)
x
′
)
=
0
.Because of the convexity ofS, and both the points x and x
′ are in the set S, x
^ is in the set S too.Lemma 3.
For everyx
∈
S
∩
Ω such that F
p
+
1
(
x
)
>
0, one has F
0
(
x
^
)
<
F
0
(
x
).Proof.
SinceF
0
(
x
′
)
<
0, and x
^
=
t
x
+
(
1
-
t
)
x
′, from the convexity of F
0
(
x
) and Assumption 1, we have
(32)
F
0
(
x
^
)
≤
t
F
0
(
x
)
+
(
1
-
t
)
F
0
(
x
′
)
<
t
F
0
(
x
)
+
(
1
-
t
)
F
0
(
x
)
=
F
0
(
x
)
.Corollary 4.
Under Assumption1, if x
* is the optimal solution of problem (RCP), it lies on S
∩
∂
G.According to the discussion of Lemma3 and Corollary 4, we know that the optimal solution must lie on the boundary, so once a feasible point x is found, we will firstly compute the point x
^ which lies on S
∩
∂
G and satisfying F
0
(
x
^
)
<
F
0
(
x
), then the upper bound U
* of the optimal value for problem (RCP) is updated as
(33)
U
*
=
min
⁡
{
U
*
,
F
0
(
x
^
)
}
.
Hence, once a better upper bound U
* is updated, the number of the deleted nodes will increase, and the unnecessary branching and bounding on some regions where the global solution does not exist will decrease greatly.


## 3.4. Reduction Cut

In this subsection, we pay our attention to how to form the bound reduction technique to accelerate the convergence of the proposed global optimization algorithm.Assume thatU
* is a current known upper bound of the optimal objective value of the problem (RCP). For any Ω
=
(
Ω
i
)
n
×
1
⊆
Ω
- with Ω
i
=
[
L
i
,
U
i
], consider the problem (
LRP
(
Ω
)
). For the sake of convenience, let the objective function and linear constraint functions of (
LRP
(
Ω
)
) be expressed as
(34)
LF
0
(
x
)
=
∑
i
=
1
n
‍
c
i
x
i
+
D
,
LF
j
(
x
)
=
∑
i
=
1
n
‍
q
j
i
x
i
-
r
j
,
j
=
1
,
…
,
p
,
-
UF
p
+
1
=
∑
i
=
1
n
‍
q
p
+
1
,
i
x
i
-
r
p
+
1
.
Then, from (26) and (27) it follows that
(35)
(
c
1
,
…
,
c
n
)
T
=
∑
k
=
1
T
0
‍
γ
0
k
K
0
k
Ω
∑
l
=
1
m
0
‍
B
0
k
l
Ω
d
0
k
l
,
D
=
∑
k
=
1
T
0
‍
γ
0
k
{
K
0
k
Ω
[
∑
l
=
1
m
0
‍
B
0
k
l
Ω
(
1
-
ln
⁡
(
B
0
k
l
Ω
)
+
b
0
k
l
)
]
m
m
m
m
m
m
n
-
K
0
k
Ω
η
_
0
k
Ω
+
ln
⁡
(
η
_
0
k
Ω
)
∑
l
=
1
m
0
‍
}
,
r
j
=
∑
k
=
1
T
j
‍
γ
j
k
{
-
K
j
k
Ω
[
∑
l
=
1
m
j
‍
B
j
k
l
Ω
(
1
-
ln
⁡
(
B
j
k
l
Ω
)
+
b
j
k
l
)
]
m
m
m
m
m
m
n
+
K
j
k
Ω
η
_
j
k
Ω
-
ln
⁡
(
η
_
j
k
Ω
)
∑
l
=
1
m
j
‍
}
,
j
=
1
,
…
,
p
,
r
p
+
1
=
∑
k
=
1
T
p
+
1
‍
γ
p
+
1
,
k
[
K
p
+
1
,
k
Ω
∑
l
=
1
m
p
+
1
‍
(
C
p
+
1
,
k
l
Ω
+
B
p
+
1
,
k
l
Ω
b
p
+
1
,
k
l
)
m
m
m
m
m
m
m
m
m
n
-
1
-
ln
⁡
(
K
p
+
1
,
k
Ω
)
∑
l
=
1
m
p
+
1
‍
]
,
(
q
j
1
,
…
,
q
j
n
)
T
=
∑
k
=
1
T
j
‍
γ
j
k
K
j
k
Ω
∑
l
=
1
m
j
‍
B
j
k
l
Ω
d
j
k
l
,
m
m
m
m
m
m
m
m
m
m
m
m
n
j
=
1
,
…
,
p
,
(
q
p
+
1,1
,
…
,
q
p
+
1
,
n
)
T
=
-
∑
k
=
1
T
p
+
1
‍
γ
p
+
1
,
k
K
p
+
1
,
k
Ω
m
m
m
m
m
m
m
m
m
m
m
×
∑
l
=
1
m
p
+
1
‍
B
p
+
1
,
k
l
Ω
d
p
+
1
,
k
l
.In the following, some notations are introduced as follows:(36)
r
C
=
∑
i
=
1
n
‍
min
⁡
{
c
i
L
i
,
c
i
U
i
}
,
r
L
j
=
∑
i
=
1
n
‍
min
⁡
{
q
j
i
L
i
,
q
j
i
U
i
}
,
ρ
i
=
U
*
-
r
C
-
D
+
min
⁡
{
c
i
L
i
,
c
i
U
i
}
,
δ
j
i
=
r
j
-
r
L
j
+
min
⁡
{
q
j
i
L
i
,
q
j
i
U
i
}
,
where j
=
1
,
…
,
p
+
1
,
i
∈
I.Based on the optimality and feasibility of the problem (RCP), we can give two theorems below to determine the region in which it is guaranteed that there is no optimal solution; thus a reduction cut technique is formed from these theorems.Theorem 5.
For any subrectangleΩ
=
(
Ω
i
)
n
×
1
⊆
Ω
- with Ω
i
=
[
L
i
,
U
i
], the following statements hold.(i)
Ifr
C
+
D
>
U
*, then there exists no optimal solution of the problem (RCP) over the subrectangle Ω.
(ii)
Ifr
C
+
D
≤
U
*, consider the following two cases: if there exists some t
∈
I satisfying c
t
>
0 and ρ
t
<
c
t
U
t, then there is no optimal solution of (RCP) over Ω
a
=
(
Ω
a
i
)
n
×
1; conversely, if c
t
<
0 and ρ
t
<
c
t
L
t for some t, then there does not exist global optimal solution of (RCP) over Ω
b
=
(
Ω
b
i
)
n
×
1, where
(37)
Ω
a
i
=
{
Ω
i
,
i
f
i
≠
t
,
(
ρ
t
c
t
,
U
t
]
⋂
‍
Ω
t
,
i
f
i
=
t
,
Ω
b
i
=
{
Ω
i
,
i
f
i
≠
t
,
[
L
t
,
ρ
t
c
t
)
⋂
‍
Ω
t
,
i
f
i
=
t
.Theorem 6.
For anyΩ
=
(
Ω
i
)
n
×
1
⊆
Ω
- with Ω
i
=
[
L
i
,
U
i
], if r
L
j
-
r
j
>
0 for some j
∈
{
1
,
…
,
p
+
1
}, then there exists no optimal solution of problem (RCP) over Ω; otherwise, for each j
∈
{
1
,
…
,
p
+
1
}, consider the following two cases.(i)
If there exists somet
∈
I
a
n
d
j
∈
{
1
,
…
,
p
+
1
} satisfying q
j
t
>
0 and δ
j
t
<
q
j
t
U
t, then there is not optimal solution of the problem (RCP) over Ω
c
=
(
Ω
c
i
)
n
×
1.
(ii)
Ifq
j
t
<
0 and δ
j
t
<
q
j
t
L
t for some t
∈
I
a
n
d
s
o
m
e
j
∈
{
1
,
…
,
p
+
1
}, then no optimal solution of the problem (RCP) over Ω
d
=
(
Ω
d
i
)
n
×
1 exists, where
(38)
Ω
c
i
=
{
Ω
i
,
i
f
i
≠
t
,
(
δ
j
t
q
j
t
,
U
t
]
⋂
‍
Ω
t
,
i
f
i
=
t
,
Ω
d
i
=
{
Ω
i
,
i
f
i
≠
t
,
[
L
t
,
δ
j
t
q
j
t
)
⋂
‍
Ω
t
,
i
f
i
=
t
.Note that the proof of Theorems5 and 6 is similar to the one of Theorems 1 and 2 in [26]; therefore it is omitted.Reduction Cut(S1) Optimality Cut. Compute r
C
+
D. If r
C
+
D
>
U
*, and let Ω
=
∅; otherwise compute c
i
(
i
=
1
,
…
,
n
). If c
t
>
0 and ρ
t
<
c
t
U
t for some t
∈
I, then let U
t
=
ρ
t
/
c
t and Ω
=
(
Ω
i
)
n
×
1 with Ω
i
=
[
L
i
,
U
i
]
(
i
=
1
,
…
,
n
). If c
t
<
0 and ρ
t
<
c
t
L
t for some t
∈
I, then let L
t
=
ρ
t
/
c
t and Ω
=
(
Ω
i
)
n
×
1 with Ω
i
=
[
L
i
,
U
i
]
(
i
=
1
,
…
,
n
).(S2) Feasibility Cut. For any j
=
1
,
…
,
p, compute LF
j
(
x
)
j and -
UF
p
+
1
(
x
). If r
L
j
-
r
j
>
0 for some j
∈
{
1
,
…
,
p
+
1
}, then let Ω
=
∅; otherwise compute q
j
i  (
j
=
1
,
…
,
p
+
1
,
i
=
1
,
…
,
n
). If q
j
t
>
0 and δ
j
t
<
q
j
t
U
t for some j
∈
{
1
,
…
,
p
+
1
} and t
∈
I, then let U
t
=
δ
j
t
/
q
j
t and Ω
=
(
Ω
i
)
n
×
1 with Ω
i
=
[
L
i
,
U
i
]
(
i
=
1
,
…
,
n
). If q
j
t
<
0 and δ
j
t
<
q
j
t
L
t for some j
∈
{
1
,
…
,
p
+
1
} and t
∈
I, then let L
t
=
δ
j
t
/
q
j
t and Ω
=
(
Ω
i
)
n
×
1 with Ω
i
=
[
L
i
,
U
i
]
(
i
=
1
,
…
,
n
).This reduction cut provides the possibility to cut away a large part of subrectangleΩ that is currently investigated by the algorithm procedure.


## 4. Algorithm and Its Convergence

Based upon the results and the algorithmic processes discussed in Section3, the basic steps of the proposed global optimization algorithm are summarized as follows.LetLB
(
Ω
) be the optimal objective function value of (
LRP
(
Ω
)
) and x
(
Ω
) refers to an element of the corresponding argmin.


### 4.1. Algorithm Statement

Step 1 (initialization).
(i)
Solve problem (RCP1) with standard convex programming software to obtain the solutionx
′ of problem (RCP1). If F
p
+
1
(
x
)
≥
0, stop with x
′ as the global solution of the primal problem (RCP).
(ii)
Let the set of all active nodesQ
0
=
{
Ω
-
}, the convergence tolerance ϵ
>
0, the bisection ratio α
∈
(
0,0.5
], the upper bound U
*
=
∞, and the iteration counter k
:
=
0.
(iii)
Find an optimal solutionx
(
Ω
-
) and the optimal value LB
(
Ω
-
) for problem (
LRP
(
Ω
-
)
). If x
(
Ω
-
)
∈
(
D
⋂
‍
Ω
-
)
∖
G, compute x
^
(
Ω
-
) as given in Section 3.3; set U
*
=
F
0
(
x
^
(
Ω
-
)
). Set the initial lower bound LB
(
0
)
=
LB
(
Ω
-
).
(iv)
IfU
*
-
LB
(
0
)
≤
ϵ, then stop; x
^
(
Ω
-
) is a global ϵ-optimal solutions for problem (RCP). Otherwise, go to Step 2.Step 2 (updating the upper bound).
Select the midpointx
mid of Ω
k; if x
mid is feasible to (
RCP
(
Ω
k
)
), then compute x
^
(
Ω
k
) as given in Section 3.3; update the upper bound U
*
=
min
⁡
{
U
*
,
F
0
(
x
^
(
Ω
k
)
)
}.Step 3 (reduction).
For the subrectangleΩ
k that is currently investigated, we use the reduction cut described in Section 3 to cut away Ω
k and the remaining part is still denoted as Ω
k.Step 4 (branching).
Using the strategy of bisection of ratioα described in Section 3.1 to get two new subrectangles and denote the set of new partition rectangles as X
-
k. For each Ω
∈
X
-
k, compute the lower bound f
j
l
:
=
min
⁡
x
∈
Ω
LF
j
(
x
)
,
j
=
0,1
,
…
,
p and f
p
+
1
u
:
=
max
⁡
x
∈
Ω
UF
p
+
1
(
x
). If there exists some j
∈
{
0,1
,
…
,
p
} such that one of the lower bounds f
j
l satisfies f
0
l
>
U
* or f
j
l
>
0 for some j
∈
{
1
,
…
,
p
} or f
p
+
1
u
<
0, then the corresponding subrectangle Ω is eliminated from X
-
k; that is, X
-
k
:
=
X
-
k
∖
Ω, and skip to the next element of X
-
k.Step 5 (bounding).
IfX
-
k
≠
∅, solve problem (
LRP
(
Ω
)
) to obtain x
(
Ω
) and LB
(
Ω
) for each Ω
∈
X
-
k. If LB
(
Ω
)
>
U
*, set X
-
k
:
=
X
-
k
∖
Ω. Otherwise, if x
(
Ω
)
∈
(
D
⋂
‍
Ω
)
∖
G, then compute x
^
(
Ω
); update the upper bound U
*
=
min
⁡
{
U
*
,
F
0
(
x
^
(
Ω
)
)
} and update x
* such that F
0
(
x
*
)
=
U
*. The partition set remaining is now Q
k
:
=
(
Q
k
∖
Ω
k
)
∪
X
-
k and a new lower bound is now LB
(
k
)
:
=
min
⁡
{
LB
(
Ω
)
∣
Ω
∈
Q
k
}.Step 6 (convergence checking).
SetQ
k
+
1
=
Q
k
∖
{
Ω
∣
LB
(
Ω
)
≥
U
*
-
ϵ
,
Ω
∈
Q
k
}. If Q
k
+
1
=
∅, then stop with U
* as the optimal value and x
* as the optimal solution. Otherwise, select an active node Ω
k
+
1 such that Ω
k
+
1
=
argmin
{
LB
(
Ω
)
∣
Ω
∈
Q
k
+
1
} for further consideration. Set k
:
=
k
+
1 and return to Step 2.Next, we give the global convergence of the above algorithm. If the algorithm does not stop finitely, then the branching rule guarantees all the intervals to an isolated point for the variables.Theorem 7.
For anyΩ
=
{
x
∣
L
i
≤
x
i
≤
U
i
,
i
∈
I
}
⊂
Ω
-, let μ
i
=
U
i
-
L
i
,
∀
i
∈
I; then, for any x
∈
Ω, ∀
j
∈
{
0,1
,
…
,
p
}, one has
(39)
F
j
(
x
)
-
LF
j
(
x
)
⟶
0
,
F
p
+
1
(
x
)
-
UF
p
+
1
(
x
)
⟶
0
,
as μ
i
→
0 for each i
∈
I.Proof.
First, let us consider the casej
=
0,1
,
…
,
p. Let
(40)
Δ
j
=
F
j
(
x
)
-
LF
j
(
x
)
=
Δ
j
1
+
Δ
j
2
,
where Δ
j
1
=
F
j
(
x
)
-
L
j
(
x
)
,
Δ
j
2
=
L
j
(
x
)
-
LF
j
(
x
).
Obviously, if we want to proveΔ
j
→
0 as μ
i
→
0
,
∀
i
∈
I, we only need to prove Δ
j
1
→
0 and Δ
j
2
→
0, as μ
i
→
0
,
∀
i
∈
I.
From (7), (20), and the definition of η
j
k
Ω in (15), we have
(41)
Δ
j
1
=
∑
k
=
1
T
j
‍
γ
j
k
ln
⁡
(
exp
⁡
(
A
j
k
x
+
b
j
k
)
)
-
∑
k
=
1
T
j
‍
γ
j
k
[
K
j
k
Ω
(
exp
⁡
(
A
j
k
x
+
b
j
k
)
-
η
_
j
k
Ω
)
+
ln
⁡
(
η
_
j
k
Ω
)
]
=
∑
k
=
1
T
j
‍
γ
j
k
[
ln
⁡
(
η
j
k
Ω
)
-
K
j
k
Ω
(
η
j
k
Ω
-
η
_
j
k
Ω
)
-
ln
⁡
(
η
_
j
k
Ω
)
]
.
Since Δ
j
1 is a concave function about η
j
k
Ω for any η
j
k
Ω
∈
[
η
_
j
k
Ω
,
η
¯
j
k
Ω
], it can attain the maximum at the point η
j
k
Ω
=
1
/
K
j
k
Ω. Let z
j
k
=
η
¯
j
k
Ω
/
η
_
j
k
Ω; then by computing we have
(42)
max
⁡
x
∈
Ω
Δ
j
1
=
∑
k
=
1
T
j
‍
γ
j
k
[
-
ln
⁡
K
j
k
Ω
-
1
+
K
j
k
Ω
η
_
j
k
Ω
-
ln
⁡
η
_
j
k
Ω
]
=
∑
k
=
1
T
j
‍
γ
j
k
[
ln
⁡
z
j
k
-
1
ln
⁡
z
j
k
-
1
+
ln
⁡
z
j
k
z
j
k
-
1
]
.
By the definition of z
j
k, if μ
i
→
0
,
∀
i
∈
I, we have z
j
k
→
1, which implies that max
⁡
x
∈
Ω
Δ
j
1
→
0 as μ
i
→
0
,
∀
i
∈
I. Therefore, we can obtain that
(43)
Δ
j
1
⟶
0
as
μ
i
⟶
0
,
∀
i
∈
I
.
Next, we will proveΔ
j
2
→
0, as μ
i
→
0
,
∀
i
∈
I. From (20) and (26), we have
(44)
Δ
j
2
=
∑
k
=
1
T
j
‍
γ
j
k
[
K
j
k
Ω
(
∑
l
=
1
m
j
‍
exp
⁡
(
d
j
k
l
x
+
b
j
k
l
)
-
η
_
j
k
Ω
)
m
m
m
m
m
+
ln
⁡
(
η
_
j
k
Ω
)
∑
l
=
1
m
j
‍
]
-
∑
k
=
1
T
j
‍
γ
j
k
{
K
j
k
Ω
[
∑
l
=
1
m
j
‍
(
B
j
k
l
Ω
(
1
-
ln
⁡
(
B
j
k
l
Ω
)
+
d
j
k
l
x
+
b
j
k
l
)
)
m
m
m
m
m
m
m
m
m
m
-
η
_
j
k
Ω
∑
l
=
1
m
j
‍
]
+
ln
⁡
(
η
_
j
k
Ω
)
}
=
∑
k
=
1
T
j
‍
γ
j
k
{
∑
l
=
1
m
j
‍
K
j
k
Ω
m
m
m
m
m
×
[
∑
l
=
1
m
j
‍
exp
⁡
(
d
j
k
l
x
+
b
j
k
l
)
mmmmmmn
-
∑
l
=
1
m
j

(

B
j
k
l
Ω
‍
(
1

-

ln
⁡
(
B
j
k
l
Ω
)

+

d
j
k
l
x

+

b
j
k
l
)
)
∑
l
=
1
m
j
‍
]
}
.
Now, let us denote
(45)
Δ
j
k
21
=
∑
l
=
1
m
j
‍
[
exp
⁡
(
d
j
k
l
x
+
b
j
k
l
)
m
m
m
m
-
B
j
k
l
Ω
(
1
-
ln
⁡
(
B
j
k
l
Ω
)
+
d
j
k
l
x
+
b
j
k
l
)
]
=
∑
l
=
1
m
j
‍
[
exp
⁡
(
Y
j
k
l
Ω
)
-
B
j
k
l
Ω
(
1
-
ln
⁡
(
B
j
k
l
Ω
)
+
Y
j
k
l
Ω
)
]
,
Δ
j
k
l
22
(
Y
j
k
l
Ω
)
=
exp
⁡
(
Y
j
k
l
Ω
)
-
B
j
k
l
Ω
(
1
-
ln
⁡
(
B
j
k
l
Ω
)
+
Y
j
k
l
Ω
)
.
Then Δ
j
2 can be rewritten in the following form:
(46)
Δ
j
2
=
∑
k
=
1
T
j
‍
γ
j
k
K
j
k
Ω
∑
l
=
1
m
j
‍
Δ
j
k
l
22
.
Since Δ
j
k
l
22 is a convex function about Y
j
k
l
Ω
=
d
j
k
l
x
+
b
j
k
l over the interval [
Y
_
j
k
l
Ω
,
Y
¯
j
k
l
Ω
], it follows that Δ
j
k
l
22 can attain the maximum max
⁡
x
∈
Ω
Δ
j
k
l
22 at the point Y
_
j
k
l
Ω or Y
¯
j
k
l
Ω. Let u
j
k
l
=
Y
¯
j
k
l
Ω
-
Y
_
j
k
l
Ω and v
j
k
l
=
(
exp
⁡
(
u
j
k
l
)
-
1
)
/
u
j
k
l, then through computing, we can derive that
(47)
Δ
j
k
l
22
(
Y
_
j
k
l
Ω
)
=
exp
⁡
(
Y
_
j
k
l
Ω
)
-
B
j
k
l
Ω
(
1
-
ln
⁡
(
B
j
k
l
Ω
)
+
Y
_
j
k
l
Ω
)
=
exp
⁡
⁡
(
Y
_
j
k
l
Ω
)
-
exp
⁡
⁡
(
Y
¯
j
k
l
Ω
)
-
exp
⁡
⁡
(
Y
_
j
k
l
Ω
)
Y
¯
j
k
l
Ω
-
Y
_
j
k
l
Ω
×
(
1
-
ln
⁡
exp
⁡
⁡
(
Y
¯
j
k
l
Ω
)
-
exp
⁡
⁡
(
Y
_
j
k
l
Ω
)
Y
¯
j
k
l
Ω
-
Y
_
j
k
l
Ω
+
Y
_
j
k
l
Ω
)
=
exp
⁡
(
Y
_
j
k
l
Ω
)
(
1
-
v
j
k
l
(
1
-
ln
⁡
v
j
k
l
)
)
,
Δ
j
k
l
22
(
Y
¯
j
k
l
Ω
)
=
exp
⁡
(
Y
¯
j
k
l
Ω
)
-
B
j
k
l
Ω
(
1
-
ln
⁡
(
B
j
k
l
Ω
)
+
Y
¯
j
k
l
Ω
)
=
exp
⁡
(
Y
¯
j
k
l
Ω
)
-
exp
⁡
⁡
(
Y
¯
j
k
l
Ω
)
-
exp
⁡
⁡
(
Y
_
j
k
l
Ω
)
Y
¯
j
k
l
Ω
-
Y
_
j
k
l
Ω
×
(
1
-
ln
⁡
exp
⁡
⁡
(
Y
¯
j
k
l
Ω
)
-
exp
⁡
⁡
(
Y
_
j
k
l
Ω
)
Y
¯
j
k
l
Ω
-
Y
_
j
k
l
Ω
+
Y
¯
j
k
l
Ω
)
=
exp
⁡
⁡
(
Y
¯
j
k
l
Ω
)
-
exp
⁡
(
Y
_
j
k
l
Ω
)
v
j
k
l
(
1
-
ln
⁡
v
j
k
l
+
Y
¯
j
k
l
Ω
-
Y
_
j
k
l
Ω
)
.
Additionally, by the definitions of Y
_
j
k
l
Ω and Y
¯
j
k
l
Ω, we know that for any j
,
k
,
l,  Y
¯
j
k
l
Ω
-
Y
_
j
k
l
Ω
→
0 and exp
⁡
(
Y
¯
j
k
l
Ω
)
-
exp
⁡
(
Y
_
j
k
l
Ω
)
→
0 as μ
i
→
0
,
∀
i
∈
I, and so, we have v
j
k
l go to 1 as each μ
i approaches zero. This implies that Δ
j
k
l
22
(
Y
_
j
k
l
Ω
)
→
0 and Δ
j
k
l
22
(
Y
¯
j
k
l
Ω
)
→
0 as μ
i
→
0
,
∀
i
∈
I; that is, max
⁡
x
∈
Ω
Δ
j
k
l
22
→
0 as μ
i
→
0
,
∀
i
∈
I. Hence, according to the above discussion, we can follow that
(48)
Δ
j
2
⟶
0
,
as
μ
i
⟶
0
,
∀
i
∈
I
.
Based on the above discussion, for eachj
=
0,1
,
…
,
p, from (40) it follows that
(49)
Δ
j
⟶
0
,
as
μ
i
⟶
0
,
∀
i
∈
I
.
Second, let us considerj
=
p
+
1. Let
(50)
Δ
p
+
1
=
UF
p
+
1
(
x
)
-
F
p
+
1
(
x
)
=
Δ
p
+
1
1
+
Δ
p
+
1
2
,
where Δ
p
+
1
1
=
U
p
+
1
(
x
)
-
F
p
+
1
(
x
),Δ
p
+
1
2
=
UF
p
+
1
(
x
)
-
U
p
+
1
(
x
). By using (7), (21), and the definition of η
p
+
1
,
k
Ω in (15) we have
(51)
Δ
p
+
1
1
=
U
p
+
1
(
x
)
-
F
p
+
1
(
x
)
=
∑
k
=
1
T
p
+
1
‍
γ
p
+
1
,
k
[
K
p
+
1
,
k
Ω
exp
⁡
(
A
p
+
1
,
k
x
+
b
p
+
1
,
k
)
m
m
m
m
m
m
n
-
1
-
ln
⁡
(
K
p
+
1
,
k
Ω
)
]
-
∑
k
=
1
T
p
+
1
‍
γ
p
+
1
,
k
ln
⁡
(
exp
⁡
(
A
p
+
1
,
k
x
+
b
p
+
1
,
k
)
)
=
∑
k
=
1
T
p
+
1
‍
γ
p
+
1
,
k
[
K
p
+
1
,
k
Ω
∑
l
=
1
m
p
+
1
‍
exp
⁡
⁡
(
d
p
+
1
,
k
l
x
+
b
p
+
1
,
k
l
)
mmmmmmmmmmmm
-
1
-
ln
⁡
⁡
(
K
p
+
1
,
k
Ω
)
m
m
m
m
m
m
m
-
ln
⁡
(
∑
l
=
1
m
p
+
1
‍
exp
⁡
(
d
p
+
1
,
k
l
x
+
b
p
+
1
,
k
l
)
)
]
=
∑
k
=
1
T
p
+
1
‍
γ
p
+
1
,
k
[
K
p
+
1
,
k
Ω
η
p
+
1
,
k
Ω
-
1
mmmmmmn
-
ln
⁡
(
K
p
+
1
,
k
Ω
)
-
ln
⁡
(
η
p
+
1
,
k
Ω
)
]
.
Since Δ
p
+
1
1 is a convex function about η
p
+
1
,
k
Ω over the interval [
η
_
p
+
1
,
k
Ω
,
η
¯
p
+
1
,
k
Ω
], it can attain the maximum max
⁡
x
∈
Ω
Δ
p
+
1
1 at the point η
_
p
+
1
,
k
Ω or η
¯
p
+
1
,
k
Ω. Let z
p
+
1
,
k
=
η
¯
p
+
1
,
k
Ω
/
η
_
p
+
1
,
k
Ω; then, by similar discussion as above we can obtain that
(52)
Δ
p
+
1
1
(
η
_
p
+
1
,
k
Ω
)
=
∑
k
=
1
T
p
+
1
‍
γ
p
+
1
,
k
[
K
p
+
1
,
k
Ω
η
_
p
+
1
,
k
Ω
-
1
-
ln
⁡
(
K
p
+
1
,
k
Ω
)
-
ln
⁡
(
η
_
p
+
1
,
k
Ω
)
]
=
∑
k
=
1
T
p
+
1
‍
γ
p
+
1
,
k
(
ln
⁡
z
p
+
1
,
k
-
1
ln
⁡
z
p
+
1
,
k
-
1
+
ln
⁡
z
p
+
1
,
k
z
p
+
1
,
k
-
1
)
,
Δ
p
+
1
1
(
η
¯
p
+
1
,
k
Ω
)
=
∑
k
=
1
T
p
+
1
‍
γ
p
+
1
,
k
[
K
p
+
1
,
k
Ω
η
¯
p
+
1
,
k
Ω
-
1
-
ln
⁡
(
K
p
+
1
,
k
Ω
)
-
ln
⁡
(
η
¯
p
+
1
,
k
Ω
)
]
=
∑
k
=
1
T
p
+
1
‍
γ
p
+
1
,
k
(
ln
⁡
z
p
+
1
,
k
-
1
ln
⁡
z
p
+
1
,
k
m
m
m
m
m
m
m
m
m
-
1
+
z
p
+
1
,
k
ln
⁡
z
p
+
1
,
k
z
p
+
1
,
k
-
1
-
ln
⁡
z
p
+
1
,
k
)
.
Since z
p
+
1
,
k
→
1 as μ
i
→
0
,
∀
i
∈
I, we have that Δ
p
+
1
1
(
η
_
p
+
1
,
k
Ω
)
→
0 and Δ
p
+
1
1
(
η
¯
p
+
1
,
k
Ω
)
→
0; that is, max
⁡
x
∈
Ω
Δ
p
+
1
1
→
0, as μ
i
→
0
,
∀
i
∈
I. Hence, according to the above discussion, we can obtain that
(53)
Δ
p
+
1
1
⟶
0
,
as
μ
i
⟶
0
,
∀
i
∈
I
.
On the other hand, from (27) and (21) it follows that
(54)
Δ
p
+
1
2
=
UF
p
+
1
(
x
)
-
U
p
+
1
(
x
)
=
∑
k
=
1
T
p
+
1
‍
γ
p
+
1
,
k
m
×
[
K
p
+
1
,
k
Ω
∑
l
=
1
m
p
+
1
(
C
p
+
1
,
k
l
Ω
+
B
p
+
1
,
k
l
Ω
(
d
p
+
1
,
k
l
x
+
b
p
+
1
,
k
l
)
)
m
m
m
m
m
m
-
1
-
ln
⁡
(
K
p
+
1
,
k
Ω
)
∑
l
=
1
m
p
+
1
]
-
∑
k
=
1
T
p
+
1
‍
γ
p
+
1
,
k
[
K
p
+
1
,
k
Ω
∑
l
=
1
m
p
+
1
‍
exp
⁡
(
d
p
+
1
,
k
l
x
+
b
p
+
1
,
k
l
)
mmmm
-
1
-
ln
⁡
(
K
p
+
1
,
k
Ω
)
∑
l
=
1
m
p
+
1
‍
]
=
∑
k
=
1
T
p
+
1
‍
γ
p
+
1
,
k
K
p
+
1
,
k
Ω
×
∑
l
=
1
m
p
+
1
‍
[
C
p
+
1
,
k
l
Ω
+
B
p
+
1
,
k
l
Ω
(
d
p
+
1
,
k
l
x
+
b
p
+
1
,
k
l
)
n
-
exp
⁡
(
d
p
+
1
,
k
l
x
+
b
p
+
1
,
k
l
)
]
=
∑
k
=
1
T
p
+
1
‍
γ
p
+
1
,
k
K
p
+
1
,
k
Ω
×
∑
l
=
1
m
p
+
1
‍
[
C
p
+
1
,
k
l
Ω
+
B
p
+
1
,
k
l
Ω
Y
p
+
1
,
k
l
Ω
-
exp
⁡
(
Y
p
+
1
,
k
l
Ω
)
]
.
Now, let us denote
(55)
Δ
p
+
1
,
k
l
21
=
C
p
+
1
,
k
l
Ω
+
B
p
+
1
,
k
l
Ω
Y
p
+
1
,
k
l
Ω
-
exp
⁡
(
Y
p
+
1
,
k
l
Ω
)
;
then, Δ
p
+
1
2 can be rewritten as follows:
(56)
Δ
p
+
1
2
=
∑
k
=
1
T
p
+
1
‍
γ
p
+
1
,
k
K
p
+
1
,
k
Ω
∑
l
=
1
m
p
+
1
‍
Δ
p
+
1
,
k
l
21
.
Since Δ
p
+
1
,
k
l
21 is a concave function about Y
p
+
1
,
k
l
Ω over the interval [
Y
_
p
+
1
,
k
l
Ω
,
Y
¯
p
+
1
,
k
l
Ω
], it attains the maximum max
⁡
x
∈
Ω
Δ
p
+
1
,
k
l
21 at the point Y
p
+
1
,
k
l
Ω
=
ln
⁡
(
B
p
+
1
,
k
l
Ω
). Let u
p
+
1
,
k
l
=
Y
¯
p
+
1
,
k
l
Ω
-
Y
_
p
+
1
,
k
l
Ω and v
p
+
1
,
k
l
=
(
exp
⁡
(
u
p
+
1
,
k
l
)
-
1
)
/
u
p
+
1
,
k
l; then by computing we can get
(57)
max
⁡
x
∈
Ω
Δ
p
+
1
,
k
l
21
=
C
p
+
1
,
k
l
Ω
+
B
p
+
1
,
k
l
Ω
ln
⁡
⁡
(
B
p
+
1
,
k
l
Ω
)
-
B
p
+
1
,
k
l
Ω
=
-
B
p
+
1
,
k
l
Ω
Y
_
p
+
1
,
k
l
Ω
+
exp
⁡
(
Y
_
p
+
1
,
k
l
Ω
)
+
B
p
+
1
,
k
l
Ω
ln
⁡
⁡
(
B
p
+
1
,
k
l
Ω
)
-
B
p
+
1
,
k
l
Ω
=
exp
⁡
(
Y
_
p
+
1
,
k
l
Ω
)
[
v
p
+
1
,
k
l
ln
⁡
v
p
+
1
,
k
l
+
1
-
v
p
+
1
,
k
l
]
.
By the definition of u
p
+
1
,
k
l and v
p
+
1
,
k
l, we have u
p
+
1
,
k
l
→
0 and v
p
+
1
,
k
l
→
1 as μ
i
→
0
,
∀
i
∈
I. This implies that max
⁡
x
∈
Ω
Δ
p
+
1
,
k
l
21
→
0 as μ
i
→
0
,
∀
i
∈
I. Therefore, we have
(58)
Δ
p
+
1
2
⟶
0
,
as
μ
i
⟶
0
,
∀
i
∈
I
.
Thus, by (50) and the above discussion, it is obvious that
(59)
Δ
p
+
1
⟶
0
as
μ
i
⟶
0
,
∀
i
∈
I
.
In summary, according to the above results, the proof is complete.Remark 8.
From Theorem7, it follows that LF
j
(
x
)
,
j
=
0,1
,
…
,
p and UF
p
+
1
(
x
) will approximate the corresponding functions F
j
(
x
)
,
j
=
0,1
,
…
,
p and F
p
+
1
(
x
) as μ
i
→
0
,
∀
i
∈
I.Theorem 9.
(a) If the algorithm is finite, then upon termination, the incumbent solution being optimal to (RCP) is a globalϵ-optimal solution for problem (RCP).
(b) If the algorithm is infinite, then it will generate an infinite sequence of iterations such that along any infinite branch of the branch and bound tree, any accumulation point of the sequence{
x
^
k
} will be the global solution of the problem (RCP).Proof.
(a) If the algorithm is finite, then it terminates in some Stepk, k
≥
0. Without loss of generality, upon termination, the incumbent solution is denoted as x
^
k. By the algorithm, it follows that U
*
-
LB
(
k
)
≤
ϵ. From (iv) of Steps 1 and 6, this implies that F
0
(
x
^
k
)
-
LB
(
k
)
≤
ϵ. Let v denote the optimal value of problem (RCP); then, by Section 3, we know that LB
(
k
)
≤
v. Since x
^
k is a feasible solution of problem (RCP), we have f
(
x
^
k
)
≥
v. Taken together, this implies that
(60)
F
0
(
x
^
k
)
≥
v
≥
LB
(
k
)
≥
F
0
(
x
^
k
)
-
ϵ
.
Therefore, x
^
k is a global ϵ-optimal solution for problem (RCP). And the proof of part (a) is complete.
(b) When the algorithm is infinite, a sufficient condition for a global optimization to be convergent to the global minimum, stated in [28], requires that the bounding operation must be consistent and the selection operation is bound improving.
A bounding operation is called consistent if at every step any unfathomed partition can be further refined, and if any infinitely decreasing sequence of successively refined partition elements satisfies(61)
lim
⁡
k
→
∞
(
UB
k
-
LB
k
)
=
0
,
where UB
k is a computed upper bound in stage k and LB
k is the best lower bound at iteration k not necessarily occurring inside the same subrectangle with UB
k. In the following, we will show that (61) holds.
Since the employed subdivision process is exhaustive. Consequently, from Theorem7 and the relationship V
(
RCP
)
≥
V
(
LRP
), the formulation (61) holds; this implies that the employed bounding operation is consistent.
A selection operation is called the bound improving if at least one partition element where the actual upper bound is attained is selected for further partition after a finite number of refinements. Clearly, the employed selection operation is the bound improving because the partition element where the actual upper bound is attained is selected for further partition in the immediately following iteration.
In summary, we have shown that the bounding operation is consistent and that selection operation is the bound improving. Therefore, according to Theorem IV.3 in [28], the employed global optimization algorithm is convergent to the global minimum of (RCP).


## 4.1. Algorithm Statement

Step 1 (initialization).
(i)
Solve problem (RCP1) with standard convex programming software to obtain the solutionx
′ of problem (RCP1). If F
p
+
1
(
x
)
≥
0, stop with x
′ as the global solution of the primal problem (RCP).
(ii)
Let the set of all active nodesQ
0
=
{
Ω
-
}, the convergence tolerance ϵ
>
0, the bisection ratio α
∈
(
0,0.5
], the upper bound U
*
=
∞, and the iteration counter k
:
=
0.
(iii)
Find an optimal solutionx
(
Ω
-
) and the optimal value LB
(
Ω
-
) for problem (
LRP
(
Ω
-
)
). If x
(
Ω
-
)
∈
(
D
⋂
‍
Ω
-
)
∖
G, compute x
^
(
Ω
-
) as given in Section 3.3; set U
*
=
F
0
(
x
^
(
Ω
-
)
). Set the initial lower bound LB
(
0
)
=
LB
(
Ω
-
).
(iv)
IfU
*
-
LB
(
0
)
≤
ϵ, then stop; x
^
(
Ω
-
) is a global ϵ-optimal solutions for problem (RCP). Otherwise, go to Step 2.Step 2 (updating the upper bound).
Select the midpointx
mid of Ω
k; if x
mid is feasible to (
RCP
(
Ω
k
)
), then compute x
^
(
Ω
k
) as given in Section 3.3; update the upper bound U
*
=
min
⁡
{
U
*
,
F
0
(
x
^
(
Ω
k
)
)
}.Step 3 (reduction).
For the subrectangleΩ
k that is currently investigated, we use the reduction cut described in Section 3 to cut away Ω
k and the remaining part is still denoted as Ω
k.Step 4 (branching).
Using the strategy of bisection of ratioα described in Section 3.1 to get two new subrectangles and denote the set of new partition rectangles as X
-
k. For each Ω
∈
X
-
k, compute the lower bound f
j
l
:
=
min
⁡
x
∈
Ω
LF
j
(
x
)
,
j
=
0,1
,
…
,
p and f
p
+
1
u
:
=
max
⁡
x
∈
Ω
UF
p
+
1
(
x
). If there exists some j
∈
{
0,1
,
…
,
p
} such that one of the lower bounds f
j
l satisfies f
0
l
>
U
* or f
j
l
>
0 for some j
∈
{
1
,
…
,
p
} or f
p
+
1
u
<
0, then the corresponding subrectangle Ω is eliminated from X
-
k; that is, X
-
k
:
=
X
-
k
∖
Ω, and skip to the next element of X
-
k.Step 5 (bounding).
IfX
-
k
≠
∅, solve problem (
LRP
(
Ω
)
) to obtain x
(
Ω
) and LB
(
Ω
) for each Ω
∈
X
-
k. If LB
(
Ω
)
>
U
*, set X
-
k
:
=
X
-
k
∖
Ω. Otherwise, if x
(
Ω
)
∈
(
D
⋂
‍
Ω
)
∖
G, then compute x
^
(
Ω
); update the upper bound U
*
=
min
⁡
{
U
*
,
F
0
(
x
^
(
Ω
)
)
} and update x
* such that F
0
(
x
*
)
=
U
*. The partition set remaining is now Q
k
:
=
(
Q
k
∖
Ω
k
)
∪
X
-
k and a new lower bound is now LB
(
k
)
:
=
min
⁡
{
LB
(
Ω
)
∣
Ω
∈
Q
k
}.Step 6 (convergence checking).
SetQ
k
+
1
=
Q
k
∖
{
Ω
∣
LB
(
Ω
)
≥
U
*
-
ϵ
,
Ω
∈
Q
k
}. If Q
k
+
1
=
∅, then stop with U
* as the optimal value and x
* as the optimal solution. Otherwise, select an active node Ω
k
+
1 such that Ω
k
+
1
=
argmin
{
LB
(
Ω
)
∣
Ω
∈
Q
k
+
1
} for further consideration. Set k
:
=
k
+
1 and return to Step 2.Next, we give the global convergence of the above algorithm. If the algorithm does not stop finitely, then the branching rule guarantees all the intervals to an isolated point for the variables.Theorem 7.
For anyΩ
=
{
x
∣
L
i
≤
x
i
≤
U
i
,
i
∈
I
}
⊂
Ω
-, let μ
i
=
U
i
-
L
i
,
∀
i
∈
I; then, for any x
∈
Ω, ∀
j
∈
{
0,1
,
…
,
p
}, one has
(39)
F
j
(
x
)
-
LF
j
(
x
)
⟶
0
,
F
p
+
1
(
x
)
-
UF
p
+
1
(
x
)
⟶
0
,
as μ
i
→
0 for each i
∈
I.Proof.
First, let us consider the casej
=
0,1
,
…
,
p. Let
(40)
Δ
j
=
F
j
(
x
)
-
LF
j
(
x
)
=
Δ
j
1
+
Δ
j
2
,
where Δ
j
1
=
F
j
(
x
)
-
L
j
(
x
)
,
Δ
j
2
=
L
j
(
x
)
-
LF
j
(
x
).
Obviously, if we want to proveΔ
j
→
0 as μ
i
→
0
,
∀
i
∈
I, we only need to prove Δ
j
1
→
0 and Δ
j
2
→
0, as μ
i
→
0
,
∀
i
∈
I.
From (7), (20), and the definition of η
j
k
Ω in (15), we have
(41)
Δ
j
1
=
∑
k
=
1
T
j
‍
γ
j
k
ln
⁡
(
exp
⁡
(
A
j
k
x
+
b
j
k
)
)
-
∑
k
=
1
T
j
‍
γ
j
k
[
K
j
k
Ω
(
exp
⁡
(
A
j
k
x
+
b
j
k
)
-
η
_
j
k
Ω
)
+
ln
⁡
(
η
_
j
k
Ω
)
]
=
∑
k
=
1
T
j
‍
γ
j
k
[
ln
⁡
(
η
j
k
Ω
)
-
K
j
k
Ω
(
η
j
k
Ω
-
η
_
j
k
Ω
)
-
ln
⁡
(
η
_
j
k
Ω
)
]
.
Since Δ
j
1 is a concave function about η
j
k
Ω for any η
j
k
Ω
∈
[
η
_
j
k
Ω
,
η
¯
j
k
Ω
], it can attain the maximum at the point η
j
k
Ω
=
1
/
K
j
k
Ω. Let z
j
k
=
η
¯
j
k
Ω
/
η
_
j
k
Ω; then by computing we have
(42)
max
⁡
x
∈
Ω
Δ
j
1
=
∑
k
=
1
T
j
‍
γ
j
k
[
-
ln
⁡
K
j
k
Ω
-
1
+
K
j
k
Ω
η
_
j
k
Ω
-
ln
⁡
η
_
j
k
Ω
]
=
∑
k
=
1
T
j
‍
γ
j
k
[
ln
⁡
z
j
k
-
1
ln
⁡
z
j
k
-
1
+
ln
⁡
z
j
k
z
j
k
-
1
]
.
By the definition of z
j
k, if μ
i
→
0
,
∀
i
∈
I, we have z
j
k
→
1, which implies that max
⁡
x
∈
Ω
Δ
j
1
→
0 as μ
i
→
0
,
∀
i
∈
I. Therefore, we can obtain that
(43)
Δ
j
1
⟶
0
as
μ
i
⟶
0
,
∀
i
∈
I
.
Next, we will proveΔ
j
2
→
0, as μ
i
→
0
,
∀
i
∈
I. From (20) and (26), we have
(44)
Δ
j
2
=
∑
k
=
1
T
j
‍
γ
j
k
[
K
j
k
Ω
(
∑
l
=
1
m
j
‍
exp
⁡
(
d
j
k
l
x
+
b
j
k
l
)
-
η
_
j
k
Ω
)
m
m
m
m
m
+
ln
⁡
(
η
_
j
k
Ω
)
∑
l
=
1
m
j
‍
]
-
∑
k
=
1
T
j
‍
γ
j
k
{
K
j
k
Ω
[
∑
l
=
1
m
j
‍
(
B
j
k
l
Ω
(
1
-
ln
⁡
(
B
j
k
l
Ω
)
+
d
j
k
l
x
+
b
j
k
l
)
)
m
m
m
m
m
m
m
m
m
m
-
η
_
j
k
Ω
∑
l
=
1
m
j
‍
]
+
ln
⁡
(
η
_
j
k
Ω
)
}
=
∑
k
=
1
T
j
‍
γ
j
k
{
∑
l
=
1
m
j
‍
K
j
k
Ω
m
m
m
m
m
×
[
∑
l
=
1
m
j
‍
exp
⁡
(
d
j
k
l
x
+
b
j
k
l
)
mmmmmmn
-
∑
l
=
1
m
j

(

B
j
k
l
Ω
‍
(
1

-

ln
⁡
(
B
j
k
l
Ω
)

+

d
j
k
l
x

+

b
j
k
l
)
)
∑
l
=
1
m
j
‍
]
}
.
Now, let us denote
(45)
Δ
j
k
21
=
∑
l
=
1
m
j
‍
[
exp
⁡
(
d
j
k
l
x
+
b
j
k
l
)
m
m
m
m
-
B
j
k
l
Ω
(
1
-
ln
⁡
(
B
j
k
l
Ω
)
+
d
j
k
l
x
+
b
j
k
l
)
]
=
∑
l
=
1
m
j
‍
[
exp
⁡
(
Y
j
k
l
Ω
)
-
B
j
k
l
Ω
(
1
-
ln
⁡
(
B
j
k
l
Ω
)
+
Y
j
k
l
Ω
)
]
,
Δ
j
k
l
22
(
Y
j
k
l
Ω
)
=
exp
⁡
(
Y
j
k
l
Ω
)
-
B
j
k
l
Ω
(
1
-
ln
⁡
(
B
j
k
l
Ω
)
+
Y
j
k
l
Ω
)
.
Then Δ
j
2 can be rewritten in the following form:
(46)
Δ
j
2
=
∑
k
=
1
T
j
‍
γ
j
k
K
j
k
Ω
∑
l
=
1
m
j
‍
Δ
j
k
l
22
.
Since Δ
j
k
l
22 is a convex function about Y
j
k
l
Ω
=
d
j
k
l
x
+
b
j
k
l over the interval [
Y
_
j
k
l
Ω
,
Y
¯
j
k
l
Ω
], it follows that Δ
j
k
l
22 can attain the maximum max
⁡
x
∈
Ω
Δ
j
k
l
22 at the point Y
_
j
k
l
Ω or Y
¯
j
k
l
Ω. Let u
j
k
l
=
Y
¯
j
k
l
Ω
-
Y
_
j
k
l
Ω and v
j
k
l
=
(
exp
⁡
(
u
j
k
l
)
-
1
)
/
u
j
k
l, then through computing, we can derive that
(47)
Δ
j
k
l
22
(
Y
_
j
k
l
Ω
)
=
exp
⁡
(
Y
_
j
k
l
Ω
)
-
B
j
k
l
Ω
(
1
-
ln
⁡
(
B
j
k
l
Ω
)
+
Y
_
j
k
l
Ω
)
=
exp
⁡
⁡
(
Y
_
j
k
l
Ω
)
-
exp
⁡
⁡
(
Y
¯
j
k
l
Ω
)
-
exp
⁡
⁡
(
Y
_
j
k
l
Ω
)
Y
¯
j
k
l
Ω
-
Y
_
j
k
l
Ω
×
(
1
-
ln
⁡
exp
⁡
⁡
(
Y
¯
j
k
l
Ω
)
-
exp
⁡
⁡
(
Y
_
j
k
l
Ω
)
Y
¯
j
k
l
Ω
-
Y
_
j
k
l
Ω
+
Y
_
j
k
l
Ω
)
=
exp
⁡
(
Y
_
j
k
l
Ω
)
(
1
-
v
j
k
l
(
1
-
ln
⁡
v
j
k
l
)
)
,
Δ
j
k
l
22
(
Y
¯
j
k
l
Ω
)
=
exp
⁡
(
Y
¯
j
k
l
Ω
)
-
B
j
k
l
Ω
(
1
-
ln
⁡
(
B
j
k
l
Ω
)
+
Y
¯
j
k
l
Ω
)
=
exp
⁡
(
Y
¯
j
k
l
Ω
)
-
exp
⁡
⁡
(
Y
¯
j
k
l
Ω
)
-
exp
⁡
⁡
(
Y
_
j
k
l
Ω
)
Y
¯
j
k
l
Ω
-
Y
_
j
k
l
Ω
×
(
1
-
ln
⁡
exp
⁡
⁡
(
Y
¯
j
k
l
Ω
)
-
exp
⁡
⁡
(
Y
_
j
k
l
Ω
)
Y
¯
j
k
l
Ω
-
Y
_
j
k
l
Ω
+
Y
¯
j
k
l
Ω
)
=
exp
⁡
⁡
(
Y
¯
j
k
l
Ω
)
-
exp
⁡
(
Y
_
j
k
l
Ω
)
v
j
k
l
(
1
-
ln
⁡
v
j
k
l
+
Y
¯
j
k
l
Ω
-
Y
_
j
k
l
Ω
)
.
Additionally, by the definitions of Y
_
j
k
l
Ω and Y
¯
j
k
l
Ω, we know that for any j
,
k
,
l,  Y
¯
j
k
l
Ω
-
Y
_
j
k
l
Ω
→
0 and exp
⁡
(
Y
¯
j
k
l
Ω
)
-
exp
⁡
(
Y
_
j
k
l
Ω
)
→
0 as μ
i
→
0
,
∀
i
∈
I, and so, we have v
j
k
l go to 1 as each μ
i approaches zero. This implies that Δ
j
k
l
22
(
Y
_
j
k
l
Ω
)
→
0 and Δ
j
k
l
22
(
Y
¯
j
k
l
Ω
)
→
0 as μ
i
→
0
,
∀
i
∈
I; that is, max
⁡
x
∈
Ω
Δ
j
k
l
22
→
0 as μ
i
→
0
,
∀
i
∈
I. Hence, according to the above discussion, we can follow that
(48)
Δ
j
2
⟶
0
,
as
μ
i
⟶
0
,
∀
i
∈
I
.
Based on the above discussion, for eachj
=
0,1
,
…
,
p, from (40) it follows that
(49)
Δ
j
⟶
0
,
as
μ
i
⟶
0
,
∀
i
∈
I
.
Second, let us considerj
=
p
+
1. Let
(50)
Δ
p
+
1
=
UF
p
+
1
(
x
)
-
F
p
+
1
(
x
)
=
Δ
p
+
1
1
+
Δ
p
+
1
2
,
where Δ
p
+
1
1
=
U
p
+
1
(
x
)
-
F
p
+
1
(
x
),Δ
p
+
1
2
=
UF
p
+
1
(
x
)
-
U
p
+
1
(
x
). By using (7), (21), and the definition of η
p
+
1
,
k
Ω in (15) we have
(51)
Δ
p
+
1
1
=
U
p
+
1
(
x
)
-
F
p
+
1
(
x
)
=
∑
k
=
1
T
p
+
1
‍
γ
p
+
1
,
k
[
K
p
+
1
,
k
Ω
exp
⁡
(
A
p
+
1
,
k
x
+
b
p
+
1
,
k
)
m
m
m
m
m
m
n
-
1
-
ln
⁡
(
K
p
+
1
,
k
Ω
)
]
-
∑
k
=
1
T
p
+
1
‍
γ
p
+
1
,
k
ln
⁡
(
exp
⁡
(
A
p
+
1
,
k
x
+
b
p
+
1
,
k
)
)
=
∑
k
=
1
T
p
+
1
‍
γ
p
+
1
,
k
[
K
p
+
1
,
k
Ω
∑
l
=
1
m
p
+
1
‍
exp
⁡
⁡
(
d
p
+
1
,
k
l
x
+
b
p
+
1
,
k
l
)
mmmmmmmmmmmm
-
1
-
ln
⁡
⁡
(
K
p
+
1
,
k
Ω
)
m
m
m
m
m
m
m
-
ln
⁡
(
∑
l
=
1
m
p
+
1
‍
exp
⁡
(
d
p
+
1
,
k
l
x
+
b
p
+
1
,
k
l
)
)
]
=
∑
k
=
1
T
p
+
1
‍
γ
p
+
1
,
k
[
K
p
+
1
,
k
Ω
η
p
+
1
,
k
Ω
-
1
mmmmmmn
-
ln
⁡
(
K
p
+
1
,
k
Ω
)
-
ln
⁡
(
η
p
+
1
,
k
Ω
)
]
.
Since Δ
p
+
1
1 is a convex function about η
p
+
1
,
k
Ω over the interval [
η
_
p
+
1
,
k
Ω
,
η
¯
p
+
1
,
k
Ω
], it can attain the maximum max
⁡
x
∈
Ω
Δ
p
+
1
1 at the point η
_
p
+
1
,
k
Ω or η
¯
p
+
1
,
k
Ω. Let z
p
+
1
,
k
=
η
¯
p
+
1
,
k
Ω
/
η
_
p
+
1
,
k
Ω; then, by similar discussion as above we can obtain that
(52)
Δ
p
+
1
1
(
η
_
p
+
1
,
k
Ω
)
=
∑
k
=
1
T
p
+
1
‍
γ
p
+
1
,
k
[
K
p
+
1
,
k
Ω
η
_
p
+
1
,
k
Ω
-
1
-
ln
⁡
(
K
p
+
1
,
k
Ω
)
-
ln
⁡
(
η
_
p
+
1
,
k
Ω
)
]
=
∑
k
=
1
T
p
+
1
‍
γ
p
+
1
,
k
(
ln
⁡
z
p
+
1
,
k
-
1
ln
⁡
z
p
+
1
,
k
-
1
+
ln
⁡
z
p
+
1
,
k
z
p
+
1
,
k
-
1
)
,
Δ
p
+
1
1
(
η
¯
p
+
1
,
k
Ω
)
=
∑
k
=
1
T
p
+
1
‍
γ
p
+
1
,
k
[
K
p
+
1
,
k
Ω
η
¯
p
+
1
,
k
Ω
-
1
-
ln
⁡
(
K
p
+
1
,
k
Ω
)
-
ln
⁡
(
η
¯
p
+
1
,
k
Ω
)
]
=
∑
k
=
1
T
p
+
1
‍
γ
p
+
1
,
k
(
ln
⁡
z
p
+
1
,
k
-
1
ln
⁡
z
p
+
1
,
k
m
m
m
m
m
m
m
m
m
-
1
+
z
p
+
1
,
k
ln
⁡
z
p
+
1
,
k
z
p
+
1
,
k
-
1
-
ln
⁡
z
p
+
1
,
k
)
.
Since z
p
+
1
,
k
→
1 as μ
i
→
0
,
∀
i
∈
I, we have that Δ
p
+
1
1
(
η
_
p
+
1
,
k
Ω
)
→
0 and Δ
p
+
1
1
(
η
¯
p
+
1
,
k
Ω
)
→
0; that is, max
⁡
x
∈
Ω
Δ
p
+
1
1
→
0, as μ
i
→
0
,
∀
i
∈
I. Hence, according to the above discussion, we can obtain that
(53)
Δ
p
+
1
1
⟶
0
,
as
μ
i
⟶
0
,
∀
i
∈
I
.
On the other hand, from (27) and (21) it follows that
(54)
Δ
p
+
1
2
=
UF
p
+
1
(
x
)
-
U
p
+
1
(
x
)
=
∑
k
=
1
T
p
+
1
‍
γ
p
+
1
,
k
m
×
[
K
p
+
1
,
k
Ω
∑
l
=
1
m
p
+
1
(
C
p
+
1
,
k
l
Ω
+
B
p
+
1
,
k
l
Ω
(
d
p
+
1
,
k
l
x
+
b
p
+
1
,
k
l
)
)
m
m
m
m
m
m
-
1
-
ln
⁡
(
K
p
+
1
,
k
Ω
)
∑
l
=
1
m
p
+
1
]
-
∑
k
=
1
T
p
+
1
‍
γ
p
+
1
,
k
[
K
p
+
1
,
k
Ω
∑
l
=
1
m
p
+
1
‍
exp
⁡
(
d
p
+
1
,
k
l
x
+
b
p
+
1
,
k
l
)
mmmm
-
1
-
ln
⁡
(
K
p
+
1
,
k
Ω
)
∑
l
=
1
m
p
+
1
‍
]
=
∑
k
=
1
T
p
+
1
‍
γ
p
+
1
,
k
K
p
+
1
,
k
Ω
×
∑
l
=
1
m
p
+
1
‍
[
C
p
+
1
,
k
l
Ω
+
B
p
+
1
,
k
l
Ω
(
d
p
+
1
,
k
l
x
+
b
p
+
1
,
k
l
)
n
-
exp
⁡
(
d
p
+
1
,
k
l
x
+
b
p
+
1
,
k
l
)
]
=
∑
k
=
1
T
p
+
1
‍
γ
p
+
1
,
k
K
p
+
1
,
k
Ω
×
∑
l
=
1
m
p
+
1
‍
[
C
p
+
1
,
k
l
Ω
+
B
p
+
1
,
k
l
Ω
Y
p
+
1
,
k
l
Ω
-
exp
⁡
(
Y
p
+
1
,
k
l
Ω
)
]
.
Now, let us denote
(55)
Δ
p
+
1
,
k
l
21
=
C
p
+
1
,
k
l
Ω
+
B
p
+
1
,
k
l
Ω
Y
p
+
1
,
k
l
Ω
-
exp
⁡
(
Y
p
+
1
,
k
l
Ω
)
;
then, Δ
p
+
1
2 can be rewritten as follows:
(56)
Δ
p
+
1
2
=
∑
k
=
1
T
p
+
1
‍
γ
p
+
1
,
k
K
p
+
1
,
k
Ω
∑
l
=
1
m
p
+
1
‍
Δ
p
+
1
,
k
l
21
.
Since Δ
p
+
1
,
k
l
21 is a concave function about Y
p
+
1
,
k
l
Ω over the interval [
Y
_
p
+
1
,
k
l
Ω
,
Y
¯
p
+
1
,
k
l
Ω
], it attains the maximum max
⁡
x
∈
Ω
Δ
p
+
1
,
k
l
21 at the point Y
p
+
1
,
k
l
Ω
=
ln
⁡
(
B
p
+
1
,
k
l
Ω
). Let u
p
+
1
,
k
l
=
Y
¯
p
+
1
,
k
l
Ω
-
Y
_
p
+
1
,
k
l
Ω and v
p
+
1
,
k
l
=
(
exp
⁡
(
u
p
+
1
,
k
l
)
-
1
)
/
u
p
+
1
,
k
l; then by computing we can get
(57)
max
⁡
x
∈
Ω
Δ
p
+
1
,
k
l
21
=
C
p
+
1
,
k
l
Ω
+
B
p
+
1
,
k
l
Ω
ln
⁡
⁡
(
B
p
+
1
,
k
l
Ω
)
-
B
p
+
1
,
k
l
Ω
=
-
B
p
+
1
,
k
l
Ω
Y
_
p
+
1
,
k
l
Ω
+
exp
⁡
(
Y
_
p
+
1
,
k
l
Ω
)
+
B
p
+
1
,
k
l
Ω
ln
⁡
⁡
(
B
p
+
1
,
k
l
Ω
)
-
B
p
+
1
,
k
l
Ω
=
exp
⁡
(
Y
_
p
+
1
,
k
l
Ω
)
[
v
p
+
1
,
k
l
ln
⁡
v
p
+
1
,
k
l
+
1
-
v
p
+
1
,
k
l
]
.
By the definition of u
p
+
1
,
k
l and v
p
+
1
,
k
l, we have u
p
+
1
,
k
l
→
0 and v
p
+
1
,
k
l
→
1 as μ
i
→
0
,
∀
i
∈
I. This implies that max
⁡
x
∈
Ω
Δ
p
+
1
,
k
l
21
→
0 as μ
i
→
0
,
∀
i
∈
I. Therefore, we have
(58)
Δ
p
+
1
2
⟶
0
,
as
μ
i
⟶
0
,
∀
i
∈
I
.
Thus, by (50) and the above discussion, it is obvious that
(59)
Δ
p
+
1
⟶
0
as
μ
i
⟶
0
,
∀
i
∈
I
.
In summary, according to the above results, the proof is complete.Remark 8.
From Theorem7, it follows that LF
j
(
x
)
,
j
=
0,1
,
…
,
p and UF
p
+
1
(
x
) will approximate the corresponding functions F
j
(
x
)
,
j
=
0,1
,
…
,
p and F
p
+
1
(
x
) as μ
i
→
0
,
∀
i
∈
I.Theorem 9.
(a) If the algorithm is finite, then upon termination, the incumbent solution being optimal to (RCP) is a globalϵ-optimal solution for problem (RCP).
(b) If the algorithm is infinite, then it will generate an infinite sequence of iterations such that along any infinite branch of the branch and bound tree, any accumulation point of the sequence{
x
^
k
} will be the global solution of the problem (RCP).Proof.
(a) If the algorithm is finite, then it terminates in some Stepk, k
≥
0. Without loss of generality, upon termination, the incumbent solution is denoted as x
^
k. By the algorithm, it follows that U
*
-
LB
(
k
)
≤
ϵ. From (iv) of Steps 1 and 6, this implies that F
0
(
x
^
k
)
-
LB
(
k
)
≤
ϵ. Let v denote the optimal value of problem (RCP); then, by Section 3, we know that LB
(
k
)
≤
v. Since x
^
k is a feasible solution of problem (RCP), we have f
(
x
^
k
)
≥
v. Taken together, this implies that
(60)
F
0
(
x
^
k
)
≥
v
≥
LB
(
k
)
≥
F
0
(
x
^
k
)
-
ϵ
.
Therefore, x
^
k is a global ϵ-optimal solution for problem (RCP). And the proof of part (a) is complete.
(b) When the algorithm is infinite, a sufficient condition for a global optimization to be convergent to the global minimum, stated in [28], requires that the bounding operation must be consistent and the selection operation is bound improving.
A bounding operation is called consistent if at every step any unfathomed partition can be further refined, and if any infinitely decreasing sequence of successively refined partition elements satisfies(61)
lim
⁡
k
→
∞
(
UB
k
-
LB
k
)
=
0
,
where UB
k is a computed upper bound in stage k and LB
k is the best lower bound at iteration k not necessarily occurring inside the same subrectangle with UB
k. In the following, we will show that (61) holds.
Since the employed subdivision process is exhaustive. Consequently, from Theorem7 and the relationship V
(
RCP
)
≥
V
(
LRP
), the formulation (61) holds; this implies that the employed bounding operation is consistent.
A selection operation is called the bound improving if at least one partition element where the actual upper bound is attained is selected for further partition after a finite number of refinements. Clearly, the employed selection operation is the bound improving because the partition element where the actual upper bound is attained is selected for further partition in the immediately following iteration.
In summary, we have shown that the bounding operation is consistent and that selection operation is the bound improving. Therefore, according to Theorem IV.3 in [28], the employed global optimization algorithm is convergent to the global minimum of (RCP).


## 5. Numerical Experiments

To demonstrate the potentiality and feasibility of the proposed global optimization algorithm, our numerical experiment is reported in this section. The algorithm is coded in C++ and each linear programming is solved by the simplex method. The convergence toleranceϵ is set to ϵ
=
1
0
-
5 in our experiments.Example 10 (see [37]).
Consider(62)
min
⁡
x
1
i
s
.
t
.
m
x
1
-
1
x
2
2
+
x
1
-
1
x
3
2
≤
1
,
mmmm
0.3
x
2
x
3
≥
1
,
m
m
m
m
x
∈
X
=
{
x
∣
1
≤
x
1
≤
100
,
m
m
m
m
m
m
m
m
m
1
≤
x
2
≤
100
,
1
≤
x
3
≤
100
}
.Example 11 (see [37]).
Consider(63)
min
⁡
x
1
i
s
.
t
.
m
3.7
x
1
-
1
x
2
0.85
+
1.985
x
1
-
1
x
2
+
700.3
x
1
-
1
x
3
-
0.75
≤
1
,
mmmm
0.7673
x
3
0.05
x
4
-
1
≤
1
,
m
m
m
m
x
4
-
1
+
0.05
x
2
x
4
-
1
≥
1
,
m
m
m
m
x
∈
X
=
{
x
∣
0.1
≤
x
1
≤
15
,
0.1
≤
x
2
≤
5
,
mmmmmmmmm
380
≤
x
3
≤
450
,
0.1
≤
x
4
≤
10
}
.Example 12 (see [37]).
Consider(64)
min
⁡
x
3
0.8
x
4
1.2
i
s
.
t
.
m
x
1
x
4
-
1
+
x
2
-
1
x
4
-
1
≤
1
,
m
m
m
m
x
1
-
2
x
3
-
1
+
x
2
x
3
-
1
≥
1
,
m
m
m
m
x
∈
X
=
{
x
∣
0.1
≤
x
1
≤
1
,
5
≤
x
2
≤
10
,
m
m
m
m
m
m
m
m
m
8
≤
x
3
≤
15
,
0.01
≤
x
4
≤
1
}
.Example 13 (see [26]).
Consider(65)
min
⁡
5
x
1
+
50000
x
1
-
1
+
20
x
2
+
72000
x
2
-
1
+
144000
x
3
-
1
i
s
.
t
.
m
4
x
1
-
1
+
32
x
2
-
1
+
120
x
3
-
1
≤
1
,
mmmm
70
≤
x
1
≤
108
,
83
≤
x
2
≤
100
,
mmmm
200
≤
x
2
≤
210
.Example 14 (see [24]).
Consider(66)
min
⁡
(
x
1
+
x
2
+
x
3
)
(
2
x
1
+
x
2
+
x
3
)
(
x
1
+
2
x
2
+
2
x
3
)
i
s
.
t
.
m
(
x
1
+
2
x
2
+
x
3
)
1.1
(
2
x
1
+
2
x
2
+
x
3
)
1.3
≤
100
,
mmmm
1
≤
x
1
,
x
2
,
x
3
≤
3
.Example 15 (see [24]).
Consider(67)
min
⁡
(
x
1
+
x
2
+
1
)
2.5
(
2
x
1
+
x
2
+
1
)
1.1
(
x
1
+
2
x
2
+
1
)
1.9
i
s
.
t
.
m
(
x
1
+
2
x
2
+
1
)
1.1
(
2
x
1
+
2
x
2
+
2
)
1.3
≤
50
,
mmmm
1
≤
x
1
≤
3
,
1
≤
x
2
≤
3
.Example 16.
Consider(68)
min
⁡
(
x
1
x
2
-
2
+
x
2
0.8
x
3
-
1.2
)
(
x
1
-
1.2
x
2
-
2
+
x
3
0.8
x
4
-
1.2
)
12
i
s
.
t
.
m
(
5
x
2
3
x
3
0.5
+
10
x
1
x
3
-
2
)
(
23
x
2
-
3
x
3
0.5
+
12
x
1
x
4
-
2
)
8
≤
1
,
mmmm
(
5
x
1
-
1.2
x
2
2
+
20
x
1
-
1
x
3
5
)
0.8
(
x
1
x
4
-
1
+
x
2
-
1
x
4
-
1
)
2.4
≤
1
,
mmmm
(
8
x
2
x
3
1.1
+
2
x
2
x
3
)
(
0.2
x
1
-
2
x
3
5
+
0.6
x
2
x
4
-
1
)
≥
1
,
m
m
m
m
x
∈
X
=
{
x
∣
0.1
≤
x
1
≤
20
,
1
≤
x
2
≤
50
,
m
m
m
m
m
m
m
m
m
1
≤
x
3
≤
60
,
0.01
≤
x
4
≤
40
}
.In order to test the effectiveness of several key strategies in Section3, we select the above four Examples 12–15 by adopting the different strategy in the branch-and-bound search, the corresponding computational results are summarized in Tables 1, 2, 3, and 4, respectively.Table 1
α
=
0.5; the reduction cut and new upper bound updating are not adopted.
Example
3
4
5
6
Iter
300
1596
83
471
L
max
⁡
73
436
22
54
Time
0.9105
12.2033
0.2504
2.2001Table 2
α
=
0.5; the reduction cut is not adopted.
Example
3
4
5
6
Iter
300
1596
52
457
L
max
⁡
70
432
6
44
Time
0.8903
11.3474
0.4003
52.4406Table 3
α
=
0.5; the strategies in Section 3 are all adopted.
Example
3
4
5
6
Iter
139
145
68
64
L
max
⁡
55
73
11
10
Time
0.4378
0.6898
0.3475
0.3026Table 4
α
=
0.35; the four strategies are all adopted in Section 3.
Number
Ref.
Iter
L
max
⁡
Time
Optimal solution
Optimal value
1
Ours
105
38
0.2192
(6.6667, 1.8257, 1.8258)
6.6667
[37]
151
33
0.15
(6.6667, 1.8257, 1.8258)
6.6667
2
Ours
113
64
0.2279
(11.9644, 0.8112, 442.66, 1.0406)
11.9644
[37]
259
104
0.62
(11.9632, 0.8158, 444.6624, 1.0408)
11.9632
3
Ours
5
2
0.0574
(0.1000, 10.0000, 8.0000, 0.2000)
0.7651
[37]
99
27
0.15
(0.1000, 10.0000, 8.0000, 0.2000)
0.7651
4
Ours
8
3
0
(100, 83, 210.0)
4213.184165257
5
Ours
1
1
0
(1.0, 1.0, 1.0)
60.0
6
Ours
1
1
0
(1.0, 1.0)
997.661265
7
Ours
25
5
1.2714
(20, 7.0536, 1, 40)
7.576
e
-
023In Table1, by setting α
=
0.5, the test does not adopt the reduction cut (i.e., Step 3 of the algorithm is skipped), and the new method to update upper bounds has not been applied; that is, U
*
=
min
⁡
{
U
*
,
F
0
(
x
^
(
Ω
)
} is replaced by U
*
=
min
⁡
{
U
*
,
F
0
(
x
(
Ω
)
} in (iii) of Steps 1 and 5 of the algorithm. In Tables 2–4, the test can be refereed the corresponding of explanation in the header of tables.In these tables, some notations have been used for column headers, that is, Iter: the number of the algorithm iterations;L
max
⁡: the maximal number of the active nodes necessary; and Time: the execution time in seconds.The computational results show that the proposed algorithm can globally solve the problem (MP) effectively. Furthermore, comparing the numerical results, from Tables1–4 it is shown that the proposed several strategies, especially in the reduction cut, upper bound updating, and bisection of ratio α, are very effective for decreasing the number of the iteration and the maximal number of the active nodes and the running CPU time.Additionally, in order to test our algorithm further, we give some other computational results, which are generated randomly. In Table5 below, the convergence tolerance parameters are set as 1
0
-
6, where the average CPU times (denoted by Ave. time), average number of iterations (denoted by Ave. Iter), and average longest node number (denoted by Ave. L) are obtained by running the algorithm for 10 times.Table 5
Numerical results for random problems.
T
p
m
n
Ave. Iter
Ave.L
Ave. time
2
3
3
6
2811
402
2.9228
2
3
3
8
12342
2832
17.225
2
5
3
6
3954
556
6.7927
2
3
5
6
5832
758
10.9702
4
3
3
6
6346
706
14.2749
4
5
3
8
38043
7695
173.6108
4
5
3
6
8739
1240
16.7542
4
3
5
6
11969
1757
36.6518Example 17.
Consider(69)
min
⁡
F
0
(
y
)
=
∏
k
=
1
T
‍
(
∑
l
=
1
m
‍
β
0
k
l
∏
i
=
1
n
‍
y
i
α
0
k
l
i
)
γ
0
k
i
s
.
t
.
F
j
(
y
)
=
∏
k
=
1
T
‍
(
∑
l
=
1
m
‍
β
j
k
l
∏
i
=
1
n
‍
y
i
α
j
k
l
i
)
γ
j
k
≤
1
,
mmmmmmmmmmnmmmmi
j
=
1
,
…
,
p
,
m
m
m
F
p
+
1
(
y
)
=
∏
k
=
1
T
‍
(
∑
l
=
1
m
‍
β
p
+
1
,
k
l
∏
i
=
1
n
‍
y
i
α
p
+
1
,
k
l
i
)
γ
p
+
1
,
k
≥
1
,
m
m
m
y
∈
Ω
=
{
y
∣
y
i
L
≤
y
i
≤
y
i
U
,
i
∈
I
}
,
where γ
j
k, α
j
k
l
i, and β
j
k
l are generated randomly in the intervals [
1
,
2
], [
0
,
5
], and [
0.1
,
10.1
], respectively. And y
i
L and y
i
U are generated randomly in the intervals [
0
,
1
] and [
10
,
11
].It is seen from Table5 that the sizes of T and n are the main factors affecting the performance of the algorithm. This is mainly because the number of terms in the subproblem linear programs (
LRP
(
Ω
)
) is proportional to T or n. Also, the CPU time increases as p or m increases, but not as sharply as T or n.


## 6. Concluding Remarks

A deterministic global optimization algorithm is proposed for solving problem (MP). It successfully reduces a complicated problem (MP) to a simpler reverse convex programming (RCP) problem. Based on the characteristics of the problem (RCP), several global optimization strategies are proposed. The first one is bisection of ratioα, which provides a more flexible subdivision rule. The second strategy is the linearization method. By adopting the two-part linearization method, the linear relaxation programming of the problem (RCP) can be obtained, whose minimum will provide the lower bound of the minimum of the problem (RCP). The third strategy is global solution location and upper bound updating. This strategy provides a method to locate the global solutions of the (RCP) and decreases the maximal number of the active nodes and the computational effort required during the algorithm. The final strategy is reduction cut as an accelerating device, which can cut away all part or a large part of the currently investigated feasible region in which the global optimal solution does not exist. A branch and bound algorithm is presented in which the four strategies are adopted successfully. The proposed algorithm is convergent to the global solutions. And the numerical results show that our algorithm is effective and feasible. It is noted that the third strategy can be used for solving the general reverse convex programming problems effectively.



---

*Source: 641909-2014-04-24.xml*