# An Out Space Accelerating Algorithm for Generalized Affine Multiplicative Programs Problem

Authors: Lei Cai; Shuai Tang; Jingben Yin; Zhisong Hou; Hongwei Jiao
Journal: Journal of Control Science and Engineering
 (2017)

---

## Abstract

This paper presents an out space branch-and-bound algorithm for solving generalized affine multiplicative programs problem. Firstly, by introducing new variables and constraints, we transform the original problem into an equivalent nonconvex programs problem. Secondly, by utilizing new linear relaxation technique, we establish the linear relaxation programs problem of the equivalent problem. Thirdly, based on the out space partition and the linear relaxation programs problem, we construct an out space branch-and-bound algorithm. Fourthly, to improve the computational efficiency of the algorithm, an out space reduction operation is employed as an accelerating device for deleting a large part of the investigated out space region. Finally, the global convergence of the algorithm is proved, and numerical results demonstrate the feasibility and effectiveness of the proposed algorithm.


---

## Body

## 1. Introduction

The generalized affine multiplicative programs problemGAMP arises naturally in many practical applications including management science, engineering optimization design, optimal control, Euclidean geometry, economic planning, production planning, and combinatorial mathematics [1, 2]. The problem GAMP usually contains many local optimum points which are not global optimum solution, so that important theoretical difficulties and computational complexities exist. Therefore, it is very necessary to establish an effective algorithm for globally solving the problem GAMP.The mathematical modelling of the generalized affine multiplicative programs problem is given as follows:GAMPv=max⁡fy=∑i=1p∑j=1ncijyj+di∑j=1neijyj+fis.t.y∈Y=y∣Ay≤b,where p≥2, cij,eij,di,fi∈R, i=1,…,p, j=1,…,n.In the last decades, many algorithms have been intended for solving the generalized linear multiplicative programming problem, such as parametric simplex algorithms [3, 4], quadratic programming algorithms [5–9], rectangle branch-and-bound algorithms [10, 11], approximate algorithms [12, 13], finite algorithm [14], outcome space algorithm [15], cutting plane algorithm [16], heuristic algorithm [17], monotonic optimization algorithms [18, 19], and simplicial branch-and-bound algorithm [20]. Although there exist some algorithms which can be used to solve the generalized linear multiplicative programming problem, as far as we know, it is still necessary to propose a more efficient algorithm for globally solving GAMP.In this paper, we shall present an effective algorithm for globally solvingGAMP. First of all, we transform GAMP into an equivalent problem EQ. Secondly, by utilizing the new linear relaxation technique, we systematically convert EQ into a series of linear relaxation programs problems, which can infinitely approximate the global optimal solution of EQ by a successive partition. Thirdly, based on the out space partition and the linear relaxation programs problem, we construct an out space branch-and-bound algorithm. In this algorithm, the proposed branching operation takes place in Rp, rather than Rn or R2p; this economizes the required computation. Fourthly, to improve the computational efficiency of the algorithm, an out space reduction operation is employed as an accelerating device for deleting a large part of the investigated out space region. Finally, the global convergence of the algorithm is proved, and numerical experimental results demonstrate the feasibility and effectiveness of the proposed algorithm.This paper is organized as follows. In Section2, by introducing new variables and constraints, we establish the equivalent problem EQ of the initial problem GAMP. Next, by utilizing the linearization technique, we derive the linear relaxation programming problem of EQ, which can provide a reliable upper bound for the global optimal value of the EQ. In Section 3, an out space region reduction operation is introduced, and by combining this operation with bounding technique, an out space accelerating branch-and-bound algorithm is established and its global convergence is proved. Section 4 presents the numerical experimental results obtained by solving some test examples. Finally, the some concluding remarks of this paper are elaborated.


## 2. Equivalent Problem and Its Linear Relaxation

