# Global Optimization for Solving Linear Multiplicative Programming Based on a New Linearization Method

Authors: Chun-Feng Wang; Yan-Qin Bai
Journal: Scientific Programming
 (2016)

---

## Abstract

This paper presents a new global optimization algorithm for solving a class of linear multiplicative programming (LMP) problem. First, a new linear relaxation technique is proposed. Then, to improve the convergence speed of our algorithm, two pruning techniques are presented. Finally, a branch and bound algorithm is developed for solving the LMP problem. The convergence of this algorithm is proved, and some experiments are reported to illustrate the feasibility and efficiency of this algorithm.


---

## Body

## 1. Introduction

Consider the following linear multiplicative programming (LMP) problem:LMP:(1)
v
=
m
i
n
ϕ
x
=
∑
i
=
1
p
c
i
T
x
+
d
i
e
i
T
x
+
f
i
s
.
t
.
x
∈
D
=
x
∈
R
n
∣
A
x
≤
b
,wherep
≥
2,  c
i
T
=
(
c
i
1
,
c
i
2
,
…
,
c
i
n
),  e
i
T
=
(
e
i
1
,
e
i
2
,
…
,
e
i
n
)
∈
R
n,  d
i
,
f
i
∈
R, i
=
1
,
…
,
p,  A
=
(
a
i
j
)
m
×
n
∈
R
m
×
n is a matrix, b
=
(
b
i
)
m
×
1
∈
R
m is a vector, and D
⊆
R
n is nonempty and bounded.As a special case of nonconvex programming problem, the problem LMP has been paid more attention since the 1990s. There are two reasons. The first one is that, from a practical point of view, LMP problem appears in a wide variety of practical applications, such as financial optimization [1], data mining/pattern recognition [2], plant layout design [3], VLISI chip design [4], and robust optimization [5]. The second one is that, from a research point of view, LMP is N-hard; that is, it usually possesses multiple local optimal solutions that are not globally optimal. So, it is hard to find its global optimal solution, and it is necessary to put forward good methods.In the past few decades, for allx
∈
D, under the assumption that c
i
T
+
d
i
>
0,  e
i
T
x
+
f
i
>
0, a number of practical algorithms have been proposed for globally solving problem LMP. These methods can be classified into parameterization based methods [6, 7], branch-and-bound methods [8–10], decomposition method [11], cutting plane method [12], and so on.The purpose of this paper is to present an effective method for globally solving problem LMP. Compared with other algorithms, the main features of this algorithm are (1) by using the special structure of LMP, a new linear relaxation technique is presented, which can be used to construct the linear relaxation programming (LRP) problem; (2) two pruning techniques are presented, which can be used to improve the convergence speed of the proposed algorithm; (3) the problem investigated in this paper has a more general form than those in [6–12]; it does not require c
i
T
x
+
d
i
>
0 and e
i
T
x
+
f
i
>
0; (4) numerical results and comparison with methods [8, 13–22] show that our algorithm works as well as or better than those methods.This paper is organized as follows. In Section2, the new linear relaxation programming (LRP) problem for LMP problem is proposed, which provides a lower bound for the optimal value of LMP. In order to improve the convergence speed of our algorithm, two pruning techniques are presented in Section 3. In Section 4, the global optimization algorithm is given, and the convergence of the algorithm is proved. Numerical experiments are carried out to show the feasibility and efficiency of our algorithm in Section 5.


## 2. Linear Relaxation Programming (LRP)

