# A Linearized Relaxing Algorithm for the Specific Nonlinear Optimization Problem

Authors: Mio Horai; Hideo Kobayashi; Takashi G. Nitta
Journal: Abstract and Applied Analysis
 (2016)

---

## Abstract

We propose a new method for the specific nonlinear and nonconvex global optimization problem by using a linear relaxation technique. To simplify the specific nonlinear and nonconvex optimization problem, we transform the problem to the lower linear relaxation form, and we solve the linear relaxation optimization problem by the Branch and Bound Algorithm. Under some reasonable assumptions, the global convergence of the algorithm is certified for the problem. Numerical results show that this method is more efficient than the previous methods.


---

## Body

## 1. Introduction

Optimization problems appeared in many subjects [1–3], for example, technology [4–7] and economy [8–10]. There is a long history of creating the method for solving the problem [11–14]. We consider the following certain nonlinear optimization problem on the set X
≔
{
x
∈
R
N
∣
0
<
x
_
i
≤
x
i
≤
x
¯
i
<
∞
(
i
=
1,2
,
…
,
N
)
}
⊂
R
N.LetT
j
a
,
T
j
b
,
T
k
j
´
c
,
T
k
j
´
d be natural numbers, let β
j
t
a
,
β
j
t
b
,
β
k
j
´
t
c
,
β
k
j
´
t
d be nonzero real constants, and let γ
j
t
i
a
,
γ
j
t
i
b
,
γ
k
j
´
t
i
c
,
γ
k
j
´
t
i
d be real constants. Then we put the four kinds of functions on X:(1)
a
j
x
≔
∑
t
=
1
T
j
a
β
j
t
a
∏
i
=
1
N
x
i
γ
j
t
i
a
,
b
j
x
≔
∑
t
=
1
T
j
b
β
j
t
b
∏
i
=
1
N
x
i
γ
j
t
i
b
,
c
k
j
´
x
≔
∑
t
=
1
T
k
j
´
c
β
k
j
´
t
c
∏
i
=
1
N
x
i
γ
k
j
´
t
i
c
,
d
k
j
´
x
≔
∑
t
=
1
T
k
j
´
d
β
k
j
´
t
d
∏
i
=
1
N
x
i
γ
k
j
´
t
i
d
,
j
=
1,2
,
…
,
P
,
j
´
=
1,2
,
…
,
P
k
,
k
=
1,2
,
…
,
M
.Let h
j
,
h
k
j
´ be two secondly differentiable functions R
↦
R satisfying the following conditions: (2)
h
j
′
>
0
o
r
h
j
′
<
0
,
h
k
j
´
′
>
0
o
r
h
k
j
´
′
<
0
,
h
j
′
′
>
0
o
r
h
j
′
′
<
0
,
h
k
j
´
′
′
>
0
o
r
h
k
j
´
′
′
<
0
.We consider the following nonlinear optimization problemP on X:P
m
i
n
f
0
x
=
∑
j
=
1
P
h
j
b
j
x
a
j
x
s.t.
f
k
x
=
∑
j
´
=
1
P
k
h
k
j
´
d
k
j
´
x
c
k
j
´
x
≤
0
j
´
=
1
,
…
,
P
k
,
k
=
1
,
…
,
M
. We propose a specific nonlinear and nonconvex optimization technique for P. It is generalized by Jiao et al., 2013 [4].In the previous our work [15], we treat the same problem P applying Pei-Ping and Gui-Xia’s [5]. The method needs to add the new valuables and takes a long time to solve the optimal problem.Jiao et al. propose the technique which does not launch new ones for the following problems:P
∗
m
i
n
h
0
x
=
∑
j
=
1
P
b
j
x
a
j
x
s.t.
h
k
x
=
∑
j
´
=
1
P
k
c
k
j
´
x
≤
0
j
´
=
1
,
…
,
P
k
,
k
=
1
,
…
,
M
,
x
∈
X
.We generalize the problem P
∗ to P and use Hongwei’s idea [4, 16] to solve the problem P; that is, we propose the new method by generalizing Hongwei’s method.Firstly, we transformP to linear relaxation problem of it. Secondly, we obtain the approximate value by Simplex method and Branch and Bound Algorithm [17, 18]. For advance preparation of the linearization, we transform the valuables x
i
=
exp
⁡
(
y
i
)
(
i
=
1,2
,
…
,
N
). Let x
_
i
≔
exp
⁡
(
y
_
i
), x
¯
i
≔
exp
⁡
(
y
¯
i
), and Y
≔
{
y
∈
R
N
∣
y
_
i
≤
y
i
≤
y
¯
i
<
∞
(
i
=
1,2
,
…
,
N
)
}.We denote(3)
a
j
y
≔
∑
t
=
1
T
j
a
β
j
t
a
exp
⁡
∑
i
=
1
N
γ
j
t
i
a
y
i
,
b
j
y
≔
∑
t
=
1
T
j
b
β
j
t
b
exp
⁡
∑
i
=
1
N
γ
j
t
i
b
y
i
,
c
k
j
´
y
≔
∑
t
=
1
T
k
j
´
c
β
k
j
´
t
c
exp
⁡
∑
i
=
1
N
γ
k
j
´
t
i
c
y
i
,
d
k
j
´
y
≔
∑
t
=
1
T
k
j
´
d
β
k
j
´
t
d
exp
⁡
∑
i
=
1
N
γ
k
j
´
t
i
d
y
i
j
=
1,2
,
…
,
P
,
j
´
=
1,2
,
…
,
P
k
,
k
=
1,2
,
…
,
M
.Accordingly, we obtain the equivalence problem of P:P
0
m
i
n
f
0
y
=
∑
j
=
1
P
h
j
b
j
y
a
j
y
s.t.
f
k
y
=
∑
j
´
=
1
P
k
h
k
j
´
d
k
j
´
y
c
k
j
´
y
≤
0
j
´
=
1
,
…
,
P
k
,
k
=
1
,
…
,
M
y
∈
Y
.As the function “exp” is convex function, we find the lower and upper bounded linearized function of it.In Section2, we show how to linearize the original problem P. In Section 3, we present our method by using the Branch and Bound Algorithm. In Section 4, we prove the convergence of the algorithm. In Section 5, we treat numerical experiments.


