# Global Optimization for a Class of Nonlinear Sum of Ratios Problem

Authors: Li Jin; Xue-Ping Hou
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

We present a branch and bound algorithm for globally solving the sum of ratios problem. In this problem, each term in the objective function is a ratio of two functions which are the sums of the absolute values of affine functions with coefficients. This problem has an important application in financial optimization, but the global optimization algorithm for this problem is still rare in the literature so far. In the algorithm we presented, the branch and bound search undertaken by the algorithm uses rectangular partitioning and takes place in a space which typically has a much smaller dimension than the space to which the decision variables of this problem belong. Convergence of the algorithm is shown. At last, some numerical examples are given to vindicate our conclusions.


---

## Body

## 1. Introduction

The sum of ratios problem has attracted considerable attention in the literature because of its large number of practical applications in various fields of study, including transportation planning, government contracting, economics, and finances [1–6]. And from a research point of view, the sum of ratios problem poses significant theoretical and computational challenges. This is mainly due to the fact that it is known to generally possess multiple local optima that are not globally optimal.Many solution algorithms have been proposed for globally solving sums of linear ratios problem with linear constraints (see, e.g., [7–11]). Recently, some algorithms have been developed for solving globally the nonlinear sum of ratios problems; for instance, Freund and Jarre [12] proposed an interior-point approach for the convex-concave ratios with convex constraints; Dai et al. [13] and Pei and Zhu [14] presented two algorithms for the sum of dc ratios; Benson [15, 16] gave two branch and bound algorithms for the concave-convex ratios; Yamamoto and Konno [17] proposed an algorithm for convex-convex ratios; Shen and Jin [18] and Jiao and Shen [19] developed global optimization algorithms for two kinds of nonlinear sum of ratios.In this paper, we are concerned with the following nonlinear sum of ratios problem:(
P
)
v
=
max
⁡
h
(
x
)
=
∑
i
=
1
p
‍
n
i
(
x
)
d
i
(
x
)
s
.
t
.
x
∈
X
,
where p
≥
1, X is a compact, convex set in R
n, and n
i
(
x
)
=
∑
s
=
1
S
i
α
s
i
|
∑
j
=
1
n
n
j
s
i
x
j
+
n
0
s
i
|, d
i
(
x
)
=
∑
t
=
1
T
i
β
t
i
|
∑
j
=
1
n
d
j
t
i
x
j
+
d
0
t
i
|, i
=
1,2
,
…
,
p. In addition, we assume that α
s
i
,
β
t
i
∈
R, 0
<
l
i
≤
n
i
(
x
)
≤
u
i, 0
<
L
i
≤
d
i
(
x
)
≤
U
i, ∀
x
∈
X, i
=
1,2
,
…
,
p.Problem(
P
) arises when we replace the variance by the absolute deviation as a measure of the variation of a portfolio. And the global optimization algorithm for this problem is still rare in the literature so far. So we believe that this paper is of interest to researchers in both the fields of portfolio optimization and fractional programming.The purpose of this paper is to present a branch and bound algorithm for globally solving problem(
P
). We believe that the proposed algorithm has four potential practical and computational advantages. First, upper bounds are obtained by maximizing the concave envelope of the objective function of problem (
P
) over rectangles. Second, the proposed algorithm uses rectangles rather than simplices as partition elements, so that branching only takes place in a space of dimension p rather than n or 2
p although the algorithm search is carried out mainly in a space of dimension 2
p. Third, we choose a simple and standard bisection rule. This rule is sufficient to ensure convergence since the partition rule is exhaustive. Finally, the upper bounding subproblems are convex programming problems that differ from each other only in the coefficients of certain linear constraints and in the bounds that describe their associated rectangles.The remainder of this paper is organized as follows. In Section2, an equivalent problem of problem (
P
) is given. Next, in Section 3, we construct the function overestimating the value of the sum of ratios. In Section 4, the proposed branch and bound algorithm is described, and the convergence of the algorithm is established. Some numerical results are reported in Section 5. A summary is proposed in the last section.


## 2. Equivalent Problem

