# A Deterministic Method for Solving the Sum of Linear Ratios Problem

Authors: Zhenping Wang; Yonghong Zhang
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

Since the sum of linear ratios problem (SLRP) has many applications in real life, for globally solving it, an efficient branch and bound algorithm is presented in this paper. By utilizing the characteristic of the problem (SLRP), we propose a convex separation technique and a two-part linearization technique, which can be used to generate a sequence of linear programming relaxation of the initial nonconvex programming problem. For improving the convergence speed of this algorithm, a deleting rule is presented. The convergence of this algorithm is established, and some experiments are reported to show the feasibility and efficiency of the proposed algorithm.


---

## Body

## 1. Introduction

This paper considers the sum of linear ratios problem (SLRP) with the following form:(1)SLRPminfx=∑i=1pγigixhix,s.t.Ax≤b,X0=x∈Rnl0≤x≤u0,where p≥2,gix=∑j=1ncijxj+diandhix=∑j=1neijxj+fi are the finite functions such that gix>0andhix>0 for all x∈Λ=xAx≤b,x∈X0, and A=aijm×n,b∈Rm, and γi are the real constant coefficients, i=1,…,p.As we know, fractional programming is an important branch of nonlinear optimization. As a special case of fractional programming, the sum of linear ratios problem has been widely concerned. The first reason is that SLRP has many important applications in the real world, such as certain government contracting problems [1], cluster analysis [2], and multiobjective bond portfolio [3]. The second reason is the objective function is neither quasiconvex nor quasiconcave, so it usually has multiple local optima that are not global optima, and it is a very challenging issue to find its global optima. In addition, as pointed by Matsui [4], a special case of SLRP was proved to be NP hard (Theorem 1, [4]), so SLRP is an NP-hard problem.Up to now, various algorithms have been proposed for solving SLRP. For instance, (i) whenp=2, by using the parametric simplex method, an algorithm was developed [5]; (ii) when p≥2, through searching iteratively the nonconvex outcome space until a global optimal solution is found, some algorithms were proposed [6, 7]. In addition, to solve special cases of SLRP, based on branch and bound, several other algorithms were presented [2, 3, 8–14].Although many algorithms have been proposed to find the global optimal solution of fractional programming, as far as we know, the research results of SLRP considered in this paper are still relatively little. Most of these algorithms proposed are intended only for the sum of linear ratios problem without coefficientsγi.The aim of the present paper is to present a new global optimization algorithm for solving SLRP. To globally solve SLRP, a convex separation technique and a two-part relaxation technique are designed to convert SLRP into a series of linear programming problems. Through a successive refinement process, the solutions of these linear programming problems can be as close as possible to the global optimum of SLRP. The main features of this algorithm are as follows: (1) compared with these methods reviewed above ([3, 6–9, 11, 15], for example), the method given in this paper can solve the general problem SLRP; (2) compared with the method in [2], this method need not introduce new variables; (3) by using a convex separation technique and a two-part relaxation technique, the initial problem SLRP can be converted into a series of linear programming problems, which is more convenient in the computation than the parametric programming (or concave minimization) methods [8]; (4) numerical results show that the proposed method can solve all of the test problems in finding globally optimal solutions with given precision.The organizational structure of this paper is as follows. To obtain the relaxed linear programming of SLRP, Section2 introduces a convex separation technique and a two-part relaxation technique. For improving the convergence speed of the proposed algorithm, a deleting rule is designed. In Section 3, the proposed branch and bound algorithm is described based on the relaxed subproblems, and the convergence of the algorithm is proved. Numerical results are given in Section 4, and some concluding remarks are provided in Section 5.


## 2. Linear Relaxation of SLRP

For solving the problem SLRP, one of the key parts is to construct lower bounds for SLRP and its partitioned subproblems. Towards this end, we propose a novel strategy to generate lower bound by underestimatingfx with a linear function. The detailed construction process is given below.LetX=x¯,x¯ be either the initial box X0 of the problem SLRP or the partitioned box in a branch and bound scheme. For convenience in expression, for i=1,…,p, let(2)gli=∑j=1nmincijx¯j,cijx¯j+di,gui=∑j=1nmaxcijx¯j,cijx¯j+di,hli=∑j=1nmineijx¯j,eijx¯j+fi,hui=∑j=1nmaxeijx¯j,eijx¯j+fi.For generating the linear relaxation offx, a convex separation technique and a two-part relaxation technique are designed.


### 2.1. First-Part Relaxation

