# An Efficient Algorithm for Solving a Class of Fractional Programming Problems

Authors: Yongjian Qiu; Yuming Zhu; Jingben Yin
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

This paper presents an efficient branch-and-bound algorithm for globally solving a class of fractional programming problems, which are widely used in communication engineering, financial engineering, portfolio optimization, and other fields. Since the kind of fractional programming problems is nonconvex, in which multiple locally optimal solutions generally exist that are not globally optimal, so there are some vital theoretical and computational difficulties. In this paper, first of all, for constructing this algorithm, we propose a novel linearizing method so that the initial fractional programming problem can be converted into a linear relaxation programming problem by utilizing the linearizing method. Secondly, based on the linear relaxation programming problem, a novel branch-and-bound algorithm is designed for the kind of fractional programming problems, the global convergence of the algorithm is proved, and the computational complexity of the algorithm is analysed. Finally, numerical results are reported to indicate the feasibility and effectiveness of the algorithm.


---

## Body

## 1. Introduction

In this paper, we consider the following a class of fractional programming problems:(1)FP:maxgx=∑j=1p∏t=1mfjtxhjtxs.t.x∈D=x|Ax≤b,where p and m are all any arbitrary natural numbers and x is an N−dimensional variable, and for any x∈D⊂RN, fjtx and hjtxj=1,…,pandt=1,…,m are all affine functions such that fjtx>0 and hjtx>0. It should be pointed out that, in portfolio optimization, the variable x refers to the amount of investment; in computer vision, the variable x refers to the mapping space; in communication engineering, variable x refers to input signal.During the past decades, as special cases of the (FP), the linear sum-of-ratios problem and linear multiplicative programming problem have attracted a huge attention of practitioners and researchers for many years. This is because the linear sum-of-ratios problem and linear multiplicative programming problem exist in very important applications such as chance optimization, portfolio optimization, engineering optimization, and data envelopment analysis [1]. In addition, the linear sum-of-ratios problem and linear multiplicative programming problem generally possess multiple local optima which are not globally optimum. The problem (FP) investigated in this paper can be looked as the extensions of the linear sum-of-ratios problem or linear multiplicative programming problem so that the problem (FP) has a broader of applications than the linear sum-of-ratios problem and the linear multiplicative programming problem, and it poses more complex theory and computational difficulties.Over the two decades, a variety of algorithms have been developed for solving the special forms of the problem (FP). For example, for the linear sum-of-ratios problem, several algorithms can be obtained, such as simplex and parametric simplex methods [2, 3], image space approach [4], branch-and-bound methods [5–12], trapezoidal algorithm [13, 14], and monotonic optimization algorithm [15]; for the linear multiplicative programming problem, some algorithms can be also found in literatures, such as branch-and-bound algorithms [16–18], polynomial time approximation algorithm [19], outcome space algorithms [20, 21], level set algorithm [22], heuristic method [23], and monotonic optimization algorithm [15]. Furthermore, Jiao et al. [24, 25] and Chen and Jiao [26] presented three different algorithms for solving the linear multiplicative programming problem. Recently, for the several kinds of special forms of the problem (FP), Huang et al. [27], Jiao et al. [12], and Wang and Zhang [28] presented three different global optimization algorithms for the sum of linear ratios’ problem; Jiao et al. [29] and Yin et al. [30] proposed two different outer space branch-and-bound algorithms for the generalized linear multiplicative programming problem; Jiao and Chen [31] and Jiao and Liu [32, 33] gave three branch-reduction-bound algorithms for solving the quadratically constrained quadratic programming problem and quadratically constrained sum of quadratic ratios’ problem; Jiao et al. [34, 35], Ghazi and Roubi [36], and Bennani et al. [37] presented four different algorithms for solving the generalized polynomial optimization problem and generalized linear fractional programming problem. In addition, several differential evolution algorithms [38–40], a novel gate resource allocation method using improved PSO-based QEA [41], and an enhanced MSIQDE algorithm with novel multiple strategies [42] are also proposed for solving the global optimization problems including the problem (FP). Up to today, although some researchers have proposed some algorithms for solving the linear sum-of-ratios problem, the linear multiplicative programming problem, or the special form of the problem (FP), to our knowledge, little work has been still done for globally the general form of the problem (FP) considered in this paper.The purpose of this paper is to develop an effective algorithm for globally solve all variants of the problem (FP). First of all, based on equivalent transformation and characteristics of the exponential function and logarithmic function, a novel linearizing method is proposed. By utilizing the linearizing method, we can convert the initial problem (FP) or its subproblem into a linear relaxation problem (LRP), whose solution can be infinitely close to the optimal solution of the problem (FP) by a successive refinement partition. Secondly, based on the branch-and-bound framework, a novel branch-and-bound algorithm is constructed for globally solving all variants of the problem (FP), and the global convergence of the proposed algorithm is proved. In addition, the computational complexity of the algorithm is analysed for the first time, and the maximum iterations of the algorithm are estimated for the first time. Finally, numerical experimental results demonstrate the feasibility and effectiveness of the proposed algorithm.The remaining sections of this paper are organized as follows. A new linearizing method is constructed for deriving the problem (LRP) of the problem (FP) in Section2. Based on the branch-and-bound scheme and the constructed problem (LRP), a global optimization algorithm is established in Section 3, and its convergence is derived. In Section 4, the computational complexity of the algorithm is analysed. In Section 5, numerical experiments are given to verify the feasibility and effectiveness of the proposed algorithm. Finally, some conclusions are given in Section 6.


