# An Efficient Polynomial Time Algorithm for a Class of Generalized Linear Multiplicative Programs with Positive Exponents

Authors: Bo Zhang; YueLin Gao; Xia Liu; XiaoLi Huang
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

This paper explains a region-division-linearization algorithm for solving a class of generalized linear multiplicative programs (GLMPs) with positive exponent. In this algorithm, the original nonconvex problem GLMP is transformed into a series of linear programming problems by dividing the outer space of the problem GLMP into finite polynomial rectangles. A new two-stage acceleration technique is put in place to improve the computational efficiency of the algorithm, which removes part of the region of the optimal solution without problems GLMP in outer space. In addition, the global convergence of the algorithm is discussed, and the computational complexity of the algorithm is investigated. It demonstrates that the algorithm is a complete polynomial time approximation scheme. Finally, the numerical results show that the algorithm is effective and feasible.


---

## Body

## 1. Introduction

Consider a class of generalized linear multiplicative programs (GLMPs):(1)LFP:minfx=∏i=1pciTx+diαis.t.x∈X=x∈ℝn|Ax≤b,x≥0.Here,p≥2, X is a nonempty bounded closed set, A∈ℝm×n,b∈ℝm,ci∈ℝn, di∈ℝ, and αi>0. T represents the transpose of a vector (e.g., ciT represents the transpose of a vector ci). Besides, we assume that for any x∈X, all make ciTx+di>0,i=1,2,…,p.The problem GLMP usually has multiple nonglobal local optimal solutions and is a class of NP-hard problems [1], which can be widely used in the fields of finance optimization [2, 3], robust optimization [4], microeconomics [5], and multiobjective decision making [6, 7]. In addition, the GLMP also includes a wide range of mathematical programming categories, such as linear multiplicative programming, quadratic programming, bilinear programming, and so on. Therefore, for these and various other reasons, GLMP has caught the attention of many experts, scholars, and engineering practitioners who have studied this theory and set off a new wave of global optimization learning. With the increasing dependence of practical problems on modeling optimization, local optimization theory and global optimization algorithms have made remarkable progress. However, compared with local optimization algorithm, the theory of global optimization algorithm is still quite insufficient. There are many methods to study this kind of problems, such as level set algorithm [8], heuristic algorithm [9, 10], branch and bound algorithm [11–13], outer approximation algorithm [14], parametric simplex algorithm [15], and so on, but these methods do not give the computational complexity of the algorithm. In addition, Depetrini and Locatelli [16] considered the problem of minimizing the product of two affine functions over a polyhedron set and proposed a polynomial time approximation algorithm. Locatelli [17] presented an approximate algorithm for solving more general types of global optimization problems and deduced the computational complexity of the algorithm, but the numerical results of the algorithm are lacking. Recently, Shen and Wang [18] also proposed a full polynomial time approximation algorithm for resolving the problem GLMP globally, but there is no acceleration technique. Moreover, for a more comprehensive overview of the GLMP, we encourage the readers to go through the more detailed literature [8, 19–21].In this paper, in order to solve the GLMP, two approximation algorithms are proposed, which is mainly by establishing a nonuniform grid; the process of solving the original problem is transformed into the process of solving a series of linear problems; it is proved that the proposed algorithm can obtain a globalε−approximation solution for GLMP. Besides, we put forward a two-stage acceleration technique to speed up Algorithm 1, which yields Algorithm 2. Then, by discussing the computational complexity of the algorithm, it is shown that the two algorithms are polynomial time approximation algorithms. Numerical experiments show that the performance of Algorithm 2 is obviously better than that of Algorithm 1, and the numerical results in Table 2 show that in solving problem 1-3, Algorithm 2 uses less CPU running time and iterations than [17, 18].Algorithm 1:Original algorithm.
(1)
Step 0 (initialization). Set ε∈0,1,δ=1+ε1/ρ,F=+∞, k=0. By using formulas (22) and (23), the ratio used for the two consecutive segments in each dimension is δ, which subdivides H into smaller rectangles. Represent the vertex of each small rectangle as ν=ν1,ν2,…,νp, which is stored in the set Bδ.(2)
Step 1. Select a point ν from the Bδ, solve the linear programming problem LPν, and let Bδ=Bδ\ν.(3)
Step 2. If the problem LPν is solvable, then Dν≠∅, and let gν=∏i=1pviαi; if gν<F, let F=gν, ν¯=ν, xν¯=xν; if Bδ≠∅, set k=k+1 and go to Step 1; otherwise, the algorithm terminates; letThe rest of this paper is organized as follows. In Section2, we first transform the problem GLMP into its equivalent optimization problem EOP and give its region-decomposition-linearization technique. Section 3 presents the global ε−approximation algorithm for problem GLMP and obtains the convergence for the proposed algorithm. In Section 4, we give the computational complexity for the proposed algorithm and carry out some numerical experiments in Section 5 to verify the feasibility and effectiveness of the algorithm. The concluding section is a simple summary.


## 2. Equivalence Problem and Its Linearization Technique

In this section, we will give the equivalent optimization problem EOP of the problem GLMP, then give the corresponding properties by studying the objective function of the EOP, and then explain the linearization technique of the equivalent problem.


### 2.1. Equivalent Problems and Their Properties