In this section, we will convert the problemGAMP into an equivalent nonconvex problem EQ. Since ∑j=1ncijyj+di and ∑j=1neijyj+fi are all finite affine functions defined in Y, there exist positive constant numbers Mi and Ni such that ∑j=1ncijyj+di+Mi>0 and ∑j=1neijyj+fi+Ni>0 for any y∈Y. Therefore, in the following, without loss of generality, we can assume that ∑j=1ncijyj+di≥0 and ∑j=1neijyj+fi≥0 for all y∈Y.Without loss of generality, we let(1)Li0=miny∈Y∑j=1neijyj+fi,Ui0=maxy∈Y∑j=1neijyj+fi,i=1,…,p.Define the set Z0={z∈Rp∣Li0≤zi≤Ui0,i=1,…,p}. For any y∈Y and z∈Z0, define the function g(y,z)=∑i=1p[zi(∑j=1ncijyj+di)], and consider the following equivalent problem: EQmax⁡gy,z=∑i=1pzi∑j=1ncijyj+dis.t.∑j=1neijyj+fi-zi≥0,i=1,…,p,y∈Y,z∈Z0.Obviously, if(y∗,z∗) is a global optimal solution for EQ, then y∗ is a global optimal solution for GAMP, and zi∗=∑j=1neijyj∗+fi, i=1,…,p. If y∗ is a global optimal solution for GAMP, then (y∗,z∗) is a global optimal solution for EQ, where zi∗=∑j=1neijyj∗+fi, i=1,…,p.In the following, the main computation is to globally solveEQ. Next, we will construct the linear relaxation programs problem of EQ, which can provide the upper bounds for EQ in the proposed branch-and-bound algorithm. Assume that Z={z∈Rp∣Li≤zi≤Ui,i=1,…,p}⊆Z0. And without loss of generality, let (2)Ti+=j∣cij≥0,j=1,…,n,Ti-=j∣cij<0,j=1,…,n,Di+=i∣di≥0,i=1,…,p,Di-=i∣di<0,i=1,…,p.Then the linear relaxation programs UZ of EQ in Z can be given as follows: UZuZ=max∑i=1p∑Ti+Uicijyj+∑Ti-Licijyj+∑Di+Uidi+∑Di-Lidis.t.Li-∑j=1neijyj+fi≤0,i=1,…,p,y∈Y,where EQ in Z is defined by EQZvZ=maxgy,z=∑i=1pzi∑j=1ncijyj+dis.t.∑j=1neijyj+fi-zi≥0,i=1,…,p,y∈Y,z∈Z⊆Z0.Theorem 1.
(i) For anyZ⊆Z0, one has uZ≥vZ. (ii) If Z-={z∈Rp∣L-≤z≤U-}⊆Z and Z-≠∅, then uZ-≤uZ.Proof.
(i) IfvZ=-∞, then we can easily obtain uZ=-∞; it is obvious that uZ≥vZ, if vZ is finite and achieved. Denote by (y-,z-) a global optimal solution for EQZ. Then y-∈Y, z-∈Z. For each i∈{1,…,p}, we have Li≤z-i≤Ui. Therefore, we have (3)∑i=1pz-i∑j=1ncijy-j+di≤∑i=1p∑Ti+Uicijy-j+∑Ti-Licijy-j+∑Di+Uidi+∑Di-Lidi.Since (y-,z-) is a global optimal solution for EQZ, it follows that (4)vZ=∑i=1pz-i∑j=1ncijy-j+di.Since y- is a feasible solution for UZ, (5)uZ≥∑i=1p∑Ti+Uicijy-j+∑Ti-Licijy-j+∑Di+Uidi+∑Di-Lidi.By the above discussions, we have uZ≥vZ.
(ii) LetZ-={z∈Rp∣L-≤z≤U-}⊆Z and Z-≠∅; we have the following conclusions.
IfUZ is infeasible, then we can easily prove that (UZ-) is also infeasible; the conclusion is obvious.
IfUZ is feasible, since Y is compact set, then uZ is finite. If (UZ-) is infeasible, then uZ-=-∞<uZ. Thus, in the following, we assume that (UZ-) is feasible, then uZ- is finite, and there exists a point y-∈Y such that L-i≤∑j=1neijy-j+fi, i=1,…,p. And (6)uZ-=∑i=1p∑Ti+U-icijy-j+∑Ti-L-icijy-j+∑Di+U-idi+∑Di-L-idi.By Z-⊆Z, we have 0<Li≤L-i≤U-i≤Ui, i=1,…,p. It follows that y- is a feasible solution of problem UZ and (7)uZ-≤∑i=1p∑Ti+Uicijy-j+∑Ti-Licijy-j+∑Di+Uidi+∑Di-Lidi.Since y- is a feasible solution of UZ, we have (8)uZ≥∑i=1p∑Ti+Uicijy-j+∑Ti-Licijy-j+∑Di+Uidi+∑Di-Lidi.By the above discussions, we have uZ≥uZ-, and the proof is completed.By Theorem1, UZ can provide the valid upper bound for EQZ.


