# Image Space Accelerating Algorithm for Solving a Class of Multiplicative Programming Problems

Authors: Haoyu Zhou; Guohou Li; Xueliang Gao; Zhisong Hou
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

This paper interprets an image space accelerating branch and bound algorithm for globally solving a class of multiplicative programming problems (MP). In this algorithm, in order to obtain the global optimal solution, the problem (MP) is transformed into an equivalent problem (P2) by introducing new variables. By utilizing new linearizing relaxation technique, the problem (P2) can be converted into a series of linear relaxation programming problems, which provide the reliable lower bound in the branch and bound search. Meanwhile, an image space accelerating method is constructed to improve the computational performance of the algorithm by deleting the subintervals which have no global optimal solution. Furthermore, the global convergence of the algorithm is proved. The computational complexity of the algorithm is analyzed, and the maximum iterations of the algorithm are estimated. Finally, numerical experimental results show that the algorithm is robust and efficient.


---

## Body

## 1. Introduction

Consider a class of multiplicative programming problems as follows:(1)MP:minϕx=∏j=1pcj⊤x+djγj,s.t.x∈X=x|Ax≤b,where p∈Z+; cj∈Rn, dj,γj∈R,j=1,2,…,p; A∈Rm×n, and b∈Rm; cj⊤x+dj>0 for any x∈X; and the feasible field X is a nonempty bound polyhedron set. The problem is well known as multiplicative programming problem that corresponds to a nonlinear optimization problem with nonconvex objective function.The problem (MP) comes from various application fields, for example, decision tree optimization [1], multiple-objective decision [2, 3], robust optimization [4], control and engineering optimization [5–9], computer vision [10, 11], network flow optimization [12–14], food science engineering, and big data analysis. That is to say, the problem is useful in many aspects, so it is of great importance to develop an efficient algorithm for the problem (MP).In the past twenty years, many deterministic feasible algorithms have been developed to solve the problem (MP). Generally, these algorithms can be divided into several categories, such as parameterization based methods [15–17], outer-approximation methods [18, 19], finite branch and bound algorithms [20–28], decomposition method [29], level set algorithms [30, 31], primal and dual simplex method [32], cutting plane methods [16, 33], and heuristic methods [34, 35] Recently, Gao et al. [19] proposed an outcome-space finite algorithm to solve a class of linear multiplicative program problems by solving only a convex quadratic program problem in each iteration. Chen and Jiao [36] present a finite branch and bound algorithm based on the theory of monotonic optimization. Wang et al. [37] used simplicial subdivision in the branch operation to solve generalized multiplicative programs. By directly mapping the original variable space to two-dimensional space, Wang et al. [38] gave a method that can effectively solve special second-order multiplicative problems. Shen and Huang [39] developed a rectangular branch and bound algorithm with bisection rule to solve linear multiplicative programming problems. Liu and Zhao [31] presented a new algorithm for solving a generalized multiplicative programming based on level set method. Zhang et al. [40] proposed an output space brand and bound algorithm for solving the linear multiplicative programs. Moreover, Shen and Wang [41] proposed a branch and bound algorithm that can solve the multiplicative programs in polynomial time. Using a piecewise linear approximation method and some outer space accelerating techniques, Hou and Liu [42] provided an outer space algorithm to solve a class of multiplicative programs effectively. Up to now, although there is a lot of progress in the development of deterministic algorithms for solving the special forms of the problem (MP), the global optimization algorithm of general forms of the problem (EP) in this paper has been little researched.In the paper, based on the branch and bound framework, a new image space accelerating algorithm is proposed by solving a series of linear relaxation problems over partitioned subsets to find a global optimal solution of the problem (MP). For this purpose, we first convert the problem (MP) into the equivalent optimization problem (P2) by mapping the problem (MP) from the origin space to image space. Second, a linear relaxation problem of the problem (P2) is constructed. Based on the linear relaxation technique, the problem (P2) is systematically converted into a sequence of linear relaxation programming problems. Third, by successive refinement iterations, the solutions of these constructed linear relaxation problems can be as close as possible to the global optimal solution of the problem (MP). Meanwhile, in the above iterations, the approximation process can be accelerated by deleting some regions in which there is no global optimal solution of the problem (P2).Compared with the known methods, the proposed algorithm has the following superiorities: (1) new variables are introduced to reducen-dimensional space into p-dimensional image space. Then, the branching operations in brand and bound framework act on the p-dimensional image space which can significantly reduce the computational cost as p is usually smaller than n. (2) In the bound operations, according to properties of the objective function of the problem (P2) and the structure of the algorithm, an accelerating method is proposed to reduce the computational cost of the algorithm. (3) We prove the global convergence of the proposed algorithm and estimate the maximum number of the iterations by analyzing the computational complexity of the algorithm. On the other hand, the efficiency of the algorithm is sensitive to the interval range of the variable of the image space.The remainder of this paper is organized as follows: In Section2, we give the equivalent transformation of the origin problem and the linear relaxation method for the equivalent problem. In Section 3, an image space accelerating algorithm based on branch and bound framework is developed and the convergence of the algorithm is proved. In addition, the computational complexity of the algorithm is analyzed and the maximum number of iterations of the algorithm is estimated. In Section 4, numerical results of some tests are provided. Finally, a brief summary is made in Section 5.


## 2. Equivalent Problem and Its Linear Relaxation