In order to solve the problem GLMP, the definition of globalϵ−approximation solution is given below.Definition 1.
Letx∗ be a global optimal solution to the problem GLMP at a given precision ε∈0,1. If x^∈X satisfies fx^≤1+εfx∗, x^ is referred to as the global approximation of the problem GLMP.
To obtain the globalε−approximation solution for GLMP, let fix=ciTx+di, li=minx∈Xfix.Theorem 1.
For eachi=1,2,…,p, let x˜i=argminx∈Xfix, Q=∪i=1px˜i, xˇ=argminx∈Qfx, U˜=fxˇ. Then, for each i∈1,2,…,p, let Mi=∏j=1,j≠ipljαj; then, fix∗≤ui with ui=U˜/Mi1/αi.Proof.
It is easy to know that for anyi∈1,2,…,p, there are li≤fix∗; thus,(2)∏j=1,j≠ipljαjfix∗αi≤∏i=1pfix∗αi=fx∗≤fxˇ=U˜.
Therefore,fix∗≤U˜/Mi1/αi=ui and then the conclusion holds.
Next, according to Theorem1, for each i=1,2,…,p, ui=U˜/Mi1/αi provide an upper bound for every fix∗.
On the basis of the above definition ofli and ui, define the rectangle H as follows.(3)H=l1,u1×l2,u2×⋯×lp,up.
Moreover, the rectangleH is also called the outer space of the GLMP. Thus, by introducing variable y=y1,y2,…,ypT∈H, the problem GLMP is equivalent to the following problem P1.(4)P1minhy=∏i=1pyiαi,s.t.fix≤yi,i=1,2,…,px∈X,y∈H.
Next, the equivalence of problems GLMP and P1 is explained by Theorem1.Theorem 2.
x∗ is a global optimal solution of problem GLMP if and only if x∗,y∗ is an optimal solution of problem P1 and yi∗=fix∗,i=1,2,…,p.Proof.
Letyi∗=fix∗,i=1,2,…,p if x∗ is a global optimal solution of the problem GLMP. Then, then it is obvious that x∗,y∗ is a feasible solution to P1. Suppose x∗,y∗ is not an optimal solution of P1; then, there is at least one feasible solution x¯,y¯ of P1, which makes(5)fx¯=∏i=1pfix¯αi≤∏i=1py¯iαi<∏i=1pyi∗αi=∏i=1pfix∗αi=fx∗,which contradicts the optimality of the x∗, so the hypothesis does not hold, and then x∗,y∗ is an optimal solution of P1.
Conversely, ifx∗,y∗ is an optimal solution for P1 and if there is a i∈1,2,…,p that makes fix∗<yi∗, let y˜i=fix∗, then x∗,y˜ is a feasible solution for P1 and(6)∏i=1py˜iαi<∏i=1pyi∗αi,which contradicts the optimality of x∗,y∗, so yi∗=fix∗,i=1,2,…,p. Suppose x∗ is not a global optimal solution of the problem GLMP; then, there must be a x¯∈X that makes fx¯<fx∗. Let y¯i=fix¯; obviously, x¯,y¯ is a feasible solution to P1, so we have(7)∏i=1py¯iαi=fx¯<fx∗=∏i=1pyi∗αi,which contradicts the optimality of x∗,y∗. Therefore, x∗ is the global optimal solution of the problem GLMP, which proves to be completed.
It is easy to understand from Theorem2 that the problems GLMP and P1 are equivalent and have the same global optimal value.
Then, for a giveny∈H, define the set(8)Dy=x∈X|fix≤yi,i=1,2,…,p,and function(9)gy=hy,Dy≠∅,+∞,Dy=∅.
Then, the problem P1 is equivalent to the following equivalent optimization problem.(10)EOPmingys.t.y∈H.Theorem 3.
y∗ is the global optimal solution of the problem EOP if and only if x∗,y∗ is the optimal solution of P1 and yi∗=fix∗,i=1,2,…,p.Proof.
Supposex∗,y∗ is an optimal solution of P1; then, according to Theorem 2, we can know yi∗=fix∗,i=1,2,…,p and y∗∈H. In addition, hy∗=gy∗=∏i=1pyi∗αi. Suppose that y∗ is not the global optimal solution of the problem EOP; there must be a y¯∈H such that gy¯<gy∗ and Dy¯≠∅; then, there must also be a x¯∈Dy¯ such that fix¯≤y¯i,i=1,2,…,p. Then, x¯,y¯ is a feasible solution of P1; there is hy¯=gy¯<gy∗=hy∗, which contradicts the optimality of x∗,y∗, so the hypothesis does not hold, so y∗ is the global optimal solution of the problem.
On the other hand, ify∗ is a global optimal solution of the problem EOP, then Dy∗≠∅, and there must be a x∗∈Dy∗ such that x∗,y∗ is a feasible solution of P1. Suppose x∗,y∗ is not the global optimal solution of the problem P1; then, there must be an optimal solution x¯,y¯ to the problem P1 such that hy¯<hy∗,y¯i=fix¯,i=1,2,…,p, so Dy¯≠∅ and gy¯=hy¯<hy∗=gy∗, which contradicts the fact that y∗ is the global optimal solution of the problem EOP. Therefore, x∗,y∗ is the global optimal solution of P1, and yi∗=fix∗,i=1,2,…,p can be obtained from Theorem 2 and then proved to be over.
Through Theorem3, the problems EOP and P1 have the same global optimal value, so combined with Theorem 2, the problems EOP and GLMP are also equivalent. Therefore, we can solve the equivalent problem EOP instead of addressing the problem GLMP.
Next, we consider the following linear programming problem:(11)LPymin∑i=1pαifixyis.t.x∈Dy.
IfDy≠∅, the optimal solution to the problem LPy is recorded as xy, and let y˜i=fixy, ρ=∑i=1pαi>0; then,(12)ρ=∑i=1pαiyiyi≥∑i=1pαifixyi,∀x∈Dy.
Furthermore, according to the Jensen inequality, we have(13)∑i=1pαifixyyi≥ρ∏i=1pfixyyiαi1/ρ=ρgy˜gy1/ρ,and then(14)ρ≥ρgy˜gy1/ρ,gy˜≤gy.Theorem 4.
Supposex∗∈X is a global optimal solution of the original problem GLMP; let yi∗=fix∗,i=1,2,…,p; then, y∗=y1∗,y2∗,…,yp∗T∈H and x∗ is also a global optimal solution of the problem LPy∗.Proof.
Firstly, according to Theorems2 and 3, we know that y∗ is a global optimal solution of the problem EOP. Then, by using formula (14) and the optimality of the global optimal solution y∗ of the EOP, we can see that x∗ is an optimal solution of the problem LPy∗.
Next, the properties of the functiongy over H are given by Theorem 5.Theorem 5.
For a given precisionε∈0,1, let δ=1+ε1/ρ; then, for any y¯∈H, there is(15)gy¯≤1+εgy,∀y∈y¯δ,y¯.In addition, ifDy¯≠∅, the optimal solution to the problem LPy¯ is recorded as x¯; then, let y˜i=fix¯i=1,2,…,p; there is also(16)gy˜≤gy¯≤1+εgy,∀y∈y¯δ,y¯.Proof.
For ally¯∈H, according to the definition of Dy and δ=1+ε1/ρ>1, one can know Dy¯/δ⊆Dy¯.
IfDy¯/δ≠∅, for any y∈y¯/δ,y¯, we have Dy≠∅; obviously, gy˜≤gy¯ and yi≥y¯i/δ for each i=1,2,…,p. Thus,(17)∏i=1py¯iδαi≤∏i=1pyiαi.
Moreover, according to the definition of functiongy, gy=∏i=1pyiαi; thus,(18)gy¯δ=∏i=1py¯iδαi=1δρ∏i=1py¯iαi=1δρgy¯.
And in combination with the formulas (17) and (18), we have(19)gy≥gy¯δ=1δρgy¯,∀y∈y¯δ,y¯.
Further, through formula (19) and combined with the definition of δ, we can understand that formula (16) is formed, and formula (15) is of course also true.
IfDy¯/δ=∅,Dy¯≠∅, it is clear that the inequality gy˜≤gy¯ is established.
For ally∈y¯/δ,y¯, if Dy≠∅, we have yi≥y¯i/δi=1,2,…,p, and y≠y¯/δ; then,(20)∏i=1py¯iδαi≤gy=∏i=1pyiαi.
Besides,(21)gy¯=∏i=1py¯iαi=δρ∏i=1py¯iδαi.
By using the definition ofδ and formulas (20) and (21), one can infer that formulas (15) and (16) hold.
IfDy=∅ and gy=+∞, then formulas (15) and (16) obviously hold.
IfDy¯=∅, the problem LPy¯ is not solved, and for any y∈y¯/δ,y¯, there is Dy=∅, then gy=+∞, so formula (15) is clearly established and the proof of the conclusion is completed.
Theorem5 shows that for any y¯∈H, we can determine whether the Dy¯ is not empty by solving the linear programming problem LPy¯ and then determine whether formula (16) holds.


### 2.2. Linearization Techniques

The objective function of the problem EOP is still nonconvex compared to the problem GLMP. But the spaceH in which the variable y of the objective function is located is p dimensions. Therefore, based on the above discussion, in order to solve the EOP, for a given ε∈0,1, we first split the outer space H on each dimension at a ratio of δ=1+ε1/ρ, thus producing several small rectangles.To do this, let(22)γi=argmaxσ∈ℕ|liδσ≤ui,i=1,2,…,p,where ℕ represents a non-negative integer set. Therefore, the number of these small rectangles is finite, and the set of all their vertices is(23)Bδ=ν1,ν2,…,νp|νi∈Piδ,i=1,2,…,p,where Piδ=li,liδ,…,liδγi. Obviously, for each y∈H, there must be a vertex ν1,ν2,…,νp∈Bδ making yi∈νi,δνi,i=1,2,…,p. Then, it can be concluded that the rectangle H can be approximated by the set Bδ.Next, by using the setBδ, the process of solving the problem EOP can be transformed into solving a series of subproblems. To this end, for each ν∈Bδ, we need to consider the value of the gν, that is, we need to determine whether the set Dν is not empty. According to Theorem 5, we can determine whether Dν is not empty by solving the linear programming problem LPν. Therefore, for each vertex ν∈Bδ, the following linear programming subproblem needs to be solved here, that is,(24)LPνmin∑i=1pαifixνis.t.fix≤νi,i=1,2,…,p,x∈X.On the basis of the conclusion of Theorem5, if the problem LPν can be solved (its solution is recorded as xν), then(25)ν˜=f1xν,f2xν,…,fpxνT∈H,and thus(26)gν˜≤gν≤1+εgy,∀y∈νδ,ν.