In order to globally solve the problem(
P
), first problem (
P
) can be converted into an equivalent nonconvex programming problem (
P
1
) as follows:
(
P
1
)
v
=
max
⁡
∑
i
=
1
p
‍
t
i
s
i
s
.
t
.
n
i
(
x
)
-
t
i
≥
0
,
i
=
1
,
…
,
p
,
-
d
i
(
x
)
+
s
i
≥
0
,
i
=
1
,
…
,
p
,
x
∈
X
,
l
i
≤
t
i
≤
u
i
,
L
i
≤
s
i
≤
U
i
,
i
=
1
,
…
,
p
.Theorem 1.
If(
x
*
,
t
*
,
s
*
) is a global optimal solution for problem (
P
1
), then t
i
*
=
n
i
(
x
*
), s
i
*
=
d
i
(
x
*
), i
=
1,2
,
…
,
p, and x
* is a global optimal solution for problem (
P
). Conversely, if x
* is a global optimal solution for problem (
P
), then (
x
*
,
t
*
,
s
*
) is a global optimal solution for problem (
P
1
), where t
i
*
=
n
i
(
x
*
), s
i
*
=
d
i
(
x
*
), i
=
1,2
,
…
,
p.Proof.
The proof of this result can be easily followed from the definitions of problems(
P
) and (
P
1
) and is therefore omitted.Without loss of generality, we assume thatα
s
i
>
0, s
=
1
,
…
,
S
s
i, β
t
i
<
0, t
=
1
,
…
,
T
t
i, i
=
1
,
…
,
p.Let us define(1)
u
s
i
-
v
s
i
=
∑
j
=
1
n
‍
n
j
s
i
x
j
+
n
0
s
i
,
u
s
i
v
s
i
=
0
,
u
s
i
≥
0
,
v
s
i
≥
0
,
s
=
1
,
…
,
S
s
i
,
i
=
1
,
…
,
p
,
ξ
t
i
-
η
t
i
=
∑
j
=
1
n
‍
d
j
t
i
x
j
+
d
0
t
i
,
ξ
t
i
η
t
i
=
0
,
ξ
t
i
≥
0
,
η
t
i
≥
0
,
t
=
1
,
…
,
T
t
i
,
i
=
1
,
…
,
p
.
Then problem (
P
1
) can be reformulated as follows:
(
P
2
)
max
⁡
∑
i
=
1
p
‍
t
i
s
i
s
.
t
.
∑
s
=
1
S
s
i
‍
α
s
i
(
u
s
i
+
v
s
i
)
+
∑
s
=
S
s
i
+
1
S
i
‍
α
s
i
|
∑
j
=
1
n
‍
n
j
s
i
x
j
+
n
0
s
i
|
-
t
i
≥
0
,
i
=
1
,
…
,
p
,
-
∑
t
=
1
T
t
i
‍
β
t
i
(
ξ
t
i
+
η
t
i
)
-
∑
t
=
T
t
i
+
1
T
i
‍
β
t
i
|
∑
j
=
1
n
‍
d
j
t
i
x
j
+
d
0
t
i
|
+
s
i
≥
0
,
i
=
1
,
…
,
p
,
u
s
i
-
v
s
i
=
∑
j
=
1
n
‍
n
j
s
i
x
j
+
n
0
s
i
,
u
s
i
v
s
i
=
0
,
u
s
i
≥
0
,
v
s
i
≥
0
,
s
=
1
,
…
,
S
s
i
,
i
=
1
,
…
,
p
,
ξ
t
i
-
η
t
i
=
∑
j
=
1
n
‍
d
j
t
i
x
j
+
d
0
t
i
,
ξ
t
i
η
t
i
=
0
ξ
t
i
≥
0
,
η
t
i
≥
0
,
t
=
1
,
…
,
T
t
i
,
i
=
1
,
…
,
p
,
x
∈
X
,
l
i
≤
t
i
≤
u
i
,
L
i
≤
s
i
≤
U
i
,
i
=
1
,
…
,
p
.As is well known, the set of complementarity conditionsu
s
i
v
s
i
=
0 can be represented as a system of linear inequalities by introducing zero-one integer variable [20]:
(2)
u
s
i
≤
a
s
i
≤
z
s
i
,
v
s
i
≤
b
s
i
(
1
-
z
s
i
)
,
where z
s
i
∈
{
0,1
} and a
s
i, b
s
i are defined as follows:
(3)
a
s
i
=
max
⁡
{
max
⁡
{
∑
j
=
1
n
‍
n
j
s
i
x
j
+
n
0
s
i
∣
x
∈
X
}
,
0
}
,
b
s
i
=
-
min
⁡
{
min
⁡
{
∑
j
=
1
n
‍
n
j
s
i
x
j
+
n
0
s
i
∣
x
∈
X
}
,
0
}
.
Then z
s
i
∈
{
0,1
} can be transformed into
(4)
0
≤
z
s
i
≤
1
,
z
s
i
(
1
-
z
s
i
)
≤
0
.Forξ
t
i
η
t
i
=
0, we do with them similarly. Let
(5)
ξ
t
i
≤
c
t
i
≤
w
t
i
,
η
t
i
≤
d
t
i
(
1
-
w
t
i
)
,
0
≤
w
t
i
≤
1
,
w
t
i
(
1
-
w
t
i
)
≤
0
,
where
(6)
c
t
i
=
max
⁡
{
max
⁡
{
∑
j
=
1
n
‍
d
j
t
i
x
j
+
d
0
t
i
∣
x
∈
X
}
,
0
}
,
d
t
i
=
-
min
⁡
{
min
⁡
{
∑
j
=
1
n
‍
d
j
t
i
x
j
+
d
0
t
i
∣
x
∈
X
}
,
0
}
.And let(7)
H
0
=
{
(
t
,
s
)
∈
R
2
p
∣
l
i
≤
t
i
≤
u
i
,
L
i
≤
s
i
≤
U
i
,
i
=
1
,
…
,
p
}
.
So the problem (
P
2
) is equivalent to the following problem:
(
P
(
H
0
)
)
max
⁡
∑
i
=
1
p
‍
t
i
s
i
s
.
t
.
∑
s
=
1
S
s
i
‍
α
s
i
(
u
s
i
+
v
s
i
)
+
∑
s
=
S
s
i
+
1
S
i
‍
α
s
i
|
∑
j
=
1
n
‍
n
j
s
i
x
j
+
n
0
s
i
|
-
t
i
≥
0
,
i
=
1
,
…
,
p
,
-
∑
t
=
1
T
t
i
‍
β
t
i
(
ξ
t
i
+
η
t
i
)
-
∑
t
=
T
t
i
+
1
T
i
‍
β
t
i
|
∑
j
=
1
n
‍
d
j
t
i
x
j
+
d
0
t
i
|
+
s
i
≥
0
,
i
=
1
,
…
,
p
,
u
s
i
-
v
s
i
=
∑
j
=
1
n
‍
n
j
s
i
x
j
+
n
0
s
i
,
s
=
1
,
…
,
S
s
i
,
i
=
1
,
…
,
p
,
ξ
t
i
-
η
t
i
=
∑
j
=
1
n
‍
d
j
t
i
x
j
+
d
0
t
i
,
t
=
1
,
…
,
T
t
i
,
i
=
1
,
…
,
p
,
u
s
i
≤
a
s
i
≤
z
s
i
,
v
s
i
≤
b
s
i
(
1
-
z
s
i
)
,
z
s
i
(
1
-
z
s
i
)
≤
0
,
s
=
1
,
…
,
S
s
i
,
i
=
1
,
…
,
p
,
ξ
t
i
≤
c
t
i
≤
w
t
i
,
η
t
i
≤
d
t
i
(
1
-
w
t
i
)
,
w
t
i
(
1
-
w
t
i
)
≤
0
,
t
=
1
,
…
,
T
t
i
,
i
=
1
,
…
,
p
,
0
≤
z
s
i
≤
1
,
0
≤
w
t
i
≤
1
,
s
=
1
,
…
,
S
s
i
,
t
=
1
,
…
,
T
t
i
,
i
=
1
,
…
,
p
,
x
∈
X
,
(
t
,
s
)
∈
H
0
.