## 2. Novel Linearizing Technique

In this section, we will present a new linearizing method for constructing the problem (LRP). For eachi=1,…,N, we firstly solve the following two linear programming problems:(2)x¯i0=minxis.t.Ax≤b,x¯i0=maxxis.t.Ax≤b.We can get an initial rectangleX0=x¯0,x¯0=x¯i0,x¯i0N×1, which contains the feasible region of the problem (FP).Next, sincefjtx>0 and hjtx>0 for all x∈X0, it can easily follow that(3)gx=∑j=1p∏t=1mfjtxhjtx=∑j=1pexp∑t=1mlnfjtx−lnhjtx.For anyx∈X=x|x¯≤x≤x¯⊆X0, for each j=1,…,pandt=1,…,m, we let(4)fjtl=minx∈Xfjtx,fjtu=maxx∈Xfjtx,kjt1=lnfjtu−lnfjtlfjtu−fjtl,hjtl=minx∈Xhjtx,hjtu=maxx∈Xhjtx,kjt2=lnhjtu−lnhjtlhjtu−hjtl.By the characteristics of the logarithmic functionslnfjtx and lnhjtx over X, it can follow that(5)lnfjtx≤kjt1fjtx−1−lnkjt1,kjt2hjtx−hjtl+lnhjtl≤lnhjtx.Then, by the above inequalities, we can follow that(6)lnfjtx−lnhjtx≤kjt1fjtx−1−lnkjt1−kjt2hjtx−hjtl+lnhjtl.For eachj=1,…,pandt=1,…,m, we let(7)φjtx=kjt1fjtx−1−lnkjt1−kjt2hjtx−hjtl+lnhjtl.Thus, by equations (3)–(7), it follows that(8)gx=∑j=1pexp∑t=1mlnfjtx−lnhjtx≤∑j=1pexp∑t=1mφjtx.For anyx∈X=x|x¯≤x≤x¯⊆X0, we let(9)φjx=∑t=1mφjtx,φjl=minx∈Xφjx,φju=maxx∈Xφjx,Kj=expφju−expφjlφju−φjl.By the characters of the exponential functionexpφjx over φjl,φju, we can get that(10)expφjx≤Kjφjx−φjl+expφjl.Therefore, we have(11)∑j=1pexpφjx≤∑j=1pKjφjx−φjl+expφjl.Let(12)Ugx=∑j=1pKjφjx−φjl+expφjl.Combining equations (8)–(12), it can follow that(13)gx≤∑j=1pexpφjx≤∑j=1pKjφjx−φjl+expφjl=Ugx.Consequently, based on the above discussions, we can establish the corresponding linear relaxation problem (LRP) of the problem (FP) overX as follows:(14)LRP:maxUgx=∑j=1pKjφjx−φjl+expφjl,s.t.Ax≤b,x∈X,where φjx,φjl, and Kj,j=1,2,…,p, are given by (9).Based on the constructing method of the linear relaxation problem (LRP), for anyX⊆X0, the global optimal value of the problem (LRP) can offer a reliable upper bound for the global optimal value of the problem (FP) over X.Theorem1 guarantees that Ugx will infinitely approximate gx as x¯−x¯⟶0.Theorem 1.
For anyx∈X=x|x¯≤x≤x¯⊆X0, we have(15)limx¯−x¯⟶0Ugx−gx⟶0.Proof.
For anyx∈X, without loss of generality, let Δ1=Ugx−∑j=1pexpφjx and Δ2=∑j=1pexpφjx−gx; we can obtain that(16)Ugx−gx=Ugx−∑j=1pexpφjx+∑j=1pexpφjx−gx=Δ1+Δ2.
Therefore, to prove thatlimx¯−x¯⟶0Ugx−gx⟶0, we just prove that limx¯−x¯⟶0Δ1⟶0 and limx¯−x¯⟶0Δ2⟶0.
First of all, letΔj1=Kjφjx−φjl+expφjl−expφjx; we have that(17)Δ1=Ugx−∑j=1pexpφjx=∑j=1pKjφjx−φjl+expφjl−∑j=1pexpφjx=∑j=1pKjφjx−φjl+expφjl−expφjx=∑j=1pΔj1.
SinceΔj1=Kjφjx−φjl+expφjl−expφjx is a concave function about φjx, it can achieve the maximum value Δj1,max at the point lnKj. Let Tj=expφju−φjl−1/φju−φjl; then, through computing, we can obtain that(18)Δj1,max=expφjl1−Tj+TjlnTj.
Since(19)limx¯−x¯⟶0φju−φjl⟶0,limφju−φjl⟶0Tj⟶1,limTj⟶1Δj1,max⟶0,we have that(20)limx¯−x¯⟶0Δj1,max⟶0.
Therefore, by (17) and (20), we have(21)limx¯−x¯⟶0Δ1=limx¯−x¯⟶0∑j=1pΔj1⟶0.
Secondly, letϕjx=∑t=1plnfjtx−lnhjtx and Δj2=expφjx−expϕjx; we have(22)Δ2=∑j=1pexpφjx−gx=∑j=1pexpφjx−∑j=1pexp∑t=1mlnfjtx−lnhjtx=∑j=1pexpφjx−expϕjx=∑j=1pΔj2.
Since(23)Δj2=expφjx−expϕjx≤φjx−ϕjxsupθj∈Lφjx,ϕjxexpθj,where(24)Lφjx,ϕjx=βφjx+1−βϕjx,β∈0,1.
For eachj∈1,…,T, let(25)Δjt.12=kjt1fjtx−1−lnkjt1−lnfjtx,Δjt.22=lnhjtx−kjt2hjtx−hjtl+lnhjtl,and then, it follows that(26)φjx−ϕjx=∑t=1Tjkjt1fjtx−1−lnkjt1−lnfjtx+∑t=1Tjlnhjtx−kjt2hjtx−hjtl+lnhjtl,=∑t=1TjΔjt.12+Δjt.22.
Since the functionΔjt.12 is a convex function about fjtx, it can obtain the maximum value Δjt.12,max at the point fjtl or fjtu. Then, through computing, we get(27)Δjt.12,max=lnfjtu/fjtlfjtu/fjtl−1−1−lnlnfjtu/fjtlfjtu/fjtl−1.
Sincefjtu/fjtl⟶1 as x¯−x¯⟶0, then we have Δjt.12,max⟶0asx¯−x¯⟶0. Therefore, it follows that(28)Δjt.12⟶0asx¯−x¯⟶0.
Similarly, we can prove that(29)Δjt.22⟶0asx¯−x¯⟶0.
By (28) and (29), it follows that, as x¯−x¯⟶0,(30)φjx−ϕjx=∑t=1mΔjt.12+Δjt.22⟶0.
Sinceexpθj is a continuous and bounded function about x, then there exists some M¯>0 such that expθj≤M¯. Therefore, by (23) and (30), it follows that(31)Δj2≤M¯φjx−ϕjx⟶0asx¯−x¯⟶0.
By (30) and (31), it follows that(32)Δ2=∑j=1mΔj2⟶0asx¯−x¯⟶0.
By (21) and (32), it follows that(33)Δ=Ugx−gx=Δ1+Δ2⟶0asx¯−x¯⟶0.
By the above discussions, it is obvious that the conclusion can be followed.
From Theorem1, it follows that Ugx will infinitely approximate gx as x¯−x¯⟶0.