## 3. Algorithm and Its Convergence

In this section, we shall present a branch-and-bound algorithm for solvingEQ. The critical operation in guaranteeing the global convergence of the proposed algorithm is the selection of a suitable branching technique. In this paper, we choose a simple bisection method. For any selected rectangle Z^={z∈Rp∣L^i≤zi≤U^i,i=1,…,p}⊆Z0, this branching rule is given as follows:(1)
LetU^k-L^k=max⁡{U^i-L^i∣i=1,…,p}.(2)
Let(9)Z^1=z∈Rp∣L^i≤zi≤U^i,i=1,…,p,i≠k;L^k≤zk≤12L^k+U^k,Z^2=z∈Rp∣L^i≤zi≤U^i,i=1,…,p,i≠k;12L^k+U^k≤zk≤U^k.


### 3.1. New Region Reduction Operation

For any rectangleZk⊆Z0, during the process of iteration, we want to recognize whether or not Zk contains a global optimal solution of EQ. The proposed new reduction operation aims at replacing the rectangle Zk=[Lk,Uk] with a smaller rectangle Z′=[L′,U′] without deleting any global optimal solution of EQ.Without loss of generality, we can assume thatLBk is a known lower bound of the optimal value for EQ(Z0) and that v(Z) is the maximum value of g(y,z) over Z and Y, and let(10)li0=miny∈Y∑j=1ncijyj+di,i=1,2,…,p,ui0=maxy∈Y∑j=1ncijyj+di,i=1,2,…,p,RUBk=∑i=1pui0Uik,ρik=LBk-RUBk+ui0Uikui0,i=1,2,…,p.Theorem 2.
For any subrectangleZk=(Zik)p×1=[Lik,Uik]p×1⊆Z0, the following conclusions hold:(i)
IfRUBk<LBk, then there is no global optimal solution of EQ(Z0) over Zk.(ii)
IfRUBk≥LBk, then, for each s∈{1,2,…,p}, there is no global optimal solution of the EQ(Z0) over Z_k, where (11)Z_k=Z_ikp×1⊆Z0withZ_ik=Zik,i≠s,i=1,2,…,p,Lik,ρik∩Ziki=s∈1,2,…,p.Proof.
(i) IfRUBk<LBk, then we have (12)vZk=maxz∈Zk,y∈Y∑i=1p∑j=1ncijyj+dizi≤∑i=1pmaxz∈Zk,y∈Y∑j=1ncijyj+dizi=∑i=1pui0Uik=RUBk<LBk.Therefore, there exists no global optimal solution of the problem EQ(Z0) over Zk.
(ii) IfRUBk≥LBk, then we have the following conclusions.
For eachs∈{1,2,…,p}, for any y∈Y and z∈Z_k, and for each i=1,2,…,p, since (13)0≤li0≤∑j=1ncijyj+di≤ui0,0≤Lik≤zi≤Uik,i≠s,0≤Lsk≤zs≤ρsk,i=s,we have (14)vZ_k=maxz∈Z_k,y∈Y∑i=1p∑j=1ncijyj+dizi≤maxz∈Z_k,y∈Y∑i=1,i≠sp∑j=1ncijyj+dizi+maxz∈Z_k,y∈Y∑j=1ncsjyj+dszs<∑i=1,i≠spui0Uik+us0ρsk=RUBk-us0Usk+LBk-RUBk-us0Usk=LBk.Therefore, there exists no global optimization solution of EQ(Z0) over Z_k.By Theorem2, we can construct a new reduction operation to cut away a part of region in which the global optimal solution of EQ does not exist. Assuming that a subrectangle (15)Zk=Zikp×1⊆Z0withZik=Lik,Uikwill be compressed, then, according to Theorem 2, the original rectangle Zk should be replaced with a new subrectangle:(16)Z′=Zi′p×1withZi′=ρik,Uik∩Zik,i∈1,2,…,p.LetUB(Zk) be the optimal value of UZ in Zk; the basic steps of the proposed algorithm are summarized as follows.


### 3.2. Algorithm Steps