In this section, we will convert the problem (MP) into an equivalent problem (P1) which has the same optimal solution as the problem (MP). Using the logarithmic function property, we can obtain this equivalent programming problem as follows:(2)P1:min,∑j=1pγjlncj⊤x+dj,s.t.,x∈X=x|Ax≤b.Next, introducep variables tj=cj⊤x+dj,j=1,2,…,p and let lj0 and uj0 be the minimum and maximum of tj,j=1,2,…,p, which can be obtained by the following linear programming.(3)lj0=mincj⊤x+dj,s.t.Ax≤b,and(4)uj0=max,cj⊤x+dj,s.t.,Ax≤b.Hence, the problem (P1) can be transformed into the following equivalent problem (P2).(5)P2:min,Ψt=∑j=1pγjlntj,s.t.,x∈X=x|Ax≤b,tj=cj⊤x+dj,t∈T0=l0,u0.Obviously, the problem (P1) has the same optimal solution as the problem (P2). In the following, the main task is to solve the problem (P2). For solving the problem (P2), the main work is to construct lower bounds of this problem and its subproblems generated by the branch and bound algorithm. Meanwhile, the lower bounds of this problem and its subproblems can be obtained by solving the corresponding linear relaxation programming problems.For anyt∈l,u⊆T0, we define the following functions:(6)kj=lnuj−lnljuj−lj,hjtj=lnlj+kjtj−lj,gjtj=kjtj−lnkj−1,fjtj=lntj.The linear relaxation programming problems of the problem (P2) can be generated by underestimating every implicit term γjlntj,j=1,2,…,p with a linear function. The following theorem will show the details of this linear relaxation technique for the problem (P2).Theorem 1.
For any functionsfjtj,gjtj, and hjtj over lj,uj,j=1,2,…,p, we have the following two statements:(1)
The functionhjtj is the linear convex envelope of the function fjtj, and the function gjtj is a supporting hyperplane of the function fjtj which is parallel with hjtj. Meanwhile, we have (7)hjtj≤fjtj≤gjtj,for∀tj∈lj,uj.(2)
Define(8)δj1tj=gjtj−fjtj,δj2tj=fjtj−hjtj,ωj=uj−lj,zj=ujlj.
Then, we have(9)maxtj∈lj,ujδj1tj⟶0,maxtj∈lj,ujδj2tj⟶0asωj⟶0.Proof.
(i) Obviously, the functionfjtj=lntj is a concave and monotone increase function of tj over lj,uj. Therefore, the line passing through the points lj,lnlj and uj,lnuj is the affine convex envelope of the function fjtj=lntj, and this line can be described as the form of hjtj=lnlj+kjtj−lj. Hence, by tj∈lj,uj, we have(10)hjtj=lnlj+kjtj−lj≤lntj=fjtj.
On the other hand, suppose that the linegtj is the tangential plane of the function fjt and parallel to the line htj, the tangential support point must appear at the point 1/kj,ln1/kj. Then, the corresponding tangential function of this line is gjt=kjtj−lnkj−1. According to the geometric properties of the function fjtj=lntj, for ∀tj∈lj,uj, we obtain(11)fjtj=lntj≤kjtj−lnkj−1=gjtj.
This completes the proof of (i) in Theorem1. With zj=uj/lj, kj=lnuj−lnlj/uj−lj, kj can be changed into(12)kj=lnzjljzj−1.
Then, we can obtain(13)δj1tj=kjtj−1−lnkj−lntj,δj2tj=lntj−lnlj−kjtj−lj.
It is known thatδj2tj is a concave function of tj over lj,uj, so the maximum δj.max2 can be obtained at the point of tangential support whose value is tj=1/kj. Thus,(14)δj.max2=ln1kj−lnlj−kj1kj−lj=−lnkjlj−1+kjlj=lnzj−1lnzj−1+lnzjzj−1.
Fromzj⟶1,lnzj/zj−1⟶1 as ωj⟶0, we can obtain that δj.max2⟶0 as ωj⟶0.
On the other hand,δj1tj is a convex function of tj for any tj∈lj,uj. Clearly, the maximum of δj1tj, named δj.max1, must occur at the critical point, lj or uj. In addition, the form of kj=lnuj−lnlj/uj−lj can be transformed into the form of(15)kjuj−lnuj=kjlj−lnlj.
Then, we have(16)δj1lj=kjlj−1−lnkj−lnlj=δj.max2,(17)δj1uj=kjuj−1−lnkj−lnuj=kjlj−lntj−lnkj−1=δj1lj=δj.max2.
From the description shown above, it holds thatδj.max1=δj1lj=δj1uj=δj.max2 and δj.max1⟶0, δj.max2⟶0 as ωj⟶0. This completes the proof of (ii).Remark.
From Theorem1, we can get approximations solution by shortening the gap between tangential hypersurface gjt and concave envelope hjt. As a result, the functions gjt and hjt infinitely approximate the function fjt when ωj⟶0.
Now, we give the linear relaxation programming of the problem (P2). Suppose that Tk=lk,uk⊆l0,u0. Denoting that ΨjLtj is the underestimating function for each nonlinear function γjlntj over Tjk=ljk,ujk⊆lj,uj, for any tj∈lj,uj, we obtain(18)γjlntj≥ΨjLtj=γjhjtjifγj>0,γjgjtjifγj<0,j=1,2,…,p.
Then, summing all the termsΨjLtj,j=1,2,…,p and expressing the result as ΨRt=∑j=1pΨjLtj, we have(19)Ψt≥ΨRt=∑j=1pΨjLtj,∀tj∈lj,uj.
Consequently, the corresponding linear relaxation programming problem overT of the problem (P2) can be constructed as follows:(20)P3:min,ΨRt,s.t.,tj=cj⊤x+dj,j=1,2,…,p,t∈T=l0,u0,x∈X=x|Ax≤b.
From the construction process of the linear relaxation programming problem, all feasible solutions of the problem (P2) over subdomain Tk are feasible to the problem (P3). Furthermore, in the subdomain Tk, the optimal value of the problem (P3) is less than that of the problem (P2). Therefore, the problem (P3) provides an effective lower bound for the solution of the problem (P2) in the partition set Tk. It should be pointed out that the problem (P3) only contains the necessary constraints to ensure the global convergence of the algorithm.


## 3. Algorithm, Convergence, and Its Complexity

By combining the branching operation, the bound operation, and the accelerating method, we design an image space accelerating algorithm to solve the equivalent problem (P2). By solving a series of linear relaxation programming problems over the subset of T0, this method finds a global optimal solution.The branch operation of the branch and bound method divides the setT0 into subhyperrectangles. Each subhyperrectangle is related to a node of the branch and bound tree, and each node is associated with the linear relaxation programming subproblem in the corresponding subhyperrectangle.UsingQk to represent the active node of the step k of the algorithm, we will get a collection of active nodes which associate with a subhyperrectangle T⊆T0,∀T∈Qk. By calculating the solution LBT of the problem (P3), we get the lower bound of the optimal value of the problem (P2) on each node Qk at step k. Thus, we denote LBk=minLBT,∀T∈Qk by the lower bound of the optimal value of the problem (P2) over the entire initial box region T0 at step k.If the solution of the problem (P3) is feasible for the problem (P2), the upper bound UB of the incumbent solution is updated. Then, for any step k, the active node Qk is satisfied with LBT<UB,∀T∈Qk.Next, an active node with the smallest lower bound is selected and its associated subhyperrectangle is divided into two subhyperrectangles. As mentioned above, the lower bound of each new node is calculated and a new set of active nodes for the next step are generated. The whole process is iterated until the global convergence is obtained.The key factor to ensure the convergence to the global minimum is to select the appropriate partition strategy. In this paper, we choose a standard and simple bisection rule. This method makes all intervals of every variables tend to zero, so it is sufficient to guarantee the global convergence of the proposed algorithm. The rule of the branching operation is as follows.Assuming that the current active node is the subhyperrectangleY′=y¯′,y¯′⊆Y0, the branching variable ys´ satisfying s=argmaxy¯i′−y¯i′,i=1,2,…,p is selected to apply the bisection rule. Then, we divide the interval y¯′,y¯′ into two equal intervals y¯s′,y¯s′+y¯s′/2 and y¯s′+y¯s′/2,y¯s′.


### 3.1. Accelerating Method