For each termgix/hixi=1,…,p, since gix>0 and hix>0 for all x∈Λ, we can denote(3)gixhix=expyi,i=1,…,p.The lower bound and upper bound ofyi can be computed as follows:(4)y¯i=lnglihui,y¯i=lnguihli,i=1,…,p.By introducing the variabley, an equivalent form of fx can be derived, which is expressed in the following form:(5)φy=∑i=1pγiexpyi.Forφy, it is not difficult to calculate its gradient and Hessian matrix:(6)∇φy=γ1expy1γ2expy2⋮γpexpyp,∇2φy=γ1expy1γ2expy2⋱γpexpyp.Therefore, the following relation holds:(7)∇2φy≤max1≤i≤pγimax1≤i≤pexpy¯i.Letλ=max1≤i≤pγimax1≤i≤pexpy¯i+0.1; then, ∀y∈Y=y¯,y¯, we have(8)∇2φy<λ.Thus, the function(9)12λy2+φy.is convex on Y. Based on the above results, we can decompose φy into the difference between two convex as follows:(10)φy=ϕy−ψy,where ϕy=1/2λy2+φyandψy=1/2λy2.Letymid=1/2y¯+y¯, and since ϕy is a convex function, we have(11)ϕy≥ϕymid+∇ϕymidTy−ymid≜ϕly.In addition,∀yi∈y¯i,y¯i, it is not difficult to show(12)y¯i+y¯iyi−y¯iy¯i≥yi2.Furthermore, we have(13)∑i=1py¯i+y¯iyi−y¯iy¯i≥y2.Sinceλ>0, it follows that(14)ψuy≜12λ∑i=1py¯i+y¯iyi−y¯iy¯i≥12λy2=ψy.Thus, from (10), (11), and (14), we obtain(15)φly=ϕly−ψuy≤φy.From (3), it follows that yi=lngix−lnhix,i=1,…,p. Hence, the first-part relaxation of fx about x can be obtained, i.e.,(16)Lx≜ϕymid+∇ϕymidTy−ymid−12λ∑i=1py¯i+y¯iyi−y¯iy¯i=ϕymid+∑i=1pλymidi+γiexpymidiyi−∇ϕymidTymid−12λ∑i=1py¯i+y¯iyi−y¯iy¯i=∑i=1pγiexpymidilngix−lnhix+ϕymid−∇ϕymidTymid+12λ∑i=1py¯iy¯i.


### 2.2. Second-Part Relaxation