Step 0.
Initialize the iteration counterk=0, the active node set Ω0={Z0}, the lower bound LB0=-∞, and the feasible points set F=∅.
Solve(UZ0); obtain uZ0 and y(Z0). Set UB0=UB(Z0)=uZ0, yc=y(Z0), and set zic=∑j=1neijyjc+fi (i=1,2,…,p), LB0=g(yc,zc). Update F=F∪{(yc,zc)}.
IfUB0-LB0≤ϵ, then the algorithm stops with (yc,zc) and yc as global optimal solutions of EQ and GAMP, respectively. Otherwise, proceed to next step.Step 1.
Use the proposed reduction operation to compress the investigated rectangleZk, and still represent remaining part of the rectangle as Zk.Step 2.
SubdivideZk into two subrectangles; denote by Θk its partitioning set.
For eachZ∈Θk, solve UZ to obtain UB(Z)=uZ and y(Z). If UB(Z)<LBk, then remove the subrectangle Z from Θk, that is, Θk≔Θk∖Z, and skip to next element of Θk.
IfΘk=∅, set LBk+1=LBk, and go to Step 3. Otherwise, set zic=zi(Z)=∑j=1neijyj(Z)+fi, i=1,2,…,p, update F=F∪{(y(Z),z(Z))}, set LBk+1=max(y,z)∈Fg(y,z), and denote by (yc,zc)=argmax(y,z)∈Fg(y,z) the best known feasible point.Step 3.
Denote byΩk+1=(Ωk∖Zk)∪Θk the remaining partition set. We can obtain a new upper bound UBk≔infZ∈Ωk+1UB(Z).Step 4.
Fathom any nonimproving nodes by settingΩk+1=Ωk∖{Z:UB(Z)-LB≤ϵ,Z∈Ωk}. If Ωk+1=∅, then stop: LB is the optimal value of EQ, and yc is a global ϵ-optimal solutions for GAMP. Otherwise, set k=k+1 and return to Step 1.


### 3.3. Convergence of the Algorithm

In this subsection, the convergence of the algorithm is given.Theorem 3.
If the algorithm is finite, upon termination, we can obtain theϵ-global optimal solutions for the problems EQ and GAMP, respectively. If the algorithm is infinite, for each k≥0, denote by yk the incumbent solution of GAMP, which is found at the end of iteration k. Then, limk→∞yk=y∗ will a global optimal solution for GAMP.Proof.
If the algorithm is finite, then the algorithm terminates at iterationk, k≥0. By the termination condition of the algorithm and the updating method of the upper bound, it can follow easily that the conclusion is obvious.
If the algorithm is infinite, then, it generates a sequence of incumbent solutions for problemEQ, which may be denoted by {(yk,zk)}. For each k≥1, (yk,zk) is found by solving problem UZk, for some rectangle Zk⊆Z0, for an optimal solution yk∈Y, and setting zik=∑j=1neijyjk+fi, i=1,…,p. Therefore, the sequence {yk} consists of feasible solutions for problem GAMP. Let y∗ be an accumulation point of {yk}, and without loss of generality we assume that limk→∞yk=y∗. Then, since Y is a compact set, y∗∈Y. Furthermore, since {yk} is infinite, we may assume without loss of generality that, for each k, Zk+1⊆Zk. Since the rectangles Zk, k≥1, are formed by rectangular bisection, this implies that, for some point z∗∈Rp, we have (17)limk→∞Zk=⋂kZk=z∗.Let Z∗={z∗} and, for each k, let Zk be given by (18)Zk=z∈Rp∣Lk≤z≤Uk.For each k, from Step 2 of the algorithm, (19)UBZk=uZk.Since Zk+1⊂Zk⊆Z0, for each k, by Theorem 1 and Step 4, this implies that {UB(Zk)} is a nonincreasing sequence bounded by v. Therefore, limk→∞UB(Zk) is a finite number and satisfies (20)limk→∞UBZk≥v.For each k, from Step 1, UB(Zk) is equal to the optimal value of problem UZk given by UZkmax⁡∑i=1p∑Ti+Uikcijyj+∑Ti-Likcijyj+∑Di+Uikdi+∑Di-Likdis.t.Lik-∑j=1neijyj+fi≤0,i=1,…,p,y∈Y,and yk is an optimal solution for this problem. By the branching technique, we have (21)limk→∞Lk=limk→∞Uk=z∗=Z∗.Since limk→∞yk=y∗, Lik≤∑j=1neijyjk+fi≤Uik and the continuity of (∑j=1neijyj+fi), for each i=1,…,p, ∑j=1neijyj∗+fi=zi∗. This implies that (y∗,z∗) is a feasible solution for EQ. Therefore, g(y∗,z∗)≤v. Combing (20), we obtain that (22)gy∗,z∗≤v≤limk→∞UBZk,since (23)limk→∞UBZk=limk→∞∑i=1p∑Ti+Uikcijyjk+∑Ti-Likcijyjk+∑Di+Uikdi+∑Di-Likdi=∑i=1pzi∗∑j=1ncijyj∗+di=gy∗,z∗.From (22) and (23), since UB(Zk)=UBk, we have limk→∞UBk=v=g(y∗,z∗). Therefore, (y∗,z∗) is a global optimal solution for EQ. By Theorem 1, this implies that y∗ is a global optimal solution for GAMP. The proof is complete.