## 2.1. Equivalent Problems and Their Properties

In order to solve the problem GLMP, the definition of globalϵ−approximation solution is given below.Definition 1.
Letx∗ be a global optimal solution to the problem GLMP at a given precision ε∈0,1. If x^∈X satisfies fx^≤1+εfx∗, x^ is referred to as the global approximation of the problem GLMP.
To obtain the globalε−approximation solution for GLMP, let fix=ciTx+di, li=minx∈Xfix.Theorem 1.
For eachi=1,2,…,p, let x˜i=argminx∈Xfix, Q=∪i=1px˜i, xˇ=argminx∈Qfx, U˜=fxˇ. Then, for each i∈1,2,…,p, let Mi=∏j=1,j≠ipljαj; then, fix∗≤ui with ui=U˜/Mi1/αi.Proof.
It is easy to know that for anyi∈1,2,…,p, there are li≤fix∗; thus,(2)∏j=1,j≠ipljαjfix∗αi≤∏i=1pfix∗αi=fx∗≤fxˇ=U˜.
Therefore,fix∗≤U˜/Mi1/αi=ui and then the conclusion holds.
Next, according to Theorem1, for each i=1,2,…,p, ui=U˜/Mi1/αi provide an upper bound for every fix∗.
On the basis of the above definition ofli and ui, define the rectangle H as follows.(3)H=l1,u1×l2,u2×⋯×lp,up.
Moreover, the rectangleH is also called the outer space of the GLMP. Thus, by introducing variable y=y1,y2,…,ypT∈H, the problem GLMP is equivalent to the following problem P1.(4)P1minhy=∏i=1pyiαi,s.t.fix≤yi,i=1,2,…,px∈X,y∈H.
Next, the equivalence of problems GLMP and P1 is explained by Theorem1.Theorem 2.
x∗ is a global optimal solution of problem GLMP if and only if x∗,y∗ is an optimal solution of problem P1 and yi∗=fix∗,i=1,2,…,p.Proof.
Letyi∗=fix∗,i=1,2,…,p if x∗ is a global optimal solution of the problem GLMP. Then, then it is obvious that x∗,y∗ is a feasible solution to P1. Suppose x∗,y∗ is not an optimal solution of P1; then, there is at least one feasible solution x¯,y¯ of P1, which makes(5)fx¯=∏i=1pfix¯αi≤∏i=1py¯iαi<∏i=1pyi∗αi=∏i=1pfix∗αi=fx∗,which contradicts the optimality of the x∗, so the hypothesis does not hold, and then x∗,y∗ is an optimal solution of P1.
Conversely, ifx∗,y∗ is an optimal solution for P1 and if there is a i∈1,2,…,p that makes fix∗<yi∗, let y˜i=fix∗, then x∗,y˜ is a feasible solution for P1 and(6)∏i=1py˜iαi<∏i=1pyi∗αi,which contradicts the optimality of x∗,y∗, so yi∗=fix∗,i=1,2,…,p. Suppose x∗ is not a global optimal solution of the problem GLMP; then, there must be a x¯∈X that makes fx¯<fx∗. Let y¯i=fix¯; obviously, x¯,y¯ is a feasible solution to P1, so we have(7)∏i=1py¯iαi=fx¯<fx∗=∏i=1pyi∗αi,which contradicts the optimality of x∗,y∗. Therefore, x∗ is the global optimal solution of the problem GLMP, which proves to be completed.
It is easy to understand from Theorem2 that the problems GLMP and P1 are equivalent and have the same global optimal value.
Then, for a giveny∈H, define the set(8)Dy=x∈X|fix≤yi,i=1,2,…,p,and function(9)gy=hy,Dy≠∅,+∞,Dy=∅.
Then, the problem P1 is equivalent to the following equivalent optimization problem.(10)EOPmingys.t.y∈H.Theorem 3.
y∗ is the global optimal solution of the problem EOP if and only if x∗,y∗ is the optimal solution of P1 and yi∗=fix∗,i=1,2,…,p.Proof.
Supposex∗,y∗ is an optimal solution of P1; then, according to Theorem 2, we can know yi∗=fix∗,i=1,2,…,p and y∗∈H. In addition, hy∗=gy∗=∏i=1pyi∗αi. Suppose that y∗ is not the global optimal solution of the problem EOP; there must be a y¯∈H such that gy¯<gy∗ and Dy¯≠∅; then, there must also be a x¯∈Dy¯ such that fix¯≤y¯i,i=1,2,…,p. Then, x¯,y¯ is a feasible solution of P1; there is hy¯=gy¯<gy∗=hy∗, which contradicts the optimality of x∗,y∗, so the hypothesis does not hold, so y∗ is the global optimal solution of the problem.
On the other hand, ify∗ is a global optimal solution of the problem EOP, then Dy∗≠∅, and there must be a x∗∈Dy∗ such that x∗,y∗ is a feasible solution of P1. Suppose x∗,y∗ is not the global optimal solution of the problem P1; then, there must be an optimal solution x¯,y¯ to the problem P1 such that hy¯<hy∗,y¯i=fix¯,i=1,2,…,p, so Dy¯≠∅ and gy¯=hy¯<hy∗=gy∗, which contradicts the fact that y∗ is the global optimal solution of the problem EOP. Therefore, x∗,y∗ is the global optimal solution of P1, and yi∗=fix∗,i=1,2,…,p can be obtained from Theorem 2 and then proved to be over.
Through Theorem3, the problems EOP and P1 have the same global optimal value, so combined with Theorem 2, the problems EOP and GLMP are also equivalent. Therefore, we can solve the equivalent problem EOP instead of addressing the problem GLMP.
Next, we consider the following linear programming problem:(11)LPymin∑i=1pαifixyis.t.x∈Dy.
IfDy≠∅, the optimal solution to the problem LPy is recorded as xy, and let y˜i=fixy, ρ=∑i=1pαi>0; then,(12)ρ=∑i=1pαiyiyi≥∑i=1pαifixyi,∀x∈Dy.
Furthermore, according to the Jensen inequality, we have(13)∑i=1pαifixyyi≥ρ∏i=1pfixyyiαi1/ρ=ρgy˜gy1/ρ,and then(14)ρ≥ρgy˜gy1/ρ,gy˜≤gy.Theorem 4.
Supposex∗∈X is a global optimal solution of the original problem GLMP; let yi∗=fix∗,i=1,2,…,p; then, y∗=y1∗,y2∗,…,yp∗T∈H and x∗ is also a global optimal solution of the problem LPy∗.Proof.
Firstly, according to Theorems2 and 3, we know that y∗ is a global optimal solution of the problem EOP. Then, by using formula (14) and the optimality of the global optimal solution y∗ of the EOP, we can see that x∗ is an optimal solution of the problem LPy∗.
Next, the properties of the functiongy over H are given by Theorem 5.Theorem 5.
For a given precisionε∈0,1, let δ=1+ε1/ρ; then, for any y¯∈H, there is(15)gy¯≤1+εgy,∀y∈y¯δ,y¯.In addition, ifDy¯≠∅, the optimal solution to the problem LPy¯ is recorded as x¯; then, let y˜i=fix¯i=1,2,…,p; there is also(16)gy˜≤gy¯≤1+εgy,∀y∈y¯δ,y¯.Proof.
For ally¯∈H, according to the definition of Dy and δ=1+ε1/ρ>1, one can know Dy¯/δ⊆Dy¯.
IfDy¯/δ≠∅, for any y∈y¯/δ,y¯, we have Dy≠∅; obviously, gy˜≤gy¯ and yi≥y¯i/δ for each i=1,2,…,p. Thus,(17)∏i=1py¯iδαi≤∏i=1pyiαi.
Moreover, according to the definition of functiongy, gy=∏i=1pyiαi; thus,(18)gy¯δ=∏i=1py¯iδαi=1δρ∏i=1py¯iαi=1δρgy¯.
And in combination with the formulas (17) and (18), we have(19)gy≥gy¯δ=1δρgy¯,∀y∈y¯δ,y¯.
Further, through formula (19) and combined with the definition of δ, we can understand that formula (16) is formed, and formula (15) is of course also true.
IfDy¯/δ=∅,Dy¯≠∅, it is clear that the inequality gy˜≤gy¯ is established.
For ally∈y¯/δ,y¯, if Dy≠∅, we have yi≥y¯i/δi=1,2,…,p, and y≠y¯/δ; then,(20)∏i=1py¯iδαi≤gy=∏i=1pyiαi.
Besides,(21)gy¯=∏i=1py¯iαi=δρ∏i=1py¯iδαi.
By using the definition ofδ and formulas (20) and (21), one can infer that formulas (15) and (16) hold.
IfDy=∅ and gy=+∞, then formulas (15) and (16) obviously hold.
IfDy¯=∅, the problem LPy¯ is not solved, and for any y∈y¯/δ,y¯, there is Dy=∅, then gy=+∞, so formula (15) is clearly established and the proof of the conclusion is completed.
Theorem5 shows that for any y¯∈H, we can determine whether the Dy¯ is not empty by solving the linear programming problem LPy¯ and then determine whether formula (16) holds.