## 3. Algorithm and Its Global Convergence

In this section, based on the above linear relaxation problem, a branch-and-bound algorithm is proposed for globally solving the problem (FP). We firstly select a rectangle bisection technique of maximum edge, which ensures the global convergence of the present algorithm. The detailed branching technique is described as follows. Suppose thatXk=x¯k,x¯k⊆X0 is the selected rectangle for partitioning; let σ∈argmaxx¯ik−x¯ik:i=1,2,…,N; subdivide the interval x¯σk,x¯σk into two subintervals x¯σk,x¯σk+x¯σk/2 and x¯σk+x¯σk/2,x¯σk so that we can subdivide Xk into two subrectangles. Next, by solving a sequence of linear relaxation problems (LRP) of the problem (FP), the upper bound of the optimal value of the problem (FP) can be updated. Moreover, by detecting the feasible points and computing the objective functional values of these feasible points, the lower bound of the optimal value of the problem (FP) can be updated.


### 3.1. The Proposed Branch-and-Bound Algorithm

LetUBXk and xk=xXk be the optimal value and the optimal solution of the problem (LRP) over Xk, respectively. The corresponding branch-and-bound algorithm is given as follows.Steps of the proposed branch-and-bound algorithm:Step 1.
Given the convergence errorɛ>0 and the initial lower bound LB0=−∞, solve the problem (LRP) over X0 to get x0 and UBX0, respectively. Let UB0=UBX0 and LB0=gx0. If UB0−LB0≤ɛ, then the algorithm terminates, and x0 is a global ϵ-optimal solution of the problem (FP). Otherwise, let Ω0=X0, Λ=∅, and k=1.Step 2.
LetLBk=LBk−1. Use the selected branching method to subdivide the rectangle Xk−1 into two new subrectangles Xk,1 and Xk,2, and let Λ=Λ∪Xk−1.Step 3.
For each subrectangleXk,t, where t=1and2, solve the problem (LRP) to get xk,t and UBXk,t, and let LBk=maxLBk,gxk,t.If the midpointxmid of Xk,tt∈1,2 is feasible to the problem (FP), let LBk=maxLBk,gxmid, and let xk be the best feasible solution satisfying that LBk=gxk.Step 4.
IfLBk≥UBXk,t, then let Λ=Λ∪Xk,t, where t=1and2, and let Ωk=X|X∈Ωk−1∪Xk,1,Xk,2,X∉Λ.Step 5.
LetUBk=maxUBX|X∈Ωk and X∈Ωk satisfy that UBk=UBX. If UBk−LBk≤ɛ, then the algorithm terminates with that xk is the global ϵ-optimal solution of the problem (FP). Otherwise, let k=k+1, and return to Step 2.