According to the structure of the branch and bound framework, we propose an accelerating technique to enhance the convergence speed of the algorithm by deleting the whole region or a part of the region in which there is no global optimal solution.Without losing generality, assume that the current subhyperrectangle isTk, where tk∈Tk=ljk,ujk⊆T0,j=1,2,…,p, and UB is the current upper bound of the problem (P1) which is obtained by the proposed algorithm. Denote(21)Ωk=∑j=1,γj>0pγjfljk+∑j=1,γj<0pγjfujk,Λk=∑j=1,j≠s,γj>0pγjfljk+∑j=1,j≠s,γj<0pγjfujk,ηsk=expUB−Λkγs,s∈1,2,…,p,Trk=ljk≤tjk≤ujk,j=1,2,…,p,j≠s,ηsk<tsk≤usk,j=s,iflsk≤ηsk≤usk,Tlk=ljk≤tjk≤ujk,j=1,2,…,p,j≠s,lsk≤tsk<ηsk,j=s.iflsk≤ηsk≤usk.The accelerating method can be given by Theorem2.Theorem 2.
For anytk∈Tk=⊆T0,j=1,2,…,p, the following conclusions hold:(1)
IfΩk>UB, there exists no global optimal solution to the problem (P2) in the current subhyperrectangle Tk(2)
IfΩk≤UB, it can be divided into two kinds of cases: for any index s∈1,2,…,p, if γs>0, there is no optimal solution in Trk; on the contrary, if γs<0, there is no optimal solution in TlkProof.
(i) IfΩk>UB, we have(22)mint∈TkΨt=mint∈Tk∑j=1pγjlntjk=∑j=1,γj>0pγjlnljk+∑j=1,γj<0pγjlnujk=Ωk>UB.
It is obvious that the problem (P2) has no global optimal solution over the current subhyperrectangle Tk. Therefore, the current subhyperrectangle Tk can be deleted. (ii) If Ωk≤UB, for any tk∈Trk, consider the sth dimensional variable tsk of tk; we have(23)γslntsk>UB−Λk,where γj>0. With(24)Λk=∑j=1,j≠s,γj>0pγjfljk+∑j=1,γj<0pγjfujk,γs>0,we have(25)mint∈TrkΨt=mint∈Trk∑j=1pγjlntjk>∑j=1,j≠s,γj>0pγjlnljk+∑j=1,γj<0pγjlnujk+γslntsk=Λk+UB−Λk=UB.
Therefore, the current subhyperrectangleTrk does not contain the global optimal solution of the problem (P2).
For anytk∈Tlk, consider the sth dimensional variable tsk of tk ; we obtain(26)γslntsk>UB−Λk,where γj<0. With(27)Λk=∑j=1,γj>0pγjfljk+∑j=1,j≠s,γj<0pγjfujk,γs<0,we have(28)mint∈TlkΨt=mint∈Trk∑j=1pγjlntjk>∑j=1,γj>0pγjlnljk+∑j=1,j≠s,γj<0pγjlnujk+γslnηsk=Λk+UB−Λk=UB.
Consequently, there is no global optimal solution overTlk. This completes the proof of Theorem 2.
From Theorem2, we can construct the accelerating method to delete the invalid subhyperrectangle or reduce the ineffective interval of all dimensions over the hyperrectangle which does not contain the global optimal solution to the problem (P2). Consequently, the efficiency of the proposed algorithm is improved.


### 3.2. Algorithmic Statement

DenoteLBTk by lower bound function of the problem (P3) over every subhyperrectangle Tk and denote tk=tTk by the element of corresponding argmin method. The specific steps of the proposed global optimization algorithm are as follows:Step 0. Initialization:(1)
Initialize the iteration numberk:=0 , the set of all active node Q:=∅ , the upper bound UB:=+∞, the lower bound LB:=−∞ , the small enough accuracy tolerance ε>0 , and the set of feasible solution F:=∅ .(2)
Definelj0=minx∈Xtj=cj⊤x+dj, and uj0=maxx∈Xtj=cj⊤x+dj,j=1,2,…,p. The upper bound uj0 and lower bound lj0 of tj are generated, and the initial interval T0 of t is obtained. Then, add the rectangle T0=l0,u0 to the activate node set Q.Step 1. Solving the problem (P3) over the hyperrectangle T=T0, the feasible solution F:=t0,x0, and the optimal solution LB:=LBT0 is obtained. Update the initial upper bound UB through substituting t0 into the problem (P2). If UB−LB≤ε, go to Step 6. Otherwise, proceed to Step 2.Step 2. Select a branching variable ts to divide Tk into two new subhyperrectangles according to the branching rule shown above and denote the set of new partition rectangles by T¯k.(1)
For eachT∈T¯k, using the above accelerating technique to compress its range, still denote the remaining subrectangle by T¯k.(2)
For eachT∈T¯k≠∅, compute the lower bound LBT¯k and the feasible solution tk,xk by solving linear relaxation programming problem (P3). If UB<LBk, discard the corresponding subhyperrectangle T from T¯k; this is to say, T¯k:=T¯k∖T, and continue to process the next element of T¯k. Otherwise, calculate UBk and add the subhyperrectangle into the active node set Q. If UBk−UB<ε, update the upper bound UB=UBk and the feasible solution F:=tk,xk similar as Step 1; then go to Step 6.Step 3. The remaining active node set is Q:=Q∖Tk∪T¯k. If Q:=∅, go to Step 6.Step 4. Update the lower bound LB:=infT∈QLBT. If UB−LB<ε, go to Step 6. Otherwise, k:=k+1 and move on to the next step.Step 5. Choose an active node Tk where Tk=argminT∈QLBT, tk:=tTk, and return to Step 2. Otherwise, move on to the next step.Step 6. Stop the algorithm with expUB as the optimal solution to the problem (MP) and the vector x∗ intercepted from F as the feasible solution.


### 3.3. Convergence of the Algorithm