## 2.2. Linearization Techniques

The objective function of the problem EOP is still nonconvex compared to the problem GLMP. But the spaceH in which the variable y of the objective function is located is p dimensions. Therefore, based on the above discussion, in order to solve the EOP, for a given ε∈0,1, we first split the outer space H on each dimension at a ratio of δ=1+ε1/ρ, thus producing several small rectangles.To do this, let(22)γi=argmaxσ∈ℕ|liδσ≤ui,i=1,2,…,p,where ℕ represents a non-negative integer set. Therefore, the number of these small rectangles is finite, and the set of all their vertices is(23)Bδ=ν1,ν2,…,νp|νi∈Piδ,i=1,2,…,p,where Piδ=li,liδ,…,liδγi. Obviously, for each y∈H, there must be a vertex ν1,ν2,…,νp∈Bδ making yi∈νi,δνi,i=1,2,…,p. Then, it can be concluded that the rectangle H can be approximated by the set Bδ.Next, by using the setBδ, the process of solving the problem EOP can be transformed into solving a series of subproblems. To this end, for each ν∈Bδ, we need to consider the value of the gν, that is, we need to determine whether the set Dν is not empty. According to Theorem 5, we can determine whether Dν is not empty by solving the linear programming problem LPν. Therefore, for each vertex ν∈Bδ, the following linear programming subproblem needs to be solved here, that is,(24)LPνmin∑i=1pαifixνis.t.fix≤νi,i=1,2,…,p,x∈X.On the basis of the conclusion of Theorem5, if the problem LPν can be solved (its solution is recorded as xν), then(25)ν˜=f1xν,f2xν,…,fpxνT∈H,and thus(26)gν˜≤gν≤1+εgy,∀y∈νδ,ν.


## 3. Analysis of Algorithm and Its Computational Complexity

This section brings an approximate algorithm based on linearization-decomposition to solve the problem EOP. After that, the analysis of its computational complexity is proved accordingly.


### 3.1. Approximate Algorithm

To solve the EOP, we subdivide the external spaceH into a finite number of small rectangles with ratio δ and put all the vertices of these small rectangles into the set Bδ.Then, for each vertexν∈Bδ, by solving the linear programming problem LPν, if LPν is feasible and has an optimal solution xν, then Dν≠∅, and we can obtain a feasible solution ν˜ (formula (25)) of the EOP according to xν, which makes(27)gν˜≤gν≤1+εgy,∀y∈νδ,ν.If there is aν˜ that satisfies gν˜≤1+εgy∗, then(28)fxν=∏i=1pfixναi=∏i=1pν˜iαi=gν˜≤1+εgy∗=1+εfx∗,and thus xν is a global ε−approximation solution of the problem GLMP. The specific algorithm steps are as follows.(1)
Step 0 (initialization). Set ε∈0,1,δ=1+ε1/ρ,F=+∞, k=0. By using formulas (22) and (23), the ratio used for the two consecutive segments in each dimension is δ, which subdivides H into smaller rectangles. Represent the vertex of each small rectangle as ν=ν1,ν2,…,νp, which is stored in the set Bδ.(2)
Step 1. Select a point ν from the Bδ, solve the linear programming problem LPν, and let Bδ=Bδ\ν.(3)
Step 2. If the problem LPν is solvable, then Dν≠∅, and let gν=∏i=1pviαi; if gν<F, let F=gν, ν¯=ν, xν¯=xν; if Bδ≠∅, set k=k+1 and go to Step 1; otherwise, the algorithm terminates; let(29)ν˜i=fixν¯,i=1,2,…,p,ν˜=ν˜1,ν˜2,…,ν˜pT,and then xν¯, ν˜ is a global ε−approximation solution to problems GLMP and EOP, respectively.Theorem 6.
For a given precisionε∈0,1, let δ=1+ε1/ρ, ν¯=argmingν|ν∈Bδ, and xν¯ be an optimal solution of the linear programming problem LPν¯. Then, Algorithm 1 will get a global ε−approximation solution xν¯ for problem GLMP, i.e.,(30)fxν¯≤1+εfx∗,where x∗ is the global optimal solution to the original problem GLMP.Proof.
Let(31)yi∗=fix∗,i=1,2,…,p.
According to Theorem1, we have(32)li≤yi∗≤ui,i=1,2,…,p.
Then, formula (32) implies that y∗=y1∗,y2∗,…,yp∗T∈H, so there must be a ν∗∈Bδ which makes(33)νi∗δ≤yi∗≤νi∗,i=1,2,…,p.
So, using Theorem5 on the small rectangle ν∗/δ,ν∗, there will be(34)fx∗=∏i=1pyi∗αi=gy∗≥∏i=1pνi∗δαi=1δΣi=1pαi∏i=1pνi∗αi=1δρgν∗.
Thus,(35)δρfx∗=δρgy∗≥gν∗.
Noting thatν¯=argmingν|ν∈Bδ, we can know(36)gν∗≥gν¯.
Sincexν¯ is the optimal solution to the linear programming problem LPν¯, let(37)ν˜i=fixν¯,i=1,2,…,p.
Apparently,ν˜=ν˜1,ν˜2,…,ν˜p∈H. So, by taking advantage of the formula (16) in Theorem 5, we have(38)gν¯≥gν˜=∏i=1pν˜iαi=∏i=1pfixν¯αi=fxν¯.
Therefore, by integrating formulas (35) and (38) and combining the δ=1+ε1/ρ, we can obtain(39)fxν¯≤1+εfx∗,and this proof is completed.Remark 1.
According to Theorem6, if y∗∈Bδ, then from Theorem 5, the optimal solution xy∗ of the linear programming problem LPy∗ is exactly the global optimal solution of the original problem GLMP.
Through Theorem6, we can see that for a given precision ε∈0,1, Algorithm 1 will obtain a global ε−approximation solution to the problem GLMP. Moreover, Remark 1 also shows that if y∗∈Bδ, then Algorithm 1 will find a global optimal solution of the problem GLMP exactly.


### 3.2. Accelerating Techniques