### 3.2. Convergence Analysis

In this section, the global convergence of the proposed algorithm is given as follows.Theorem 2.
If the proposed algorithm is finite, then the algorithm will terminate afterk iteration, and xk is the global ϵ−optimal solution of the problem (FP). Otherwise, the proposed algorithm will produce an infinite sequence of iterations such that any accumulation point of the sequence xk will be the global optimal solution of the problem (FP).If the proposed algorithm terminates afterk iteration, by the termination condition of the proposed algorithm, we can get that UBk−LBk≤ɛ. By the updating method of the upper bound, we have that LBk=gxk. By the structure of the branch-and-bound algorithm, we have that v≤UBkandLBk≤v. By combining these inequalities, we have that v≤gxk≤v+ɛ. Thus, xk is a global ϵ-optimal solution of the problem (FP).If the present algorithm does not stop afterk iterations, by the branch-and-bound structure of the algorithm, it is well known that we can obtain a nondecreasing sequence UBk with that the lower bound is maxx∈Πgx, where Π is the set of the known feasible point. Thus, we get that limk⟶∞UBk≥maxx∈Πgx.Becausexk∈X0 and X0 is a bounded close set, we can follow that there must exist a convergent subsequence xμ⊆xk satisfying that limμ⟶∞xμ=x∗. It is obvious that we have x∗∈X0. By the branch-and-bound framework of the algorithm, there must exist a subsequence Xμ⊆Xk, where Xk∈Ωk with xμ∈Xμ,UBμ=UBXμ=Ugxμ, limμ⟶∞xμ=x∗, and limμ⟶∞Xμ=x∗. By Theorem 1 and continuity of the function gx, we can follow that limμ⟶∞UBμ=limμ⟶∞UBXμ=limμ⟶∞Ugxμ=limμ⟶∞gxμ=gx∗. From the steps of the algorithm, we know that xμ is always a feasible solution to the problem (FP), thus x∗ is the global optimal solution for the problem (FP), and the proof of the theorem is completed.