In this subsection, the global convergence properties of the proposed algorithm are given. It is obvious that the partitioning sets used by the proposed algorithm are all rectangular and compact. Tuy [43] pointed out that rectangular subdivisions are exhaustive. Therefore, the proposed algorithm is exhaustive according to the branch operation rule mentioned above. Otherwise, if the proposed algorithm is infinite, the subdivision of T generates an infinite, nested sequence of partition sets Tk, and an associated sequence of diameters dTk satisfies the condition as follows:(29)Tk⊃Tk+1∀k=0,1,…,limk⟶∞dTk=0,limk⟶∞Tk=∩kTk=t^.Lemma 1.
Given a functionΨt in (4), ΨRt given by (19) is strongly consistent over T0. That is, there are subsequences Tq of subhyperrectangle Tk and a corresponding sequence tq with tq∈Tk satisfying ΨRtq⟶Ψt^ as q⟶∞.Proof.
By exhaustive partition according to the branching rule, a sequence of subhyperrectangleTk that is exhaustive on T0 is generated. Meanwhile, a corresponding sequence tk|tk∈Tk is obtained. Through an exhaustive subdivision, we get that Tk⟶t^ and tk⟶t^. Since the upper bound and the lower bound over Tk are both sequences in a compact space, there exists a convergent subsequence. Hence, Tq=t¯q,t¯q⟶t^,t^ as q⟶∞. Corresponding to this subsequence, there is the sequence t¯q,t¯q,tq⟶t^,t^,t^ as q⟶∞ with tq∈t¯q,t¯q.
Furthermore, according to (5), (18), (19), and (20), it follows that(30)Ψt=∑j=1pγjfjtj=∑j=1,γj>0pγjfjtj+∑j=1,γj<0pγjfjtj,(31)ΨRt=∑j=1pΨjLtj=∑j=1,γj>0pγjhjtj+∑j=1,γj<0pγjgjtj.
From Theorem1, we have(32)0≤gjt−fjt≤lnzjzj−1−1+lnzj−1lnzj∀j=1,2,…,p,where zj=uj/lj and ωj=uj−lj=t¯jq−t¯jq, for t∈Tq=t¯q,t¯q.
Sincegjtjq and fjtjq can be regarded as the continuous functions of tjq and ωj is the function of t¯jq,t¯jq, by the problem (P3), we have(33)limq⟶∞gjtjq−fjtjq=gjtj^−fjtj^=0.
Using the similar proof process to (32), we obtain(34)limq⟶∞fjtjq−hjtjq=fjtj^−hjtj^=0.
Therefore, it can be seen from (30), (31), (32), and (33) that(35)ΨjRxq⟶Ψjt^asq⟶∞,which satisfies the strongly consistent underestimating requirements.Lemma 2.
Given the functionΨt in (5), Ψt has tight bounds. That is, there exist the upper bound Ψ¯t and the lower bound Ψ¯t of Ψt, respectively, such that, for any infinite sequence Tk which is produced by the exhaustive subpartition with Tk⟶t^, there exists limk⟶∞Ψ¯tk=limk⟶∞Ψtk=limk⟶∞Ψ¯tk=Ψt^.Proof.
Just as Lemma1, for any infinite subhyperrectangle sequence Tk, Tk=t¯k,t¯k, which is produced by an exhaustive subpartition of T0 with tk⟶t^ as k⟶∞, there exists a sequence tk with tk∈Tk such that tk⟶t^ as k⟶∞. Corresponding to this sequence, there exists the sequence t¯k,t¯k,tk⟶t^,t^,t^ as k⟶∞. Corresponding to (30) and (31), denote Ψ¯t=ΨRx and define the function as follows:(36)Ψ¯t=∑j=1,γj>0pγjgjtj+∑j=1,γj<0pγjhjtj.
By Theorem1, it is obvious that(37)Ψ¯t≤Ψt≤Ψ¯t,for∀t∈Tk=t¯k,t¯k.
Denotelk,uk by the lower bound and upper bound for Tk, respectively. According to (ii) of Theorem 1, for any t∈Tk, we have(38)gjtj−maxt∈Tδj1tj≤fjtj≤hjtj+maxt∈Tδj2tj,j=1,…,p,where maxt∈Tδj1t and maxt∈Tδj2t are given by Theorem 1. Since zj⟶1 as k⟶∞, thus, maxt∈Tδj1t⟶0 and maxt∈Tδj2t⟶0 as k⟶∞.
Hence, by continuity of the functionsfjt over Tk, it follows from inequality (31) that(39)limk⟶∞gjtk−maxt∈Tδj1t=limk⟶∞hjtk+maxt∈tδj2t=fjt^.
That is,(40)limk⟶∞gjtk=limk⟶∞hjtk=limk⟶∞fjtk=fjt^.
Consequently, from (30), (31), (32), (37), and (40), the conclusion can be drawn as follows:(41)limk⟶∞Ψ¯tk=limk⟶∞Ψjtk=limk⟶∞Ψ¯tk=Ψt^.
As shown above, the functionΨt has tight upper bound Ψ¯t and tight lower bound Ψ¯t.
LetTa be the set of accumulation points of tk and denote T∗ by the region of argmint∈DΨt, where D≠∅ is the feasible space of the problem (P2).Theorem 3.
The proposed algorithm either terminates within finite iterations at the incumbent solution being an optimal solution to the problem (P2) or an infinite sequence of the branch and bound tree is generated such that(42)LB=limk⟶∞LBk=mint∈DΨt,Ta⊂T∗.Proof.
For each step of iterations in the proposed algorithm,k=0,1,2,…, we have LBk≤mint∈DΨt,Tk∈argminT∈QkLBT,tk=tTk∈Tk⊆T0.
Horst [44] proved that LBk is a nondecreasing sequence bounded with mint∈DΨt, which ensures the limit LB=limk⟶∞LBk≤mint∈DΨt exists. Since tk is a sequence on a compact set, it has a convergent subsequence. In addition, for any t^∈Ta, there is a sequence tr of tk with limr⟶∞tr=t^. By Tuy [43] and Lemma 1, it can be drawn that the partition for subhyperrectangle sets in Step 2 is exhaustive on T0 and the choice of subhyperrectangle to be subdivided in Step 2 is bound improving. Therefore, there is a decreasing subsequence Tq⊂Tr where Tr is the T space of the partition Qr with tq∈Tq, LBq=LBTq=ΨRTq, and limq⟶∞tq=t^. From Lemma 2, we have limq⟶∞LBq=LB=Ψt^.
Next, we prove that the conditiont^∈D is satisfied. T0 is a closed set, such that t^∈T0. Proved by contradiction, the above condition can be proved. Let t^∈D; there exists Ψt^=δ>0. Since Ψ is a continuous function, the sequence Ψtq can be converged to Ψt^. According to the convergence property of Ψ, ∃qδ such that Ψtq−Ψt^<δ as q>qδ. Hence, for q>qδ,Ψtq>0 implying that the problem (P2) is infeasible and violating the assumption that tq=tTq. This leads to a contradiction, and therefore, t^∈D. As a result, we obtain LB=Ψt^=mint∈DΨt,t^∈T∗. And the proof of Theorem 3 is completed.


### 3.4. Computational Complexity of the Algorithm

In this subsection, we analyze the computational complexity of the proposed algorithm by estimating the maximum number of iterations. In the process of branching operations, we denote the diameter of theTk=lk,uk⊆T0 by(43)ΔTk=maxj=1,2,…,pujk−ljk.Meanwhile, we introduce some notations as follows.(44)ρ=maxj=1,2,…,plnuj0−lnlj0uj0−lj0,(45)μ=∑j=1pγj.Lemma 3.
For given convergence toleranceε≥0, if the subhyperrectangle Tk⊆T0 is satisfied with ΔTk≤ε/μρ at the kth iteration, we have(46)UB−LBTk≤ε,where UB is current global upper bound of the equivalent problem and LBTk indicates the linear relaxation solution of current subhyperrectangle.Proof.
Assuming thattk is the optimal solution of the linear relaxation problem, we have(47)ψRtk=LBTk≤UB=ψtk.
According to (4) and (19), we can conclude that(48)UB−LBTk=ψt−ψRtk=∑j=1pγjftjk−∑j=1,γj>0pγjhjtjk−∑j=1,γj<0pγjgjtjk=∑j=1,γj>0pγjftjk−hjtjk+∑j=1,γj<0pγjftjk−gjtjk.
Then, by using (16) and (17), we have(49)UB−LBTk=∑j=1pγjlnuj−lnlj−kjtj−lj≤∑j=1pγjlnuj−lnlj=∑j=1pγjρjuj−lj≤μρΔTk.
From the previous formula and the condition ofΔTk≤ε/μρ, we can obtain that UB−LBTk<ε.. This completes the proof of Lemma 3.Theorem 4.
Given the convergence toleranceε≥0, the maximum iterations of the proposed algorithm to obtain the ε -globally optimal solution are(50)N=∑j=1plog2μρuj−ljε,where μ and ρ are given in (44) and (45), respectively.Proof.
Suppose that, at thekj.th iteration, the subhyperrectangle Tk⊆T0 is satisfying with(51)ΔTk≤εμρ.
Meanwhile, according to the branching operation in Step 2, we have(52)ΔTjk=12kjuj0−lj0,j=1,2,…,p.
From (51) and (52), we obtain(53)12kjuj0−lj0≤εμρ,j=1,2,…,p,i.e.,(54)kj≥log2μρuj0−lj0ε,j=1,2,…,p.
With the proof of Lemma3, we can get that ψt−ψRtk≤ε. Denote(55)kj¯=log2μρuj0−lj0ε,j=1,2,…,p.
After at most iterations,(56)N=∑j=1pkj¯,=∑j=1plog2μρuj0−lj0ε, we have(57)UB−LBT≤ψt∗−ψRt∗≤ε.where t∗ is the optimal solution of the equivalent problem (P2). Therefore, we obtain the ε -globally optimal solution. The proof of Theorem 3 is completed.