Algorithm1 shows that, for any ν∈Bδ, it is required to solve the linear programming problem LPν, in order to verify that the Dν is nonempty. Hence, the computational cost of Algorithm 1 depends on the number of points within the set Bδ, respectively. Then, the proposal of the acceleration technique will discard some points that are not necessary to consider the set Bδ and only consider the region that contains the global optimal solution of the problem EOP. The detailed process is given below.Ifν¯ is the best known solution to the problem EOP, xν¯ is the optimal solution to the linear programming problem LPν¯; for each i=1,2,…,p, let ν˜i=fixν¯,ν˜=ν˜1,ν˜2,…,ν˜pT; obviously gν˜≤gν¯; then, ν˜ may be a better solution than ν¯. Well, using ν˜ may be able to remove more vertices from Bδ that do not need to be explored. To give the acceleration technique for Algorithm 1, we first need to specify a necessary condition that the points in each subrectangle Hk⊆H0=Hk≥1 containing the global optimal solution of the problem EOP must be satisfied, that is,(40)∏i=1pliαi≤gy∗≤gy≤gν˜,∀y∈Hk,where Hk=l,uk, uk=u1k,u2k,…,upkT, uik≤uik−1≤ui, i=1,2,…,p. Similarly, if δ=1+ε1/ρ are used to segment rectangles Hk on each dimension, this will produce a limited number of small rectangles. For this purpose, let(41)γik=argmaxσ∈ℕ|liδσ≤uik,i=1,2,…,p.Then, a set of vertices of a finite number of small rectangles will also be generated on a rectangularHk, that is,(42)Bkδ=ν1,ν2,…,νp|νi∈Pkiδ,i=1,2,…,p,where Pkiδ=li,liδ,…,liδγik. Clearly, Bkδ⊆B0δ=Bδ and Bkδ⊂Hk⊆H0=H.Based on the above discussion, we will give Propositions1 and 2 to clarify the acceleration techniques of the algorithm.Proposition 1.
The global optimal solution of the problem EOP cannot be obtained on the setB¯kiδ if a i∈1,2,…,p makes gν˜/Mi1/αi<liδγik, of which(43)B¯kiδ=ν∈Bkδ|gν˜Mi1/αi<νi,i∈1,2,…,p.Proof.
Ifν∈B¯kiδ, then there must be gν˜/Mi1/αi<νi≤liδγik, and thus there is(44)gν˜=gν˜Mi1/αiαiMi<νiαiMi=νiαi∏j=1,j≠ipljαj≤∏j=1pνjαj=gν,which contradicts the inequality chain (40), so the conclusion is valid.
With Proposition1, we generate a new rectangle Hk+1 and vertex set Bk+1δ, i.e., for each i=1,2,…,p, let(45)uik+1=gν˜Mi1/αi,gν˜Mi1/αi<liδγik,uik,gν˜Mi1/αi≥liδγik,as well as(46)γik+1=argmaxσ∈ℕ|liδσ≤uik+1,gν˜Mi1/αi<liδγik,γik,gν˜Mi1/αi≥liδγik.
Well,uk+1=l,uk+1 with uk+1=u1k+1,u2k+1,…,upk+1.
Moreover, the above rules may produce a small rectangular vertex setBk+1δ with relatively few new elements, but there is still ν˜∈Bk+1δ, so we then give Proposition 2 to delete the other unconsidered elements in Bk+1δ.Proposition 2.
Ifν¯ is the best known solution to the problem EOP, xν¯ is the optimal solution to the linear programming problem LPν¯; for each i=1,2,…,p, let ν˜i=fixν¯,ν˜=ν˜1,ν˜2,…,ν˜pT, and define the set(47)B¯k+1δ=ν∈Bk+1δ|ν˜i≤νi,i=1,2,…,p.Then, for anyν∈B¯k+1δ, the EOP cannot get a better solution than ν˜.Proof.
Sincexν¯ is the optimal solution to a linear programming problem LPν¯, then there is at least one point xν¯ in the set Dν˜, so Dν˜≠∅. For arbitrary ν∈B¯k+1δ, obviously Dν˜⊆Dν, and thus Dν≠∅. According to the definition of the function gy, for each ν∈B¯k+1δ, the objective function value of the EOP meets(48)gν=∏i=1pνiαi≥∏i=1pν˜iαi=gν˜,and this conclusion is proved.
Next, for a givenε∈0,1, δ=1+ε1/ρ, make use of Proposition 2; let(49)τik+1=argminσ∈ℕ|ν˜i≤liδσ≤uik+1.
Through the expression ofγik+1 in (46), the set B¯k+1δ is defined as follows.(50)B¯k+1δ=liδσ1,liδσ2,…,liδσp|σi∈τik+1,τik+1+1,…,γik+1,i=1,2,…,p.
Therefore, for the convenience of narration, letSk+1δ=Bk+1δ∖B¯k+1δ. This means that in order to obtain a global ε−approximation solution for problem EOP, it is only necessary to calculate up to Sk+1δ linear programming subproblems LPν to determine whether the Dν is not empty, which determines the function value gν at each vertex ν∈Sk+1δ. Then, by using the set Sk+1δ, the computational efficiency of Algorithm 1 will be improved, leading to the following algorithm.
(51)ν˜i=fixν¯,i=1,2,…,p,ν˜=ν˜1,ν˜2,…,ν˜pT,and then xν¯, ν˜ is a global ε−approximation solution to the problems GLMP and EOP, respectively.
Note that the Algorithm2 simply removes the set of vertices that do not contain a global optimal solution; therefore, it is similar to Theorem 6; Algorithm 2 will also return a global ε−approximation solution of the problem GLMP and EOP as well.Algorithm 2:Improved algorithm.
(1)
Step 0 (initialization). Set ε∈0,1,δ=1+ε1/ρ. By using formulas (22) and (23), H0=H is subdivided into smaller rectangles, such that the ratio of two consecutive segments is δ in each dimension. Represent the vertex of each small rectangle as ν=ν1,ν2,…,νp, which is stored in the set Bδ. Let F=+∞, T=∅, B0δ=Bδ, Ξ0=B0δ, k=0.(2)
Step 1. Select a point ν=ν1,ν2,…,νpT from the Ξk, solve the linear programming problem LPν, and let T=T∪ν.(3)
Step 2. If the problem LPν is solvable, then Dν≠∅, and let gν=∏i=1pνiαi; if gν<F, let ν¯=ν, xν¯=xν, ν˜=ν˜1,ν˜2,…,ν˜pT=f1xν¯,f2xν¯,…,fpxν¯T, F=gν˜. Use rules (45) and (46) to produce Hk+1 and Bk+1δ and use formulas (49) and (50) to obtain set B¯k+1δ; let Sk+1δ=Bk+1δ∖B¯k+1δ, Ξk=Sk+1δ∖T. If Ξk≠∅, set k=k+1 and go to Step 1; otherwise, the algorithm terminates; let


## 3.1. Approximate Algorithm