## 2. Linear Relaxation Programing

In this section, we show how to transformP
0 to the linear relaxation problem.We define(4)
Y
j
t
a
≔
∑
i
=
1
N
γ
j
t
i
a
y
i
.Corresponding to the transformation of coordinates, the domain is changed fromy to Y, as follows:(5)
Y
_
j
t
a
≔
∑
i
=
1
N
min
⁡
γ
j
t
i
a
y
_
i
,
γ
j
t
i
a
y
¯
i
,
Y
¯
j
t
a
≔
∑
i
=
1
N
max
⁡
γ
j
t
i
a
y
_
i
,
γ
j
t
i
a
y
¯
i
.Since all β
j
t
a
exp
⁡
(
Y
j
t
a
) are convex, there exist the lower and upper bounded linear functions for them. We denote these functions by L
β
j
t
a
l
(
Y
j
t
a
) and L
β
j
t
a
u
(
Y
j
t
a
).Whenβ
j
t
a is negative, we can define the lower linearized function L
β
j
t
a
l
(
Y
j
t
a
):(6)
L
β
j
t
a
l
Y
j
t
a
≔
β
j
t
a
exp
⁡
Y
¯
j
t
a
-
β
j
t
a
exp
⁡
Y
_
j
t
a
Y
¯
j
t
a
-
Y
_
j
t
a
Y
j
t
a
-
Y
_
j
t
a
+
β
j
t
a
exp
⁡
Y
_
j
t
a
.Since each β
j
t
a
exp
⁡
(
Y
j
t
a
) is continuous and differentiable on [
Y
_
j
t
a
,
Y
¯
j
t
a
], there exists c
j
t
a
∈
Y
_
j
t
a
,
Y
¯
j
t
a such that(7)
β
j
t
a
e
x
p
′
c
j
t
a
=
β
j
t
a
e
x
p
Y
¯
j
t
a
-
β
j
t
a
e
x
p
Y
_
j
t
a
Y
¯
j
t
a
-
Y
_
j
t
aby the mean value theorem.Sinceβ
j
t
a
exp
⁡
(
Y
j
t
a
) is monotonic function on [
Y
_
j
t
a
,
Y
¯
j
t
a
], there exists the inverse function of β
j
t
a
e
x
p
′
(
Y
j
t
a
). Hence c
j
t
a is uniquely given such that(8)
c
j
t
a
=
β
j
t
a
e
x
p
′
-
1
β
j
t
a
exp
⁡
Y
¯
j
t
a
-
β
j
t
a
exp
⁡
Y
_
j
t
a
Y
¯
j
t
a
-
Y
_
j
t
a
.When β
j
t
a is positive, we define L
β
j
t
a
l
(
Y
j
t
a
):(9)
L
β
j
t
a
l
Y
j
t
a
≔
β
j
t
a
exp
⁡
Y
¯
j
t
a
-
β
j
t
a
exp
⁡
Y
_
j
t
a
Y
¯
j
t
a
-
Y
_
j
t
a
Y
j
t
a
-
c
j
t
a
+
β
j
t
a
exp
⁡
c
j
t
a
.For the upper linearized function of β
j
t
a
exp
⁡
(
Y
j
t
a
), we define L
β
j
t
a
u
(
Y
j
t
a
) as follows.Whenβ
j
t
a is negative, we define(10)
L
β
j
t
a
u
Y
j
t
a
≔
β
j
t
a
exp
⁡
Y
¯
j
t
a
-
β
j
t
a
exp
⁡
Y
_
j
t
a
Y
¯
j
t
a
-
Y
_
j
t
a
Y
j
t
a
-
c
j
t
a
+
β
j
t
a
exp
⁡
c
j
t
a
.Whenβ
j
t
a is positive, we define L
β
j
t
a
u
(
Y
j
t
a
):(11)
L
β
j
t
a
u
Y
j
t
a
≔
β
j
t
a
exp
⁡
Y
¯
j
t
a
-
β
j
t
a
exp
⁡
Y
_
j
t
a
Y
¯
j
t
a
-
Y
_
j
t
a
Y
j
t
a
-
Y
_
j
t
a
+
β
j
t
a
exp
⁡
Y
_
j
t
a
.As the above definitions, we have the lower and upper linearized functions of a
j
(
y
); that is, (12)
l
a
j
l
y
≔
∑
t
=
1
T
j
a
L
β
j
t
a
l
Y
j
t
a
,
l
a
j
u
y
≔
∑
t
=
1
T
j
a
L
β
j
t
a
u
Y
j
t
a
,and l
b
j
l
(
y
), l
b
j
u
(
y
), l
c
k
j
´
l
(
y
), l
c
k
j
´
u
(
y
), l
d
k
j
´
l
(
y
), and l
d
k
j
´
u
(
y
) are also defined for b
j
(
y
), c
k
j
´
(
y
), and d
k
j
´
(
y
) as the same method. Moreover, we can assume l
a
j
l
(
y
)
>
0, l
b
j
l
(
y
)
>
0, l
c
k
j
´
l
(
y
)
>
0, and l
d
k
j
´
l
(
y
)
>
0 by adding some constraints.Now, we define the new valuablesY
a
b
j
∈
min
⁡
l
b
j
l
(
y
)
/
max
⁡
l
a
j
u
(
y
)
,
max
⁡
l
b
j
u
(
y
)
/
min
⁡
l
a
j
l
(
y
) and Y
c
d
k
j
´
∈
min
⁡
l
d
k
j
´
l
(
y
)
/
max
⁡
l
c
k
j
´
u
(
y
)
,
max
⁡
l
d
k
j
´
u
(
y
)
/
min
⁡
l
c
k
j
´
l
(
y
). Let us consider the lower linearized functions l
h
j, l
h
k
j
´ for h
j, h
k
j
´. We suppose l
h
j as follows.Case 1 (h
j
′
>
0).
In the case, we put the valuableY
a
b
j
∈
Y
_
a
b
j
,
Y
¯
a
b
j; that is, Y
_
a
b
j
≔
min
⁡
l
b
j
l
y
/
max
⁡
l
a
j
u
y, Y
¯
a
b
j
≔
max
⁡
l
b
j
l
(
y
)
/
max
⁡
l
a
j
u
(
y
).
Ash
j
′
>
0, h
j
l
b
j
l
(
y
)
/
l
a
j
u
(
y
)
≤
h
j
b
j
(
y
)
/
a
j
(
y
).
Whenh
j
′
′
<
0, we define the lower linearized functions of h
j as follows:(13)
l
h
j
Y
a
b
j
≔
h
j
Y
¯
a
b
j
-
h
j
Y
_
a
b
j
Y
¯
a
b
j
-
Y
_
a
b
j
Y
a
b
j
-
Y
_
a
b
j
+
h
j
Y
_
a
b
j
.Incidentally, as h
j
(
Y
a
b
j
) is continuous and differentiable on [
Y
_
a
b
j
,
Y
¯
a
b
j
], there exists C
h
j
∈
Y
_
a
b
j
,
Y
¯
a
b
j such that h
j
′
(
C
h
j
)
=
h
j
Y
¯
a
b
j
-
h
j
Y
_
a
b
j
/
Y
¯
a
b
j
-
Y
_
a
b
j by the mean value theorem.
Sinceh
j
′
(
Y
a
b
j
) is monotonic function on [
Y
_
a
b
j
,
Y
¯
a
b
j
], there exists the inverse function of h
j
′
(
Y
a
b
j
). Hence C
h
j is uniquely given such that (14)
C
h
j
=
h
j
′
-
1
h
j
Y
¯
a
b
j
-
h
j
Y
_
a
b
j
Y
¯
a
b
j
-
Y
_
a
b
j
.When h
j
′
′
>
0, we define the lower linear function l
h
j as the following:(15)
l
h
j
Y
a
b
j
≔
h
j
Y
¯
a
b
j
-
h
j
Y
_
a
b
j
Y
¯
a
b
j
-
Y
_
a
b
j
Y
a
b
j
-
C
h
j
+
h
j
C
h
j
.Similarly, l
h
k
j
´ is defined as above.Case 2 (h
j
′
<
0).
In the case, we put the valuableY
a
b
j
∈
Y
_
a
b
j
,
Y
¯
a
b
j; that is, Y
_
a
b
j
≔
min
⁡
l
b
j
u
(
y
)
/
min
⁡
l
a
j
l
(
y
) and Y
¯
a
b
j
≔
max
⁡
l
b
j
u
(
y
)
/
min
⁡
l
a
j
l
(
y
).
Ash
j
′
<
0, h
j
l
b
j
u
(
y
)
/
l
a
j
l
(
y
)
≤
h
j
b
j
(
y
)
/
a
j
(
y
).
Whenh
j
′
′
<
0, we define the linear functions l
h
j; that is,(16)
l
h
j
Y
a
b
j
≔
h
j
Y
¯
a
b
j
-
h
j
Y
_
a
b
j
Y
¯
a
b
j
-
Y
_
a
b
j
Y
a
b
j
-
Y
_
a
b
j
+
h
j
Y
_
a
b
j
.When h
j
′
′
>
0, we define l
h
j as follows:(17)
l
h
j
Y
a
b
j
≔
h
j
Y
¯
a
b
j
-
h
j
Y
_
a
b
j
Y
¯
a
b
j
-
Y
_
a
b
j
Y
a
b
j
-
C
h
j
+
h
j
C
h
j
.
l
h
k
j
´ is also defined as the above.We have the lower bounded linearized optimization problem ofP
0; that is, L
R
P
P
0
m
i
n
l
f
0
y
=
∑
j
=
1
P
l
h
j
y
s.t.
l
f
k
y
=
∑
j
=
1
P
k
l
h
k
j
´
y
≤
0
.We rewrite our problem P putting some technical assumption.We assumel
a
j
l
(
x
)
>
0, l
b
j
l
(
x
)
>
0, l
c
k
j
´
l
(
x
)
>
0, and l
d
k
j
´
l
(
x
)
>
0, and the problem is P
′
m
i
n
f
0
x
=
∑
j
=
1
P
h
j
b
j
x
a
j
x
s.t.
f
k
x
=
∑
j
´
=
1
P
k
h
k
j
´
d
k
j
´
x
c
k
j
´
x
≤
0
j
´
=
1
,
…
,
P
k
,
k
=
1
,
…
,
M
x
∈
X
,where h
j on min
⁡
l
b
j
l
(
x
)
/
max
⁡
l
a
j
u
(
x
)
,
max
⁡
l
b
j
u
(
x
)
/
min
⁡
l
a
j
l
(
x
) and h
k
j
´ on min
⁡
l
d
k
j
´
l
(
x
)
/
max
⁡
l
c
k
j
´
u
(
x
)
,
max
⁡
l
d
k
j
´
u
(
x
)
/
min
⁡
l
c
k
j
´
l
(
x
) satisfied the following condition:(18)
h
j
′
>
0
o
r
h
j
′
<
0
,
h
k
j
´
′
>
0
o
r
h
k
j
´
′
<
0
,
h
j
′
′
>
0
o
r
h
j
′
′
<
0
,
h
k
j
´
′
′
>
0
o
r
h
k
j
´
′
′
<
0
.