## 3.1. The Proposed Branch-and-Bound Algorithm

LetUBXk and xk=xXk be the optimal value and the optimal solution of the problem (LRP) over Xk, respectively. The corresponding branch-and-bound algorithm is given as follows.Steps of the proposed branch-and-bound algorithm:Step 1.
Given the convergence errorɛ>0 and the initial lower bound LB0=−∞, solve the problem (LRP) over X0 to get x0 and UBX0, respectively. Let UB0=UBX0 and LB0=gx0. If UB0−LB0≤ɛ, then the algorithm terminates, and x0 is a global ϵ-optimal solution of the problem (FP). Otherwise, let Ω0=X0, Λ=∅, and k=1.Step 2.
LetLBk=LBk−1. Use the selected branching method to subdivide the rectangle Xk−1 into two new subrectangles Xk,1 and Xk,2, and let Λ=Λ∪Xk−1.Step 3.
For each subrectangleXk,t, where t=1and2, solve the problem (LRP) to get xk,t and UBXk,t, and let LBk=maxLBk,gxk,t.If the midpointxmid of Xk,tt∈1,2 is feasible to the problem (FP), let LBk=maxLBk,gxmid, and let xk be the best feasible solution satisfying that LBk=gxk.Step 4.
IfLBk≥UBXk,t, then let Λ=Λ∪Xk,t, where t=1and2, and let Ωk=X|X∈Ωk−1∪Xk,1,Xk,2,X∉Λ.Step 5.
LetUBk=maxUBX|X∈Ωk and X∈Ωk satisfy that UBk=UBX. If UBk−LBk≤ɛ, then the algorithm terminates with that xk is the global ϵ-optimal solution of the problem (FP). Otherwise, let k=k+1, and return to Step 2.


## 3.2. Convergence Analysis