To solve problem LMP, the principal task is the construction of lower bound for this problem and its partitioned subproblems. A lower bound of LMP problem and its partitioned subproblems can be obtained by solving a linear relaxation programming problem. For generating this linear relaxation, the strategy proposed by this paper is to underestimate the objective functionϕ
(
x
) with a linear function. All the details of this procedure will be given in the following.First, we solve2
n linear programming problems: l
j
0
=
m
i
n
x
∈
D
x
j, u
j
0
=
m
a
x
x
∈
D
x
j, j
=
1
,
…
,
n, and construct a rectangle H
0
=
{
x
∈
R
n
∣
l
j
0
≤
x
j
≤
u
j
0
,
j
=
1
,
…
,
n
}. Then, the LMP problem can be rewritten as the following form:LMP:(2)
v
=
m
i
n
ϕ
x
=
∑
i
=
1
p
c
i
T
x
+
d
i
e
i
T
x
+
f
i
s
.
t
.
x
∈
D
=
x
∈
R
n
∣
A
x
≤
b
,
H
0
=
x
∣
l
j
0
≤
x
j
≤
u
j
0
,
j
=
1
,
…
,
n
.LetH
=
[
l
,
u
] be the initial rectangle H
0 or some subrectangle of H
0 that is generated by the proposed algorithm. Next, we will show how to construct the linear relaxation programming problem LRP for LMP.Towards this end, fori
=
1
,
…
,
p, compute(3)
ξ
_
i
=
∑
j
=
1
n
m
i
n
c
i
j
l
j
,
c
i
j
u
j
+
d
i
,
ξ
¯
i
=
∑
j
=
1
n
m
a
x
c
i
j
l
j
,
c
i
j
u
j
+
d
i
,
η
_
i
=
∑
j
=
1
n
m
i
n
e
i
j
l
j
,
e
i
j
u
j
+
f
i
,
η
¯
i
=
∑
j
=
1
n
m
a
x
e
i
j
l
j
,
e
i
j
u
j
+
f
i
,and consider the product term (
c
i
T
x
+
d
i
)
(
e
i
T
x
+
f
i
) in ϕ
(
x
).Sincec
i
T
x
+
d
i
-
ξ
_
i
≥
0,  e
i
T
x
+
f
i
-
η
_
i
≥
0, we have(4)
c
i
T
x
+
d
i
-
ξ
_
i
e
i
T
x
+
f
i
-
η
_
i
≥
0
; that is,(5)
c
i
T
x
+
d
i
e
i
T
x
+
f
i
-
η
_
i
c
i
T
x
+
d
i
-
ξ
_
i
e
i
T
x
+
f
i
+
ξ
_
i
η
_
i
≥
0
. Furthermore, we have(6)
c
i
T
x
+
d
i
e
i
T
x
+
f
i
≥
η
_
i
c
i
T
x
+
d
i
+
ξ
_
i
e
i
T
x
+
f
i
-
ξ
_
i
η
_
i
.In addition, sincec
i
T
x
+
d
i
-
ξ
_
i
≥
0,  e
i
T
x
+
f
i
-
η
¯
i
≤
0, we have(7)
c
i
T
x
+
d
i
-
ξ
_
i
e
i
T
x
+
f
i
-
η
¯
i
≤
0
. Furthermore, we can obtain(8)
c
i
T
x
+
d
i
e
i
T
x
+
f
i
≤
η
¯
i
c
i
T
x
+
d
i
+
ξ
_
i
e
i
T
x
+
f
i
-
ξ
_
i
η
¯
i
.From (6) and (8), we have the following relations:(9)
ϕ
x
=
∑
i
=
1
p
c
i
T
x
+
d
i
e
i
T
x
+
f
i
≥
∑
i
=
1
p
η
_
i
c
i
T
x
+
d
i
+
ξ
_
i
e
i
T
x
+
f
i
-
ξ
_
i
η
_
i
=
ϕ
l
x
,
ϕ
x
=
∑
i
=
1
p
c
i
T
x
+
d
i
e
i
T
x
+
f
i
≤
∑
i
=
1
p
η
¯
i
c
i
T
x
+
d
i
+
ξ
_
i
e
i
T
x
+
f
i
-
ξ
_
i
η
¯
i
=
ϕ
u
x
.Based on the above discussion, the linear relaxation programming (LRP) problem can be established as follows, which provides a lower bound for the optimal value of LMP problem overH:LRP:(10)
m
i
n
ϕ
l
x
s
.
t
.
A
x
≤
b
,
x
∈
H
.Theorem 1.
For allx
∈
H, let Δ
x
=
u
-
l and consider the functions ϕ
l
(
x
),  ϕ
(
x
), and ϕ
u
(
x
). Then, one has l
i
m
Δ
x
→
0
(
ϕ
(
x
)
-
ϕ
l
(
x
)
)
=
l
i
m
Δ
x
→
0
(
ϕ
u
(
x
)
-
ϕ
(
x
)
)
=
0.Proof.
We first provel
i
m
Δ
x
→
0
(
ϕ
(
x
)
-
ϕ
l
(
x
)
)
=
0. By the definitions ϕ
(
x
) and ϕ
l
(
x
), we have(11)
ϕ
x
-
ϕ
l
x
=
∑
i
=
1
p
c
i
T
x
+
d
i
e
i
T
x
+
f
i
-
∑
i
=
1
p
η
_
i
c
i
T
x
+
d
i
+
ξ
_
i
e
i
T
x
+
f
i
-
ξ
_
i
η
_
i
≤
∑
i
=
1
p
c
i
T
x
+
d
i
e
i
T
x
+
f
i
-
η
_
i
c
i
T
x
+
d
i
+
∑
i
=
1
p
ξ
_
i
e
i
T
x
+
f
i
-
ξ
_
i
η
_
i
≤
∑
i
=
1
p
c
i
T
x
+
d
i
e
i
T
x
+
f
i
-
η
_
i
+
∑
i
=
1
p
ξ
_
i
e
i
T
x
+
f
i
-
η
_
i
.Sice D is nonempty and bounded, there exists M
i such that M
i
=
m
a
x
x
∈
D
|
c
i
T
x
+
d
i
|. From the above inequality, we have(12)
ϕ
x
-
ϕ
l
x
≤
∑
i
=
1
p
M
i
η
¯
i
-
η
_
i
+
∑
i
=
1
p
ξ
_
i
η
¯
i
-
η
_
i
. By the definitions of η
_
i and η
¯
i, we know that Δ
s
=
η
¯
i
-
η
_
i
→
0 as Δ
x
→
0. Combining (12), we have l
i
m
Δ
x
→
0
(
ϕ
(
x
)
-
ϕ
l
(
x
)
)
=
0.
Similarly, we can provel
i
m
Δ
x
→
0
(
ϕ
u
(
x
)
-
ϕ
(
x
)
)
=
0, and the proof is complete.Theorem1 implies that ϕ
l
(
x
) and ϕ
u
(
x
) will approximate the function ϕ
(
x
) as Δ
x
→
0.