## 3. Branch and Bound Algorithm

In this section, we use the Simplex method and the Branch and Bound Algorithm and show how to find the approximate value ofP
0.We set the initial domainY
0
≔
Y, the active domain set Q
q, and the active domain Y
q
(
m
)
=
{
y
∣
y
_
i
q
m
≤
y
i
q
m
≤
y
¯
i
q
m
,
i
=
1
,
…
,
N
}
⊆
Y
0, where q is the times of the cutting domains and the number of the stages in the algorithm and m is the number of the active domains on stage q. If Y
q
(
m
) is active domain, we divide Y
q
(
m
) into half domains Y
q
(
m
)
·
1
,
Y
q
(
m
)
·
2. On each domain, we linearize the problem P
0 and solve the linearized problems L
R
P
P
0) to obtain the lower and upper bound values of P
0. After the repeat of the above calculations, we obtain the convergence for the sequences of the lower and upper bound values. The procedure leads the optimal value and the optimal solution for our problem.


### 3.1. Branching Rule

We select the branching variablei such that i
=
n
max
⁡
{
y
¯
n
q
(
m
)
-
y
_
n
q
(
m
)
,
n
=
1,2
,
…
,
N
}. We divide the interval [
y
_
i
q
(
m
)
,
y
¯
i
q
(
m
)
] into half intervals: [
y
_
i
q
(
m
)
,
(
y
_
i
q
(
m
)
+
y
¯
i
q
(
m
)
)
/
2
] and [
(
y
_
i
q
(
m
)
+
y
¯
i
q
(
m
)
)
/
2
,
y
¯
i
q
(
m
)
].