## 3. Convex Relaxation Programming

The principle construct in the development of a solution procedure for solving(
P
(
H
0
)
) is the construction of a convex relaxation programming of (
P
(
H
0
)
) for obtaining the upper bound for this problem, as well as for its partitioned subproblems. Such a convex relaxation can be realized by using the concave envelope of the objective function of (
P
(
H
0
)
) over an associated rectangle.To help obtain convex relaxations, the concept of a concave envelope may be defined as follows.Definition 2 (see [21]).
LetM
⊆
R
q be a compact, convex set, and let f
:
M
→
R be upper semicontinuous on M. Then f
M
:
M
→
R is called the concave envelope of f on M if(i)
f
M
(
x
) is a concave function on M,
(ii)
f
M
(
x
)
≥
f
(
x
) for all x
∈
M,
(iii)
there is no functionω
(
x
) satisfying (i) and (ii) such that ω
(
x
¯
)
<
f
M
(
x
¯
) for some point x
¯
∈
M.The following theorem is obtained from the definition above.Theorem 3.
Consider a rectangleM of R
2
:
M
=
{
(
x
1
,
x
2
)
∈
R
2
∣
l
≤
x
1
≤
u
,
L
≤
x
2
≤
U
}, where l
,
u
,
Ł
,
U satisfy 0
<
l
<
u, 0
<
L
<
U. For any (
x
1
,
x
2
)
∈
R
2
(
x
2
≠
0
), we define function f
(
x
1
,
x
2
)
=
x
1
/
x
2; then the concave envelope f
M of the function f
:
M
→
R is given by
(8)
f
M
(
x
1
,
x
2
)
=
min
⁡
{
1
L
x
1
-
l
L
U
x
2
+
l
U
,
1
U
x
1
-
u
L
U
x
2
+
u
L
}
.Proof.
This result is essentially shown in [15] and is therefore omitted.
In order to obtain an upper bound of the optimal value to(
P
(
H
0
)
) by solving a convex programming, we can utilize Theorem 3 and convex the reverse convex constraints to problem (
P
(
H
0
)
) such that a convex program is given by
(
RCP
(
H
0
)
)
max
⁡
∑
i
=
1
p
‍
r
i
s
.
t
.
r
i
≤
1
L
i
t
i
-
l
i
L
i
U
i
s
i
+
l
i
U
i
,
i
=
1
,
…
,
p
,
r
i
≤
1
U
i
t
i
-
u
i
L
i
U
i
s
i
+
u
i
L
i
,
i
=
1
,
…
,
p
,
∑
s
=
1
S
s
i
‍
α
s
i
(
u
s
i
+
v
s
i
)
+
∑
s
=
S
s
i
+
1
S
i
‍
α
s
i
|
∑
j
=
1
n
‍
n
j
s
i
x
j
+
n
0
s
i
|
-
t
i
≥
0
,
i
=
1
,
…
,
p
,
-
∑
t
=
1
T
t
i
‍
β
t
i
(
ξ
t
i
+
η
t
i
)
-
∑
t
=
T
t
i
+
1
T
i
‍
β
t
i
|
∑
j
=
1
n
‍
d
j
t
i
x
j
+
d
0
t
i
|
+
s
i
≥
0
,
i
=
1
,
…
,
p
,
u
s
i
-
v
s
i
=
∑
j
=
1
n
‍
n
j
s
i
x
j
+
n
0
s
i
,
s
=
1
,
…
,
S
s
i
,
i
=
1
,
…
,
p
,
ξ
t
i
-
η
t
i
=
∑
j
=
1
n
‍
d
j
t
i
x
j
+
d
0
t
i
,
t
=
1
,
…
,
T
t
i
,
i
=
1
,
…
,
p
,
u
s
i
≤
a
s
i
≤
z
s
i
,
v
s
i
≤
b
s
i
(
1
-
z
s
i
)
,
ξ
t
i
≤
c
t
i
≤
w
t
i
,
η
t
i
≤
d
t
i
(
1
-
w
t
i
)
,
z
s
i
-
(
z
s
i
l
)
2
-
(
z
s
i
u
+
z
s
i
l
)
(
z
s
i
-
z
s
i
l
)
≤
0
,
s
=
1
,
…
,
S
s
i
,
i
=
1
,
…
,
p
,
w
t
i
-
(
w
t
i
l
)
2
-
(
w
t
i
u
+
w
t
i
l
)
(
w
t
i
-
w
t
i
l
)
≤
0
,
t
=
1
,
…
,
T
t
i
,
i
=
1
,
…
,
p
,
0
≤
z
s
i
≤
1
,
0
≤
w
t
i
≤
1
,
s
=
1
,
…
,
S
s
i
,
t
=
1
,
…
,
T
t
i
,
i
=
1
,
…
,
p
,
x
∈
X
,
(
t
,
s
)
∈
H
0
.