Forlnz over the interval z¯,z¯, we can derive its linear lower bound and linear upper bound as follows:(17)Kz−z¯+lnz¯≤lnz≤Kz−1−lnK,where K=lnz¯−lnz¯/z¯−z¯. Therefore, we have(18)K1igix−gli+lngli≤lngix≤K1igix−1−lnK1i,K2ihix−hli+lnhli≤lnhix≤K2ihix−1−lnK2i,where K1i=lngui−lngli/gui−gliandK2i=lnhui−lnhli/hui−hli.In (16), let βi=γiexpymidii=1,…,p. Then, we can obtain the linear lower bound function flx of fx as follows:(19)flx≜∑i=1pfilx+ϕymid−∇ϕymidTymid+12λ∑i=1py¯iy¯i,where(20)filx=βiK1igix−gli+lngli−K2ihix+1+lnK2i,ifβi≥0,βiK1igix−1−lnK1i−K2ihix−hli−lnhli,else.Obviously,flx≤fx.Consequently, the corresponding approximation relaxation linear programming (RLP) of SLRP inX is given as follows:(21)RLPminflxs.t.Ax≤b,x∈X.Theorem 1.
Letδj=x¯j−x¯j,ωi=y¯i−y¯i,ui=gui/gli,andvi=hui/hli,i=1,…,p,j=1,…,n. Then, for any x∈X, we have(22)fx−flx⟶0asδj⟶0,j=1,…,n.Proof.
∀x∈X, let Δ=fx−flx=fx−Lx+Lx−flx and let Δ1=fx−Lx,Δ2=Lx−flx. Obviously, we only need to prove Δ1⟶0andΔ2⟶0 as δj⟶0,j=1,…,n.First, by the definition ofΔ1, we have(23)Δ1=fx−Lx=∑i=1pγigixhix−∑i=1pγiexpymidilngix−lnhix+ϕymid+∇ϕymidTy−ymid+12λ∑i=1py¯iy¯i=∑i=1pγiexpyi−∑i=1pγiexpymidilngix−lnhix+ϕymid+∇ϕymidTy−ymid+12λ∑i=1py¯iy¯i=φy−φly≤∇ϕξ−∇ϕymidTy−ymid+12λy¯−y¯2≤2λξ−ymidy−ymid+12λy¯−y¯2≤52λy¯−y¯2,where ξ is a constant vector and satisfies ϕx−ϕymid=∇ϕξTy−ymid.Furthermore, according to the definition ofyi, we know that y¯−y¯⟶0 as δj⟶0,j=1,…,n. Thus, we have Δ1⟶0 as δj⟶0j=1,…,n.Second, consider the differenceΔ2=Lx−flx. By (16), we have(24)Δ2=Lx−flx=∑i=1pβilngix−lnhix−filx=∑βi≥0βilngix−K1igix−gli−lngli+K2ihix−lnK2i−1−lnhix+∑βi<0βilngix−K1igix−1−lnK1i+K2ihix−lnhli+lnhli−lnhix.From the definitions ofgli,gui,hli, and hui, we know that ωi⟶0 as δj⟶0. Consequently, from [16] (Theorem 1), we have Δ2⟶0 as δj⟶0.Taken together above, we have(25)Δ=Δ1+Δ2⟶0,asδj⟶0,j=1,…,n.By Theorem1, it can be seen that flx will approximate the objective function fx as δj⟶0,j=1,…,n.From the above discussion, it can be seen that the objective value of RLP is smaller than or equal to that of LFP for all feasible points; thus, RLP provides a valid lower bound for the solution of LFP. Thus, for any problem (P), let us denote the optimal value of P by VP, and then we have(26)VRLP≤VLFP.For improving the convergence speed of the proposed algorithm, a deleting technique is proposed, which can be used to eliminate the region that does not contain optimal solutions of SLRP.LetUB be the current known upper bound of the optimal objective value f∗ of the problem SLRP. Denoting(27)αj=∑i=1pβiK1icij−K2ieij,j=1,…,n,T^=∑i=1pT˜i,whereT˜i=βiK1idi−gli+lngli−K2ifi+1+lnK2i,ifβi≥0,βiK1idi−1−lnK1i−K2ifi−hli−lnhli,else,T=T^+ϕymid−∇ϕymidTymid+12λ∑i=1py¯y¯.The following theorem gives the deleting technique.Theorem 2.
For any subrectangleX=Xjn×1⊆X0 with Xj=x¯j,x¯j, let(28)ρk=UB−∑j=1,t≠knminαjx¯j,αjx¯j−T,k=1,…,n.If there existsk∈1,2,…,n such that αk>0 and ρk<αkx¯k, then there is no global optimal solution of SLRP over X1; if ∃k∈1,2,…,n such that αk<0 and ρk<αkx¯k, then there is no global optimal solution of SLRP over X2, where(29)X1=Xj1n×1⊆X,withXj1=Xj,j≠k,ρkαk,x¯k∩Xj,j=k,X2=Xj2n×1⊆X,withXj2=Xj,j≠k,x¯k,ρkαk∩Xj,j=k.Proof.
We first show that∀x∈X1, fx>UB. Consider the k-th component xk of x, and it obviously follows that(30)ρkαk<xk≤x¯k.
Note thatαk>0, and then from the definition of ρk and the above inequality, we have(31)UB<∑j=1,j≠knminαjx¯j,αjx¯t+αkxk+T≤∑j=1nαjxj+T=∑i=1pfilx+ϕymid−∇ϕymidTymid+12λ∑i=1py¯y¯=flx.
∀x∈X1, since f∗≤UB<flx≤fx, there does not exist global optimal solution of SLRP over X1.
Similarly,∀x∈X2, if αk<0 and ρk<αkx¯k with some k, we can derive that there is no global optimal solution of SLRP over X2.


## 2.1. First-Part Relaxation