To solve the EOP, we subdivide the external spaceH into a finite number of small rectangles with ratio δ and put all the vertices of these small rectangles into the set Bδ.Then, for each vertexν∈Bδ, by solving the linear programming problem LPν, if LPν is feasible and has an optimal solution xν, then Dν≠∅, and we can obtain a feasible solution ν˜ (formula (25)) of the EOP according to xν, which makes(27)gν˜≤gν≤1+εgy,∀y∈νδ,ν.If there is aν˜ that satisfies gν˜≤1+εgy∗, then(28)fxν=∏i=1pfixναi=∏i=1pν˜iαi=gν˜≤1+εgy∗=1+εfx∗,and thus xν is a global ε−approximation solution of the problem GLMP. The specific algorithm steps are as follows.(1)
Step 0 (initialization). Set ε∈0,1,δ=1+ε1/ρ,F=+∞, k=0. By using formulas (22) and (23), the ratio used for the two consecutive segments in each dimension is δ, which subdivides H into smaller rectangles. Represent the vertex of each small rectangle as ν=ν1,ν2,…,νp, which is stored in the set Bδ.(2)
Step 1. Select a point ν from the Bδ, solve the linear programming problem LPν, and let Bδ=Bδ\ν.(3)
Step 2. If the problem LPν is solvable, then Dν≠∅, and let gν=∏i=1pviαi; if gν<F, let F=gν, ν¯=ν, xν¯=xν; if Bδ≠∅, set k=k+1 and go to Step 1; otherwise, the algorithm terminates; let(29)ν˜i=fixν¯,i=1,2,…,p,ν˜=ν˜1,ν˜2,…,ν˜pT,and then xν¯, ν˜ is a global ε−approximation solution to problems GLMP and EOP, respectively.Theorem 6.
For a given precisionε∈0,1, let δ=1+ε1/ρ, ν¯=argmingν|ν∈Bδ, and xν¯ be an optimal solution of the linear programming problem LPν¯. Then, Algorithm 1 will get a global ε−approximation solution xν¯ for problem GLMP, i.e.,(30)fxν¯≤1+εfx∗,where x∗ is the global optimal solution to the original problem GLMP.Proof.
Let(31)yi∗=fix∗,i=1,2,…,p.
According to Theorem1, we have(32)li≤yi∗≤ui,i=1,2,…,p.
Then, formula (32) implies that y∗=y1∗,y2∗,…,yp∗T∈H, so there must be a ν∗∈Bδ which makes(33)νi∗δ≤yi∗≤νi∗,i=1,2,…,p.
So, using Theorem5 on the small rectangle ν∗/δ,ν∗, there will be(34)fx∗=∏i=1pyi∗αi=gy∗≥∏i=1pνi∗δαi=1δΣi=1pαi∏i=1pνi∗αi=1δρgν∗.
Thus,(35)δρfx∗=δρgy∗≥gν∗.
Noting thatν¯=argmingν|ν∈Bδ, we can know(36)gν∗≥gν¯.
Sincexν¯ is the optimal solution to the linear programming problem LPν¯, let(37)ν˜i=fixν¯,i=1,2,…,p.
Apparently,ν˜=ν˜1,ν˜2,…,ν˜p∈H. So, by taking advantage of the formula (16) in Theorem 5, we have(38)gν¯≥gν˜=∏i=1pν˜iαi=∏i=1pfixν¯αi=fxν¯.
Therefore, by integrating formulas (35) and (38) and combining the δ=1+ε1/ρ, we can obtain(39)fxν¯≤1+εfx∗,and this proof is completed.Remark 1.
According to Theorem6, if y∗∈Bδ, then from Theorem 5, the optimal solution xy∗ of the linear programming problem LPy∗ is exactly the global optimal solution of the original problem GLMP.
Through Theorem6, we can see that for a given precision ε∈0,1, Algorithm 1 will obtain a global ε−approximation solution to the problem GLMP. Moreover, Remark 1 also shows that if y∗∈Bδ, then Algorithm 1 will find a global optimal solution of the problem GLMP exactly.


## 3.2. Accelerating Techniques

Algorithm1 shows that, for any ν∈Bδ, it is required to solve the linear programming problem LPν, in order to verify that the Dν is nonempty. Hence, the computational cost of Algorithm 1 depends on the number of points within the set Bδ, respectively. Then, the proposal of the acceleration technique will discard some points that are not necessary to consider the set Bδ and only consider the region that contains the global optimal solution of the problem EOP. The detailed process is given below.Ifν¯ is the best known solution to the problem EOP, xν¯ is the optimal solution to the linear programming problem LPν¯; for each i=1,2,…,p, let ν˜i=fixν¯,ν˜=ν˜1,ν˜2,…,ν˜pT; obviously gν˜≤gν¯; then, ν˜ may be a better solution than ν¯. Well, using ν˜ may be able to remove more vertices from Bδ that do not need to be explored. To give the acceleration technique for Algorithm 1, we first need to specify a necessary condition that the points in each subrectangle Hk⊆H0=Hk≥1 containing the global optimal solution of the problem EOP must be satisfied, that is,(40)∏i=1pliαi≤gy∗≤gy≤gν˜,∀y∈Hk,where Hk=l,uk, uk=u1k,u2k,…,upkT, uik≤uik−1≤ui, i=1,2,…,p. Similarly, if δ=1+ε1/ρ are used to segment rectangles Hk on each dimension, this will produce a limited number of small rectangles. For this purpose, let(41)γik=argmaxσ∈ℕ|liδσ≤uik,i=1,2,…,p.Then, a set of vertices of a finite number of small rectangles will also be generated on a rectangularHk, that is,(42)Bkδ=ν1,ν2,…,νp|νi∈Pkiδ,i=1,2,…,p,where Pkiδ=li,liδ,…,liδγik. Clearly, Bkδ⊆B0δ=Bδ and Bkδ⊂Hk⊆H0=H.Based on the above discussion, we will give Propositions1 and 2 to clarify the acceleration techniques of the algorithm.Proposition 1.
The global optimal solution of the problem EOP cannot be obtained on the setB¯kiδ if a i∈1,2,…,p makes gν˜/Mi1/αi<liδγik, of which(43)B¯kiδ=ν∈Bkδ|gν˜Mi1/αi<νi,i∈1,2,…,p.Proof.
Ifν∈B¯kiδ, then there must be gν˜/Mi1/αi<νi≤liδγik, and thus there is(44)gν˜=gν˜Mi1/αiαiMi<νiαiMi=νiαi∏j=1,j≠ipljαj≤∏j=1pνjαj=gν,which contradicts the inequality chain (40), so the conclusion is valid.
With Proposition1, we generate a new rectangle Hk+1 and vertex set Bk+1δ, i.e., for each i=1,2,…,p, let(45)uik+1=gν˜Mi1/αi,gν˜Mi1/αi<liδγik,uik,gν˜Mi1/αi≥liδγik,as well as(46)γik+1=argmaxσ∈ℕ|liδσ≤uik+1,gν˜Mi1/αi<liδγik,γik,gν˜Mi1/αi≥liδγik.
Well,uk+1=l,uk+1 with uk+1=u1k+1,u2k+1,…,upk+1.
Moreover, the above rules may produce a small rectangular vertex setBk+1δ with relatively few new elements, but there is still ν˜∈Bk+1δ, so we then give Proposition 2 to delete the other unconsidered elements in Bk+1δ.Proposition 2.
Ifν¯ is the best known solution to the problem EOP, xν¯ is the optimal solution to the linear programming problem LPν¯; for each i=1,2,…,p, let ν˜i=fixν¯,ν˜=ν˜1,ν˜2,…,ν˜pT, and define the set(47)B¯k+1δ=ν∈Bk+1δ|ν˜i≤νi,i=1,2,…,p.Then, for anyν∈B¯k+1δ, the EOP cannot get a better solution than ν˜.Proof.
Sincexν¯ is the optimal solution to a linear programming problem LPν¯, then there is at least one point xν¯ in the set Dν˜, so Dν˜≠∅. For arbitrary ν∈B¯k+1δ, obviously Dν˜⊆Dν, and thus Dν≠∅. According to the definition of the function gy, for each ν∈B¯k+1δ, the objective function value of the EOP meets(48)gν=∏i=1pνiαi≥∏i=1pν˜iαi=gν˜,and this conclusion is proved.
Next, for a givenε∈0,1, δ=1+ε1/ρ, make use of Proposition 2; let(49)τik+1=argminσ∈ℕ|ν˜i≤liδσ≤uik+1.
Through the expression ofγik+1 in (46), the set B¯k+1δ is defined as follows.(50)B¯k+1δ=liδσ1,liδσ2,…,liδσp|σi∈τik+1,τik+1+1,…,γik+1,i=1,2,…,p.
Therefore, for the convenience of narration, letSk+1δ=Bk+1δ∖B¯k+1δ. This means that in order to obtain a global ε−approximation solution for problem EOP, it is only necessary to calculate up to Sk+1δ linear programming subproblems LPν to determine whether the Dν is not empty, which determines the function value gν at each vertex ν∈Sk+1δ. Then, by using the set Sk+1δ, the computational efficiency of Algorithm 1 will be improved, leading to the following algorithm.
(51)ν˜i=fixν¯,i=1,2,…,p,ν˜=ν˜1,ν˜2,…,ν˜pT,and then xν¯, ν˜ is a global ε−approximation solution to the problems GLMP and EOP, respectively.
Note that the Algorithm2 simply removes the set of vertices that do not contain a global optimal solution; therefore, it is similar to Theorem 6; Algorithm 2 will also return a global ε−approximation solution of the problem GLMP and EOP as well.Algorithm 2:Improved algorithm.
(1)
Step 0 (initialization). Set ε∈0,1,δ=1+ε1/ρ. By using formulas (22) and (23), H0=H is subdivided into smaller rectangles, such that the ratio of two consecutive segments is δ in each dimension. Represent the vertex of each small rectangle as ν=ν1,ν2,…,νp, which is stored in the set Bδ. Let F=+∞, T=∅, B0δ=Bδ, Ξ0=B0δ, k=0.(2)
Step 1. Select a point ν=ν1,ν2,…,νpT from the Ξk, solve the linear programming problem LPν, and let T=T∪ν.(3)
Step 2. If the problem LPν is solvable, then Dν≠∅, and let gν=∏i=1pνiαi; if gν<F, let ν¯=ν, xν¯=xν, ν˜=ν˜1,ν˜2,…,ν˜pT=f1xν¯,f2xν¯,…,fpxν¯T, F=gν˜. Use rules (45) and (46) to produce Hk+1 and Bk+1δ and use formulas (49) and (50) to obtain set B¯k+1δ; let Sk+1δ=Bk+1δ∖B¯k+1δ, Ξk=Sk+1δ∖T. If Ξk≠∅, set k=k+1 and go to Step 1; otherwise, the algorithm terminates; let