## 4. Branch and Bound Algorithm

In this section, a branch and bound algorithm is developed to solve(
P
(
H
0
)
) based on the former convex relaxation method. This algorithm needs to solve a sequence of convex relaxation programming problems about rectangle H
0 or the subrectangle H of H
0 to find a global solution.


### 4.1. Rectangular Partition Rule

The critical element in guaranteeing convergence to a global maximum of(
P
(
H
0
)
) is the choice of a suitable partitioning strategy. In this paper, we choose a simple and standard bisection rule. This rule is sufficient to ensure convergence since it derives all the intervals shrinking to a singleton for all the variables along any infinite branch of the branch and bound tree. Assume that, at each stage of the branch and bound algorithm, H
0 or a subrectangle of H
0 is subdivided into two rectangles by the branching process. To explain this process, assume without loss of generality that H
0 or a subrectangle of H
0 to be divided is H
=
{
(
t
,
s
)
∈
R
2
p
∣
l
i
≤
t
i
≤
u
i
,
L
i
≤
s
i
≤
U
i
,
i
=
1
,
…
,
p
}. This branching rule is as follows.(i)
Letq
∈
argmax
{
U
i
-
L
i
∣
i
=
1
,
…
,
p
}.
(ii)
Letγ
=
(
L
q
+
U
q
)
/
2.
(iii)
Let(9)
H
1
=
{
L
q
≤
s
q
(
t
,
s
)
∈
R
2
p
∣
l
i
≤
t
i
≤
u
i
,
L
i
≤
s
i
≤
U
i
,
c
c
c
c
i
≠
q
,
L
q
≤
s
q
≤
γ
}
,
H
2
=
{
γ
≤
s
q
≤
U
q
(
t
,
s
)
∈
R
2
p
∣
l
i
≤
t
i
≤
u
i
,
L
i
≤
s
i
≤
U
i
,
c
c
c
c
i
≠
q
,
γ
≤
s
q
≤
U
q
}
.It follows easily that this branching process is exhaustive.We are now ready to formally state the overall algorithm for globally solving problem(
P
). The basic steps of the algorithm are summarized in the following statement.