For each termgix/hixi=1,…,p, since gix>0 and hix>0 for all x∈Λ, we can denote(3)gixhix=expyi,i=1,…,p.The lower bound and upper bound ofyi can be computed as follows:(4)y¯i=lnglihui,y¯i=lnguihli,i=1,…,p.By introducing the variabley, an equivalent form of fx can be derived, which is expressed in the following form:(5)φy=∑i=1pγiexpyi.Forφy, it is not difficult to calculate its gradient and Hessian matrix:(6)∇φy=γ1expy1γ2expy2⋮γpexpyp,∇2φy=γ1expy1γ2expy2⋱γpexpyp.Therefore, the following relation holds:(7)∇2φy≤max1≤i≤pγimax1≤i≤pexpy¯i.Letλ=max1≤i≤pγimax1≤i≤pexpy¯i+0.1; then, ∀y∈Y=y¯,y¯, we have(8)∇2φy<λ.Thus, the function(9)12λy2+φy.is convex on Y. Based on the above results, we can decompose φy into the difference between two convex as follows:(10)φy=ϕy−ψy,where ϕy=1/2λy2+φyandψy=1/2λy2.Letymid=1/2y¯+y¯, and since ϕy is a convex function, we have(11)ϕy≥ϕymid+∇ϕymidTy−ymid≜ϕly.In addition,∀yi∈y¯i,y¯i, it is not difficult to show(12)y¯i+y¯iyi−y¯iy¯i≥yi2.Furthermore, we have(13)∑i=1py¯i+y¯iyi−y¯iy¯i≥y2.Sinceλ>0, it follows that(14)ψuy≜12λ∑i=1py¯i+y¯iyi−y¯iy¯i≥12λy2=ψy.Thus, from (10), (11), and (14), we obtain(15)φly=ϕly−ψuy≤φy.From (3), it follows that yi=lngix−lnhix,i=1,…,p. Hence, the first-part relaxation of fx about x can be obtained, i.e.,(16)Lx≜ϕymid+∇ϕymidTy−ymid−12λ∑i=1py¯i+y¯iyi−y¯iy¯i=ϕymid+∑i=1pλymidi+γiexpymidiyi−∇ϕymidTymid−12λ∑i=1py¯i+y¯iyi−y¯iy¯i=∑i=1pγiexpymidilngix−lnhix+ϕymid−∇ϕymidTymid+12λ∑i=1py¯iy¯i.


## 2.2. Second-Part Relaxation