In this section, the global convergence of the proposed algorithm is given as follows.Theorem 2.
If the proposed algorithm is finite, then the algorithm will terminate afterk iteration, and xk is the global ϵ−optimal solution of the problem (FP). Otherwise, the proposed algorithm will produce an infinite sequence of iterations such that any accumulation point of the sequence xk will be the global optimal solution of the problem (FP).If the proposed algorithm terminates afterk iteration, by the termination condition of the proposed algorithm, we can get that UBk−LBk≤ɛ. By the updating method of the upper bound, we have that LBk=gxk. By the structure of the branch-and-bound algorithm, we have that v≤UBkandLBk≤v. By combining these inequalities, we have that v≤gxk≤v+ɛ. Thus, xk is a global ϵ-optimal solution of the problem (FP).If the present algorithm does not stop afterk iterations, by the branch-and-bound structure of the algorithm, it is well known that we can obtain a nondecreasing sequence UBk with that the lower bound is maxx∈Πgx, where Π is the set of the known feasible point. Thus, we get that limk⟶∞UBk≥maxx∈Πgx.Becausexk∈X0 and X0 is a bounded close set, we can follow that there must exist a convergent subsequence xμ⊆xk satisfying that limμ⟶∞xμ=x∗. It is obvious that we have x∗∈X0. By the branch-and-bound framework of the algorithm, there must exist a subsequence Xμ⊆Xk, where Xk∈Ωk with xμ∈Xμ,UBμ=UBXμ=Ugxμ, limμ⟶∞xμ=x∗, and limμ⟶∞Xμ=x∗. By Theorem 1 and continuity of the function gx, we can follow that limμ⟶∞UBμ=limμ⟶∞UBXμ=limμ⟶∞Ugxμ=limμ⟶∞gxμ=gx∗. From the steps of the algorithm, we know that xμ is always a feasible solution to the problem (FP), thus x∗ is the global optimal solution for the problem (FP), and the proof of the theorem is completed.


## 4. Computational Complexity of the Algorithm