## 4. Analysis of Computational Complexity of the Algorithm

We first give Lemma1 to discuss the computational complexity of the two algorithms.Lemma 1.
(see [22]). Let λ be the maximum of the absolute values of all the elements A,b,ci,di in problem GLMP; then, each component xj0 of any pole x0 of X can be expressed as xj0=pj/q, where 0≤pj≤nλn, 0<q≤nλn, j=1,2,…,n.Because for eachi=1,2,…,p, the solution x˜i to the linear programming problem li=minx∈Xfix is the pole of X, by Lemma 1, we have x˜ji=pji/qi, where 0≤pji≤nλn, 0<qi≤nλn, j=1,2,…,n. Thus, li=∑j=1ncijpji/qi+di,i=1,2,…,p. Moreover, let(52)q˜=max1qi|i=1,2,…,p,ω=minli|i=1,2,…,p,(53)U˜=fxˇ=min1≤i≤pfx˜i,and for the sake of the following smooth description of Theorem 7, here xˇ is defined in Theorem 1.Theorem 7.
For a givenp≥2, in order to obtain a global ε−approximation solution to the problem GLMP, the upper limit of the time required for the proposed Algorithm 1 is(54)O2α˜ρ2εn+1lnnλ−lnω+1p⋅Tm+p,n,where α˜=max1/αi|i=1,2,…,p, ρ=∑i=1pαi, and Tm+p,n represents the upper limit of the time used to solve a linear programming problem with m+p linear constraints and n variables at a time.Proof.
From the formulas (22) and (23), we can see that the maximum number of midpoint of the set Bδ is(55)∏i=1plogδuili+1.
Using the definition ofq˜,ω in formula (52) and Lemma 1, we have(56)ω≤li≤q˜nλnλn+λ≤2q˜nλn+1,i=1,2,…,p.
Furthermore, we also have(57)U˜=∏i=1pciTxˇ+diαi≤∏i=1p2q˜nλn+1αi=2q˜nλn+1∑i=1pαi,by using formula (53) and the above inequality (56). Of course, according to the definition of Mi and ui in Theorem 1, and in conjunction with ρ=∑i=1pαi, there will be(58)ui=U^Mi1/αi≤2q˜nλn+12q˜nλn+1ωρ/αi−1.
By means of above formulas (56) and (58), we can have(59)uili≤2q˜nλn+1ωρ/αi,and thus(60)lnuili≤ραiln2q˜+n+1lnnλ−lnω≤ρα˜ln2q˜+n+1lnnλ−lnω.
Usingε∈0,1,δ=1+ε1/ρ in Algorithm 1 and ε/2<ln1+ε<ε, then there will be(61)logδuili=ρlog1+εuili=ρlnui/liln1+ε<2ρlnui/liε.
Then, by using the above formulas (55), (60), and (61), the upper limit of the number (expressed in Bδ) of interior points of Bδ is(62)Bδ≤2α˜ρ2εln2q˜+n+1lnnλ−lnω+1p,in the utilized formula (55), (60), (61). From the above formula (62), we can see that the running time of Algorithm 1 is at most(63)O2α˜ρ2εn+1lnnλ−lnω+1p⋅Tm+p,n,when the global ε−approximation solution is obtained, and then the proof of the conclusion is completed.Remark 2.
Propositions1 and 2 show that we can accelerate Algorithm 1 by removing the vertices of the small rectangle that needs not be considered, which leads to Algorithm 2 that is more resource-efficient than Algorithm 1; in other words, Algorithm 2 is an improvement on Algorithm 1. Then, the upper bound of the CPU running time required by Algorithm 2 is the same as that of Algorithm 1 in the most extreme cases (where acceleration techniques always fail). Therefore, Algorithm 2 is likewise a polynomial time approximation algorithm.


## 5. Numerical Experiments