## 3.1. New Region Reduction Operation

For any rectangleZk⊆Z0, during the process of iteration, we want to recognize whether or not Zk contains a global optimal solution of EQ. The proposed new reduction operation aims at replacing the rectangle Zk=[Lk,Uk] with a smaller rectangle Z′=[L′,U′] without deleting any global optimal solution of EQ.Without loss of generality, we can assume thatLBk is a known lower bound of the optimal value for EQ(Z0) and that v(Z) is the maximum value of g(y,z) over Z and Y, and let(10)li0=miny∈Y∑j=1ncijyj+di,i=1,2,…,p,ui0=maxy∈Y∑j=1ncijyj+di,i=1,2,…,p,RUBk=∑i=1pui0Uik,ρik=LBk-RUBk+ui0Uikui0,i=1,2,…,p.Theorem 2.
For any subrectangleZk=(Zik)p×1=[Lik,Uik]p×1⊆Z0, the following conclusions hold:(i)
IfRUBk<LBk, then there is no global optimal solution of EQ(Z0) over Zk.(ii)
IfRUBk≥LBk, then, for each s∈{1,2,…,p}, there is no global optimal solution of the EQ(Z0) over Z_k, where (11)Z_k=Z_ikp×1⊆Z0withZ_ik=Zik,i≠s,i=1,2,…,p,Lik,ρik∩Ziki=s∈1,2,…,p.Proof.
(i) IfRUBk<LBk, then we have (12)vZk=maxz∈Zk,y∈Y∑i=1p∑j=1ncijyj+dizi≤∑i=1pmaxz∈Zk,y∈Y∑j=1ncijyj+dizi=∑i=1pui0Uik=RUBk<LBk.Therefore, there exists no global optimal solution of the problem EQ(Z0) over Zk.
(ii) IfRUBk≥LBk, then we have the following conclusions.
For eachs∈{1,2,…,p}, for any y∈Y and z∈Z_k, and for each i=1,2,…,p, since (13)0≤li0≤∑j=1ncijyj+di≤ui0,0≤Lik≤zi≤Uik,i≠s,0≤Lsk≤zs≤ρsk,i=s,we have (14)vZ_k=maxz∈Z_k,y∈Y∑i=1p∑j=1ncijyj+dizi≤maxz∈Z_k,y∈Y∑i=1,i≠sp∑j=1ncijyj+dizi+maxz∈Z_k,y∈Y∑j=1ncsjyj+dszs<∑i=1,i≠spui0Uik+us0ρsk=RUBk-us0Usk+LBk-RUBk-us0Usk=LBk.Therefore, there exists no global optimization solution of EQ(Z0) over Z_k.By Theorem2, we can construct a new reduction operation to cut away a part of region in which the global optimal solution of EQ does not exist. Assuming that a subrectangle (15)Zk=Zikp×1⊆Z0withZik=Lik,Uikwill be compressed, then, according to Theorem 2, the original rectangle Zk should be replaced with a new subrectangle:(16)Z′=Zi′p×1withZi′=ρik,Uik∩Zik,i∈1,2,…,p.LetUB(Zk) be the optimal value of UZ in Zk; the basic steps of the proposed algorithm are summarized as follows.


## 3.2. Algorithm Steps