### 4.2. Algorithm Statement

Step 1 (initialization).
Given a convergence toleranceε
>
0. Set the iteration counter k
=
0, the set of all active nodes Ω
0
=
{
H
0
}, the lower bound LB
=
-
∞, and the set of feasible points F
=
∅.
Solve the convex relaxation programming problem(
RCP
(
H
0
)
) and obtain the optimal value μ
(
H
0
) and an optimal solution x
(
H
0
). Set U
B
0
=
μ
(
H
0
), x
c
=
x
(
H
0
), and LB
=
h
(
x
c
). Update F
=
F
⋃
‍
{
x
c
}.
IfU
B
0
-
LB
≤
ε, then stop with x
c which is the globally ε-optimal solution and LB is the optimal value to problem (
P
). Otherwise, proceed to Step 2.Step 2 (branching).
According to the above selected branching rule, partitionH
k into two new rectangles. Call the set of new partition rectangles Θ
k.
For eachH
∈
Θ
k, solve convex programming problem (
RCP
(
H
0
)
) to obtain optimal value μ
(
H
) and optimal solution x
(
H
) of the problem (
RCP
(
H
0
)
). If μ
(
H
)
<
LB, then remove the corresponding subrectangle H from Θ
k, that is, Θ
k
=
Θ
k
∖
H, and skip to the next element of Θ
k.
IfΘ
k
=
∅, go to Step 3. Otherwise, update F
=
F
⋃
‍
{
x
(
H
)
,
H
∈
Θ
k
}, and set LB
=
max
⁡
x
∈
F
h
(
x
); the best known feasible point is denoted by x
c
=
argmax
x
∈
F
h
(
x
).Step 3 (updating upper bound).
Denote the partition set remaining as(10)
Ω
k
+
1
=
(
Ω
k
∖
H
k
)
⋃
‍
Θ
k
giving a new upper bound U
B
k
=
inf
⁡
H
∈
Ω
k
+
1
μ
(
H
).Step 4 (convergence check).
Fathom any improving nodes by settingΩ
k
+
1
=
Ω
k
∖
{
H
:
μ
(
H
)
-
LB
≤
ε
,
H
∈
Ω
k
}. If Ω
k
+
1
=
∅, then stop: LB is the optimal value, and x
c are global ε-optimal solutions for problem (
P
), respectively. Otherwise, set k
=
k
+
1 and return to Step 2.


### 4.3. Convergence Analysis