## 3.1. Accelerating Method

According to the structure of the branch and bound framework, we propose an accelerating technique to enhance the convergence speed of the algorithm by deleting the whole region or a part of the region in which there is no global optimal solution.Without losing generality, assume that the current subhyperrectangle isTk, where tk∈Tk=ljk,ujk⊆T0,j=1,2,…,p, and UB is the current upper bound of the problem (P1) which is obtained by the proposed algorithm. Denote(21)Ωk=∑j=1,γj>0pγjfljk+∑j=1,γj<0pγjfujk,Λk=∑j=1,j≠s,γj>0pγjfljk+∑j=1,j≠s,γj<0pγjfujk,ηsk=expUB−Λkγs,s∈1,2,…,p,Trk=ljk≤tjk≤ujk,j=1,2,…,p,j≠s,ηsk<tsk≤usk,j=s,iflsk≤ηsk≤usk,Tlk=ljk≤tjk≤ujk,j=1,2,…,p,j≠s,lsk≤tsk<ηsk,j=s.iflsk≤ηsk≤usk.The accelerating method can be given by Theorem2.Theorem 2.
For anytk∈Tk=⊆T0,j=1,2,…,p, the following conclusions hold:(1)
IfΩk>UB, there exists no global optimal solution to the problem (P2) in the current subhyperrectangle Tk(2)
IfΩk≤UB, it can be divided into two kinds of cases: for any index s∈1,2,…,p, if γs>0, there is no optimal solution in Trk; on the contrary, if γs<0, there is no optimal solution in TlkProof.
(i) IfΩk>UB, we have(22)mint∈TkΨt=mint∈Tk∑j=1pγjlntjk=∑j=1,γj>0pγjlnljk+∑j=1,γj<0pγjlnujk=Ωk>UB.
It is obvious that the problem (P2) has no global optimal solution over the current subhyperrectangle Tk. Therefore, the current subhyperrectangle Tk can be deleted. (ii) If Ωk≤UB, for any tk∈Trk, consider the sth dimensional variable tsk of tk; we have(23)γslntsk>UB−Λk,where γj>0. With(24)Λk=∑j=1,j≠s,γj>0pγjfljk+∑j=1,γj<0pγjfujk,γs>0,we have(25)mint∈TrkΨt=mint∈Trk∑j=1pγjlntjk>∑j=1,j≠s,γj>0pγjlnljk+∑j=1,γj<0pγjlnujk+γslntsk=Λk+UB−Λk=UB.
Therefore, the current subhyperrectangleTrk does not contain the global optimal solution of the problem (P2).
For anytk∈Tlk, consider the sth dimensional variable tsk of tk ; we obtain(26)γslntsk>UB−Λk,where γj<0. With(27)Λk=∑j=1,γj>0pγjfljk+∑j=1,j≠s,γj<0pγjfujk,γs<0,we have(28)mint∈TlkΨt=mint∈Trk∑j=1pγjlntjk>∑j=1,γj>0pγjlnljk+∑j=1,j≠s,γj<0pγjlnujk+γslnηsk=Λk+UB−Λk=UB.
Consequently, there is no global optimal solution overTlk. This completes the proof of Theorem 2.
From Theorem2, we can construct the accelerating method to delete the invalid subhyperrectangle or reduce the ineffective interval of all dimensions over the hyperrectangle which does not contain the global optimal solution to the problem (P2). Consequently, the efficiency of the proposed algorithm is improved.


## 3.2. Algorithmic Statement

DenoteLBTk by lower bound function of the problem (P3) over every subhyperrectangle Tk and denote tk=tTk by the element of corresponding argmin method. The specific steps of the proposed global optimization algorithm are as follows:Step 0. Initialization:(1)
Initialize the iteration numberk:=0 , the set of all active node Q:=∅ , the upper bound UB:=+∞, the lower bound LB:=−∞ , the small enough accuracy tolerance ε>0 , and the set of feasible solution F:=∅ .(2)
Definelj0=minx∈Xtj=cj⊤x+dj, and uj0=maxx∈Xtj=cj⊤x+dj,j=1,2,…,p. The upper bound uj0 and lower bound lj0 of tj are generated, and the initial interval T0 of t is obtained. Then, add the rectangle T0=l0,u0 to the activate node set Q.Step 1. Solving the problem (P3) over the hyperrectangle T=T0, the feasible solution F:=t0,x0, and the optimal solution LB:=LBT0 is obtained. Update the initial upper bound UB through substituting t0 into the problem (P2). If UB−LB≤ε, go to Step 6. Otherwise, proceed to Step 2.Step 2. Select a branching variable ts to divide Tk into two new subhyperrectangles according to the branching rule shown above and denote the set of new partition rectangles by T¯k.(1)
For eachT∈T¯k, using the above accelerating technique to compress its range, still denote the remaining subrectangle by T¯k.(2)
For eachT∈T¯k≠∅, compute the lower bound LBT¯k and the feasible solution tk,xk by solving linear relaxation programming problem (P3). If UB<LBk, discard the corresponding subhyperrectangle T from T¯k; this is to say, T¯k:=T¯k∖T, and continue to process the next element of T¯k. Otherwise, calculate UBk and add the subhyperrectangle into the active node set Q. If UBk−UB<ε, update the upper bound UB=UBk and the feasible solution F:=tk,xk similar as Step 1; then go to Step 6.Step 3. The remaining active node set is Q:=Q∖Tk∪T¯k. If Q:=∅, go to Step 6.Step 4. Update the lower bound LB:=infT∈QLBT. If UB−LB<ε, go to Step 6. Otherwise, k:=k+1 and move on to the next step.Step 5. Choose an active node Tk where Tk=argminT∈QLBT, tk:=tTk, and return to Step 2. Otherwise, move on to the next step.Step 6. Stop the algorithm with expUB as the optimal solution to the problem (MP) and the vector x∗ intercepted from F as the feasible solution.


## 3.3. Convergence of the Algorithm