In this section, first of all, we derive the difference betweenUgx and gx with the relationship of x¯−x¯ to analyse the computational complexity of the present algorithm.For anyx∈X⊆X0, for each j=1,…,pandt=1,…,m, without loss of generality, assume that(34)fjtx=∑i=1Nαjtixi+djt,hjtx=∑i=1Nδjtixi+γjt,and define(35)ξ^jtl=minx∈X0∑i=1Nαjtixi+djt,η^jtl=minx∈X0∑i=1Nδjtixi+γjt,φ^ju=maxx∈X0φjx.Obviously, we have that(36)kjt1≤1ξ^jtl,kjt2≤1η^jtl,j=1,…,pandt=1,…,m,and for any x∈X⊆X0 and j=1,…,p, we have that(37)φ^ju=maxx∈X0φjx≥maxx∈Xφjx=φju.Theorem 3.
For anyx∈X⊆X0, the difference between Ugx and gx with the relationship of x¯−x¯ satisfies the following inequality:(38)Ugx−gx≤∑i=1N3∑j=1pexpφ^ju∑t=1m1ξ^jtlαjti+1η^jtlδjtix¯i−x¯i.By Theorem1, we have that(39)Ugx−gx=Ugx−∑j=1pexpφjx+∑j=1pexpφjx−gx.By the proving process of Theorem1, we have(40)Ugx−∑j=1pexpφjx=∑j=1pKjφjx−φjl+expφjl−∑j=1pexpφjx=∑j=1pKjφjx−φjl+expφjl−expφjx.From the proving process of Theorem1, for any x∈X⊆X0, we have that(41)∑j=1pKjφjx−φjl+expφjl−expφjx≤∑j=1pKjφju−φjl+expφjl−expφjx=∑j=1pexpφju−expφjl+expφjl−expφjx=∑j=1pexpφju−expφjx≤∑j=1pexpφjuφju−φjl≤∑j=1pexpmaxx∈X0φjxφju−φjl=∑j=1pexpφ^ju×∑t=1mkjt1∑i=1Nαjtix¯i−x¯i+∑t=1mkjt2∑i=1Nδjtix¯i−x¯i=∑j=1pexpφ^ju×∑i=1N∑t=1mkjt1αjti+∑t=1mkjt2δjtix¯i−x¯i=∑j=1pexpφ^ju×∑i=1N∑t=1mkjt1αjti+kjt2δjtix¯i−x¯i≤∑j=1pexpφ^ju×∑i=1N∑t=1m1ξ^jtlαjti+1η^jtlδjtix¯i−x¯i=∑i=1N∑j=1pexpφ^ju∑t=1m1ξ^jtlαjti+1η^jtlδjtix¯i−x¯i.By the proving process of Theorem1, for any x∈X⊆X0, we also have(42)∑j=1pexpφjx−gx=∑j=1pexpφjx−exp∑t=1mlnfjtx−lnhjtx≤∑j=1pexpφjxφjx−∑t=1mlnfjtx−lnhjtx≤∑j=1pexpmaxx∈X0φjxφjx−∑t=1mlnfjtx−lnhjtx≤∑j=1pexpφ^ju×maxx∈Xφjx−∑t=1mlnfjtx−lnhjtx≤∑j=1pexpφ^ju×2∑i=1N∑t=1m1ξ^jtlαjti+1η^jtlδjtix¯i−x¯i=∑i=1N2∑j=1pexpφ^ju∑t=1m1ξ^jtlαjti+1η^jtlδjtix¯i−x¯i.Therefore, by the above conclusions, we can get that(43)Ugx−gx=Ugx−∑j=1pexpφjx+∑j=1pexpφjx−gx≤∑i=1N3∑j=1pexpφ^ju∑t=1m1ξ^jtlαjti+1η^jtlδjtix¯i−x¯i.Without losing generality, we define the sizeΘX of a rectangle X=x∈|RNx¯i≤xi≤x¯i,i=1,2,…,N⊆X0 by(44)ΘX≔maxx¯i−x¯i|i=1,2,…,N.Besides, for convenience, we let(45)β=max3∑j=1pexpφ^ju∑t=1m1ξ^jtlαjti+1η^jtlδjti,i=1,…,N.Theorem 4.
For any given convergence errorε>0, if there exists a rectangle Xk at the kth iteration, which satisfies that ΘXk≤ε/Nβ, then we have that(46)UBXk−LBk≤ε,where UBXk is the optimum value to the problem LRP over Xk and LBk is the known best lower bound of the global minimum value of the problem (FP).Proof.
Assume thatxk is the optimal solution to the problem (LRP) over Xk; obviously, xk is also feasible to the problem (FP) over Xk. Therefore, we have that(47)gxk≤LBk≤UBXk=Ugxk.
By the conclusion of Theorem3, we can get that(48)UBXk−LBk≤Ugxk−gxk≤∑i=1N3∑j=1pexpφ^ju∑t=1m1ξ^jtlαjti+1η^jtlδjtix¯i−x¯i≤∑i=1NΘXkβ≤NβΘXk.
Furthermore, byΘXk≤ε/Nβ, we can get that(49)UBXk−LBk≤NβΘXk≤ε,and the proof of the theorem is completed.
From the steps of the algorithm and the conclusions of Theorem4, when ΘXk≤ε/Nβ, the investigated rectangle Xk can be deleted from the active nodes’ set. Therefore, when the sizes of all investigated rectangles X satisfy ΘX≤ε/Nβ, the present algorithm will be terminated. From the conclusions of Theorem 4, we can estimate the maximum iterations of the present algorithm as follows.Theorem 5.
For any given convergence errorɛ∈0,1, the present algorithm can obtain a global ϵ-optimal solution to the problem (FP) in at most(50)N⋅log2NβΘX0ɛiterations.Without loss of generality, assume that the subrectangleXk⊆X0 is selected for subdividing in Step 2 of the present algorithm for every iteration. After k·N iterations, we can get that(51)ΘXk≤12kΘX0.From the conclusions of Theorem4, when(52)12kΘX0≤ɛNβ,i.e.,(53)k≥log2NβΘX0ɛ,we can obtain that UBXk−LBk≤ɛ. Therefore, after at most(54)N⋅log2NβΘX0ɛiterations, we can obtain a global ϵ-optimal solution to the problem (FP), and the proof of the theorem is completed.


## 5. Numerical Experiments