Step 0.
Initialize the iteration counterk=0, the active node set Ω0={Z0}, the lower bound LB0=-∞, and the feasible points set F=∅.
Solve(UZ0); obtain uZ0 and y(Z0). Set UB0=UB(Z0)=uZ0, yc=y(Z0), and set zic=∑j=1neijyjc+fi (i=1,2,…,p), LB0=g(yc,zc). Update F=F∪{(yc,zc)}.
IfUB0-LB0≤ϵ, then the algorithm stops with (yc,zc) and yc as global optimal solutions of EQ and GAMP, respectively. Otherwise, proceed to next step.Step 1.
Use the proposed reduction operation to compress the investigated rectangleZk, and still represent remaining part of the rectangle as Zk.Step 2.
SubdivideZk into two subrectangles; denote by Θk its partitioning set.
For eachZ∈Θk, solve UZ to obtain UB(Z)=uZ and y(Z). If UB(Z)<LBk, then remove the subrectangle Z from Θk, that is, Θk≔Θk∖Z, and skip to next element of Θk.
IfΘk=∅, set LBk+1=LBk, and go to Step 3. Otherwise, set zic=zi(Z)=∑j=1neijyj(Z)+fi, i=1,2,…,p, update F=F∪{(y(Z),z(Z))}, set LBk+1=max(y,z)∈Fg(y,z), and denote by (yc,zc)=argmax(y,z)∈Fg(y,z) the best known feasible point.Step 3.
Denote byΩk+1=(Ωk∖Zk)∪Θk the remaining partition set. We can obtain a new upper bound UBk≔infZ∈Ωk+1UB(Z).Step 4.
Fathom any nonimproving nodes by settingΩk+1=Ωk∖{Z:UB(Z)-LB≤ϵ,Z∈Ωk}. If Ωk+1=∅, then stop: LB is the optimal value of EQ, and yc is a global ϵ-optimal solutions for GAMP. Otherwise, set k=k+1 and return to Step 1.


## 3.3. Convergence of the Algorithm

In this subsection, the convergence of the algorithm is given.Theorem 3.
If the algorithm is finite, upon termination, we can obtain theϵ-global optimal solutions for the problems EQ and GAMP, respectively. If the algorithm is infinite, for each k≥0, denote by yk the incumbent solution of GAMP, which is found at the end of iteration k. Then, limk→∞yk=y∗ will a global optimal solution for GAMP.Proof.
If the algorithm is finite, then the algorithm terminates at iterationk, k≥0. By the termination condition of the algorithm and the updating method of the upper bound, it can follow easily that the conclusion is obvious.
If the algorithm is infinite, then, it generates a sequence of incumbent solutions for problemEQ, which may be denoted by {(yk,zk)}. For each k≥1, (yk,zk) is found by solving problem UZk, for some rectangle Zk⊆Z0, for an optimal solution yk∈Y, and setting zik=∑j=1neijyjk+fi, i=1,…,p. Therefore, the sequence {yk} consists of feasible solutions for problem GAMP. Let y∗ be an accumulation point of {yk}, and without loss of generality we assume that limk→∞yk=y∗. Then, since Y is a compact set, y∗∈Y. Furthermore, since {yk} is infinite, we may assume without loss of generality that, for each k, Zk+1⊆Zk. Since the rectangles Zk, k≥1, are formed by rectangular bisection, this implies that, for some point z∗∈Rp, we have (17)limk→∞Zk=⋂kZk=z∗.Let Z∗={z∗} and, for each k, let Zk be given by (18)Zk=z∈Rp∣Lk≤z≤Uk.For each k, from Step 2 of the algorithm, (19)UBZk=uZk.Since Zk+1⊂Zk⊆Z0, for each k, by Theorem 1 and Step 4, this implies that {UB(Zk)} is a nonincreasing sequence bounded by v. Therefore, limk→∞UB(Zk) is a finite number and satisfies (20)limk→∞UBZk≥v.For each k, from Step 1, UB(Zk) is equal to the optimal value of problem UZk given by UZkmax⁡∑i=1p∑Ti+Uikcijyj+∑Ti-Likcijyj+∑Di+Uikdi+∑Di-Likdis.t.Lik-∑j=1neijyj+fi≤0,i=1,…,p,y∈Y,and yk is an optimal solution for this problem. By the branching technique, we have (21)limk→∞Lk=limk→∞Uk=z∗=Z∗.Since limk→∞yk=y∗, Lik≤∑j=1neijyjk+fi≤Uik and the continuity of (∑j=1neijyj+fi), for each i=1,…,p, ∑j=1neijyj∗+fi=zi∗. This implies that (y∗,z∗) is a feasible solution for EQ. Therefore, g(y∗,z∗)≤v. Combing (20), we obtain that (22)gy∗,z∗≤v≤limk→∞UBZk,since (23)limk→∞UBZk=limk→∞∑i=1p∑Ti+Uikcijyjk+∑Ti-Likcijyjk+∑Di+Uikdi+∑Di-Likdi=∑i=1pzi∗∑j=1ncijyj∗+di=gy∗,z∗.From (22) and (23), since UB(Zk)=UBk, we have limk→∞UBk=v=g(y∗,z∗). Therefore, (y∗,z∗) is a global optimal solution for EQ. By Theorem 1, this implies that y∗ is a global optimal solution for GAMP. The proof is complete.