## 3. Pruning Technique

To improve the convergence speed of this algorithm, we present two pruning techniques, which can be used to eliminate the region in which the global optimal solution of LMP problem does not exist.Assume thatU
B and L
B are the current known upper bound and lower bound of the optimal value v of the problem LMP. Let(13)
α
j
=
∑
i
=
1
p
η
_
i
c
i
j
+
ξ
_
i
e
i
j
,
j
=
1
,
…
,
n
,
Λ
1
=
∑
i
=
1
p
η
_
i
d
i
+
ξ
_
f
i
-
η
_
i
ξ
_
,
γ
k
=
U
B
-
∑
j
=
1
,
j
≠
k
n
min
⁡
α
j
l
j
,
α
j
u
j
-
Λ
1
,
k
=
1
,
…
,
n
,
β
j
=
∑
i
=
1
p
η
¯
i
c
i
j
+
ξ
_
i
e
i
j
,
j
=
1
,
…
,
n
,
Λ
2
=
∑
i
=
1
p
η
¯
i
d
i
+
ξ
_
f
i
-
η
¯
i
ξ
_
,
ρ
k
=
L
B
-
∑
j
=
1
,
j
≠
k
n
m
a
x
β
j
l
j
,
β
j
u
j
-
Λ
2
,
k
=
1
,
…
,
n
.The pruning techniques are derived as in the following theorems.Theorem 2.
For any subrectangleH
⊆
H
0 with H
j
=
[
l
j
,
u
j
], if there exists some index k
∈
{
1,2
,
…
,
n
} such that α
k
>
0 and γ
k
<
α
k
u
k, then there is no globally optimal solution of LMP problem over H
1; if α
k
<
0 and γ
k
<
α
k
l
k, for some k, then there is no globally optimal solution of LMP problem over H
2, where(14)
H
1
=
H
j
1
n
×
1
⊆
H
,
w
i
t
h
H
j
1
=
H
j
,
j
≠
k
,
γ
k
α
k
,
u
k
∩
H
k
,
j
=
k
,
H
2
=
H
j
2
n
×
1
⊆
H
,
w
i
t
h
H
j
2
=
H
j
,
j
≠
k
,
l
k
,
γ
k
α
k
∩
H
k
,
j
=
k
.Proof.
For allx
∈
H
1, we first show that ϕ
(
x
)
>
U
B. Consider the kth component x
k of x. Since x
k
∈
(
γ
k
/
α
k
,
u
k
], we can obtain that(15)
γ
k
α
k
<
x
k
≤
u
k
.From α
k
>
0, we have γ
k
<
α
k
x
k. For all x
∈
H
1, by the above inequality and the definition of γ
k, it implies that(16)
U
B
-
∑
j
=
1
,
j
≠
k
n
m
i
n
α
j
l
j
,
α
j
u
j
-
Λ
1
<
α
k
x
k
; that is,(17)
U
B
<
∑
j
=
1
,
j
≠
k
n
m
i
n
α
j
l
j
,
α
j
u
j
+
α
k
x
k
+
Λ
1
≤
∑
j
=
1
n
α
j
x
j
+
Λ
1
=
ϕ
l
x
.Thus, for all x
∈
H
1, we have ϕ
(
x
)
≥
ϕ
l
(
x
)
>
U
B
≥
v; that is, for all x
∈
H
1, ϕ
(
x
) is always greater than the optimal value v of the problem LMP. Therefore, there cannot exist globally optimal solution of LMP problem over H
1.
Similarly, for allx
∈
H
2, if there exists some k such that α
k
<
0 and γ
k
<
α
k
l
k, it can be derived that there is no globally optimal solution of LMP problem over H
2.Theorem 3.
For any subrectangleH
⊆
H
0 with H
j
=
[
l
j
,
u
j
], if there exists some index k
∈
{
1,2
,
…
,
n
} such that β
k
>
0 and ρ
k
>
β
k
l
k, then there is no globally optimal solution of LMP problem over H
3; if β
k
<
0 and ρ
k
>
β
k
u
k, for some k, then there is no globally optimal solution of LMP problem over H
4, where(18)
H
3
=
H
j
3
n
×
1
⊆
H
,
w
i
t
h
H
j
3
=
H
j
,
j
≠
k
,
l
k
,
ρ
k
β
k
∩
H
k
,
j
=
k
,
H
4
=
H
j
4
n
×
1
⊆
H
,
w
i
t
h
H
j
4
=
H
j
,
j
≠
k
,
ρ
k
β
k
,
u
k
∩
H
k
,
j
=
k
.Proof.
First, we show that, for allx
∈
H
3, ϕ
(
x
)
<
L
B. Consider the kth component x
k of x. By the assumption and the definitions of β
k and ρ
k, we have(19)
l
k
≤
x
k
<
ρ
k
β
k
. Note that since β
k
>
0, we have ρ
k
>
β
k
x
k. For all x
∈
H
3, by the above inequality and the definition of ρ
k, it implies that(20)
L
B
>
∑
j
=
1
,
j
≠
k
n
m
a
x
β
j
l
j
,
β
j
u
j
+
β
k
x
k
+
Λ
2
≥
∑
j
=
1
n
β
j
x
j
+
Λ
2
=
Φ
u
x
≥
ϕ
x
.Thus, for all x
∈
H
3, we have v
≥
L
B
>
ϕ
(
x
). Therefore, there cannot exist globally optimal solution of LMP problem over H
3.
For allx
∈
H
4, if there exists some k such that β
k
<
0 and ρ
k
>
β
k
u
k, from arguments similar to the above, it can be derived that there is no globally optimal solution of LMP problem over H
4.