Next, we will give the convergence properties of the algorithm.Theorem 4.
(a) If the algorithm is finite, then, upon termination,x
k is a global ε-optimal solution to problem (
P
).
(b) If the algorithm is infinite, then every accumulation pointx
* of an infinite feasible solutions sequence {
x
k
} to problem (
P
) generated by the algorithm is a global optimal solution to problem (
P
).Proof.
(a) If the algorithm is finite, then it terminates in Stepk, k
≥
1. Upon termination, since x
k is found by solving problem (
P
(
H
0
)
) for some H
⊆
H
0, x
k is a feasible solution to problem (
P
). Upon termination of the algorithm,
(11)
U
B
k
-
∑
i
=
1
p
‍
n
i
(
x
k
)
d
i
(
x
k
)
≤
ε
is satisfied. It is easy to show by standard arguments for branch and bound algorithm that
(12)
U
B
k
≥
v
.
Since x
k is a feasible solution for problem (
P
), we have
(13)
∑
i
=
1
p
‍
n
i
(
x
k
)
d
i
(
x
k
)
≤
v
.
Taken together, the three previous statements imply that
(14)
v
≤
U
B
k
≤
∑
i
=
1
p
‍
n
i
(
x
k
)
d
i
(
x
k
)
+
ε
≤
v
+
ε
.
Therefore,
(15)
v
-
ε
≤
∑
i
=
1
p
‍
n
i
(
x
k
)
d
i
(
x
k
)
≤
v
,
and the proof of part (a) is complete.
(b) Assume that the algorithm is infinite, by [21]; then a sufficient condition for a global optimization to be convergent to the global maximum 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(16)
lim
⁡
k
→
∞
(
U
B
k
-
LB
)
=
0
,
where U
B
k is a computed upper bound in Step k and LB is the best lower bound at iteration k not necessarily occurring inside the same subrectangle with U
B
k. Now, we show that (16) holds.
Since the employed subdivision process is rectangle bisection, the process is exhaustive. Consequently, from the relationv
(
R
C
P
(
H
)
)
≤
v
(
P
), where v
(
R
C
P
(
H
)
) and v
(
P
) denote the optimal values of problem (
RCP
(
H
0
)
) and (
P
) over the rectangle H, respectively, the formulation holds, and this implies that the employed bounding operation is consistent.
A selection operation is called 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 bound improving because the partition element where the actual upper bound is attained is selected for further partition in the immediately following iteration.
From the above discussion, the branch and bound algorithm proposed in this paper is convergent to the global maximum of(
P
).


## 4.1. Rectangular Partition Rule

The critical element in guaranteeing convergence to a global maximum of(
P
(
H
0
)
) is the choice of a suitable partitioning strategy. In this paper, we choose a simple and standard bisection rule. This rule is sufficient to ensure convergence since it derives all the intervals shrinking to a singleton for all the variables along any infinite branch of the branch and bound tree. Assume that, at each stage of the branch and bound algorithm, H
0 or a subrectangle of H
0 is subdivided into two rectangles by the branching process. To explain this process, assume without loss of generality that H
0 or a subrectangle of H
0 to be divided is H
=
{
(
t
,
s
)
∈
R
2
p
∣
l
i
≤
t
i
≤
u
i
,
L
i
≤
s
i
≤
U
i
,
i
=
1
,
…
,
p
}. This branching rule is as follows.(i)
Letq
∈
argmax
{
U
i
-
L
i
∣
i
=
1
,
…
,
p
}.
(ii)
Letγ
=
(
L
q
+
U
q
)
/
2.
(iii)
Let(9)
H
1
=
{
L
q
≤
s
q
(
t
,
s
)
∈
R
2
p
∣
l
i
≤
t
i
≤
u
i
,
L
i
≤
s
i
≤
U
i
,
c
c
c
c
i
≠
q
,
L
q
≤
s
q
≤
γ
}
,
H
2
=
{
γ
≤
s
q
≤
U
q
(
t
,
s
)
∈
R
2
p
∣
l
i
≤
t
i
≤
u
i
,
L
i
≤
s
i
≤
U
i
,
c
c
c
c
i
≠
q
,
γ
≤
s
q
≤
U
q
}
.It follows easily that this branching process is exhaustive.We are now ready to formally state the overall algorithm for globally solving problem(
P
). The basic steps of the algorithm are summarized in the following statement.


## 4.2. Algorithm Statement