## 4. Numerical Experiments

To verify the performance of the proposed algorithm, some test problems are implemented on an Intel(R) Core(TM)2 Duo CPU (1.58 GHZ) microcomputer. The algorithm is coded in C++, and each linear programs problem is solved by simplex method in our experiments. These test problems are given in the following, and their numerical results are listed in Tables1 and 2.Table 1
Computational results of Examples1 and 2.
Example
Ref.
Optimal solution
Optimal value
Iteration
ϵ
Time(s)
Example1
This paper
(0, 3.33333, 0)
11611.1
2
10-6
0.0065
[14]
(0, 3.33333, 0)
11611.1
2
1
0
-
6
0.0074
Example2
This paper
(0, 0.625, 1.875)
14214.8
1
1
0
-
6
0.0198
[14]
(0, 0.625, 1.875)
14214.8
2
1
0
-
6
0.0228Table 2
Numerical results for Example3.
n
p
Time(s)
10
10
0.0285
20
10
0.0192
30
10
0.0279
30
30
0.0590
30
40
0.1102
30
50
0.0945
35
50
0.1283
40
50
0.2423
50
50
0.2899Example 1 (see [14]).
One has(24)max3y1+5y2+3y3+50×3y1+4y2+5y3+50+3y1+4y2+50×4y1+3y2+2y3+50+4y1+2y2+4y3+50×5y1+4y2+3y3+50s.t.6y1+3y2+3y3≤10,10y1+3y2+8y3≤10,y1,y2,y3≥0.Example 2 (see [14]).
One has(25)max4y1+3y2+3y3+50×3y2+3y3+50+3y1+4y3+50×4y1+4y2+5y3+50+y1+2y2+5y3+50×y1+5y2+5y3+50+y1+2y2+4y3+50×5y2+4y3+50s.t.2y1+y2+5y3≤10,y1+6y2+3y3≤10,5y1+9y2+2y3≤10,9y1+7y2+3y3≤10,y1,y2,y3≥0.
In Table1, the notations have been used for column headers: iteration, number of iterations; time: execution time(s) of the algorithm in seconds.Example 3.
One has(26)max∑i=1p∑j=1ncijyj+di∑j=1neijyj+fis.t.0≤yj≤γj,j=1,…,n,where cij,eij,di,fi,i=1,…,p,j=0,1,…,n are randomly generated between 0 and 1; γj (j=1,…,n) were randomly generated between 0 and 16.
Numerical results for Example3 are given in Table 2, where the convergence tolerance is set to ϵ=10-6.
From Tables1 and 2, it is seen that the proposed algorithm in this paper can be used to globally solve the problem GAMP with the effectiveness and robustness.


## 5. Concluding Remarks

In this article, an out space accelerating branch-and-bound algorithm is presented for globally solving the generalized affine multiplicative programs problemGAMP. First of all, we transform the GAMP into an equivalent problem EQ. By utilizing the new linear relaxation technique, we systematically convert EQ into a series of linear relaxation programs problems, which can infinitely approximate the global optimal solution of EQ by a successive partition. To improve the computational efficiency of the algorithm, we introduce an out space reduction operation, which offers a theoretical possibility of reducing a large part of the investigated out space region and which can be seen as an accelerating device for improving the convergent speed of the proposed algorithm. By combining the established linear relaxed programs problem with the new reduction operation in a branch-and-bound framework, we design an out space accelerating algorithm for effectively solving GAMP. By subsequently dividing the initial rectangle and subsequently solving a series of linear relaxed programs problems, the presented algorithm is convergent to the global minimum of GAMP. Compared with the known algorithms, numerical results demonstrate that the proposed algorithm has higher computational efficiency.



---

*Source: 5249160-2017-06-14.xml*