## 4. Algorithm and Its Convergence

Based on the previous results, this section presents the branch and bound algorithm and gives its convergence.


### 4.1. Branching Rule

In branch and bound algorithm, branch rule is a critical element in guaranteeing convergence. This paper chooses a simple and standard bisection rule, which is sufficient to ensure convergence since it drives the intervals shrinking to a singleton for all the variables along any infinite branch of the branch and bound tree.Consider any node subproblem identified by rectangleH
=
{
x
∈
R
n
∣
l
j
≤
x
j
≤
u
j
,
j
=
1
,
…
,
n
}
⊆
H
0. The branching rule is as follows:(i)
letk
=
a
r
g
m
a
x
{
u
j
-
l
j
∣
j
=
1
,
…
,
n
};
(ii)
letτ
=
(
l
k
+
u
k
)
/
2;
(iii)
let(21)
H
1
=
x
∈
R
n
∣
l
j
≤
x
j
≤
u
j
,
j
≠
k
,
l
k
≤
x
k
≤
τ
,
H
2
=
x
∈
R
n
∣
l
j
≤
x
j
≤
u
j
,
j
≠
k
,
τ
≤
x
k
≤
u
k
.Through using this branching rule, the rectangleH is partitioned into two subrectangles H
1 and H
2.


### 4.2. Branch and Bound Algorithm

From the above discussion, the branch and bound algorithm for globally solving LMP problem is summarized as follows.LetL
B
(
H
k
) be the optimal function value of LRP over the subrectangle H
=
H
k and x
k
=
x
(
H
k
) be an element of the corresponding argmin.Algorithm StatementStep 1.
Chooseϵ
≥
0. Find an optimal solution x
0
=
x
(
H
0
) and the optimal value L
B
(
H
0
) for problem LRP with H
=
H
0. Set L
B
0
=
L
B
(
H
0
), and U
B
0
=
ϕ
(
x
0
). If U
B
0
-
L
B
0
≤
ϵ, then stop: x
0 is an ϵ-optimal solution of problem LMP. Otherwise, set Q
0
=
{
H
0
}, k
=
1, and go to Step 2.Step 2.
SetU
B
k
=
U
B
k
-
1. Subdivide H
k
-
1 into two subrectangles via the branching rule, and denote the set of new partition rectangles as H
¯
k.Step 3.
For each new rectangleH
∈
H
¯
k, utilizing the pruning techniques of Theorems 2 and 3 to prune rectangle H. For i
=
1
,
…
,
m, if there exists some i such that ∑
‍
j
=
1
n
m
i
n
{
a
i
j
l
j
,
a
i
j
u
j
}
≥
b
i over rectangle H, then remove the rectangle H from H
¯
k; that is, H
¯
k
=
H
¯
k
∖
H.Step 4.
IfH
¯
k
≠
∅, solve LRP to obtain L
B
(
H
) and x
(
H
) for each H
∈
H
¯
k. If L
B
(
H
)
>
U
B
k, set H
¯
k
=
H
¯
k
∖
H. Otherwise, let U
B
k
=
m
i
n
{
U
B
k
,
ϕ
(
x
(
H
)
)
}. If U
B
k
=
ϕ
(
x
(
H
)
), set x
k
=
x
(
H
).Step 5.
Set(22)
Q
k
=
Q
k
-
1
∖
H
k
-
1
∪
H
¯
k
.Step 6.
SetL
B
k
=
m
i
n
{
L
B
(
H
)
∣
H
∈
Q
k
}. Let H
k be the subrectangle which satisfies that L
B
k
=
L
B
(
H
k
). If U
B
k
-
L
B
k
≤
ϵ, then stop: x
k is a global ϵ-optimal solution of problem LMP. Otherwise, set k
=
k
+
1, and go to Step 2.


### 4.3. Convergence Analysis

In this subsection, the convergence properties of the algorithm are given.Theorem 4.
The algorithm either terminates finitely with globallyε-optimal solution or generates an infinite sequence {
x
k
}, where any accumulation point is a globally optimal solution of LMP.Proof.
If the algorithm terminates finitely, without loss of generality, assume that the algorithm terminates at thekth step; by the algorithm, we have(23)
U
B
k
-
L
B
k
≤
ε
. So, x
k is a global optimal solution of the problem LMP.
If the algorithm is infinite, then an infinite sequence{
x
k
} will be generated. Since the feasible region of LMP is bounded, the sequence {
x
k
} must have a convergence subsequence. Without loss of generality, set l
i
m
k
→
∞
x
k
=
x
∗. By the algorithm, we have(24)
lim
k
→
∞
⁡
L
B
k
≤
v
.Since x
∗ is a feasible solution of problem LMP, v
≤
Φ
(
x
∗
). Taken together, the following relation holds:(25)
lim
k
→
∞
⁡
L
B
k
≤
v
≤
ϕ
x
∗
.On the other hand, by the algorithm and the continuity of ϕ
l
(
x
), we have(26)
lim
k
→
∞
⁡
L
B
k
=
lim
k
→
∞
⁡
ϕ
l
x
k
=
ϕ
l
x
∗
. By Theorem 1, we can obtain(27)
ϕ
x
∗
=
ϕ
l
x
∗
. Therefore, v
=
ϕ
(
x
∗
); that is x
∗ is a global optimal solution of problem LMP.