Step 1 (initialization).
Given a convergence toleranceε
>
0. Set the iteration counter k
=
0, the set of all active nodes Ω
0
=
{
H
0
}, the lower bound LB
=
-
∞, and the set of feasible points F
=
∅.
Solve the convex relaxation programming problem(
RCP
(
H
0
)
) and obtain the optimal value μ
(
H
0
) and an optimal solution x
(
H
0
). Set U
B
0
=
μ
(
H
0
), x
c
=
x
(
H
0
), and LB
=
h
(
x
c
). Update F
=
F
⋃
‍
{
x
c
}.
IfU
B
0
-
LB
≤
ε, then stop with x
c which is the globally ε-optimal solution and LB is the optimal value to problem (
P
). Otherwise, proceed to Step 2.Step 2 (branching).
According to the above selected branching rule, partitionH
k into two new rectangles. Call the set of new partition rectangles Θ
k.
For eachH
∈
Θ
k, solve convex programming problem (
RCP
(
H
0
)
) to obtain optimal value μ
(
H
) and optimal solution x
(
H
) of the problem (
RCP
(
H
0
)
). If μ
(
H
)
<
LB, then remove the corresponding subrectangle H from Θ
k, that is, Θ
k
=
Θ
k
∖
H, and skip to the next element of Θ
k.
IfΘ
k
=
∅, go to Step 3. Otherwise, update F
=
F
⋃
‍
{
x
(
H
)
,
H
∈
Θ
k
}, and set LB
=
max
⁡
x
∈
F
h
(
x
); the best known feasible point is denoted by x
c
=
argmax
x
∈
F
h
(
x
).Step 3 (updating upper bound).
Denote the partition set remaining as(10)
Ω
k
+
1
=
(
Ω
k
∖
H
k
)
⋃
‍
Θ
k
giving a new upper bound U
B
k
=
inf
⁡
H
∈
Ω
k
+
1
μ
(
H
).Step 4 (convergence check).
Fathom any improving nodes by settingΩ
k
+
1
=
Ω
k
∖
{
H
:
μ
(
H
)
-
LB
≤
ε
,
H
∈
Ω
k
}. If Ω
k
+
1
=
∅, then stop: LB is the optimal value, and x
c are global ε-optimal solutions for problem (
P
), respectively. Otherwise, set k
=
k
+
1 and return to Step 2.


## 4.3. Convergence Analysis

Next, we will give the convergence properties of the algorithm.Theorem 4.
(a) If the algorithm is finite, then, upon termination,x
k is a global ε-optimal solution to problem (
P
).
(b) If the algorithm is infinite, then every accumulation pointx
* of an infinite feasible solutions sequence {
x
k
} to problem (
P
) generated by the algorithm is a global optimal solution to problem (
P
).Proof.
(a) If the algorithm is finite, then it terminates in Stepk, k
≥
1. Upon termination, since x
k is found by solving problem (
P
(
H
0
)
) for some H
⊆
H
0, x
k is a feasible solution to problem (
P
). Upon termination of the algorithm,
(11)
U
B
k
-
∑
i
=
1
p
‍
n
i
(
x
k
)
d
i
(
x
k
)
≤
ε
is satisfied. It is easy to show by standard arguments for branch and bound algorithm that
(12)
U
B
k
≥
v
.
Since x
k is a feasible solution for problem (
P
), we have
(13)
∑
i
=
1
p
‍
n
i
(
x
k
)
d
i
(
x
k
)
≤
v
.
Taken together, the three previous statements imply that
(14)
v
≤
U
B
k
≤
∑
i
=
1
p
‍
n
i
(
x
k
)
d
i
(
x
k
)
+
ε
≤
v
+
ε
.
Therefore,
(15)
v
-
ε
≤
∑
i
=
1
p
‍
n
i
(
x
k
)
d
i
(
x
k
)
≤
v
,
and the proof of part (a) is complete.
(b) Assume that the algorithm is infinite, by [21]; then a sufficient condition for a global optimization to be convergent to the global maximum 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(16)
lim
⁡
k
→
∞
(
U
B
k
-
LB
)
=
0
,
where U
B
k is a computed upper bound in Step k and LB is the best lower bound at iteration k not necessarily occurring inside the same subrectangle with U
B
k. Now, we show that (16) holds.
Since the employed subdivision process is rectangle bisection, the process is exhaustive. Consequently, from the relationv
(
R
C
P
(
H
)
)
≤
v
(
P
), where v
(
R
C
P
(
H
)
) and v
(
P
) denote the optimal values of problem (
RCP
(
H
0
)
) and (
P
) over the rectangle H, respectively, the formulation holds, and this implies that the employed bounding operation is consistent.
A selection operation is called 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 bound improving because the partition element where the actual upper bound is attained is selected for further partition in the immediately following iteration.
From the above discussion, the branch and bound algorithm proposed in this paper is convergent to the global maximum of(
P
).