### 3.2. Algorithm Statement

Step 0. Let q be 0, and let m be 1. We set an appropriate ϵ-value as a convergence tolerance, the initial upper bound V
∗
=
∞, and Q
0
=
{
Y
0
(
1
)
}. We solve L
R
P
(
Y
0
(
1
)
), and we write y
^
(
Y
0
(
1
)
) and L
B
0
(
1
) for the linear optimal solution and optimal value. If y
^
(
Y
0
(
1
)
) is feasible for P
0, update V
∗
=
f
0
(
y
^
(
Y
0
(
1
)
)
) and we set the initial lower bound L
B
=
L
B
0
(
1
). If V
∗
-
L
B
≤
ϵ, then we get the ϵ-approximate optimal value f
0
(
y
^
(
Y
0
(
1
)
)
) and optimal solution y
^
(
Y
0
(
1
)
) of P
0, so we stop this algorithm. Otherwise, we proceed to Step 1.Step 1. For all m, we divide Y
q
(
m
) into two half domains Y
q
(
m
)
·
1 and Y
q
(
m
)
·
2 according to above branching rule.Step 2. For all m and each domain Y
q
(
m
)
·
v
(
v
=
1,2
), we calculate(19)
f
_
k
v
=
∑
j
´
=
1
,
h
k
j
´
′
>
0
P
k
h
k
j
´
Y
_
c
d
_
k
j
´
Y
q
m
·
v
+
∑
j
´
=
1
,
h
k
j
´
′
<
0
P
k
h
k
j
´
Y
¯
c
d
¯
k
j
´
Y
q
m
·
v
k
=
1
,
…
,
M
,where Y
_
c
d
_
k
j
´
Y
q
(
m
)
·
v
,
Y
¯
c
d
¯
k
j
´
Y
q
(
m
)
·
v are defined on Y
q
(
m
)
·
v: (20)
Y
_
c
d
_
k
j
´
Y
q
m
·
v
≔
∑
t
=
1
,
β
k
j
´
t
d
>
0
T
k
j
´
d
β
k
j
´
t
d
exp
⁡
∑
i
=
1
,
γ
k
j
´
t
i
d
>
0
N
γ
k
j
´
t
i
d
y
i
_
+
∑
i
=
1
,
γ
k
j
´
t
i
d
<
0
N
γ
k
j
´
t
i
d
y
i
¯
+
∑
t
=
1
,
β
k
j
´
t
d
<
0
T
k
j
´
d
β
k
j
´
t
d
exp
⁡
∑
i
=
1
,
γ
k
j
´
t
i
d
>
0
N
γ
k
j
´
t
i
d
y
i
¯
+
∑
i
=
1
,
γ
k
j
´
t
i
d
<
0
N
γ
k
j
´
t
i
d
y
i
_
∑
t
=
1
,
β
k
j
´
t
c
>
0
T
k
j
´
c
β
k
j
´
t
c
exp
⁡
∑
i
=
1
,
γ
k
j
´
t
i
c
>
0
N
γ
k
j
´
t
i
c
y
i
¯
+
∑
i
=
1
,
γ
k
j
´
t
i
c
<
0
N
γ
k
j
´
t
i
c
y
i
_
+
∑
t
=
1
,
β
k
j
´
t
c
<
0
T
k
j
´
c
β
k
j
´
t
c
exp
⁡
∑
i
=
1
,
γ
k
j
´
t
i
c
>
0
N
γ
k
j
´
t
i
c
y
i
_
+
∑
i
=
1
,
γ
k
j
´
t
i
c
<
0
N
γ
k
j
´
t
i
c
y
i
¯
.
Y
¯
c
d
¯
k
j
´
Y
q
m
·
v
≔
∑
t
=
1
,
β
k
j
´
t
d
>
0
T
k
j
´
d
β
k
j
´
t
d
exp
⁡
∑
i
=
1
,
γ
k
j
´
t
i
d
>
0
N
γ
k
j
´
t
i
d
y
i
¯
+
∑
i
=
1
,
γ
k
j
´
t
i
d
<
0
N
γ
k
j
´
t
i
d
y
i
_
+
∑
t
=
1
,
β
k
j
´
t
d
<
0
T
k
j
´
d
β
k
j
´
t
d
e
x
p
∑
i
=
1
,
γ
k
j
´
t
i
d
>
0
N
γ
k
j
´
t
i
d
y
i
_
+
∑
i
=
1
,
γ
k
j
´
t
i
d
<
0
N
γ
k
j
´
t
i
d
y
i
¯
∑
t
=
1
,
β
k
j
´
t
c
>
0
T
k
j
´
c
β
k
j
´
t
c
exp
⁡
∑
i
=
1
,
γ
k
j
´
t
i
c
>
0
N
γ
k
j
´
t
i
c
y
i
_
+
∑
i
=
1
,
γ
k
j
´
t
i
c
<
0
N
γ
k
j
´
t
i
c
y
i
¯
+
∑
t
=
1
,
β
k
j
´
t
c
<
0
T
k
j
´
c
β
k
j
´
t
c
exp
⁡
∑
i
=
1
,
γ
k
j
´
t
i
c
>
0
N
γ
k
j
´
t
i
c
y
i
¯
+
∑
i
=
1
,
γ
k
j
´
t
i
c
<
0
N
γ
k
j
´
t
i
c
y
i
_
.If there is f
_
k
(
v
) that satisfies f
_
k
(
v
)
>
0 for some k
∈
{
1,2
,
…
,
M
}, the domain Y
q
m
·
v is infeasible for P
0. In the case, we delete the domain from Q
q. If Y
q
(
m
)
·
v
(
v
=
1,2
) are deleted for all m, then the problem has no feasible solution.Step 3. For left domains, we solve L
R
P
(
Y
q
(
m
)
·
v
) by the Simplex algorithm, and we write (
y
^
(
Y
q
(
m
)
·
v
)
,
L
B
q
(
m
)
·
v
) for the obtained linear optimal solution and the value. If y
^
(
Y
q
(
m
)
·
v
) is feasible for P
0, we update V
∗
=
min
⁡
{
V
∗
,
f
0
(
y
^
(
Y
q
(
m
)
·
v
)
)
}. If L
B
q
(
m
)
·
v
>
V
∗, we delete the corresponding domain from Q
q. If V
∗
-
L
B
q
(
m
)
·
v
≤
ϵ, we obtain the ϵ-approximate optimal value f
0
(
y
^
(
Y
q
(
m
)
·
v
)
) and optimal solution y
^
(
Y
q
(
m
)
·
v
) of P
0. Hence we stop this algorithm. Otherwise, we proceed to Step 4.Step 4. We update the index of left domains Y
q
(
m
)
·
v to Y
q
+
1
(
m
). We initialize m and settle that Q
q
+
1 is a set of Y
q
+
1
(
m
) and go to Step 1.