Forlnz over the interval z¯,z¯, we can derive its linear lower bound and linear upper bound as follows:(17)Kz−z¯+lnz¯≤lnz≤Kz−1−lnK,where K=lnz¯−lnz¯/z¯−z¯. Therefore, we have(18)K1igix−gli+lngli≤lngix≤K1igix−1−lnK1i,K2ihix−hli+lnhli≤lnhix≤K2ihix−1−lnK2i,where K1i=lngui−lngli/gui−gliandK2i=lnhui−lnhli/hui−hli.In (16), let βi=γiexpymidii=1,…,p. Then, we can obtain the linear lower bound function flx of fx as follows:(19)flx≜∑i=1pfilx+ϕymid−∇ϕymidTymid+12λ∑i=1py¯iy¯i,where(20)filx=βiK1igix−gli+lngli−K2ihix+1+lnK2i,ifβi≥0,βiK1igix−1−lnK1i−K2ihix−hli−lnhli,else.Obviously,flx≤fx.Consequently, the corresponding approximation relaxation linear programming (RLP) of SLRP inX is given as follows:(21)RLPminflxs.t.Ax≤b,x∈X.Theorem 1.
Letδj=x¯j−x¯j,ωi=y¯i−y¯i,ui=gui/gli,andvi=hui/hli,i=1,…,p,j=1,…,n. Then, for any x∈X, we have(22)fx−flx⟶0asδj⟶0,j=1,…,n.Proof.
∀x∈X, let Δ=fx−flx=fx−Lx+Lx−flx and let Δ1=fx−Lx,Δ2=Lx−flx. Obviously, we only need to prove Δ1⟶0andΔ2⟶0 as δj⟶0,j=1,…,n.First, by the definition ofΔ1, we have(23)Δ1=fx−Lx=∑i=1pγigixhix−∑i=1pγiexpymidilngix−lnhix+ϕymid+∇ϕymidTy−ymid+12λ∑i=1py¯iy¯i=∑i=1pγiexpyi−∑i=1pγiexpymidilngix−lnhix+ϕymid+∇ϕymidTy−ymid+12λ∑i=1py¯iy¯i=φy−φly≤∇ϕξ−∇ϕymidTy−ymid+12λy¯−y¯2≤2λξ−ymidy−ymid+12λy¯−y¯2≤52λy¯−y¯2,where ξ is a constant vector and satisfies ϕx−ϕymid=∇ϕξTy−ymid.Furthermore, according to the definition ofyi, we know that y¯−y¯⟶0 as δj⟶0,j=1,…,n. Thus, we have Δ1⟶0 as δj⟶0j=1,…,n.Second, consider the differenceΔ2=Lx−flx. By (16), we have(24)Δ2=Lx−flx=∑i=1pβilngix−lnhix−filx=∑βi≥0βilngix−K1igix−gli−lngli+K2ihix−lnK2i−1−lnhix+∑βi<0βilngix−K1igix−1−lnK1i+K2ihix−lnhli+lnhli−lnhix.From the definitions ofgli,gui,hli, and hui, we know that ωi⟶0 as δj⟶0. Consequently, from [16] (Theorem 1), we have Δ2⟶0 as δj⟶0.Taken together above, we have(25)Δ=Δ1+Δ2⟶0,asδj⟶0,j=1,…,n.By Theorem1, it can be seen that flx will approximate the objective function fx as δj⟶0,j=1,…,n.From the above discussion, it can be seen that the objective value of RLP is smaller than or equal to that of LFP for all feasible points; thus, RLP provides a valid lower bound for the solution of LFP. Thus, for any problem (P), let us denote the optimal value of P by VP, and then we have(26)VRLP≤VLFP.For improving the convergence speed of the proposed algorithm, a deleting technique is proposed, which can be used to eliminate the region that does not contain optimal solutions of SLRP.LetUB be the current known upper bound of the optimal objective value f∗ of the problem SLRP. Denoting(27)αj=∑i=1pβiK1icij−K2ieij,j=1,…,n,T^=∑i=1pT˜i,whereT˜i=βiK1idi−gli+lngli−K2ifi+1+lnK2i,ifβi≥0,βiK1idi−1−lnK1i−K2ifi−hli−lnhli,else,T=T^+ϕymid−∇ϕymidTymid+12λ∑i=1py¯y¯.The following theorem gives the deleting technique.Theorem 2.
For any subrectangleX=Xjn×1⊆X0 with Xj=x¯j,x¯j, let(28)ρk=UB−∑j=1,t≠knminαjx¯j,αjx¯j−T,k=1,…,n.If there existsk∈1,2,…,n such that αk>0 and ρk<αkx¯k, then there is no global optimal solution of SLRP over X1; if ∃k∈1,2,…,n such that αk<0 and ρk<αkx¯k, then there is no global optimal solution of SLRP over X2, where(29)X1=Xj1n×1⊆X,withXj1=Xj,j≠k,ρkαk,x¯k∩Xj,j=k,X2=Xj2n×1⊆X,withXj2=Xj,j≠k,x¯k,ρkαk∩Xj,j=k.Proof.
We first show that∀x∈X1, fx>UB. Consider the k-th component xk of x, and it obviously follows that(30)ρkαk<xk≤x¯k.
Note thatαk>0, and then from the definition of ρk and the above inequality, we have(31)UB<∑j=1,j≠knminαjx¯j,αjx¯t+αkxk+T≤∑j=1nαjxj+T=∑i=1pfilx+ϕymid−∇ϕymidTymid+12λ∑i=1py¯y¯=flx.
∀x∈X1, since f∗≤UB<flx≤fx, there does not exist global optimal solution of SLRP over X1.
Similarly,∀x∈X2, if αk<0 and ρk<αkx¯k with some k, we can derive that there is no global optimal solution of SLRP over X2.


## 3. Algorithm and Its Convergence

Based on the former linear relaxation programming (RLP), this section presents a branch and bound algorithm to solve the problem SLRP. In this method, a sequence of RLP problems over partitioned subsets ofX0 needs to be solved.As the algorithm goes on, the setX0 will be partitioned into some subrectangles. Each subrectangle is associated with a node of the branch and bound tree and a relaxation linear subproblem.At thek-th iteration of the algorithm, let Qk be a collection of active nodes denoted, i.e., each node in Qk is associated with a rectangle X⊆X0. ∀X∈Qk, a lower bound LBX of the optimal value of SLRP needs to be computed. The lower bound of the optimal value of SLRP is computed on the whole initial rectangle X0 at the k-th iteration by LBk=maxLBX,∀X∈Qk. Let Xk be the active node X with LBk=LBX and is partitioned into two subrectangles as described below. Meanwhile, the upper bound for each new node is computed as before. If necessary, the upper bound UBk is updated. After deleting all nodes that cannot be improved, a collection of active nodes for the next stage can be obtained. The above process is repeated until the termination conditions are met.


### 3.1. Branching Rule