To verify the feasibility of the proposed algorithm, the algorithm is coded in C++ software, and the simplex method is used to solve the problem (LRP); some numerical examples are solved on the microcomputer with Intel(R) Core(TM)2 i5-4590s CPU @3.0 GHz; the computational comparison of numerical results is listed Tables1 and 2 ; although these numerical examples have a relatively small-size variable, they are still challenging. In Table 1, we denote “Iter” as the number of iteration of the present algorithm.Table 1
Numerical comparison among the algorithm BARON and our algorithm on Examples A.1–A.5.
ExampleRefs.Optimal solutionOptimal valueIterCPU timeA.1This paper(1.5, 1.5)4.912587413170.079BARON(1.5, 1.5)4.912650.12A.2This paper(3.0, 4.0)5.0520.24BARON(3.0, 4.0)5.090.24A.3This paper(0.0, 0.0, 0.0)3.0250.101BARON(0.0, 0.0, 0.0)3.050.12A.4This paper(1.111111111, 0.0, 0.0)4.090702948110.061BARON(1.1111, 0.0000, 0.0000)4.090710.08A.5This paper(0, 0)0.53333333380.063BARON(0, 0)0.533330.10Table 2
Numerical computational comparisons among the algorithm BARON and our algorithm on Problem1.
p,NOur algorithmBARONAvg (std).NTAvg (std).timeAvg (std).NTAvg (std).time(2, 2)24 (15.75506973)0.15023405 (0.093567381)9.4 (11.06746985)0.228 (0.132815662)(2, 3)75.4 (43.58440088)0.7650699 (0.449198958)300 (824.0233276)0.887 (1.666667)(2, 4)154 (80.77953536)2.299828 (1.207666995)——(2, 5)422.8 (260.6222469)8.358369 (5.156726039)——(2, 6)505.5 (528.8942869)9.886233 (10.21000994)——(2, 7)3243.3 (1540.659603)107.42306 (50.68952342)——(2, 8)9178.5 (7330.518357)389.16934 (315.0401155)——(2, 9)11195.2 (7294.911283)575.2941 (382.8851755)——In the following, first of all, some small-size certainty examples in Appendix were tested with the present algorithm; a deep and accurate numerical comparison with the current state-of-the-art “BARON” is given in Table1. Next, to verify the robustness and reliability of the proposed algorithm, with the convergence error ɛ=10−2, we have also solved following randomly generated test Problem 1; numerical comparisons with the current state-of-the-art “BARON” are listed in Table 2.Problem 1.
(55)FP:maxgx=∑j=1p∑i=1Ncji1xi+dj1∑i=1Neji1xi+fj1×∑i=1Ncji2xi+dj2∑i=1Neji2xi+fj2s.t.Ax≤b,x∈0,1,where p is a natural number, A∈RM×N, b∈RM, and cji1, eji1, dj1, fj1, cji2, eji2, dj2, and fj2, j=1,…,pandi=1,…,N, are all randomly generated between 0 and 1; all elements of the matrix A are randomly generated between 0 and 1; all elements of vector b are randomly generated between 0 and 16; the number of the constraints M=5.
WhenN≥4, the software BARON failed to solve all arbitrary ten tests in 4800s. Thus, we just report the numerical computational results of our algorithm in Table 2.
In Table2, some notations have been used as follows: Avg.NT denotes the average number of iterations for the algorithm; Std.NT denotes the standard deviation of number of iterations for the algorithm; Avg.Time denotes the average running time of the algorithm in seconds; Std.Time denotes the standard deviation of running time for the algorithm.
From Table1, it is observed that, our algorithm spends less running time than the software BARON. Thus, our algorithm is the most efficient one for solving the problem (FP) with the small-size variable.
From Table2, we can observe that, when N≥4, the software BARON failed to solve all arbitrary ten tests in 4800s, but our algorithm can obtain the global optimal solution of the problem (FP) for arbitrary ten tests in a short time. So this demonstrates that our algorithm has the stronger robustness and stability than the software BARON.


## 6. Conclusions

In this paper, based on the branch-and-bound framework, we present an efficient global optimization algorithm for solving the problem (FP). In this algorithm, a novel linearizing technique is proposed for deriving the linear relaxation problem of the problem (FP), which can provide a reliable upper bound in the branch-and-bound algorithm. By subsequently partitioning the initial rectangle and solving a series of linear relaxation problems, the proposed algorithm is convergent to the global optimal solution for the problem (FP). Furthermore, based on the steps of the branch-and-bound algorithm, the computational complexity of the algorithm is analysed. Finally, numerical experiments verify the feasibilities and effectiveness of the proposed algorithm. The future work is to extend our new algorithm to the min-max affine fractional programming problem and generalized linear fractional programming problems.



---

*Source: 5556130-2021-07-07.xml*