## 3.1. Branching Rule

We select the branching variablei such that i
=
n
max
⁡
{
y
¯
n
q
(
m
)
-
y
_
n
q
(
m
)
,
n
=
1,2
,
…
,
N
}. We divide the interval [
y
_
i
q
(
m
)
,
y
¯
i
q
(
m
)
] into half intervals: [
y
_
i
q
(
m
)
,
(
y
_
i
q
(
m
)
+
y
¯
i
q
(
m
)
)
/
2
] and [
(
y
_
i
q
(
m
)
+
y
¯
i
q
(
m
)
)
/
2
,
y
¯
i
q
(
m
)
].


## 3.2. Algorithm Statement

Step 0. Let q be 0, and let m be 1. We set an appropriate ϵ-value as a convergence tolerance, the initial upper bound V
∗
=
∞, and Q
0
=
{
Y
0
(
1
)
}. We solve L
R
P
(
Y
0
(
1
)
), and we write y
^
(
Y
0
(
1
)
) and L
B
0
(
1
) for the linear optimal solution and optimal value. If y
^
(
Y
0
(
1
)
) is feasible for P
0, update V
∗
=
f
0
(
y
^
(
Y
0
(
1
)
)
) and we set the initial lower bound L
B
=
L
B
0
(
1
). If V
∗
-
L
B
≤
ϵ, then we get the ϵ-approximate optimal value f
0
(
y
^
(
Y
0
(
1
)
)
) and optimal solution y
^
(
Y
0
(
1
)
) of P
0, so we stop this algorithm. Otherwise, we proceed to Step 1.Step 1. For all m, we divide Y
q
(
m
) into two half domains Y
q
(
m
)
·
1 and Y
q
(
m
)
·
2 according to above branching rule.Step 2. For all m and each domain Y
q
(
m
)
·
v
(
v
=
1,2
), we calculate(19)
f
_
k
v
=
∑
j
´
=
1
,
h
k
j
´
′
>
0
P
k
h
k
j
´
Y
_
c
d
_
k
j
´
Y
q
m
·
v
+
∑
j
´
=
1
,
h
k
j
´
′
<
0
P
k
h
k
j
´
Y
¯
c
d
¯
k
j
´
Y
q
m
·
v
k
=
1
,
…
,
M
,where Y
_
c
d
_
k
j
´
Y
q
(
m
)
·
v
,
Y
¯
c
d
¯
k
j
´
Y
q
(
m
)
·
v are defined on Y
q
(
m
)
·
v: (20)
Y
_
c
d
_
k
j
´
Y
q
m
·
v
≔
∑
t
=
1
,
β
k
j
´
t
d
>
0
T
k
j
´
d
β
k
j
´
t
d
exp
⁡
∑
i
=
1
,
γ
k
j
´
t
i
d
>
0
N
γ
k
j
´
t
i
d
y
i
_
+
∑
i
=
1
,
γ
k
j
´
t
i
d
<
0
N
γ
k
j
´
t
i
d
y
i
¯
+
∑
t
=
1
,
β
k
j
´
t
d
<
0
T
k
j
´
d
β
k
j
´
t
d
exp
⁡
∑
i
=
1
,
γ
k
j
´
t
i
d
>
0
N
γ
k
j
´
t
i
d
y
i
¯
+
∑
i
=
1
,
γ
k
j
´
t
i
d
<
0
N
γ
k
j
´
t
i
d
y
i
_
∑
t
=
1
,
β
k
j
´
t
c
>
0
T
k
j
´
c
β
k
j
´
t
c
exp
⁡
∑
i
=
1
,
γ
k
j
´
t
i
c
>
0
N
γ
k
j
´
t
i
c
y
i
¯
+
∑
i
=
1
,
γ
k
j
´
t
i
c
<
0
N
γ
k
j
´
t
i
c
y
i
_
+
∑
t
=
1
,
β
k
j
´
t
c
<
0
T
k
j
´
c
β
k
j
´
t
c
exp
⁡
∑
i
=
1
,
γ
k
j
´
t
i
c
>
0
N
γ
k
j
´
t
i
c
y
i
_
+
∑
i
=
1
,
γ
k
j
´
t
i
c
<
0
N
γ
k
j
´
t
i
c
y
i
¯
.
Y
¯
c
d
¯
k
j
´
Y
q
m
·
v
≔
∑
t
=
1
,
β
k
j
´
t
d
>
0
T
k
j
´
d
β
k
j
´
t
d
exp
⁡
∑
i
=
1
,
γ
k
j
´
t
i
d
>
0
N
γ
k
j
´
t
i
d
y
i
¯
+
∑
i
=
1
,
γ
k
j
´
t
i
d
<
0
N
γ
k
j
´
t
i
d
y
i
_
+
∑
t
=
1
,
β
k
j
´
t
d
<
0
T
k
j
´
d
β
k
j
´
t
d
e
x
p
∑
i
=
1
,
γ
k
j
´
t
i
d
>
0
N
γ
k
j
´
t
i
d
y
i
_
+
∑
i
=
1
,
γ
k
j
´
t
i
d
<
0
N
γ
k
j
´
t
i
d
y
i
¯
∑
t
=
1
,
β
k
j
´
t
c
>
0
T
k
j
´
c
β
k
j
´
t
c
exp
⁡
∑
i
=
1
,
γ
k
j
´
t
i
c
>
0
N
γ
k
j
´
t
i
c
y
i
_
+
∑
i
=
1
,
γ
k
j
´
t
i
c
<
0
N
γ
k
j
´
t
i
c
y
i
¯
+
∑
t
=
1
,
β
k
j
´
t
c
<
0
T
k
j
´
c
β
k
j
´
t
c
exp
⁡
∑
i
=
1
,
γ
k
j
´
t
i
c
>
0
N
γ
k
j
´
t
i
c
y
i
¯
+
∑
i
=
1
,
γ
k
j
´
t
i
c
<
0
N
γ
k
j
´
t
i
c
y
i
_
.If there is f
_
k
(
v
) that satisfies f
_
k
(
v
)
>
0 for some k
∈
{
1,2
,
…
,
M
}, the domain Y
q
m
·
v is infeasible for P
0. In the case, we delete the domain from Q
q. If Y
q
(
m
)
·
v
(
v
=
1,2
) are deleted for all m, then the problem has no feasible solution.Step 3. For left domains, we solve L
R
P
(
Y
q
(
m
)
·
v
) by the Simplex algorithm, and we write (
y
^
(
Y
q
(
m
)
·
v
)
,
L
B
q
(
m
)
·
v
) for the obtained linear optimal solution and the value. If y
^
(
Y
q
(
m
)
·
v
) is feasible for P
0, we update V
∗
=
min
⁡
{
V
∗
,
f
0
(
y
^
(
Y
q
(
m
)
·
v
)
)
}. If L
B
q
(
m
)
·
v
>
V
∗, we delete the corresponding domain from Q
q. If V
∗
-
L
B
q
(
m
)
·
v
≤
ϵ, we obtain the ϵ-approximate optimal value f
0
(
y
^
(
Y
q
(
m
)
·
v
)
) and optimal solution y
^
(
Y
q
(
m
)
·
v
) of P
0. Hence we stop this algorithm. Otherwise, we proceed to Step 4.Step 4. We update the index of left domains Y
q
(
m
)
·
v to Y
q
+
1
(
m
). We initialize m and settle that Q
q
+
1 is a set of Y
q
+
1
(
m
) and go to Step 1.