In the proposed algorithm, a simple and standard bisection rule is used. Consider any node subproblem identified by rectangleX=x∈Rnx¯j≤xj≤x¯j,j=1,…,n⊆X0. The branching rule is briefly introduced as follows:(a)
Let(32)i=argmaxx¯j−x¯j,j=1,…,n.(b)
Let(33)γi=12x¯i+x¯i.(c)
Let(34)X1=x∈Rnx¯j≤xj≤x¯j,j≠i,x¯i≤xi≤γi,X2=x∈Rnx¯j≤xj≤x¯j,j≠i,γi≤xi≤x¯i.According to this branching rule, the rectangleX is partitioned into two subrectangles X1 and X2.Since this branching will derive the intervals to zero along any infinite branch of the branch and bound tree, it is sufficient to ensure convergence. This is very important to ensure the convergence of the algorithm.


### 3.2. Algorithm Statement

LetLBX be the optimal objective function value of the problem (RLP) over the rectangle X. Based on the results above, we give the basic steps of the proposed global optimization algorithm.Step 1. Choosing ε≥0. An optimal solution x0 and the optimal value LBX0 are found for the problem (RLP) with X=X0, and set(35)LB0=LBX0,UB0=fx0.IfUB0−LB0≤ε, then stop. x0 is a global ε-optimal solution for the problem SLRP. Otherwise, set(36)Q0=X0,F=ø,k=1.Step 2. Setting LBk=LBk−1. Xk−1 is subdivided into two rectangles Xk,1,Xk,2⊆Rn via the branching rule. Let F=F∪Xk−1.Step 3. For each node Xk,1,Xk,2, the lower bound for each linear constraint function ∑j=1naijxj,i=1,…,m is computed over the present considered rectangle, i.e., computing lower bound:(37)∑aij>0aijx¯j+∑aij<0aijx¯j,wherex¯j and x¯j denote the lower bound and the upper bound of the present considered rectangle, respectively. If there exists i∈1,…,m such that(38)∑aij>0aijx¯j+∑aij<0aijx¯j>bi,then we will put the corresponding node intoF. If Xk,1,Xk,2 are both put into F, i.e.,(39)F=F∪Xk,1,Xk,2,then go to Step 7.Step 4. For the undeleted subrectangle Xk,1 and/or Xk,2, parameters K1i,K2igli,gui,hli,hui,y¯i,y¯i,i=1,…,p are updated. LBXk,t is computed, and an optimal solution xk,t is found for the problem (RLP) with X=Xk,t, where t=1ort=2ort=1,2. If necessary, UBk is updated as follows:(40)UBk=minUBk,fxk,t,and letxk denote the point which satisfies UBk=fxk.Step 5. If UBk≤LBXk,t, then set(41)F=F∪Xk,t.Step 6. Setting(42)F=F∪X∈Qk−1UBk≤LBX.Step 7. Setting(43)Qk=XX∈Qk−1∪Xk,1,Xk,2,X∉F.Step 8. Setting LBk=minLBXX∈Qk, and let Xk∈Qk satisfy LBk=LBXk. If UBk−LBk≤ε, then stop. xk is a global ε-optimal solution for the problem SLRP. Otherwise, set k=k+1 and go to Step 2.


### 3.3. Convergence of the Algorithm

The following theorem gives some convergence properties of the algorithm.Theorem 3.
(i)
If the algorithm is finite, then upon termination,xk is a global ε-optimal solution of SLRP.(ii)
If the algorithm is infinite, then any accumulation point of the sequencexk, which is generated along any infinite branch of the branch and bound tree, will be the global solution of SLRP.Proof.
(i)
If the algorithm is finite, then it will terminate at some stagek, k≥0. Upon termination, by the algorithm, we have(44)UBk−LBk≤ε.According to Steps 1 and 4, it follows that(45)fxk−LBk≤ε.Letv be the optimal value of the problem SLRP. By Section 2, it can be known that(46)LBk≤v.Sincexk is a feasible solution of SLRP, we have(47)fxk≥v.Combined with the above discussion, this implies that(48)v≤fxk≤LBk+ε≤v+ε.Thus, we have(49)v≤fxk≤v+ε,and the proof of part (i) is complete.(ii)
When the algorithm is infinite, by the algorithm, we know thatLBk is a nondecreasing sequence and bounded above by minx∈Λfx. So, we have LB=limk⟶∞LBk≤minx∈Λfx. Since X0 is a compact set, there must be one convergent subsequence xs⊆xk. Suppose that lims⟶∞xs=x^. By the proposed algorithm, there exists a decreasing subsequence Xr⊆Xs where Xs∈Qs with xr∈Xr,LBr=LBXr=flxr, and limr⟶∞Xr=x^. From Theorem 1, we have(50)limr⟶∞flxr=limr⟶∞fxr=fx^.
By the definitions of RLP and SLRP,x^ is a feasible solution of SLRP obviously. Combining (50), it follows that x^ is a global solution of SLRP, and the proof of part (ii) is complete.