In this subsection, the global convergence properties of the proposed algorithm are given. It is obvious that the partitioning sets used by the proposed algorithm are all rectangular and compact. Tuy [43] pointed out that rectangular subdivisions are exhaustive. Therefore, the proposed algorithm is exhaustive according to the branch operation rule mentioned above. Otherwise, if the proposed algorithm is infinite, the subdivision of T generates an infinite, nested sequence of partition sets Tk, and an associated sequence of diameters dTk satisfies the condition as follows:(29)Tk⊃Tk+1∀k=0,1,…,limk⟶∞dTk=0,limk⟶∞Tk=∩kTk=t^.Lemma 1.
Given a functionΨt in (4), ΨRt given by (19) is strongly consistent over T0. That is, there are subsequences Tq of subhyperrectangle Tk and a corresponding sequence tq with tq∈Tk satisfying ΨRtq⟶Ψt^ as q⟶∞.Proof.
By exhaustive partition according to the branching rule, a sequence of subhyperrectangleTk that is exhaustive on T0 is generated. Meanwhile, a corresponding sequence tk|tk∈Tk is obtained. Through an exhaustive subdivision, we get that Tk⟶t^ and tk⟶t^. Since the upper bound and the lower bound over Tk are both sequences in a compact space, there exists a convergent subsequence. Hence, Tq=t¯q,t¯q⟶t^,t^ as q⟶∞. Corresponding to this subsequence, there is the sequence t¯q,t¯q,tq⟶t^,t^,t^ as q⟶∞ with tq∈t¯q,t¯q.
Furthermore, according to (5), (18), (19), and (20), it follows that(30)Ψt=∑j=1pγjfjtj=∑j=1,γj>0pγjfjtj+∑j=1,γj<0pγjfjtj,(31)ΨRt=∑j=1pΨjLtj=∑j=1,γj>0pγjhjtj+∑j=1,γj<0pγjgjtj.
From Theorem1, we have(32)0≤gjt−fjt≤lnzjzj−1−1+lnzj−1lnzj∀j=1,2,…,p,where zj=uj/lj and ωj=uj−lj=t¯jq−t¯jq, for t∈Tq=t¯q,t¯q.
Sincegjtjq and fjtjq can be regarded as the continuous functions of tjq and ωj is the function of t¯jq,t¯jq, by the problem (P3), we have(33)limq⟶∞gjtjq−fjtjq=gjtj^−fjtj^=0.
Using the similar proof process to (32), we obtain(34)limq⟶∞fjtjq−hjtjq=fjtj^−hjtj^=0.
Therefore, it can be seen from (30), (31), (32), and (33) that(35)ΨjRxq⟶Ψjt^asq⟶∞,which satisfies the strongly consistent underestimating requirements.Lemma 2.
Given the functionΨt in (5), Ψt has tight bounds. That is, there exist the upper bound Ψ¯t and the lower bound Ψ¯t of Ψt, respectively, such that, for any infinite sequence Tk which is produced by the exhaustive subpartition with Tk⟶t^, there exists limk⟶∞Ψ¯tk=limk⟶∞Ψtk=limk⟶∞Ψ¯tk=Ψt^.Proof.
Just as Lemma1, for any infinite subhyperrectangle sequence Tk, Tk=t¯k,t¯k, which is produced by an exhaustive subpartition of T0 with tk⟶t^ as k⟶∞, there exists a sequence tk with tk∈Tk such that tk⟶t^ as k⟶∞. Corresponding to this sequence, there exists the sequence t¯k,t¯k,tk⟶t^,t^,t^ as k⟶∞. Corresponding to (30) and (31), denote Ψ¯t=ΨRx and define the function as follows:(36)Ψ¯t=∑j=1,γj>0pγjgjtj+∑j=1,γj<0pγjhjtj.
By Theorem1, it is obvious that(37)Ψ¯t≤Ψt≤Ψ¯t,for∀t∈Tk=t¯k,t¯k.
Denotelk,uk by the lower bound and upper bound for Tk, respectively. According to (ii) of Theorem 1, for any t∈Tk, we have(38)gjtj−maxt∈Tδj1tj≤fjtj≤hjtj+maxt∈Tδj2tj,j=1,…,p,where maxt∈Tδj1t and maxt∈Tδj2t are given by Theorem 1. Since zj⟶1 as k⟶∞, thus, maxt∈Tδj1t⟶0 and maxt∈Tδj2t⟶0 as k⟶∞.
Hence, by continuity of the functionsfjt over Tk, it follows from inequality (31) that(39)limk⟶∞gjtk−maxt∈Tδj1t=limk⟶∞hjtk+maxt∈tδj2t=fjt^.
That is,(40)limk⟶∞gjtk=limk⟶∞hjtk=limk⟶∞fjtk=fjt^.
Consequently, from (30), (31), (32), (37), and (40), the conclusion can be drawn as follows:(41)limk⟶∞Ψ¯tk=limk⟶∞Ψjtk=limk⟶∞Ψ¯tk=Ψt^.
As shown above, the functionΨt has tight upper bound Ψ¯t and tight lower bound Ψ¯t.
LetTa be the set of accumulation points of tk and denote T∗ by the region of argmint∈DΨt, where D≠∅ is the feasible space of the problem (P2).Theorem 3.
The proposed algorithm either terminates within finite iterations at the incumbent solution being an optimal solution to the problem (P2) or an infinite sequence of the branch and bound tree is generated such that(42)LB=limk⟶∞LBk=mint∈DΨt,Ta⊂T∗.Proof.
For each step of iterations in the proposed algorithm,k=0,1,2,…, we have LBk≤mint∈DΨt,Tk∈argminT∈QkLBT,tk=tTk∈Tk⊆T0.
Horst [44] proved that LBk is a nondecreasing sequence bounded with mint∈DΨt, which ensures the limit LB=limk⟶∞LBk≤mint∈DΨt exists. Since tk is a sequence on a compact set, it has a convergent subsequence. In addition, for any t^∈Ta, there is a sequence tr of tk with limr⟶∞tr=t^. By Tuy [43] and Lemma 1, it can be drawn that the partition for subhyperrectangle sets in Step 2 is exhaustive on T0 and the choice of subhyperrectangle to be subdivided in Step 2 is bound improving. Therefore, there is a decreasing subsequence Tq⊂Tr where Tr is the T space of the partition Qr with tq∈Tq, LBq=LBTq=ΨRTq, and limq⟶∞tq=t^. From Lemma 2, we have limq⟶∞LBq=LB=Ψt^.
Next, we prove that the conditiont^∈D is satisfied. T0 is a closed set, such that t^∈T0. Proved by contradiction, the above condition can be proved. Let t^∈D; there exists Ψt^=δ>0. Since Ψ is a continuous function, the sequence Ψtq can be converged to Ψt^. According to the convergence property of Ψ, ∃qδ such that Ψtq−Ψt^<δ as q>qδ. Hence, for q>qδ,Ψtq>0 implying that the problem (P2) is infeasible and violating the assumption that tq=tTq. This leads to a contradiction, and therefore, t^∈D. As a result, we obtain LB=Ψt^=mint∈DΨt,t^∈T∗. And the proof of Theorem 3 is completed.


## 3.4. Computational Complexity of the Algorithm