## 4. Convergence of the Optimization Method

In this section, we prove the following two theorems to guarantee the convergence of our optimization method.Theorem 1.
Ify
¯
-
y
_
→
0, then (21)
∑
j
=
1
P
h
j
y
-
∑
j
=
1
P
l
h
j
y
⟶
0
,
(22)
∑
j
=
1
P
k
h
k
j
´
y
-
∑
j
=
1
P
k
l
h
k
j
´
y
⟶
0
.One proves convergence (21). The convergence of (22) is proved by the same procedure as (21).Proof.
We show the following.
Ify
¯
-
y
_
→
0, then h
j
(
y
)
-
l
h
j
(
y
)
→
0 for each j. Consider (23)
h
j
y
-
l
h
j
y
=
h
j
b
j
y
a
j
y
-
l
h
j
l
b
j
l
y
max
⁡
l
a
j
u
y
=
h
j
b
j
y
a
j
y
-
l
h
j
b
j
y
a
j
y
+
l
h
j
b
j
y
a
j
y
-
l
h
j
l
b
j
l
y
a
j
y
+
l
h
j
l
b
j
l
y
a
j
y
-
l
h
j
l
b
j
l
y
l
a
j
u
y
+
l
h
j
l
b
j
l
y
l
a
j
u
y
-
l
h
j
l
b
j
l
y
max
⁡
l
a
j
u
y
≤
h
j
b
j
y
a
j
y
-
l
h
j
b
j
y
a
j
y
+
l
h
j
b
j
y
a
j
y
-
l
h
j
l
b
j
l
y
a
j
y
+
l
h
j
l
b
j
l
y
a
j
y
-
l
h
j
l
b
j
l
y
l
a
j
u
y
+
l
h
j
l
b
j
l
y
l
a
j
u
y
-
l
h
j
l
b
j
l
y
max
⁡
l
a
j
u
y
.We prove the convergence of the 4 terms of the above.
(i) The proof ofh
j
b
j
(
y
)
/
a
j
(
y
)
-
l
h
j
b
j
(
y
)
/
a
j
(
y
)
→
0 is as follows.
Whenh
j
′
′
>
0, we define the lower linearized function of h
j
(
y
); that is,(24)
l
h
j
Y
a
b
j
≔
h
j
Y
¯
a
b
j
-
h
j
Y
_
a
b
j
Y
¯
a
b
j
-
Y
_
a
b
j
Y
a
b
j
-
C
h
j
+
h
j
C
h
j
.Then (25)
max
⁡
h
j
Y
a
b
j
-
l
h
j
Y
a
b
j
=
h
j
Y
a
b
j
-
h
j
Y
¯
a
b
j
-
h
j
Y
_
a
b
j
Y
¯
a
b
j
-
Y
_
a
b
j
Y
a
b
j
-
C
h
j
+
h
j
C
h
j
.We put I
Y
a
b
j
≔
Y
¯
a
b
j
-
Y
_
a
b
j, C
h
j
=
Y
_
a
b
j
+
θ
a
b
j
·
I
Y
a
b
j
0
≤
θ
a
b
j
≤
1. It is∗
1
h
j
Y
a
b
j
-
h
j
Y
¯
a
b
j
-
h
j
Y
_
a
b
j
Y
¯
a
b
j
-
Y
_
a
b
j
Y
a
b
j
-
Y
_
a
b
j
-
θ
a
b
j
·
I
Y
a
b
j
-
h
j
Y
_
a
b
j
+
θ
a
b
j
·
I
Y
a
b
j
=
h
j
Y
_
a
b
j
+
h
j
Y
¯
a
b
j
-
h
j
Y
_
a
b
j
θ
a
b
j
·
I
Y
a
b
j
-
h
j
Y
_
a
b
j
+
θ
a
b
j
·
I
Y
a
b
j
⋯
.If y
¯
-
y
_
→
0, then θ
a
b
j
·
I
Y
a
b
j
→
0. Hence ∗
1  →
0.
Whenh
j
′
′
<
0, we define l
h
j
(
Y
a
b
j
) as follows:(26)
l
h
j
Y
a
b
j
≔
h
j
Y
¯
a
b
j
-
h
j
Y
_
a
b
j
Y
¯
a
b
j
-
Y
_
a
b
j
Y
a
b
j
-
Y
_
a
b
j
+
h
j
Y
_
a
b
j
.
∗
2
max
⁡
h
j
Y
a
b
j
-
l
h
j
Y
a
b
j
=
h
j
C
h
j
-
l
h
j
C
h
j
=
h
j
Y
_
a
b
j
+
θ
a
b
j
·
I
Y
a
b
j
-
h
j
Y
¯
a
b
j
-
h
j
Y
_
a
b
j
Y
¯
a
b
j
-
Y
_
a
b
j
Y
_
a
b
j
+
θ
a
b
j
·
I
Y
a
b
j
-
Y
_
a
b
j
-
h
j
Y
_
a
b
j
⋯
.When y
¯
-
y
_
→
0, then θ
a
b
j
·
I
Y
a
b
j
→
0. Then ∗
2  →
0.
(ii) The proof ofl
h
j
b
j
(
y
)
/
a
j
(
y
)
-
l
h
j
l
b
j
l
(
y
)
/
a
j
(
y
)
→
0 is as follows.
We show thatb
j
(
y
)
-
l
b
j
l
(
y
)
→
0 if y
¯
-
y
_
→
0.
By the definition ofL
β
j
t
b
l
(
Y
j
t
b
), we show that β
j
t
b
exp
⁡
(
Y
j
t
b
)
-
L
β
j
t
b
l
(
Y
j
t
b
)
→
0 for any t similarly to (i).
(iii) The proof ofl
h
j
l
b
j
l
(
y
)
/
a
j
(
y
)
-
l
h
j
l
b
j
l
(
y
)
/
l
a
j
u
(
y
)
→
0 is as follows.
We prove thata
j
(
y
)
-
l
a
j
u
(
y
)
→
0 if y
¯
-
y
_
→
0.
By the definition ofL
β
j
t
a
u
(
Y
j
t
a
), we show that β
j
t
a
exp
⁡
(
Y
j
t
a
)
-
L
β
j
t
a
u
(
Y
j
t
a
)
→
0 for any t similarly to (i).
(iv) The proof ofl
h
j
l
b
j
l
(
y
)
/
l
a
j
u
(
y
)
-
l
h
j
l
b
j
l
(
y
)
/
max
⁡
l
a
j
u
(
y
)
→
0 is as follows.
Ify
¯
-
y
_
→
0, then l
a
j
u
(
y
)
→
max
⁡
l
a
j
u
(
y
).Theorem 2.
Suppose that problemP
0 has a global optimal solution, denoted by μ
0
∗. Then one has the following.
(i) For the caseϵ
>
0: the algorithm always terminates after finitely many iterations yielding a global ϵ-optimal solution y
∗ and a global ϵ-optimal value V
∗ for problem P
0 in the sense that y
∗
∈
Y, V
∗
-
ϵ
≤
μ
0
∗ with V
∗
=
f
0
(
y
∗
).
(ii) For the caseϵ
→
0: one assumes the sequence ϵ
n is convergence tolerance, such that ϵ
1
>
ϵ
2
>
⋯
>
ϵ
n
>
ϵ
n
+
1
>
⋯
>
0; that is, l
i
m
n
→
∞
ϵ
n
=
0. And we assume the sequence y
n
∗ is optimal solution of P
0 corresponding to ϵ
n. Then the accumulation point of y
n
∗ is global optimal solution of P
0.Proof.
(i) It is obvious by the algorithm statement.
(ii) We denote that the upper bound corresponding toϵ
n is V
n
∗:(27)
f
0
y
n
∗
∈
V
n
∗
-
ϵ
,
V
n
∗
.Then {
y
n
∗
} is the point sequence on bounded closed set, and {
y
n
∗
} has a converge subsequence {
y
n
i
∗
}.
We denotel
i
m
i
→
∞
y
n
i
∗
=
y
∗, and then(28)
V
n
i
∗
-
ϵ
n
i
≤
f
0
V
n
i
∗
≤
V
n
i
∗
.
If
i
⟶
∞
,
then
n
i
⟶
∞
,
l
i
m
n
i
→
∞
ϵ
n
i
=
0
.Now {
V
n
∗
} is a monotone decreasing sequence; therefore it is convergent. We put l
i
m
n
→
∞
V
n
∗
=
μ
0
∗:(29)
l
i
m
i
→
∞
V
n
i
∗
-
ϵ
n
i
≤
l
i
m
i
→
∞
f
0
y
n
i
∗
≤
l
i
m
i
→
∞
V
n
i
∗
.Since f
0
(
y
) is a continuous function, l
i
m
i
→
∞
f
0
(
y
n
i
)
=
f
0
(
y
∗
). Therefore, μ
0
∗
≤
f
0
(
y
∗
)
≤
μ
0
∗, and f
0
(
y
∗
)
=
μ
0
∗. Since f
k
(
y
n
∗
)
≤
0, for each k, and f
k
(
y
∗
) is continuous, we obtain that l
i
m
n
→
∞
f
k
(
y
n
∗
)
=
f
k
(
y
∗
)
≤
0.