## 3.1. Branching Rule

In the proposed algorithm, a simple and standard bisection rule is used. Consider any node subproblem identified by rectangleX=x∈Rnx¯j≤xj≤x¯j,j=1,…,n⊆X0. The branching rule is briefly introduced as follows:(a)
Let(32)i=argmaxx¯j−x¯j,j=1,…,n.(b)
Let(33)γi=12x¯i+x¯i.(c)
Let(34)X1=x∈Rnx¯j≤xj≤x¯j,j≠i,x¯i≤xi≤γi,X2=x∈Rnx¯j≤xj≤x¯j,j≠i,γi≤xi≤x¯i.According to this branching rule, the rectangleX is partitioned into two subrectangles X1 and X2.Since this branching will derive the intervals to zero along any infinite branch of the branch and bound tree, it is sufficient to ensure convergence. This is very important to ensure the convergence of the algorithm.


## 3.2. Algorithm Statement

LetLBX be the optimal objective function value of the problem (RLP) over the rectangle X. Based on the results above, we give the basic steps of the proposed global optimization algorithm.Step 1. Choosing ε≥0. An optimal solution x0 and the optimal value LBX0 are found for the problem (RLP) with X=X0, and set(35)LB0=LBX0,UB0=fx0.IfUB0−LB0≤ε, then stop. x0 is a global ε-optimal solution for the problem SLRP. Otherwise, set(36)Q0=X0,F=ø,k=1.Step 2. Setting LBk=LBk−1. Xk−1 is subdivided into two rectangles Xk,1,Xk,2⊆Rn via the branching rule. Let F=F∪Xk−1.Step 3. For each node Xk,1,Xk,2, the lower bound for each linear constraint function ∑j=1naijxj,i=1,…,m is computed over the present considered rectangle, i.e., computing lower bound:(37)∑aij>0aijx¯j+∑aij<0aijx¯j,wherex¯j and x¯j denote the lower bound and the upper bound of the present considered rectangle, respectively. If there exists i∈1,…,m such that(38)∑aij>0aijx¯j+∑aij<0aijx¯j>bi,then we will put the corresponding node intoF. If Xk,1,Xk,2 are both put into F, i.e.,(39)F=F∪Xk,1,Xk,2,then go to Step 7.Step 4. For the undeleted subrectangle Xk,1 and/or Xk,2, parameters K1i,K2igli,gui,hli,hui,y¯i,y¯i,i=1,…,p are updated. LBXk,t is computed, and an optimal solution xk,t is found for the problem (RLP) with X=Xk,t, where t=1ort=2ort=1,2. If necessary, UBk is updated as follows:(40)UBk=minUBk,fxk,t,and letxk denote the point which satisfies UBk=fxk.Step 5. If UBk≤LBXk,t, then set(41)F=F∪Xk,t.Step 6. Setting(42)F=F∪X∈Qk−1UBk≤LBX.Step 7. Setting(43)Qk=XX∈Qk−1∪Xk,1,Xk,2,X∉F.Step 8. Setting LBk=minLBXX∈Qk, and let Xk∈Qk satisfy LBk=LBXk. If UBk−LBk≤ε, then stop. xk is a global ε-optimal solution for the problem SLRP. Otherwise, set k=k+1 and go to Step 2.


## 3.3. Convergence of the Algorithm