This section will test the performance of the algorithm through several test problems. All of our testing procedures were performed via MATLAB (2012a) on computers with Intel(R) Core(TM)i5-2320, 3.00 GHz power processor, 4.00 GB memory, and Microsoft Win7 operating system.Problem 1.
(see [17, 18])(64)min0.813396x1+0.67440x2+0.305038x3+0.129742x4+0.217796×0.224508x1+0.063458x2+0.932230x3+0.528736x4+0.091947s.t.0.488509x1+0.063565x2+0.945686x3+0.210704x4≤3.562809,−0.324014x1−0.501754x2−0.719204x3+0.099562x4≤−0.052215,0.445225x1−0.346896x2+0.637939x3−0.257623x4≤0.427920,−0.202821x1+0.647361x2+0.920135x3−0.983091x4≤0.840950,−0.886420x1−0.802444x2−0.305441x3−0.180123x4≤−1.353686,−0.515399x1−0.424820x2+0.897498x3+0.187268x4≤2.137251,−0.591515x1+0.060581x2−0.427365x3+0.579388x4≤−0.290987,0.423524x1+0.940496x2−0.437944x3−0.742941x4≤0.373620,x1≥0,x2≥0,x3≥0,x4≥0.Problem 2.
(see [17, 18])(65)min3x1−2x2−22/3x1+2x2+22/5s.t.2x1−x2≥2,x1−2x2≤2,x1+x2≤5,3≤x1≤5,1≤x2≤3.Problem 3.
(see [8, 17, 18])(66)minx1+x2+12.52x1+x2+11.1x1+2x2+11.9s.t.x1+2x2≤6,2x1+x2≤8,1≤x1≤3,1≤x2≤3.Problem 4.
(see [20])(67)minx1+x2x1−x2+7s.t.2x1+x2≤14,x1+x2≤10,−4x1+x2≤0,2x1+x2≥6,x1+2x2≥6,x1−x2≤3,1.99≤x1≤2.01,7.99≤x2≤8.01.Problem 5.
(see [19])(68)minc1Tx+d1c2Tx+d2s.t.Ax=b,x≥0,where(69)A=992100000008180100000018801000000711000−100001710000−100011700000−1001000000001001000000001,b=81,72,72,9,9,9,8,8T,c1=1,0,19,0,0,0,0,0,0,0,0T,c2=0,1,19,0,0,0,0,0,0,0,0T,d1=0,d2=0.
Obviously, Problem5 can be transformed into the following forms:(70)minx1+19x3x2+19x3s.t.9x1+9x2+2x3≤81,8x1+x2+8x3≤72,x1+8x2+8x3≤72,7x1+x2+x3≥9,x1+7x2+x3≥9,x1+x2+7x3≥9,0≤x1≤8,0≤x2≤8,0≤x3≤9.Problem 6.
(see [8])(71)min3x1−4x2+5x1+2x2−10.52x1−x2+4×x1−2x2+80.52x1+x2−1s.t.5x1−8x2≥−24,5x1+8x2≤44,6x1−3x2≤15,4x1+5x2≥10,1≤x1≤3,0≤x2≤1.Problem 7.
(72)min∏i=1pciTxj+diαis.t.Ax≤b,x≥0,where p≥2, ci∈ℝni=1,2,…,p are pseudo-random numbers in [0, 1], αii=1,2,…,p are pseudo-random numbers in [0.00001, 1], di=1, constraint matrix elements aij are generated in [−1, 1] via aij=2∗ϖ−1, in which ϖ are pseudo-random numbers in [0, 1], and the right-hand side values are generated via bi=∑j=1naij+2βi, in which βi are pseudo-random numbers in [0, 1].
The numerical results in Tables1 and 2 show that Algorithms 1 and 2 can effectively solve the three test problems known in the literature and get an approximate solution, so both algorithms are feasible.
Further, we do the corresponding random numerical experiments through Problem7, which is utilized to explore the performance of the two algorithms. We determine the convergence accuracy of the algorithm to 0.05. For each set of fixed parameters p,m,n, we run the two algorithms 10 times for numerical comparison, and the numerical results are given in Table 3. In Table 3, Avg (Std) time and Avg (Std) Iter represent the average (standard deviation) of the CPU running time and the average (standard deviation) of iterations, respectively, after the algorithm has run 10 times. Table 3 shows that the computation effect of Algorithm 2 is better than that of Algorithm 1, mainly because our acceleration technique plays a significant role by deleting the vertices of small rectangles that do not need to be considered. Hence, we believe that this acceleration technique may be generalized on other approximation algorithms such as [17, 18, 20].
Moreover, under the condition that the fixed parametersp,m are invariant, the CPU running time of the two algorithms will increase with the scale n of Problem 7. Under the condition that the prefixed parameters m,n are invariant, the CPU running time and iterations of the two algorithms will grow with the number (p) of linear functions in the objective function of Problem 7.Table 1
Comparison of results in Problems1–6.
ProblemReferenceOptimal solutionOptimal optimum1Locatelli [17](1.3148, 0.1396, 0.0000, 0.4233)0.890190Shen and Wang [18](1.3148, 0.1396, 0.0000, 0.4233)0.890190Liu and Zhao [8](1.3148, 0.13955, 2.6891×10−14, 0.42329)0.890190Algorithms1/2(1.3148, 0.1396, 0.0000, 0.4233)0.8901902Locatelli [17](3.000, 2.000)5.014514Shen and Wang [18](3.000, 2.000)5.009309Liu and Zhao [8](3.000, 2.000)5.009309Algorithm1(3.000, 2.000)5.009309Algorithm2(3.000, 2.000)5.0093093Liu and Zhao [8](1, 1)997.661265Locatelli [17](1, 1)997.661265Shen and Wang [18](1, 1)997.661265Algorithm1/2(1, 1)997.6612654Shen and Hang [20](2, 8)10Algorithm1/2(2, 8)105Zhang et al. [19](0.0, 8.0, 1.0, …)0.91235Algorithm1(0.0, 8.0, 1.0, …)0.91235Algorithm2(0.0, 8.0, 1.0, …)0.912356Liu and Zhao [8](1.25, 1)263.785989Algorithm1(1.25, 1)263.785989Algorithm2(1.25, 1)263.785989Table 2
Comparison of results in Problems1–6.
ProblemReferenceIterTimeε1Locatelli [17]4049.6060.05Shen and Wang [18]30.0470.05Algorithm1/210.01490.052Locatelli [17]692.49600.15009Shen and Wang [18]40.08000.15009Algorithm160.10240.15009Algorithm240.06570.150093Locatelli [17]51.1260.2Shen and Wang [18]40.0850.2Algorithm1/210.01160.24Algorithm1/210.02410.015Algorithm179747.53670.2Algorithm250730.21110.26Algorithm16359.43040.2Algorithm23735.60720.2Table 3
Comparison of numerical results by using Problem7.
p,m,nAlgorithm1Algorithm2Avg (Std) timeAvg (Std) IterAvg (Std) timeAvg (Std) Iter(2, 10, 20)2.9068 (2.8062)75.8 (84.7700)1.9686 (1.9352)22.5 (27.3395)(2, 20, 20)2.3784 (3.1017)52.6 (76.8936)1.7129 (2.1472)23.4 (35.1801)(2, 22, 20)0.8663 (0.9232)18.1 (25.0257)0.6568 (0.6239)8 (10.0199)(2, 20, 30)6.2414 (6.3274)165.2 (164.0334)3.4923 (3.7124)49 (61.764)(2, 35, 50)3.9868 (4.4041)66.4 (78.2102)3.3046 (3.9017)32.3 (38.6886)(2, 45, 60)5.8908 (5.4016)129.1 (125.2481)3.7409 (3.3526)40.5 (38.1084)(2, 45, 100)6.6579 (5.9685)125.3 (123.7061)4.2665 (3.6485)40.2 (40.1343)(2, 60, 100)7.8626 (6.3057)96.6 (99.4818)4.5517 (2.8324)26 (19.8343)(2, 70, 100)9.1245 (8.1057)96.3 (104.6633)5.0942 (3.3528)23.6 (18.9430)(2, 70, 120)11.2742 (13.2311)148 (215.2185)6.0341 (5.5968)35 (37.3256)(2, 100, 10)0.1877 (0.1300)2.4 (2.9732)0.1542 (0.0663)1.3 (0.6403)(2, 100, 50)0.9029 (0.5392)8.9 (7.0632)0.6542 (0.3654)3.9 (2.7730)(2, 100, 100)9.8811 (8.0793)68.6 (55.5287)6.9462 (6.3403)24.1 (26.6813)(2, 100, 150)15.4331 (10.2573)97.4 (75.1720)9.8838 (6.2545)30.8 (22.1260)(2, 100, 200)27.1157 (25.3267)124.4 (130.8076)18.9561 (16.8612)49.2 (47.3810)(2, 100, 250)64.8144 (72.0125)285.1 (353.7955)40.3711 (41.0487)91 (103.9576)(2, 100, 300)87.5572 (100.4846)331 (398.8197)55.5067 (64.5147)117.2 (153.2434)(2, 100, 400)132.4251 (176.2381)363.9 (581.9823)87.0321 (97.4482)130.7 (169.6585)(2, 100, 500)158.4767 (183.7060)338.3 (493.9785)111.0958 (106.7086)133.8 (145.3470)(2, 100, 700)331.3275 (351.8534)414.2 (546.8741)272.7311 (264.9189)227.1 (257.8927)(2, 100, 1000)1020.9318 (880.7910)1063.6 (1019.7921)778.8913 (638.1782)522 (460.2479)(3, 100, 10)4.4724 (7.4341)59.7 (117.2502)3.6522 (5.7934)35.2 (55.7867)(3, 100, 50)90.8139 (74.9843)1062.4 (982.8277)57.8342 (55.5978)473.3 (564.6533)(4, 100, 10)75.4301 (189.1250)1509.3 (4122.7180)52.9122 (122.0553)868.1 (2203.3283)


## 6. Concluding Remarks

In this paper, we mainly propose two polynomial time approximation algorithms that can be utilized to solve the problem GLMP globally, where Algorithm2 is obtained by accelerating Algorithm 1 by the proposed acceleration technique. The numerical results show that both algorithms are effective and feasible, but the overall calculation effect of Algorithm 2 is better than that of Algorithm 1, which shows that our acceleration technique is efficient and may be extended to some approximation algorithms such as [17, 18, 20].



---

*Source: 8877037-2021-02-26.xml*