## 4.1. Branching Rule

In branch and bound algorithm, branch rule is a critical element in guaranteeing convergence. This paper chooses a simple and standard bisection rule, which is sufficient to ensure convergence since it drives the intervals shrinking to a singleton for all the variables along any infinite branch of the branch and bound tree.Consider any node subproblem identified by rectangleH
=
{
x
∈
R
n
∣
l
j
≤
x
j
≤
u
j
,
j
=
1
,
…
,
n
}
⊆
H
0. The branching rule is as follows:(i)
letk
=
a
r
g
m
a
x
{
u
j
-
l
j
∣
j
=
1
,
…
,
n
};
(ii)
letτ
=
(
l
k
+
u
k
)
/
2;
(iii)
let(21)
H
1
=
x
∈
R
n
∣
l
j
≤
x
j
≤
u
j
,
j
≠
k
,
l
k
≤
x
k
≤
τ
,
H
2
=
x
∈
R
n
∣
l
j
≤
x
j
≤
u
j
,
j
≠
k
,
τ
≤
x
k
≤
u
k
.Through using this branching rule, the rectangleH is partitioned into two subrectangles H
1 and H
2.


## 4.2. Branch and Bound Algorithm

From the above discussion, the branch and bound algorithm for globally solving LMP problem is summarized as follows.LetL
B
(
H
k
) be the optimal function value of LRP over the subrectangle H
=
H
k and x
k
=
x
(
H
k
) be an element of the corresponding argmin.Algorithm StatementStep 1.
Chooseϵ
≥
0. Find an optimal solution x
0
=
x
(
H
0
) and the optimal value L
B
(
H
0
) for problem LRP with H
=
H
0. Set L
B
0
=
L
B
(
H
0
), and U
B
0
=
ϕ
(
x
0
). If U
B
0
-
L
B
0
≤
ϵ, then stop: x
0 is an ϵ-optimal solution of problem LMP. Otherwise, set Q
0
=
{
H
0
}, k
=
1, and go to Step 2.Step 2.
SetU
B
k
=
U
B
k
-
1. Subdivide H
k
-
1 into two subrectangles via the branching rule, and denote the set of new partition rectangles as H
¯
k.Step 3.
For each new rectangleH
∈
H
¯
k, utilizing the pruning techniques of Theorems 2 and 3 to prune rectangle H. For i
=
1
,
…
,
m, if there exists some i such that ∑
‍
j
=
1
n
m
i
n
{
a
i
j
l
j
,
a
i
j
u
j
}
≥
b
i over rectangle H, then remove the rectangle H from H
¯
k; that is, H
¯
k
=
H
¯
k
∖
H.Step 4.
IfH
¯
k
≠
∅, solve LRP to obtain L
B
(
H
) and x
(
H
) for each H
∈
H
¯
k. If L
B
(
H
)
>
U
B
k, set H
¯
k
=
H
¯
k
∖
H. Otherwise, let U
B
k
=
m
i
n
{
U
B
k
,
ϕ
(
x
(
H
)
)
}. If U
B
k
=
ϕ
(
x
(
H
)
), set x
k
=
x
(
H
).Step 5.
Set(22)
Q
k
=
Q
k
-
1
∖
H
k
-
1
∪
H
¯
k
.Step 6.
SetL
B
k
=
m
i
n
{
L
B
(
H
)
∣
H
∈
Q
k
}. Let H
k be the subrectangle which satisfies that L
B
k
=
L
B
(
H
k
). If U
B
k
-
L
B
k
≤
ϵ, then stop: x
k is a global ϵ-optimal solution of problem LMP. Otherwise, set k
=
k
+
1, and go to Step 2.


## 4.3. Convergence Analysis

In this subsection, the convergence properties of the algorithm are given.Theorem 4.
The algorithm either terminates finitely with globallyε-optimal solution or generates an infinite sequence {
x
k
}, where any accumulation point is a globally optimal solution of LMP.Proof.
If the algorithm terminates finitely, without loss of generality, assume that the algorithm terminates at thekth step; by the algorithm, we have(23)
U
B
k
-
L
B
k
≤
ε
. So, x
k is a global optimal solution of the problem LMP.
If the algorithm is infinite, then an infinite sequence{
x
k
} will be generated. Since the feasible region of LMP is bounded, the sequence {
x
k
} must have a convergence subsequence. Without loss of generality, set l
i
m
k
→
∞
x
k
=
x
∗. By the algorithm, we have(24)
lim
k
→
∞
⁡
L
B
k
≤
v
.Since x
∗ is a feasible solution of problem LMP, v
≤
Φ
(
x
∗
). Taken together, the following relation holds:(25)
lim
k
→
∞
⁡
L
B
k
≤
v
≤
ϕ
x
∗
.On the other hand, by the algorithm and the continuity of ϕ
l
(
x
), we have(26)
lim
k
→
∞
⁡
L
B
k
=
lim
k
→
∞
⁡
ϕ
l
x
k
=
ϕ
l
x
∗
. By Theorem 1, we can obtain(27)
ϕ
x
∗
=
ϕ
l
x
∗
. Therefore, v
=
ϕ
(
x
∗
); that is x
∗ is a global optimal solution of problem LMP.