In this subsection, we analyze the computational complexity of the proposed algorithm by estimating the maximum number of iterations. In the process of branching operations, we denote the diameter of theTk=lk,uk⊆T0 by(43)ΔTk=maxj=1,2,…,pujk−ljk.Meanwhile, we introduce some notations as follows.(44)ρ=maxj=1,2,…,plnuj0−lnlj0uj0−lj0,(45)μ=∑j=1pγj.Lemma 3.
For given convergence toleranceε≥0, if the subhyperrectangle Tk⊆T0 is satisfied with ΔTk≤ε/μρ at the kth iteration, we have(46)UB−LBTk≤ε,where UB is current global upper bound of the equivalent problem and LBTk indicates the linear relaxation solution of current subhyperrectangle.Proof.
Assuming thattk is the optimal solution of the linear relaxation problem, we have(47)ψRtk=LBTk≤UB=ψtk.
According to (4) and (19), we can conclude that(48)UB−LBTk=ψt−ψRtk=∑j=1pγjftjk−∑j=1,γj>0pγjhjtjk−∑j=1,γj<0pγjgjtjk=∑j=1,γj>0pγjftjk−hjtjk+∑j=1,γj<0pγjftjk−gjtjk.
Then, by using (16) and (17), we have(49)UB−LBTk=∑j=1pγjlnuj−lnlj−kjtj−lj≤∑j=1pγjlnuj−lnlj=∑j=1pγjρjuj−lj≤μρΔTk.
From the previous formula and the condition ofΔTk≤ε/μρ, we can obtain that UB−LBTk<ε.. This completes the proof of Lemma 3.Theorem 4.
Given the convergence toleranceε≥0, the maximum iterations of the proposed algorithm to obtain the ε -globally optimal solution are(50)N=∑j=1plog2μρuj−ljε,where μ and ρ are given in (44) and (45), respectively.Proof.
Suppose that, at thekj.th iteration, the subhyperrectangle Tk⊆T0 is satisfying with(51)ΔTk≤εμρ.
Meanwhile, according to the branching operation in Step 2, we have(52)ΔTjk=12kjuj0−lj0,j=1,2,…,p.
From (51) and (52), we obtain(53)12kjuj0−lj0≤εμρ,j=1,2,…,p,i.e.,(54)kj≥log2μρuj0−lj0ε,j=1,2,…,p.
With the proof of Lemma3, we can get that ψt−ψRtk≤ε. Denote(55)kj¯=log2μρuj0−lj0ε,j=1,2,…,p.
After at most iterations,(56)N=∑j=1pkj¯,=∑j=1plog2μρuj0−lj0ε, we have(57)UB−LBT≤ψt∗−ψRt∗≤ε.where t∗ is the optimal solution of the equivalent problem (P2). Therefore, we obtain the ε -globally optimal solution. The proof of Theorem 3 is completed.


## 4. Numerical Experiment