## 5. Numerical Experiment

In this section, we show some numerical experiments for these optimization problems according to the former rules. We make the algorithm coded with Matlab. In these codes, we use Matlab’s unique function code “linprog” to solve the linear optimization problems.Example 1.
Consider(30)
m
i
n
exp
⁡
-
x
1
2
+
3
x
1
+
2
x
2
2
+
3
x
2
+
3.5
x
1
+
1
-
exp
⁡
x
2
x
1
2
-
2
x
1
+
x
2
2
-
8
x
2
+
20
s.t.
x
1
-
x
2
x
1
≤
1
2
x
1
x
2
+
x
2
≤
6
X
=
x
:
1
≤
x
1
≤
3
,
1
≤
x
2
≤
3
.We set ϵ
=
0.000001. After the algorithm, we found a global ϵ-optimal value V
∗
=
59.3054 when the global ϵ-optimal solution is (
x
1
,
x
2
)
T
=
(
1,1.6180
).Example 2.
Consider(31)
m
i
n
sin
⁡
x
1
2
+
2
x
2
-
2
x
1
+
x
2
2
x
1
+
x
2
2
+
4
+
cos
⁡
3
x
1
2
-
3
x
2
+
2
x
1
+
x
2
2
+
3
x
1
2
+
2
x
2
2
+
10
s.t.
sin
⁡
x
1
2
+
3
x
2
-
2
x
2
2
+
2
x
1
2
+
x
2
+
5
+
cos
⁡
-
x
2
2
+
2
x
1
+
2
x
2
x
1
+
5
≤
0
X
=
x
:
1
≤
x
1
≤
2
,
1
≤
x
2
≤
2
.We set ϵ
=
0.000001. After the algorithm, we found a global ϵ-optimal value V
∗
=
0.9023 when the global ϵ-optimal solution is (
x
1
,
x
2
)
T
=
(
2,1
).Example 3.
Consider(32)
m
i
n
log
⁡
2
x
1
2
-
x
2
+
35
-
x
1
+
2
x
2
2
+
9
-
log
⁡
3
x
1
2
-
x
2
+
35
x
1
2
-
x
1
+
x
2
2
+
2
x
2
+
3
s.t.
x
1
2
-
2
x
2
≤
1
x
1
-
x
2
x
1
≤
1
X
=
x
:
1
≤
x
1
≤
3
,
1
≤
x
2
≤
3
.We set ϵ
=
0.000001. After the algorithm, we found a global ϵ-optimal value V
∗
=
-
0.5382 when the global ϵ-optimal solution is (
x
1
,
x
2
)
T
=
(
1,1
).


## 6. Concluding Remarks

In this paper, we propose the specific nonlinear and nonconvex optimization technique which does not launch new valuables applying Hongwei’s method [6]. We compute the examples of our previous work [17] by the new method. In [17], it had taken over 8 hours to find optimal value for each problem. The proposed method can compute the same problems in 10 minutes. If the algorithms are coded by C or C++, we obtain the optimal value in a shorter time.



---

*Source: 1304954-2016-06-02.xml*