## 5. Numerical Experiments

To verify the performance of the proposed algorithm, some numerical experiments are carried out and compared with some other methods [8, 13–22]. The algorithm is compiled with Matlab 7.1 on a Pentium IV (3.06 GHZ) microcomputer. The simplex method is applied to solve the linear relaxation programming problems. In our experiments, for Examples 1–10, the convergence tolerance ϵ is 10
-
6; for Example 11, the convergence tolerance ϵ is 10
-
2.The results of problems  1–10 are summarized in Table1, where the following notations have been used in row headers: Iter is the number of algorithm iterations; Time (s) is execution time in seconds. Except for the results of our algorithm, the results of the other eleven algorithms are taken directly from the corresponding references. In Table 1, “—” denotes the corresponding value is not available.Table 1
Comparison results of Examples1–10.
Example (p
,
m
,
n)
Methods
Time (s)
Iter
Optimal solution
Optimal value
1 (min) (1,8
,
2)
[13]
5.0780
48
(2.0, 8.0)
10
[14]
0.3
53
(2.0, 8.0)
10
[15]
10.83
27
(2.0003, 7.9999)
10.0042
Ours
0.062
1
(2.0, 8.0)
10
2 (min) (2,6
,
2)
[13]
0.2030
2
(0.0, 4.0)
3
[16]
—
3
(0.0, 4.0)
3
Ours
0.086
1
(0.0, 4.0)
3
3 (min) (1,12,4)
[13]
0.1880
1
(1.3148, 0.1396, 0.0, 0.4233)
0.8902
[17]
—
6
(1.3148, 0.1396, 0.0, 0.4233)
0.8902
Ours
0.093
1
(1.3148, 0.1396, 0.0, 0.4233)
0.8902
4 (min) (2,5
,
2)
[8]
—
—
(0.0, 4.0)
3
[18]
—
—
(0.0, 4.0)
3
Ours
0.0842
1
(0.0, 4.0)
3
5 (min) (2,4
,
2)
[19]
—
—
(1.0, 3.0)
−13
Ours
0.0150
1
(1.0, 3.0)
−13
6 (min) (2,4
,
2)
[19]
—
—
(1.0, 4.0)
−22
Ours
0.0160
1
(1.0, 4.0)
−22
7 (min) (3,7
,
3)
[20]
—
57
(5.5556, 1.7778, 2.6667)
−112.754
Ours
1.5930
34
(5.5556, 1.7778, 2.6667)
−112.7531
8 (max) (2,4
,
2)
[21]
—
13
(0.74984, 0.74984)
−38.87628
Ours
0.5
16
(0.75, 0.75)
−38.8750
9 (min) (2,6
,
2)
[22]
—
7
(1.547, 2.421)
−16.2837
Ours
0.659
23
(1.5480, 2.4152)
−16.2893
10 (min) (2,6
,
2)
[22]
—
29
(1.5549, 0.7561)
10.6756
Ours
0.7662
27
(1.5568, 0.7545)
10.6753For problems  1–10, the efficiency of the algorithm proposed by this paper (named Algorithm  1) and the algorithm proposed by this paper but without using the pruning techniques (named Algorithm  2) is compared. The comparison results are given in Table2.Table 2
Comparison results of Algorithms1 and 2 for Examples 1–10.
Example(p
,
m
,
n)
Methods
Time (s)
Iter
Optimal solution
Optimal value
1 (min)(1,8
,
2)
Algorithm1
0.062
1
(2.0, 8.0)
10
Algorithm2
0.062
1
(2.0, 8.0)
10
2 (min)(2,6
,
2)
Algorithm1
0.086
1
(0.0, 4.0)
3
Algorithm2
0.086
1
(0.0, 4.0)
3
3 (min)(1,12,4)
Algorithm1
0.093
1
(1.3148, 0.1396, 0.0, 0.4233)
0.8902
Algorithm2
0.093
1
(1.3148, 0.1396, 0.0, 0.4233)
0.8902
4 (min)(2,5
,
2)
Algorithm1
0.0842
1
(0.0, 4.0)
3
Algorithm2
0.0842
1
(0.0, 4.0)
3
5 (min)(2,4
,
2)
Algorithm1
0.0150
1
(1.0, 3.0)
−13
Algorithm2
0.0150
1
(1.0, 3.0)
−13
6 (min)(2,4
,
2)
Algorithm1
0.0160
1
(1.0, 4.0)
−22
Algorithm2
0.0160
1
(1.0, 4.0)
−22
7 (min)(3,7
,
3)
Algorithm1
1.5930
34
(5.5556, 1.7778, 2.6667)
−112.7531
Algorithm2
1.9091
58
(5.5556, 1.7778, 2.6667)
−112.7531
8 (max)(2,4
,
2)
Algorithm1
0.5
16
(0.75, 0.75)
−38.8750
Algorithm2
1.6425
64
(0.75, 0.75)
−38.8750
9 (min)(2,6
,
2)
Algorithm1
0.659
23
(1.5480, 2.4152)
−16.2893
Algorithm2
1.7235
39
(1.5480, 2.4152)
−16.2893
10 (min)(2,6
,
2)
Algorithm1
0.7662
27
(1.5568, 0.7545)
10.6753
Algorithm2
1.4862
68
(1.5480, 2.4152)
10.6753Example 1 (see [13–15]).
(28)
m
i
n
x
1
+
x
2
x
1
-
x
2
+
7
s
.
t
.
2
x
1
+
x
2
≤
14
,
x
1
+
x
2
≤
10
,
-
4
x
1
+
x
2
≤
0
,
-
2
x
1
-
x
2
≤
-
6
,
-
x
1
-
2
x
2
≤
-
6
,
x
1
-
x
2
≤
3
,
x
1
≥
0
,
x
2
≥
0
.Example 2 (see [13, 16]).
(29)
m
i
n
x
1
+
2
x
1
-
3
x
2
+
13
x
1
+
x
2
-
1
s
.
t
.
-
x
1
+
2
x
2
≤
8
,
-
x
2
≤
-
3
,
x
1
+
2
x
2
≤
12
,
x
1
-
2
x
2
≤
-
5
,
x
1
≥
0
,
x
2
≥
0
.Example 3 (see [13, 17]).
(30)
m
i
n
0.813396
x
1
+
0.67440
x
2
+
0.305038
x
3
+
0.129742
x
4
+
0.217796
×
0.224508
x
1
+
0.063458
x
2
+
0.932230
x
3
+
0.528736
x
4
+
0.091947
s
.
t
.
0.488509
x
1
+
0.063565
x
2
+
0.945686
x
3
+
0.210704
x
4
≤
3.562809
,
-
0.324014
x
1
-
0.501754
x
2
-
0.719204
x
3
+
0.099562
x
4
≤
-
0.052215
,
0.445225
x
1
-
0.346896
x
2
+
0.637939
x
3
-
0.257623
x
4
≤
0.427920
,
-
0.202821
x
1
+
0.647361
x
2
+
0.920135
x
3
-
0.983091
x
4
≤
0.840950
,
-
0.886420
x
1
-
0.802444
x
2
-
0.305441
x
3
-
0.180123
x
4
≤
-
1.353686
,
-
0.515399
x
1
-
0.424820
x
2
+
0.897498
x
3
+
0.187268
x
4
≤
2.137251
,
-
0.591515
x
1
+
0.060581
x
2
-
0.427365
x
3
+
0.579388
x
4
≤
-
0.290987
,
0.423524
x
1
+
0.940496
x
2
-
0.437944
x
3
-
0.742941
x
4
≤
0.373620
,
x
1
≥
0
,
x
2
≥
0
,
x
3
≥
0
,
x
4
≥
0
.Example 4 (see [8, 18]).
(31)
m
i
n
x
1
+
x
1
-
x
2
+
5
x
1
+
x
2
-
1
s
.
t
.
-
2
x
1
-
3
x
2
≤
-
9
,
3
x
1
-
x
2
≤
8
,
-
x
1
+
2
x
2
≤
8
,
x
1
+
2
x
2
≤
12
,
x
1
≥
0
.Example 5 (see [19]).
(32)
m
i
n
x
1
+
x
2
x
1
-
x
2
+
x
1
+
x
2
+
1
x
1
-
x
2
+
1
s
.
t
.
x
1
+
2
x
2
≤
10
,
x
1
-
3
x
2
≤
20
,
1
≤
x
1
≤
3
,
1
≤
x
2
≤
3
.Example 6 (see [19]).
(33)
m
i
n
x
1
+
x
2
x
1
-
x
2
+
x
1
+
x
2
+
2
x
1
-
x
2
+
2
s
.
t
.
x
1
+
2
x
2
≤
20
,
x
1
-
3
x
2
≤
20
,
1
≤
x
1
≤
4
,
1
≤
x
2
≤
4
.Example 7 (see [20]).
(34)
m
i
n
2
x
1
-
2
x
2
+
x
3
+
2
-
2
x
1
+
3
x
2
+
x
3
-
4
+
-
2
x
1
+
x
2
+
x
3
+
2
x
1
+
x
2
-
3
x
3
+
5
+
-
2
x
1
-
x
2
+
2
x
3
+
7
4
x
1
-
x
2
-
2
x
3
-
5
s
.
t
.
x
1
+
x
2
+
x
3
≤
10
,
x
1
-
2
x
2
+
3
x
3
≤
10
,
-
2
x
1
+
2
x
2
+
3
x
3
≤
10
,
-
x
1
+
2
x
2
+
3
x
3
≥
6
,
x
1
≥
1
,
x
2
≥
1
,
x
3
≥
1
.Example 8 (see [21]).
(35)
m
a
x
-
2
x
1
+
3
x
2
-
6
3
x
1
-
5
x
2
+
3
+
4
x
1
-
5
x
2
-
7
-
3
x
1
+
3
x
2
+
4
s
.
t
.
x
1
+
x
2
≤
1.5
,
x
1
-
x
2
≤
0
,
x
1
≥
0
,
x
2
≥
0
.Example 9 (see [22]).
(36)
m
i
n
x
1
+
2
x
2
-
2
-
2
x
1
-
x
2
+
3
+
3
x
1
-
2
x
2
+
3
x
1
-
x
2
-
1
s
.
t
.
-
2
x
1
+
3
x
2
≤
6
,
4
x
1
-
5
x
2
≤
8
,
5
x
1
+
3
x
2
≤
15
,
-
4
x
1
-
3
x
2
≤
-
12
,
x
1
≥
0
,
x
2
≥
0
.Example 10 (see [22]).
(37)
m
i
n
-
x
1
+
2
x
2
-
0.5
-
2
x
1
+
x
2
+
6
+
3
x
1
-
2
x
2
+
6.5
x
1
+
x
2
-
1
s
.
t
.
-
5
x
1
+
8
x
2
≤
24
,
5
x
1
+
8
x
2
≤
44
,
6
x
1
-
3
x
2
≤
15
,
-
4
x
1
-
5
x
2
≤
-
10
,
x
1
≥
0
,
x
2
≥
0
.
To further verify the effectiveness of Algorithm  1, a random problem with variable scale is constructed, which is defined as follows.Example 11.
(38)
m
i
n
f
x
=
∑
i
=
1
p
c
i
T
x
+
d
i
e
i
T
x
+
f
i
s
.
t
.
x
∈
D
=
x
∣
x
∈
R
n
,
A
x
≤
b
,where the real elements of c
i, d
i, e
i, f
i are pseudorandomly generated in the range [
-
0.5,0.5
]; the real elements of A, b are pseudorandomly generated in the range [
0.01,1
]. For Example 11, Algorithms  1 and  2 are used to solve 10 different random instances for each size and present statistics of the results. The computational results are summarized in Table 3, where the following notations have been used in row headers: Avg.Iter is the average number of iterations; Avg.Time is the average execution time in seconds; m is the number of constraints; n is the number of variables.Table 3
Comparison results of Algorithms1 and 2 for Example 11.
(p
,
m
,
n)
Methods
Avg.Time
Avg.Iter
(3, 5, 5)
Algorithm1
0.8520
3.4
Algorithm2
3.8780
13.6
(3, 10, 10)
Algorithm1
1.3142
4.2
Algorithm2
16.1132
46.8
(3, 20, 20)
Algorithm1
23.2650
49.6
Algorithm2
32.5486
66.8
(3, 100, 100)
Algorithm1
42.8972
62.5
Algorithm2
75.0706
32.2
(6, 5, 5)
Algorithm1
3.7030
5.2
Algorithm2
8.6610
16.6
(6, 10, 10)
Algorithm1
5.1134
7.8
Algorithm2
40.2840
69.8
(6, 20, 20)
Algorithm1
12.7132
13.4
Algorithm2
100.4470
128.8
(6, 100, 100)
Algorithm1
31.9760
25.3
Algorithm2
254.5428
183.4
(10, 5, 5)
Algorithm1
17.0344
17.6
Algorithm2
29.5778
30.4
(10, 10, 10)
Algorithm1
26.1132
46.8
Algorithm2
195.9464
136.8
(10, 20, 20)
Algorithm1
32.5126
27.8
Algorithm2
249.4000
169.2
(10, 100, 100)
Algorithm1
42.8972
56.8
Algorithm2
402.0530
215.3From Table1, it can be seen that our algorithm can determine the global optimal solution more effectively than that of [8, 13–22] in most cases. For Examples 8 and 9, although the number of iterations of our algorithm is more than that of the literatures [21, 22], the optimal values and optimal solutions obtained by our algorithm are better than them.From Table2, it can be seen that, for Examples 1–6, Algorithms  1 and  2 all only need one iteration to find the optimal solution; the advantage of Algorithm  1 is not reflected. However, for Examples 7–10, the performance of Algorithm  1 is better than that of Algorithm  2.From Table3, we can see that, for small scale problems, the advantage of Algorithm  1 is not much better than the Algorithm  2, but with the increase of the scale of the problem, the advantage of Algorithm  1 is more and more powerful. For example, when (
p
,
m
,
n
)
=
(
10,5
,
5
), the average running time of Algorithms  1 and  2 is 17.0344 and 29.5778, respectively; the average iterations of Algorithms  1 and  2 are 17.6 and 30.4. However, when (
p
,
m
,
n
)
=
(
10,100,100
), the average running time of Algorithms  1 and  2 is 42.8972 and 402.0530, respectively; the average iterations of Algorithms  1 and  2 are 56.8 and 215.3. It is clear that the efficiency of Algorithm  1 is much better than that of Algorithm  2 for large scale problems. In addition, from Table 3, we also can see that, compared with m and n, the impact of p on our algorithm is even greater; the Avg.Time and Avg.Iter of Algorithm  1 are not increased significantly with the increase of the problem size.The comparison results of Tables2 and 3 show that the pruning techniques are very good at improving the convergence speed of our algorithm.The test results show that our algorithm is both feasible and efficient.



---

*Source: 3204368-2016-08-31.xml*