## 5. Computational Results

We conducted numerical experiments on the branch and bound algorithm on a Pentium IV microcomputer and the algorithm was coded in Fortran 95. Although these problems have a relatively small number of variables, they are quite challenging. For all test problems, numerical results show that the proposed global optimization algorithm can solve these problems efficiently. Computational results are illustrated in Tables1 and 2.Table 1
Computational results for Problem5.
n
p
Iter
Node
Time
p
Iter
Node
Time
p
Iter
Node
Time
50
2
11
3
0
4
59
10
0
6
103
17
0
100
2
13
5
0
4
67
11
0
6
145
21
0
150
2
16
3
0
4
69
11
0
6
180
19
0
200
2
26
7
0
4
77
13
0
6
185
23
0Table 2
Computational results for Problem6.
n
p
Iter
Node
Time
p
Iter
Node
Time
p
Iter
Node
Time
50
2
14
2
0
4
91
13
0
6
117
21
0
100
2
17
3
0
4
75
15
0
6
136
22
0
150
2
26
4
0
4
79
17
0
6
150
29
0
200
42
29
7
0
4
87
23
0
6
212
33
0In Tables1 and 2, some notations have been used for column headers: Iter: the number of the algorithm iterations; Max-node: the maximal number of the active nodes necessary; Time: the execution time in seconds, where when the execution time is very short (e.g., Time < 0.1 second), we record with 0 second in short.We choose the following two types of sum of ratios problems to test our algorithm, which are generated randomly.Problem 5.
Consider(17)
max
⁡
∑
i
=
1
p
‍
(
1
/
T
i
)
∑
t
=
1
T
i
|
∑
j
=
1
n
(
r
j
t
i
-
r
j
i
)
x
j
|
(
1
/
T
i
)
∑
t
=
1
T
i
|
∑
j
=
1
n
(
r
~
j
t
i
-
r
~
j
i
)
x
j
|
s
.
t
.
∑
j
=
1
n
‍
x
j
=
1
,
0
≤
x
j
≤
1
,
j
=
1
,
…
,
n
,
where T
i is an integer number (e.g., T
i is taken to be n), r
j
t
i is generated randomly in the interval [
0,1
], and r
j
i
=
∑
t
=
1
T
i
r
j
t
i
/
T
i, while r
~
j
t
i, r
~
j
i are corresponding values calculated by an appropriate factor model [22].Problem 6.
Consider(18)
max
⁡
∑
i
=
1
p
‍
∑
s
=
1
S
i
α
s
i
|
∑
j
=
1
n
n
j
s
i
x
j
+
n
0
s
i
|
∑
t
=
1
T
i
β
t
i
|
∑
j
=
1
n
d
j
t
i
x
j
+
d
0
t
i
|
s
.
t
.
∑
i
=
1
j
‍
x
i
≤
j
,
j
=
1,2
,
…
,
n
;
0
≤
x
i
,
i
=
1
,
…
,
n
,
where T
i and S
i are integer numbers (e.g., they are taken to be n, resp.) and α
s
i, β
t
i, n
0
s
i, and d
0
t
i are all generated by using random numbers in the intervals [
0,0.1
], [
0,0.1
], [
0,1
], and [
0,1
], respectively. n
j
s
i and d
j
t
i are randomly generated according to the normal distribution N
(
0,1
).For solving the above test Problems5 and 6, we utilized the proposed algorithm, the convergence tolerance parameters are set as ε
=
0.01, and the corresponding numerical results are listed in Tables 1 and 2, respectively. Average percentages are obtained by running the algorithm for 10 test problems. Tables 1 and 2 show the variation in the average number of computational results required when n was changed in {
50,100,150,200
} and p was changed in {
2,4
,
6
}. From Tables 1 and 2 we see that the algorithm works better for smaller p. So the size of p is the main factor affecting the performance of the algorithm. This is mainly because branching in the subproblem is proportional to p. Also, the time increases as n increases, but not as sharply as p.


## 6. Conclusion

We have presented and validated a branch and bound algorithm for global sums of ratios problem(
P
), where each term in the objective function is a ratio of two functions which are the sums of the absolute values of affine functions with coefficients. This problem computes the upper bounds by solving convex programming problems. These problems are derived by using the concave envelope of the objective function. The convergence of the algorithm is proved, and computational results for several test problems have been reported to show the feasibility and efficiency of the proposed algorithm.



---

*Source: 103569-2014-04-03.xml*