The following theorem gives some convergence properties of the algorithm.Theorem 3.
(i)
If the algorithm is finite, then upon termination,xk is a global ε-optimal solution of SLRP.(ii)
If the algorithm is infinite, then any accumulation point of the sequencexk, which is generated along any infinite branch of the branch and bound tree, will be the global solution of SLRP.Proof.
(i)
If the algorithm is finite, then it will terminate at some stagek, k≥0. Upon termination, by the algorithm, we have(44)UBk−LBk≤ε.According to Steps 1 and 4, it follows that(45)fxk−LBk≤ε.Letv be the optimal value of the problem SLRP. By Section 2, it can be known that(46)LBk≤v.Sincexk is a feasible solution of SLRP, we have(47)fxk≥v.Combined with the above discussion, this implies that(48)v≤fxk≤LBk+ε≤v+ε.Thus, we have(49)v≤fxk≤v+ε,and the proof of part (i) is complete.(ii)
When the algorithm is infinite, by the algorithm, we know thatLBk is a nondecreasing sequence and bounded above by minx∈Λfx. So, we have LB=limk⟶∞LBk≤minx∈Λfx. Since X0 is a compact set, there must be one convergent subsequence xs⊆xk. Suppose that lims⟶∞xs=x^. By the proposed algorithm, there exists a decreasing subsequence Xr⊆Xs where Xs∈Qs with xr∈Xr,LBr=LBXr=flxr, and limr⟶∞Xr=x^. From Theorem 1, we have(50)limr⟶∞flxr=limr⟶∞fxr=fx^.
By the definitions of RLP and SLRP,x^ is a feasible solution of SLRP obviously. Combining (50), it follows that x^ is a global solution of SLRP, and the proof of part (ii) is complete.


## 4. Numerical Experiment

To test the performance of the proposed global optimization algorithm, it is compared with some other algorithms based on five test problems. The convergence tolerance is set toε = 1.0e − 2 in our experiment. The results are summarized in Table 1.Table 1
Computational results of test problems.
ExampleMethodsOptimal solutionOptimal valueIterTime1[13](0.0, 3.3333, 0.0)1.980Ours(0.0, 3.3333, 0.0)1.910.0152[17](1.0, 0.0, 0.0)−4.081481380.02Ours(1.0, 0.0, 0.0)−4.081550.253[5](0.0, 3.3333, 0.0)−3.002923975119<1[16](0.0, 3.3333, 0.0)−3.002923972150Ours(0.0, 3.3333, 0.0)−3.0029140.8124[13](3.0, 4.0)−3.2916790Ours(3.0, 4.0)−3.291770.255[5](0.0, 0.283935547)1.62318335871<1Ours(0.0, 0.2812)1.6232452.468Notations have been used for column headers: Iter: number of algorithm iteration; time: execution time in seconds.Example 1 (see ref [13]).
(51)min−3x1+4x2+503x1+5x2+4x3+50+3x1+5x2+3x3+505x1+5x2+4x3+50+x1+2x2+4x3+505x2+4x3+50+4x1+3x2+3x3+503x2+3x3+50s.t.6x1+3x2+3x3≤1010x1+3x2+8x3≤100≤x1≤10≤x2≤3.33330≤x3≤1.Example 2 (see ref [17]).
(52)min−4x1+3x2+3x3+503x2+3x3+50−3x1+4x3+504x1+4x2+5x3+50−x1+2x2+5x3+50x1+5x2+5x3+50−x1+2x2+4x3+505x2+4x3+50s.t.2x1+x2+5x3≤10x1+6x2+3x3≤105x1+9x2+2x3≤109x1+7x2+3x3≤100≤x1≤1,0≤x2≤1,0≤x3≤2.Example 3 (see ref [5, 16]).
(53)min−3x1+5x2+3x3+503x1+4x2+5x3+50−3x1+4x2+504x1+3x2+2x3+50−4x1+2x2+4x3+505x1+4x2+3x3+50s.t.6x1+3x2+3x3≤1010x1+3x2+8x3≤100≤x1≤10≤x2≤3.33330≤x3≤1.Example 4 (see ref [13]).
(54)min−37x1+73x2+1313x1+13x2+13+63x1−18x2+3913x1+26x2+13−13x1+13x2+1363x2−18x3+39+13x1+26x2+1337x1+73x2+13s.t.5x1−3x2=31.5≤x1≤31.5≤x2≤4.Example 5 (see ref [5]).
(55)min−x1+2x2+23x1−4x2+5+4x1−3x2+4−2x1+x2+3s.t.x1+x2≤1.5x1−x2≤00≤x1≤10≤x2≤1.
From Table1, it is seen that our algorithm can globally solve the problem SLRP successfully.


## 5. Concluding Remarks

In this paper, for solving the problem SLRP, we present a branch and bound algorithm. In this algorithm, we utilize a convex separation technique and a two-part relaxation technique to obtain a sequence of linear programming relaxation of the initial nonconvex programming problem SLRP, which is embedded in a branch and bound frame. Furthermore, for improving the convergence speed of the proposed algorithm, a deleting rule is designed. Numerical results show that it can solve the problem SLRP effectively.



---

*Source: 6174352-2020-09-28.xml*