In this section, we give some numerical experiments to verify the performance of the proposed global optimization algorithm. These experiments are carried out on a workstation running Microsoft Windows 10 with Intel(R) Xeon(R) E5-2620 2.10 GHz processor and 16 GB memory. The proposed algorithm is written in Python programming language (v3.7) and the elementary simplex method is used to solve the linear relaxation programming. The corresponding numerical results are demonstrated in Tables1, 2, and 3.Table 1
Computational comparisons among algorithms of [19, 31, 36–41] and our new algorithm for Examples 1–6.
Refs.Optimal solutionOptimumIterTimeε1[36](1.9999998, 7.9999988)10.0000090410.0210−5[37](2.0, 8.0)10.0485.078010−3[38](2.0, 8.0)10.010.012810−6[39](2.0, 8.0)10.010.04610−4[40](2.0000, 8.0000)10.000020.018210−6Ours(2.0000, 8.0000)10.000010.015610−62[37](1.3148, 0.1396, 0.0, 0.4233)0.890210.188010−3[38](1.3148, 0.1396, 0.0, 0.4233)0.890210.060110−6[39](1.3148, 0.1396, 0.0, 0.4233)0.890210.09310−4[40](1.3148, 0.1396, 0.0, 0.4233)0.890210.022610−6[41](1.3148, 0.1396, 0.0, 0.4233)0.8901930.0470.05Ours(1.3148, 0.1396, 0.0, 0.4233)0.890210.019910−63[40](1.0000, 2.0000, 1.0000, …)9503.999920.069110−6Ours(1.0000, 2.0000, 1.0000, …)9504.000110.028010−64[40](0.0000, 0.0000, 2.7999)1.680090.137710−6Ours(0.0000, 0.0000, 2.8000)1.680060.109910−65[19](0.0, 8.0, 1.0, …)0.90123530.0469—[36](8.0, 0.0, 1.0, …)0.90123530.0010−3[40](0.0, 8.0, 1.0, …)0.90123550.074310−3Ours(8.0, 0.0, 1.0, …)0.90123530.051210−66[31](3, 2)5.00930620.5439910−6Ours(3.0, 2.0)5.00930910.010910−6Table 2
Computational comparisons among the algorithm of [40] and our new algorithm for problem 1.
pm,nReference [40]OursAvg.TimeAvg.IterAvg.TimeAvg.Iter2(10, 20)0.14524.60.06814.4(20, 40)0.15143.90.16607.3(40, 80)0.24415.20.400910.5(60, 120)0.61796.80.57359.5(80, 160)1.98866.50.88428.6(100, 200)4.10278.41.43799.73(10, 20)0.320510.70.211813(20, 40)0.32869.70.468621(40, 80)0.706012.91.047126.9(60, 120)2.791120.81.429024(80, 160)6.768827.51.752221.4(100, 200)14.277231.03.0576224(10, 20)0.665410.80.496329(20, 40)1.166825.10.802037.6(40, 80)2.278046.42.190256.5(60, 120)6.579776.53.121552.5(80, 160)14.768843.83.802345.4(100, 200)46.849479.27.544954.15(10, 20)1.260945.70.788247.1(20, 40)1.392945.71.536469.1(40, 80)10.4108117.62.761770.8(60, 120)18.3711143.44.510776.4(80, 160)81.1816310.27.014883.5(100, 200)114.7671230.612.2047896(10, 20)1.728743.81.083065(20, 40)6.650677.02.031793.7(40, 80)16.3945133.14.4962115.1(60, 120)25.2491387.18.1542138.5(80, 160)98.5674315.361112.4520146.5(100, 200)120.0034657.821.0908140.27(10, 20)19.2006458.81.691896.4(20, 40)23.8151496.62.4351123.1(40, 80)86.12291177.37.4351183.5(60, 120)155.5248640.213.9036234.2(80, 160)278.3208891.119.4804226.5(100, 200)321.4063469.326.9879193.5Table 3
Computational comparisons among the algorithms of [21, 45, 47] and our new algorithm for Problem2.
m,n[21][45][46]OursAvg (Std)Avg (Std)Avg (Std)Avg (Std)Avg (Std)Avg (Std)Avg (Std)Avg (Std)TimeIterTimeIterTimeIterTimeIter(10, 20)0.1 (0.1)6.2 (4.3)0.6062 (0.0695)14.2 (1.5492)0.0177 (0.0176)8.5833 (4.3580)0.0318 (0.0170)1.6 (1.1738)(20, 20)0.2 (0.1)7.0 (2.8)0.8368 (0.0756)17.4 (1.7127)0.0195 (0.0087)8.9167 (4.1661)0.0291 (0.0111)1.3 (0.6749)(22, 20)0.2 (0.1)8.8 (4.2)0.9460 (0.1235)18.5 (1.9003)0.0558 (0.0204)3.4167 (0.7930)0.0324 (0.0105)1.4 (0.6992)(20, 30)0.3 (0.1)8.0 (3.6)1.0781 (0.0674)19.9 (0.5676)0.0911 (0.0326)6.0833 (1.9287)0.0562 (0.0308)2.9 (1.9692)(35, 50)1.0 (0.4)11.0 (3.5)1.8415 (0.1338)21.2 (0.4316)0.1179 (0.0496)6.75 (2.4909)0.0780 (0.0245)2.8 (1.1353)(45, 60)1.2 (0.3)13.3 (4.9)2.4338 (0.1016)23.0 (0.6667)0.1674 (0.0333)9.6154 (1.7578)0.0764 (0.0326)2.2 (1.2293)(45, 100)3.9 (1.2)15.2 (6.0)5.1287 (0.0935)35.7 (1.1595)0.2293 (0.0377)11.2308 (1.7394)0.1467 (0.5389)4.2 (2.0976)(60, 100)5.6 (1.2)14.8 (3.8)6.8143 (0.1713)36.1 (0.7379)0.2502 (0.0321)11.8462 (1.3445)0.0944 (0.0214)2.3 (0.6749)(70, 100)6.5 (3.0)17.5 (7.2)8.1967 (0.2121)36.6 (1.2649)0.2745 (0.0760)8.3077 (2.3939)0.1021 (0.0285)2.2 (0.7888)(70, 120)9.0 (1.8)17.2 (4.8)9.5642 (0.2975)39.1 (1.6633)0.3115 (0.0750)8.8461 (2.2674)0.1513 (0.0437)3.3 (1.0594)(100, 100)7.6 (1.0)13.3 (4.3)13.0578 (0.3543)37.5 (2.1731)0.3279 (0.0231)6.3077 (0.9473)0.0956 (0.0406)1.7 (0.9487)Some exact tests in recent literatures [19, 31, 36–41] are implemented to show that the proposed algorithm can globally solve the problem (MP) effectively. For these tests, the results obtained by the proposed algorithm are illustrated in Table 1. To describe the numerical results, we use the following notations for column headers in Table 1: Iter: the number of iterations; time: the execution time in seconds; optimum: the approximation optimal value; optimal solution: the approximation optimal solution for the tests; ε: the accuracy tolerance value.The experiment results show that our algorithm can globally solve the problem (MP) effectively.Example 1.
We have (see [36–40])(58)minx1+x2x1−x2+7,s.t.2x1+x2≤14,x1+x2≤10,−4x1+x2≤0,2x1+x2≥6,x1+2x2≥6,x1−x2≤3,x1+x2≥0,x1−x2+7≥0,x1≥0,x2≥0.Example 2.
We have (see [37–41])(59)minfx=0.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.Example 3.
We have (see [40])(60)minfx=−4x1−2x4+3x5+214x1+2x2+3x3−4x4+4x5−3×3x1+4x2+2x3−2x4+2x5−7−2x1+x2−2x3+2x5+11s.t.4x1+4x2+5x3+3x4+x5≤25,−x1−5x2+2x3+3x4+x5≤2,x1+2x2+x3−2x4+2x5≥6,4x2+3x3−8x4+11x5≥8,x1+x2+x3+x4+x5≤6,x1≥1,x2≥1,x3≥1,x4≥1,x5≥1.Example 4.
We have (see [40])(61)min−x1+2x2+6x1+x2−x3+3x1+x2−2x3+7,s.t.x2−2x3≤1,3x1−3x2+4x3≤12,3x2−5x3≥−14,x1≥0,x2≥0,x3≥0.Example 5.
We have (see [19, 36, 40])(62)minc1Tx+d1c2Tx+d2,s.t.Ax=b,x≥0,where(63)b=81,72,72,9,9,9,8,8T,d1=0,d2=0,c1=1,0,19,0,0,0,0,0,0,0,0T,c2=0,1,19,0,0,0,0,0,0,0,0T,A=992100000008180100000018800100000711000−100001710000−100011700000−1001000000001001000000001.Example 6.
We have [31](64)min3x1−2x2−22/3x1+2x2+22/5s.t.2x1−x2≥2,x1−2x2≤2,x1+x2≤5,3≤x1≤5,1≤x2≤3.
As shown in Table1, compared with the other algorithms [19, 31, 36–41], it can be seen that the proposed algorithm can solve Examples 1–6 with fewer iterations and less time.
In order to illustrate the performance of the proposed algorithm in the complex environment, we perform a series of random problems as follows.Problem 1.
We get (see [40])(65)min∏j=1pcjTx,s.t.x∈X=x|Ax≤b,x∈0,1,Problem 2.
We get (see [21, 45, 46])(66)min∏j=12cjTx+1,s.t.x∈X=x|Ax≤b,x≥0.
In problems (1) and (2), each element of the vectors cj is pseudorandom number generated in 0,1, all of the elements aij of the constraint matrix A are randomly generated in the interval −1,1, and bi,i=1,2,…,m is generated by bi=∑j=1naij+2η, where η is pseudorandom number generated in 0,1.
For the numerical experiments for problems (1) and (2), we perform 10 different random instances at every different scale and record the statistics information of these results in Table 2 and 3, respectively. To compare the performance of the algorithm, we set tolerance accuracy value ε=10−6.
In Tables2 and 3, Avg.Time and Avg.Iter represent the average CPU times in seconds and the average number of iterations. Std.Time and Std.Iter illustrate the standard deviation of CPU times and the standard deviation of the number of iterations.
According to the computational results shown in Table2, when p is fixed at 2, 3, 4, 5, 6, and 7 in turn, it is obvious that the elapsed CPU time of the proposed algorithm is better than what is mentioned by Zhang and Gao [40]. On the other hand, when p is smaller than 4, the number of iterations is approximately the same as that of Zhang and Gao [40]. When p is greater than 4, the number of iterations will be greatly reduced. That is, the proposed algorithm can effectively solve larger scale problems (problem 1).
Table3 illustrates that the proposed algorithm can solve problem (2) with less computational time and fewer iterations. Meanwhile, the stability of the proposed algorithm is as good as that of Shen and Huang [46]. In addition, it is clear that the average CPU time and average iteration of the algorithm increase linearly and slowly with the scale of the problem when p is constant.
From the above numerical results, it can be concluded that the proposed algorithm can solve all examples with effectiveness and robustness.


## 5. Conclusion

In this paper, we study a class of multiplicative programming problems (MP) and propose a new image space branch and bound algorithm. In this algorithm, using the transformation of the logarithmic function, we transform the problem (MP) into the problem (P2). Then, based on the linear relaxation technique, we construct the linear relaxation programming problem for the problem (P2). Different from the existing algorithm, the branch operations of the proposed algorithm take place in p-dimensional image space which brings great benefits for improving the computational efficiency of the proposed algorithm. In addition, the ε-global convergence of the proposed algorithm is achieved at most ∑j=1plog2μρuj0−lj0/ε iterations. The numerical results demonstrate the feasibility and the efficiency of our algorithm. Our future work is to improve the universality of generalized linear multiplicative problems.



---

*Source: 1565764-2022-07-20.xml*