# A Simplicial Branch and Bound Duality-Bounds Algorithm to Linear Multiplicative Programming

Authors: Xue-Gang Zhou; Bing-Yuan Cao
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

A simplicial branch and bound duality-bounds algorithm is presented
to globally solving the linear multiplicative programming (LMP). We firstly convert the problem
(LMP) into an equivalent programming one by introducingp auxiliary variables. During the
branch and bound search, the required lower bounds are computed by solving ordinary linear
programming problems derived by using a Lagrangian duality theory. The proposed algorithm
proves that it is convergent to a global minimum through the solutions to a series of linear
programming problems. Some examples are given to illustrate the feasibility of the present
algorithm.


---

## Body

## 1. Introduction

### 1.1. Problem and Applications

In this paper, linear multiplicative programming problems are given by:(1)(LMP)v=minh(x)=∑i=1p(ciTx+ci0)(diTx+di0),s.t.x∈X={x∈Rn∣Ax⩽b,x⩾0},
where p⩾2, ciT=(ci1,ci2,…,cin), diT=(di1,di2,…,din)∈ℝn,i=1,2,…,p, bT=(b1,b2,…,bm)∈ℝm, ci0,di0∈ℝ,i=1,2,…,p, A is an m×n matrix, X⊆Rn is a nonempty, compact convex set. We assume also that for each i=1,2,…,p, diTx+di0>0. Generally, the problem (LMP) is a special case of non-convex programming problem, known to be an NP-hard even at p=1 [1].Problem (LMP) has many important applications. Since it subsumes quadratic programming, bilinear programming and linear zero-one programming as special cases, the applications appear quite numerous. Readers may refer to Benson [2] for the following analysis. Now the quadratic programming problem is given as follows:
(2)min12yTQy+dTy+c,s.t.y∈Y={y∈Rn∣Ay⩽b,y⩾0},
where Q is an n×n symmetric matrix of rank p,d∈Rn and c∈R. From Tuy [3], there exist linearly independent sets of n-dimensional vectors, {v1,v2,…,vp} and {w1,w2,…,wp}, such that, for all y∈Rn,
(3)12yTQy=12∑i=1p‍(viTy)(wiTy).
Thus, problem (LMP) encompasses the general quadratic programming problem as a special case, and the applications of problem (LMP) include all of the applications of general quadratic programming. Among the latter, for example, quadratic assignment problems [4], problems in economies of scale [5], the constrained linear regression problem [6], VLSI chip design problems [7], the linear complementarity problem [5], and portfolio analysis problems [6].The bilinear programming problem can be converted into the LMP and it may be written by(4)min12bTy+dTz+yTQz,s.t.y∈Y={y∈Rm∣Cy⩽c,y⩾0},z∈Z={z∈Rn∣Ez⩽e,z⩾0},
where b∈Rm, d∈Rn, c∈Rq, e∈Rr, Q is an m×n matrix of rank p, C and E are q×m matrix and r×n matrix, respectively. From Konno and Yajima [8], by using a constructive procedure, it can be written in the form
(5)min12bTy+dTz+∑i=1p(viTy)(wiTz),s.t.y∈Y,z∈Z,
where v1,v2,…,vp∈Rm and w1,w2,…,wp∈Rn. The latter is a special case of the LMP with xT=[yT,zT], h(x)=bTy+dTz+∑i=1p(αiTx)(βiTx), αiT=[viT,0T] and βiT=[0T,wiT], αi,βi∈Rm+n,i=1,2,…,p, and X={(y,z)∈Rm+n∣Cy⩽c,Ez⩽e,y,z⩾0}. Therefore, among the applications problem (P) are all of the applications of bilinear programming, including, for example, location-allocation problems [9], constrained bimatrix games [10], the three-dimensional assignment problem [11], certain linear max-min problems [12], and many problems in engineering design, economic management and operations research.A linear zero-one programming problem may be written as(6)(Q)min12bTy,s.t.y∈Y={y∈Rm∣Cy⩽c,y⩾0},yi∈{0,1},i=1,2,…,n,
where b∈Rm, c∈Rp,  C is p×m matrix. From Raghavachari [13], for M>0 sufficiently large, y* is an optimal solution to problem (Q) if and only if y* is an optimal solution to the problem
(7)(QC)min12bTy+M∑i=1nyi(1-yi),s.t.y∈Y={y∈Rm∣Cy⩽c,y⩾0},0⩽yi⩽1,i=1,2,…,n.
Since problem (QC) is a special case of the LMP, it follows that all of the numerous applications of linear zero-one programming are embodied among the applications of the LMP. For an overview of some of these applications, see Nemhauser and Wolsey [14].


### 1.2. Purpose and Content

The LMP is a global optimization problem. In the past 20 years, many algorithms have been proposed globally to a multiplicative programming one. The methods can be classified as parameterization based methods [2, 15–17], outer-approximation and branch-and-bound methods [18–25], vertex enumeration methods [26, 27], a method based on image space analysis [28], a primal and dual simplex method [29], an outcome-space cutting plane method [30], heuristic methods [31, 32], and decomposition method [33].In this paper, a simplicial branch and bound duality-bounds algorithm is presented to the problem (LMP) by solving a sequence of linear programming one over partitioned subsets. The algorithm implements a simplicial branch and bound search, finding a global optimal solution to the problem, equivalent to the problem (LMP). Branching takes place in a space of only dimensionp in the algorithm, where p is the number of terms in the objective function of problem (LMP). During the search, the required lower bounds are computed by solving ordinary linear programming problems. When the algorithm is infinite, any accumulation point of this sequence of feasible solutions is guaranteed to globally solve the problem. The proposed branch and bound algorithm is summarized as follows. Firstly, the branch and bound search takes place in a space of only dimension p, where p is the number of terms in the objective function of problem (LMP), rather than in the decision space ℝn. Secondly, the subproblems that must be solved during the search are all linear programming problems that can be solved very efficiently, for example, by a simplex method. The algorithms in this article are motivated by the seminal works of [34], the sum of linear ratios problem, and Horst and Tuy [35] by using branch and bound for global optimization.The organization and content of this article can be summarized as follows. In Section2, some preliminary results and operations are presented to implement the simplicial branch and bound duality-bounds algorithm. The simplicial branch and bound duality-bounds algorithm is given in Section 3. In Section 4, the convergence of the algorithm is established. In Section 5 some examples are solved to demonstrate that the proposed algorithm is effective. Some concluding remarks are given in Section 6.


## 1.1. Problem and Applications

In this paper, linear multiplicative programming problems are given by:(1)(LMP)v=minh(x)=∑i=1p(ciTx+ci0)(diTx+di0),s.t.x∈X={x∈Rn∣Ax⩽b,x⩾0},
where p⩾2, ciT=(ci1,ci2,…,cin), diT=(di1,di2,…,din)∈ℝn,i=1,2,…,p, bT=(b1,b2,…,bm)∈ℝm, ci0,di0∈ℝ,i=1,2,…,p, A is an m×n matrix, X⊆Rn is a nonempty, compact convex set. We assume also that for each i=1,2,…,p, diTx+di0>0. Generally, the problem (LMP) is a special case of non-convex programming problem, known to be an NP-hard even at p=1 [1].Problem (LMP) has many important applications. Since it subsumes quadratic programming, bilinear programming and linear zero-one programming as special cases, the applications appear quite numerous. Readers may refer to Benson [2] for the following analysis. Now the quadratic programming problem is given as follows:
(2)min12yTQy+dTy+c,s.t.y∈Y={y∈Rn∣Ay⩽b,y⩾0},
where Q is an n×n symmetric matrix of rank p,d∈Rn and c∈R. From Tuy [3], there exist linearly independent sets of n-dimensional vectors, {v1,v2,…,vp} and {w1,w2,…,wp}, such that, for all y∈Rn,
(3)12yTQy=12∑i=1p‍(viTy)(wiTy).
Thus, problem (LMP) encompasses the general quadratic programming problem as a special case, and the applications of problem (LMP) include all of the applications of general quadratic programming. Among the latter, for example, quadratic assignment problems [4], problems in economies of scale [5], the constrained linear regression problem [6], VLSI chip design problems [7], the linear complementarity problem [5], and portfolio analysis problems [6].The bilinear programming problem can be converted into the LMP and it may be written by(4)min12bTy+dTz+yTQz,s.t.y∈Y={y∈Rm∣Cy⩽c,y⩾0},z∈Z={z∈Rn∣Ez⩽e,z⩾0},
where b∈Rm, d∈Rn, c∈Rq, e∈Rr, Q is an m×n matrix of rank p, C and E are q×m matrix and r×n matrix, respectively. From Konno and Yajima [8], by using a constructive procedure, it can be written in the form
(5)min12bTy+dTz+∑i=1p(viTy)(wiTz),s.t.y∈Y,z∈Z,
where v1,v2,…,vp∈Rm and w1,w2,…,wp∈Rn. The latter is a special case of the LMP with xT=[yT,zT], h(x)=bTy+dTz+∑i=1p(αiTx)(βiTx), αiT=[viT,0T] and βiT=[0T,wiT], αi,βi∈Rm+n,i=1,2,…,p, and X={(y,z)∈Rm+n∣Cy⩽c,Ez⩽e,y,z⩾0}. Therefore, among the applications problem (P) are all of the applications of bilinear programming, including, for example, location-allocation problems [9], constrained bimatrix games [10], the three-dimensional assignment problem [11], certain linear max-min problems [12], and many problems in engineering design, economic management and operations research.A linear zero-one programming problem may be written as(6)(Q)min12bTy,s.t.y∈Y={y∈Rm∣Cy⩽c,y⩾0},yi∈{0,1},i=1,2,…,n,
where b∈Rm, c∈Rp,  C is p×m matrix. From Raghavachari [13], for M>0 sufficiently large, y* is an optimal solution to problem (Q) if and only if y* is an optimal solution to the problem
(7)(QC)min12bTy+M∑i=1nyi(1-yi),s.t.y∈Y={y∈Rm∣Cy⩽c,y⩾0},0⩽yi⩽1,i=1,2,…,n.
Since problem (QC) is a special case of the LMP, it follows that all of the numerous applications of linear zero-one programming are embodied among the applications of the LMP. For an overview of some of these applications, see Nemhauser and Wolsey [14].


## 1.2. Purpose and Content

The LMP is a global optimization problem. In the past 20 years, many algorithms have been proposed globally to a multiplicative programming one. The methods can be classified as parameterization based methods [2, 15–17], outer-approximation and branch-and-bound methods [18–25], vertex enumeration methods [26, 27], a method based on image space analysis [28], a primal and dual simplex method [29], an outcome-space cutting plane method [30], heuristic methods [31, 32], and decomposition method [33].In this paper, a simplicial branch and bound duality-bounds algorithm is presented to the problem (LMP) by solving a sequence of linear programming one over partitioned subsets. The algorithm implements a simplicial branch and bound search, finding a global optimal solution to the problem, equivalent to the problem (LMP). Branching takes place in a space of only dimensionp in the algorithm, where p is the number of terms in the objective function of problem (LMP). During the search, the required lower bounds are computed by solving ordinary linear programming problems. When the algorithm is infinite, any accumulation point of this sequence of feasible solutions is guaranteed to globally solve the problem. The proposed branch and bound algorithm is summarized as follows. Firstly, the branch and bound search takes place in a space of only dimension p, where p is the number of terms in the objective function of problem (LMP), rather than in the decision space ℝn. Secondly, the subproblems that must be solved during the search are all linear programming problems that can be solved very efficiently, for example, by a simplex method. The algorithms in this article are motivated by the seminal works of [34], the sum of linear ratios problem, and Horst and Tuy [35] by using branch and bound for global optimization.The organization and content of this article can be summarized as follows. In Section2, some preliminary results and operations are presented to implement the simplicial branch and bound duality-bounds algorithm. The simplicial branch and bound duality-bounds algorithm is given in Section 3. In Section 4, the convergence of the algorithm is established. In Section 5 some examples are solved to demonstrate that the proposed algorithm is effective. Some concluding remarks are given in Section 6.


## 2. Preliminaries

In this section, we firstly show how to convert the LMP into an equivalent nonconvex programming (LMP(S0)) by introducing a p-dimension vector y for finding a simplex. Then, for each p-dimensional simplex S created by the branching process, the lower bound LB(S) can be found by solving an ordinary linear program by using the Lagrangian weak duality theorem of nonlinear programming.


### 2.1. Initial Simplex

To globally solve the LMP, the branch and bound algorithm to be developed will be used for searching values ofdiTx+di0,i=1,2,…,p, at optimality. For each i=1,2,…,p, let li=minx∈X{diTx+di0}, and γi=maxx∈X{diTx+di0}. By introducing additional variable vector y=(y1,y2,…,yp)∈ℝp, we construct a set Y as follows:
(8)Y={y∈ℝp∣diTx+di0-yi⩽0,i=1,2,…,p,y∈D,forsomex∈X},
where D≜{y∈ℝp∣li⩽yi⩽γi,i=1,2,…,p}.In order to construct simplexS0, denoting γ=minx∈X∑i=1p(diTx+di0). Let S0∈Rp be the convex hull of v0,v1,…,vp, where vj0=γj,j=1,2,…,n, and, for each j=1,2,…,n,
(9)vji={γjifj≠i,γ-∑j≠i‍γjifj=i.
Notice that either γ=∑i=1pγi or γ<∑i=1pγi, and for any j=1,…,p,(vj-v0)T=(0,0,…,γ-∑i=1pγi,…,0), where γ-∑i=1pγi is the jth component of vj-v0. We can easily show the following theorem (see Benson [34]).Theorem 1.
S
0 is either a single point or S0 is a p-dimensional simplex. In either case, S0⊇Y.Remark 2.
From Theorem1, S0 is either a single point or S0 is a p-dimensional simplex. Notice that if S0 is a single one, that is, S0={y*} is a single one, then X={x*} is a single point set and x* is a global optimal solution to the LMP, where x* is any optimal solution to the linear program obtained by setting x equal to x* in problem (LMP(S0)). Therefore, we will assume in the remainder of this article that S0 is a p-dimensional simplex.


### 2.2. Equivalent Problem

For any simplexS⊂ℝp, define the problem
(10)(LMP(S))v(S)=minh¯(x,y)=∑i=1p(ciTx+ci0)yi,s.t.diTx+di0-yi⩽0,i=1,2,…,p,Ax-b⩽0,x⩾0,y∈S.In order to solve the LMP, the branch and bound algorithm is used to solves problem (LMP(S0)) instead. The validity of solving problem (LMP(S0)), in order to solve the LMP, follows from the next result.Theorem 3.
If(x*,y*) is a global optimal solution for problem (LMP(S0)), then x* is a global optimal solution for problem (LMP). If x* is a global optimal solution for problem (LMP), then (x*,y*) is a global optimal solution for problem (LMP(S0)), where yi*=diTx*+di0,i=1,2,…,p. The global optimal values v and v(S0) of problems (LMP) and (LMP(S0)), respectively, are equal.Proof.
By using the fact thatS0⊇Y, the proof of this theorem follows easily from the defintions of problem (LMP(S0)).


### 2.3. Duality Bound

For eachp-dimensional simplex S created by the branching process, the algorithm computes a lower bound LB(S) for the optimal value v(S) of problem (LMP(S)). The next theorem shows that, by using the Lagrangian weak duality theorem of nonlinear programming, the lower bound LB(S) can be found by solving an ordinary linear programming.Theorem 4.
LetS⊆ℝp be a p-dimensional simplex with vertices y¯0,y¯1,…,y¯p, and let J={0,1,2,…,p}. Then LB(S)⩽v(S), where LB(S) is the optimal value of the linear programming problem
(11)(LP(S))LB(S)=max∑i=1p‍θidi0-λTb+ts.t.-∑i=1p‍θidi-ATλ⩽C,∑i=1py¯ijθi+t⩽∑i=1p‍y¯ijci0,j=0,1,2,…,p,θ⩾0,λ⩾0,tfree,
where C∈ℝn and C=(minj∈J(∑i=1py¯ijci1), minj∈J(∑i=1py¯ijci2),…,minj∈J(∑i=1py¯ijcin))T.Proof.
By the definition ofv(S) and the weak duality theorem of Lagrangian duality, v(S)⩾LB(S), where
(12)LB(S)=maxθ⩾0λ⩾0{miny∈Sx⩾0[∑i=1p(ciTx+ci0)yi+∑i=1pθi[diTx+di0-yi]+λTAx-λTbminy∈Sx0[∑i=1p(ciTx+ci0)yi]}=maxθ⩾0λ⩾0{[〈∑i=1p(yiciT+θidiT)〉∑i=1pθidi0-λTb+miny∈Sx⩾0[〈∑i=1p(yiciT+θidiT)+λTA,x〉+∑i=1pyi(ci0-θi)]}.
Since(13)miny∈S〈∑i=1p(yiciT+θidiT)+λTA,x〉={0,∑i=1p(yiciT+θidiT)+λTA⩾0,∀x⩾0,-∞,otherwise,
it follows that,
(14)LB(S)=max{∑i=1p‍θidi0-λTb+miny∈S[∑i=1p‍yi(ci0-θi)]}s.t.∑i=1p‍(yiciT+θidiT)+λTA⩾0,∀y∈S,λ⩾0,θ⩾0.
Since S is a compact polyhedron with extreme points y¯j,j=0,1,2,…,p, for each θ∈ℝp and λ⩾0, ∑i=1p(yiciT+θidiT)+λTA⩾0 holds for all y∈S if and only if it holds for all y∈{y¯0,y¯1,…,y¯p}. So, for all j∈J, we can get ∑i=1p(y¯ijciT+θidiT)+λTA⩾0, that is,
(15)-∑i=1pθidiT-λTA⩽∑i=1py¯ijciT,∀j∈J.
Notice that for all j∈J, the left-hand-side of (15) is the same linear function of θ and λ, then (15) is equivalent to -∑i=1pθidi-ATλ⩽C, where C∈ℝn and C=(minj∈J(∑i=1py¯ijci1),…,minj∈J(∑i=1py¯ijcin))T.
Therefore,(16)(LB(S))=max[∑i=1p‍θidi0-λTb+miny∈S(∑i=1p‍yi(ci0-θi))]s.t.-∑i=1p‍θidi-ATλ⩽C,θ⩾0,λ⩾0.
That is,
(17)(LB(S))=max∑i=1p‍θidi0-λTb+ts.t.-∑i=1p‍θidi-ATλ⩽C,∑i=1p‍yi(ci0-θi)⩾t,θ⩾0,λ⩾0.
For any θ∈ℝp, yi(ci0-θi) is a linear function. Because simplex S is a compact polyhedron with extreme points y¯0,y¯1,…,y¯p, this implies for any θ∈ℝp, ∑i=1pyi(ci0-θi)⩾t holds if and only if
(18)∑i=1p‍y¯ij(ci0-θi)-t⩾0,j=0,1,2,…,p.
The proof is complete.Proposition 5.
LetS1,S2⊆ℝp be a p-dimensional subsimplices of S formed by the branching process such that S1⊆S2⊆S0. Then(i)
LB(S1)⩾LB(S2).(ii)
LetS⊆ℝpbe ap-dimensional simplex with verticesy¯0,y¯1,…,y¯p. ThenLB>-∞.Proof.
The proof is similar to [34, Proposition 3], it is omitted here.Remark 6.
From part (ii) of Proposition5, for any p-dimensional simplex S created by the algorithm during the branch and bound search, the duality bounds-based lower bound LB(S) for the optimal value v(S) of problem (LMP(S)) is either finite or equal to +∞. When LB(S)=+∞, problem (LMP(S)) is infeasible and, as we shall see, S will be eliminated from further consideration by the deletion by bounding process of the algorithm. The monotonicity property in part (i) of Proposition 5 will be used to help to show the convergence of the algorithm.
Now, we show how to determine an upper bound of the global optimal value for (LMP(S)). For each p-dimensional simplex S generated by the algorithm such that LB(S) is finite, the algorithm generates a feasible solution w to problem (LMP). As the algorithm finds more and more feasible solutions to it an upper bound for the optimal value v of it improves iteratively. These feasible solutions are found from dual optimal ones to the lower bounding problems (LP(S)) that are solved by the algorithm, as given in the following result.Proposition 7.
LetS⊆ℝp be a p-dimensional simplex with vertices y¯0,y¯1,…,y¯p, and suppose that LB(S)≠+∞. Let w∈ℝn be optimal dual variables corresponding to the first n constraints of linear program LP(S). Then w is a feasible solution for problem (LMP).Proof.
The dual linear program to problem (LP(S)) is
(19)DLP(S)LB(S)=minCTw+∑j=0p‍qj∑i=1p‍y¯ijci0s.t.-diTw+∑j=0p‍y¯ijqj⩾di0,i=1,2,…,p,-Aw⩾-b,∑j=0p‍qj=1,w⩾0.
The constraints of problem (DLP(S)) imply that Aw⩽b, w⩾0.


## 2.1. Initial Simplex

To globally solve the LMP, the branch and bound algorithm to be developed will be used for searching values ofdiTx+di0,i=1,2,…,p, at optimality. For each i=1,2,…,p, let li=minx∈X{diTx+di0}, and γi=maxx∈X{diTx+di0}. By introducing additional variable vector y=(y1,y2,…,yp)∈ℝp, we construct a set Y as follows:
(8)Y={y∈ℝp∣diTx+di0-yi⩽0,i=1,2,…,p,y∈D,forsomex∈X},
where D≜{y∈ℝp∣li⩽yi⩽γi,i=1,2,…,p}.In order to construct simplexS0, denoting γ=minx∈X∑i=1p(diTx+di0). Let S0∈Rp be the convex hull of v0,v1,…,vp, where vj0=γj,j=1,2,…,n, and, for each j=1,2,…,n,
(9)vji={γjifj≠i,γ-∑j≠i‍γjifj=i.
Notice that either γ=∑i=1pγi or γ<∑i=1pγi, and for any j=1,…,p,(vj-v0)T=(0,0,…,γ-∑i=1pγi,…,0), where γ-∑i=1pγi is the jth component of vj-v0. We can easily show the following theorem (see Benson [34]).Theorem 1.
S
0 is either a single point or S0 is a p-dimensional simplex. In either case, S0⊇Y.Remark 2.
From Theorem1, S0 is either a single point or S0 is a p-dimensional simplex. Notice that if S0 is a single one, that is, S0={y*} is a single one, then X={x*} is a single point set and x* is a global optimal solution to the LMP, where x* is any optimal solution to the linear program obtained by setting x equal to x* in problem (LMP(S0)). Therefore, we will assume in the remainder of this article that S0 is a p-dimensional simplex.


## 2.2. Equivalent Problem

For any simplexS⊂ℝp, define the problem
(10)(LMP(S))v(S)=minh¯(x,y)=∑i=1p(ciTx+ci0)yi,s.t.diTx+di0-yi⩽0,i=1,2,…,p,Ax-b⩽0,x⩾0,y∈S.In order to solve the LMP, the branch and bound algorithm is used to solves problem (LMP(S0)) instead. The validity of solving problem (LMP(S0)), in order to solve the LMP, follows from the next result.Theorem 3.
If(x*,y*) is a global optimal solution for problem (LMP(S0)), then x* is a global optimal solution for problem (LMP). If x* is a global optimal solution for problem (LMP), then (x*,y*) is a global optimal solution for problem (LMP(S0)), where yi*=diTx*+di0,i=1,2,…,p. The global optimal values v and v(S0) of problems (LMP) and (LMP(S0)), respectively, are equal.Proof.
By using the fact thatS0⊇Y, the proof of this theorem follows easily from the defintions of problem (LMP(S0)).


## 2.3. Duality Bound

For eachp-dimensional simplex S created by the branching process, the algorithm computes a lower bound LB(S) for the optimal value v(S) of problem (LMP(S)). The next theorem shows that, by using the Lagrangian weak duality theorem of nonlinear programming, the lower bound LB(S) can be found by solving an ordinary linear programming.Theorem 4.
LetS⊆ℝp be a p-dimensional simplex with vertices y¯0,y¯1,…,y¯p, and let J={0,1,2,…,p}. Then LB(S)⩽v(S), where LB(S) is the optimal value of the linear programming problem
(11)(LP(S))LB(S)=max∑i=1p‍θidi0-λTb+ts.t.-∑i=1p‍θidi-ATλ⩽C,∑i=1py¯ijθi+t⩽∑i=1p‍y¯ijci0,j=0,1,2,…,p,θ⩾0,λ⩾0,tfree,
where C∈ℝn and C=(minj∈J(∑i=1py¯ijci1), minj∈J(∑i=1py¯ijci2),…,minj∈J(∑i=1py¯ijcin))T.Proof.
By the definition ofv(S) and the weak duality theorem of Lagrangian duality, v(S)⩾LB(S), where
(12)LB(S)=maxθ⩾0λ⩾0{miny∈Sx⩾0[∑i=1p(ciTx+ci0)yi+∑i=1pθi[diTx+di0-yi]+λTAx-λTbminy∈Sx0[∑i=1p(ciTx+ci0)yi]}=maxθ⩾0λ⩾0{[〈∑i=1p(yiciT+θidiT)〉∑i=1pθidi0-λTb+miny∈Sx⩾0[〈∑i=1p(yiciT+θidiT)+λTA,x〉+∑i=1pyi(ci0-θi)]}.
Since(13)miny∈S〈∑i=1p(yiciT+θidiT)+λTA,x〉={0,∑i=1p(yiciT+θidiT)+λTA⩾0,∀x⩾0,-∞,otherwise,
it follows that,
(14)LB(S)=max{∑i=1p‍θidi0-λTb+miny∈S[∑i=1p‍yi(ci0-θi)]}s.t.∑i=1p‍(yiciT+θidiT)+λTA⩾0,∀y∈S,λ⩾0,θ⩾0.
Since S is a compact polyhedron with extreme points y¯j,j=0,1,2,…,p, for each θ∈ℝp and λ⩾0, ∑i=1p(yiciT+θidiT)+λTA⩾0 holds for all y∈S if and only if it holds for all y∈{y¯0,y¯1,…,y¯p}. So, for all j∈J, we can get ∑i=1p(y¯ijciT+θidiT)+λTA⩾0, that is,
(15)-∑i=1pθidiT-λTA⩽∑i=1py¯ijciT,∀j∈J.
Notice that for all j∈J, the left-hand-side of (15) is the same linear function of θ and λ, then (15) is equivalent to -∑i=1pθidi-ATλ⩽C, where C∈ℝn and C=(minj∈J(∑i=1py¯ijci1),…,minj∈J(∑i=1py¯ijcin))T.
Therefore,(16)(LB(S))=max[∑i=1p‍θidi0-λTb+miny∈S(∑i=1p‍yi(ci0-θi))]s.t.-∑i=1p‍θidi-ATλ⩽C,θ⩾0,λ⩾0.
That is,
(17)(LB(S))=max∑i=1p‍θidi0-λTb+ts.t.-∑i=1p‍θidi-ATλ⩽C,∑i=1p‍yi(ci0-θi)⩾t,θ⩾0,λ⩾0.
For any θ∈ℝp, yi(ci0-θi) is a linear function. Because simplex S is a compact polyhedron with extreme points y¯0,y¯1,…,y¯p, this implies for any θ∈ℝp, ∑i=1pyi(ci0-θi)⩾t holds if and only if
(18)∑i=1p‍y¯ij(ci0-θi)-t⩾0,j=0,1,2,…,p.
The proof is complete.Proposition 5.
LetS1,S2⊆ℝp be a p-dimensional subsimplices of S formed by the branching process such that S1⊆S2⊆S0. Then(i)
LB(S1)⩾LB(S2).(ii)
LetS⊆ℝpbe ap-dimensional simplex with verticesy¯0,y¯1,…,y¯p. ThenLB>-∞.Proof.
The proof is similar to [34, Proposition 3], it is omitted here.Remark 6.
From part (ii) of Proposition5, for any p-dimensional simplex S created by the algorithm during the branch and bound search, the duality bounds-based lower bound LB(S) for the optimal value v(S) of problem (LMP(S)) is either finite or equal to +∞. When LB(S)=+∞, problem (LMP(S)) is infeasible and, as we shall see, S will be eliminated from further consideration by the deletion by bounding process of the algorithm. The monotonicity property in part (i) of Proposition 5 will be used to help to show the convergence of the algorithm.
Now, we show how to determine an upper bound of the global optimal value for (LMP(S)). For each p-dimensional simplex S generated by the algorithm such that LB(S) is finite, the algorithm generates a feasible solution w to problem (LMP). As the algorithm finds more and more feasible solutions to it an upper bound for the optimal value v of it improves iteratively. These feasible solutions are found from dual optimal ones to the lower bounding problems (LP(S)) that are solved by the algorithm, as given in the following result.Proposition 7.
LetS⊆ℝp be a p-dimensional simplex with vertices y¯0,y¯1,…,y¯p, and suppose that LB(S)≠+∞. Let w∈ℝn be optimal dual variables corresponding to the first n constraints of linear program LP(S). Then w is a feasible solution for problem (LMP).Proof.
The dual linear program to problem (LP(S)) is
(19)DLP(S)LB(S)=minCTw+∑j=0p‍qj∑i=1p‍y¯ijci0s.t.-diTw+∑j=0p‍y¯ijqj⩾di0,i=1,2,…,p,-Aw⩾-b,∑j=0p‍qj=1,w⩾0.
The constraints of problem (DLP(S)) imply that Aw⩽b, w⩾0.


## 3. Global Optimizing Algorithm

To globally solve problem (LMP(S)), the algorithm to be presented uses a branch and bound approach. There are three fundamental processes in the algorithm, a branching process, a lower bounding one, and an upper bounding one.


### 3.1. Branching Rule

The branch and bound approach is based on partitioning thep-dimensional simplex S0 into smaller subsimplices that are also of dimension p, each concerned with a node of the branch and bound tree, and each node is associated with a linear subproblem on each subsimplicie. These subsimplices are obtained by the branching process, which helps the branch and bound procedure identify a location in the feasible region of problem (LMP(S0)) that contains a global optimal solution to the problem.During each iteration of the algorithm, the branching process creates a more refined partition of a portion inS=S0 that cannot yet be excluded from consideration in the search for a global optimal solution for problem (LMP(S)). The initial partition Q1 consists simply of S, since at the beginning of the branch and bound procedure, no portion of S can as yet be excluded from consideration.During iterationk of the algorithm, k⩾1, the branching process is used to help create a new partition Qk+1. First, a screening procedure is used to remove any rectangle from Qk that can, at this point of the search, be excluded from further consideration, and Qk+1 is temporarily set equal to the set of simplices that remain. Later in iteration k, a rectangle Sk in Qk+1 is identified for further examination. The branching process is then evoked to subdivide Sk into two subsimplices S1k,S2k. This subdivision is accomplished by a process called simplicial bisection.Definition 8 (see [35]).
LetS be a p-dimensional simplex with vertex set {v0,v1,…,vp}. Let w be the midpoint of any of the longest edges [vr,vt] of S. Then {S1,S2} is called a simplicialbisection of S, where the vertex set of S1 is {v0,v1,…,vr-1,w,vr+1,…,vp} and the vertex set of S2 is {v0,v1,…,vt-1,w,vt+1,…,vp}.


### 3.2. Lower Bound and Upper Bound

The second fundamental process of the algorithm is the lower bounding one. For each simplexS⊆S0 created by the branching process, this process gives a lower bound LB(S) for the optimal value v(S) of the following problem LMP(S),
(20)v(S)=minh(x)=∑i=1p‍(ciTx+ci0)yi,s.t.diTx+di0-yi⩽0Ax-b⩽0,x⩾0,y∈S.
For each simplex S created by the branching process, LB(S) is found by solving a single linear programming LP(S) as follows,
(21)(LB(S))=max∑i=1p‍θidi0-λTb+t*s.t.-∑i=1p‍θidi-ATλ⩽C,∑i=1p‍y¯ijθi+t⩽∑i=1p‍y¯ijci0,j=0,1,2,…,p,θ⩾0,λ⩾0,tfree,
where y¯0,y¯1,…,y¯p denote the vertices of the p-dimensional simplex S.During each iterationk⩾0, the lower bounding process computes a lower bound LBk for the optimal value v(S0) of problem (LMP(S0)). For each k⩾0, this lower process bound LBk is given by
(22)LBk=min{LB(S)∣S∈Qk}.The upper bounding process is the third fundamental one of the branch and bound algorithm. For eachp-dimensional simplex S created by the branching process, this process finds an upper bound for (LMP(S)). Let w∈ℝn be optimal dual variables corresponding to the first n constraints of linear program LP(S), and set x*=w*. Then, from definition of problem (DLP(S)), we have that Ax*⩽b,x*⩾0. This implies that x* is a feasible solution to (LMP(S)). Therefore, an upper bound UB(S) of (LMP(S)) is h(x*). In each iteration of the algorithm, this process finds an upper bound for v. For each k⩾0, let w∈ℝn be optimal dual variables corresponding to the first n constraints of linear program LP(S), then this upper bound UBk is given by
(23)UBk=h(x),
where x is the incumbent feasible solution to the problem.


### 3.3. Deleting Technique

As the branch and bound search proceeds, certainp-dimensional simplices created by the algorithm are eliminated from further consideration. There are two ways occuring, either by deletion by bounding or by deletion by infeasibility.During any iterationk, k⩾1, let UBk be the smallest objective function value achieved in problem (LMP) by the feasible solutions to problem (LMP(S)) thus far generated by the algorithm. A simplex S⊆S0 is deleted by bounding when
(24)LB(S)⩾UBk
holds. When (30) holds, searching simplex S further will not improve upon the best feasible solution found thus far for problem (LMP).As soon as eachp-dimensional simplex S is created by simplicial bisection in the algorithm, it is subjected to the deletion by infeasibility test. Let y¯0,y¯1,…,y¯p denote the vertices of such a simplex S. If for some i∈{1,2,…,p}, either
(25)min{y¯i0,y¯i1,…,y¯ip}>Li,
or
(26)max{y¯i0,y¯i1,…,y¯ip}<li,
then simplex S is said to pass the deletion by infeasibility test and it is eliminated by the algorithm from further consideration. If for each i∈{1,2,…,p}, both (25) and (26) fail to hold, then simplex S fails the deletion by infeasibility test and it is retained for further scrutiny by the algorithm. The validity of the deletion by infeasibility test follows from the fact that if (25) or (26) holds for some i, then for each y∈S, there is no x∈X such that
(27)diTx+di0-yi=0.
This implies problem (LMP(S)) infeasible.


### 3.4. Branch and Bound Algorithm

Based on the results and algorithmic process discussed in this section, the branch and bound algorithm for globally solving the LMP can be stated as follows.Step 1 (Initialization).
(0.1)
Initialize the iteration counterk:=0; the set of all active nodes Q0:={S0}; the upper bound UB0=+∞.
(0.2)
Solve linear program (LP(S0)) for its finite optimal value LB(S0). Let w∈ℝn be optimal dual variables corresponding to the first n constraints of linear program LP(S0). Set x0=w,UB0=h(x0),LB0=LB(S0). Set k=1, and go to iteration k.
Main Step (at iteration
k
)Step 2 (Termination).
IfUBk-1-LBk-1⩽ε, where ε>0 is some accuracy tolerance, then stop, and xk-1 is a global ε-optimal solution for problem (LMP) and v=LBk-1. Otherwise, set xk=xk-1, LBk=LBk-1, UBk=UBk-1. Go to Step 3.Step 3 (Branching).
LetSk∈Qk-1 satisfy Sk∈argmin{LB(S)∣S∈Qk-1}. Use simplicial bisection to divide Sk into S1k and S2k. Let R^={S1k,S2k}.Step 4 (Infeasiblity Test).
Delete fromR^ each simplex that passes the deletion by infeasiblity test. Let R represent the subset of R^ thereby obtained.Step 5 (Fathoming).
For each new sub-simplexS∈R, compute optimal value LB(S) of linear program (LP(S0)). If LB(S) is finite, let w∈ℝn be optimal dual variables corresponding to the first (p+1)n constraints of linear program (LP(S)).Step 6 (Updating upper Bound).
Ifh(w)<h(xk), set xk=w, UBk=h(xk).Step 7 (New Partition).
LetQk={Qk-1∖{Sk}}⋃‍R.Step 8 (Deletion).
Q
k
=
Q
k
∖
{
S
:
LB
(
S
)
-
UB
k
⩾
ε
}.Step 9 (Convergence).
IfQk=∅, then stop. UBk is an optimal value of the LMP, and xk is a global ε-optimal solution for problem (LMP). Otherwise, set k+1 and go to Step 2.


## 3.1. Branching Rule

The branch and bound approach is based on partitioning thep-dimensional simplex S0 into smaller subsimplices that are also of dimension p, each concerned with a node of the branch and bound tree, and each node is associated with a linear subproblem on each subsimplicie. These subsimplices are obtained by the branching process, which helps the branch and bound procedure identify a location in the feasible region of problem (LMP(S0)) that contains a global optimal solution to the problem.During each iteration of the algorithm, the branching process creates a more refined partition of a portion inS=S0 that cannot yet be excluded from consideration in the search for a global optimal solution for problem (LMP(S)). The initial partition Q1 consists simply of S, since at the beginning of the branch and bound procedure, no portion of S can as yet be excluded from consideration.During iterationk of the algorithm, k⩾1, the branching process is used to help create a new partition Qk+1. First, a screening procedure is used to remove any rectangle from Qk that can, at this point of the search, be excluded from further consideration, and Qk+1 is temporarily set equal to the set of simplices that remain. Later in iteration k, a rectangle Sk in Qk+1 is identified for further examination. The branching process is then evoked to subdivide Sk into two subsimplices S1k,S2k. This subdivision is accomplished by a process called simplicial bisection.Definition 8 (see [35]).
LetS be a p-dimensional simplex with vertex set {v0,v1,…,vp}. Let w be the midpoint of any of the longest edges [vr,vt] of S. Then {S1,S2} is called a simplicialbisection of S, where the vertex set of S1 is {v0,v1,…,vr-1,w,vr+1,…,vp} and the vertex set of S2 is {v0,v1,…,vt-1,w,vt+1,…,vp}.


## 3.2. Lower Bound and Upper Bound

The second fundamental process of the algorithm is the lower bounding one. For each simplexS⊆S0 created by the branching process, this process gives a lower bound LB(S) for the optimal value v(S) of the following problem LMP(S),
(20)v(S)=minh(x)=∑i=1p‍(ciTx+ci0)yi,s.t.diTx+di0-yi⩽0Ax-b⩽0,x⩾0,y∈S.
For each simplex S created by the branching process, LB(S) is found by solving a single linear programming LP(S) as follows,
(21)(LB(S))=max∑i=1p‍θidi0-λTb+t*s.t.-∑i=1p‍θidi-ATλ⩽C,∑i=1p‍y¯ijθi+t⩽∑i=1p‍y¯ijci0,j=0,1,2,…,p,θ⩾0,λ⩾0,tfree,
where y¯0,y¯1,…,y¯p denote the vertices of the p-dimensional simplex S.During each iterationk⩾0, the lower bounding process computes a lower bound LBk for the optimal value v(S0) of problem (LMP(S0)). For each k⩾0, this lower process bound LBk is given by
(22)LBk=min{LB(S)∣S∈Qk}.The upper bounding process is the third fundamental one of the branch and bound algorithm. For eachp-dimensional simplex S created by the branching process, this process finds an upper bound for (LMP(S)). Let w∈ℝn be optimal dual variables corresponding to the first n constraints of linear program LP(S), and set x*=w*. Then, from definition of problem (DLP(S)), we have that Ax*⩽b,x*⩾0. This implies that x* is a feasible solution to (LMP(S)). Therefore, an upper bound UB(S) of (LMP(S)) is h(x*). In each iteration of the algorithm, this process finds an upper bound for v. For each k⩾0, let w∈ℝn be optimal dual variables corresponding to the first n constraints of linear program LP(S), then this upper bound UBk is given by
(23)UBk=h(x),
where x is the incumbent feasible solution to the problem.


## 3.3. Deleting Technique

As the branch and bound search proceeds, certainp-dimensional simplices created by the algorithm are eliminated from further consideration. There are two ways occuring, either by deletion by bounding or by deletion by infeasibility.During any iterationk, k⩾1, let UBk be the smallest objective function value achieved in problem (LMP) by the feasible solutions to problem (LMP(S)) thus far generated by the algorithm. A simplex S⊆S0 is deleted by bounding when
(24)LB(S)⩾UBk
holds. When (30) holds, searching simplex S further will not improve upon the best feasible solution found thus far for problem (LMP).As soon as eachp-dimensional simplex S is created by simplicial bisection in the algorithm, it is subjected to the deletion by infeasibility test. Let y¯0,y¯1,…,y¯p denote the vertices of such a simplex S. If for some i∈{1,2,…,p}, either
(25)min{y¯i0,y¯i1,…,y¯ip}>Li,
or
(26)max{y¯i0,y¯i1,…,y¯ip}<li,
then simplex S is said to pass the deletion by infeasibility test and it is eliminated by the algorithm from further consideration. If for each i∈{1,2,…,p}, both (25) and (26) fail to hold, then simplex S fails the deletion by infeasibility test and it is retained for further scrutiny by the algorithm. The validity of the deletion by infeasibility test follows from the fact that if (25) or (26) holds for some i, then for each y∈S, there is no x∈X such that
(27)diTx+di0-yi=0.
This implies problem (LMP(S)) infeasible.


## 3.4. Branch and Bound Algorithm

Based on the results and algorithmic process discussed in this section, the branch and bound algorithm for globally solving the LMP can be stated as follows.Step 1 (Initialization).
(0.1)
Initialize the iteration counterk:=0; the set of all active nodes Q0:={S0}; the upper bound UB0=+∞.
(0.2)
Solve linear program (LP(S0)) for its finite optimal value LB(S0). Let w∈ℝn be optimal dual variables corresponding to the first n constraints of linear program LP(S0). Set x0=w,UB0=h(x0),LB0=LB(S0). Set k=1, and go to iteration k.
Main Step (at iteration
k
)Step 2 (Termination).
IfUBk-1-LBk-1⩽ε, where ε>0 is some accuracy tolerance, then stop, and xk-1 is a global ε-optimal solution for problem (LMP) and v=LBk-1. Otherwise, set xk=xk-1, LBk=LBk-1, UBk=UBk-1. Go to Step 3.Step 3 (Branching).
LetSk∈Qk-1 satisfy Sk∈argmin{LB(S)∣S∈Qk-1}. Use simplicial bisection to divide Sk into S1k and S2k. Let R^={S1k,S2k}.Step 4 (Infeasiblity Test).
Delete fromR^ each simplex that passes the deletion by infeasiblity test. Let R represent the subset of R^ thereby obtained.Step 5 (Fathoming).
For each new sub-simplexS∈R, compute optimal value LB(S) of linear program (LP(S0)). If LB(S) is finite, let w∈ℝn be optimal dual variables corresponding to the first (p+1)n constraints of linear program (LP(S)).Step 6 (Updating upper Bound).
Ifh(w)<h(xk), set xk=w, UBk=h(xk).Step 7 (New Partition).
LetQk={Qk-1∖{Sk}}⋃‍R.Step 8 (Deletion).
Q
k
=
Q
k
∖
{
S
:
LB
(
S
)
-
UB
k
⩾
ε
}.Step 9 (Convergence).
IfQk=∅, then stop. UBk is an optimal value of the LMP, and xk is a global ε-optimal solution for problem (LMP). Otherwise, set k+1 and go to Step 2.


## 4. Convergence of the Algorithm

In this section we give a global convergence of algorithm above. By the construction of the algorithm, when the algorithm is finite, thenQk=∅, so that v(S0)⩾UBk+ε=h(xk)+ε. Since, by Proposition 5, v=v(S0) and since xk∈X, this implies that v⩾h(xk)+ε and xk is a global ε-optimal solution to the LMP. Thus, when the algorithm is finite, it globally solves the LMP as desired.If the algorithm does not terminate after finitely many iterations, then it is easy to show that it generates at least one infinite nested subsequence{Sr} of simplices, that is, where Sr+1⊆Sr for all r. In this case, the following result is a key to convergence in the algorithm.Theorem 9.
Suppose that the Branch and Bound Algorithm is infinite, and that{Sr} is an infinite nested subsequence of simplices generated by the algorithm. Let w* denote any accumulation point of {wr}r=0∞ where, for each r,wr∈ℝn denotes any optimal dual variables corresponding to the first n constraints of linear program (LP(Sr)). Then w* is a global optimal solution for problem (LMP).Proof.
Suppose that the algorithm is infinite, and let{Sr} be chosen as in the theorem. Then, from Horst and Tuy [35], ⋂rSr={y*} for some point y*∈ℝp.
For each simplexSr, denote its vertices by y¯r,j,j=0,1,…,p, denote (wr,q0r,q1r,…,qpr) as an optimal dual solution to linear program (LP(Sr)). Set U={q∈ℝp+1∣∑j=0pqj=1,qj⩾0,j=0,1,…,p}, then U is compact and for each r, qr≜(q0r,q1r,…,qpr)∈U.
By Proposition7, for each r, wr∈X. Since X is bounded, this implies that {wr} has at least one convergent subsequence. Let {wr}r∈R denote any such subsequence, and let w*=limr∈Rwr. Then, since X is closed, w*∈X. Now, we show that w* is a global optimal solution for problem (LMP).
SinceU is bounded, then there exists an infinite subsequence R′ of R such that for each j=0,1,2,…,p,limr∈R′qr=q*. We have q*∈U, since U is close. Notice that since limr∈Rwr=w*, limr∈R′wr=w*. Also, since ⋂rSr={y*},limr∈R′y¯r,j=y* for each j=0,1,2,…,p. Set (Cr)T=(minj∈J(∑i=1py¯ir,jci1), minj∈J(∑i=1py¯ir,jci2),…,minj∈J(∑i=1py¯ir,jcin)). Then, we have
(28)limr∈R′(Cr)T=C*T=(minj∈J(∑i=1p‍y¯i*ci1),minj∈J(∑i=1p‍y¯i*ci2),…,minj∈J(∑i=1p‍y¯i*cin))=(y¯i*ci1,y¯i*ci2,…,y¯i*cin).
From Theorems3–4, Proposition 5, and the algorithm, for each r,r′∈R′ such that r′>r, LB(Sr)⩽LB(Sr′)⩽v. Therefore, for some infinite subsequence R′′ of R′, limr∈R′′LB(Sr) exists and satisfies limr∈R′′LB(Sr)⩽v.
Form an objective function of problem (DLP(Sr)), we obtain the equation
(29)LB(Sr)=(Cr)Twr+∑j=0p‍qjr∑i=1p‍y¯ir,jci0,∀r∈R′′.
Taking limits over r∈R′′ in this equation yields
(30)limr∈R′′LB(Sr)=(C*)Tw*+∑j=0p‍qj*∑i=1p‍y¯i*ci0=(C*)Tw*+∑i=1p‍y¯i*ci0=∑i=1p‍(ciTw*+ci0)yi*⩽v,
where the first equation follows from limr∈R′′wr=w*, limr∈R′(Cr)T=C*T,limr∈R′′y¯r,j=y*,j=0,1,…,p, and limr∈R′′qr=q*, the second equation holds because q*∈U, the third equation follows form C*T=(y¯i*ci1,y¯i*ci2,…,y¯i*cin), and the inequality holds because limr∈R′′LB(Sr)⩽v.
We will now show that(x,y)=(w*,y*) is a feasible solution to problem LMP(S0). First, notice that since S0 is closed, y*∈S0, and, since w*∈X,Aw*⩽b and w*⩾0. Let i∈{1,2,…,p}, For each r∈R′′, from constraint i of problem (DLP(Sr)), -diTwr+∑j=0py¯1r,jqjr=di0. Taking limits over r∈R′′ in the above equation, we obtain
(31)di0=-diTw*+∑j=0p‍y¯i*qj*=-diTw*+y¯i*∑j=0p‍qj*=-diTw*+y¯i*,
where the first equation follows from limr∈R′′wr=w*,limr∈R′′y¯r,j=y*,j=0,1,…,p, and limr∈R′′qr=q*, the last equation is due to the fact that q*∈U. By the choice of i, since y*∈S0,Aw*⩽b and w*⩾0, (31) implies that (x,y)=(w*,y*) is a feasible solution for problem LMP(S0). Therefore, by Theorem 3,
(32)∑i=1p‍(ciTw*+ci0)yi*⩾v.
From (30) and Theorem 3, (32) implies that the feasible solution (w*,y*) to problem LMP(S0) is a global optimal solution to problem LMP(S0). Therefore, by Theorem 3, w* is a global optimal solution to the LMP.With Theorem9, we can easily show two fundamental convergence properties of the algorithm as follows.Corollary 10.
Suppose that the Branch and Bound Algorithm is infinite. Then each accumulation point of{xk}k=0∞ is a global optimal solution for problem.Proof.
The proof is similar to in [34, Corollary 1], it is omitted here.Corollary 11.
Suppose that the Branch and Bound Algorithm is infinite. Thenlimk→∞LBk=limk→∞LBk=v.Proof.
The proof is similar to [34, Corollary 2], it is omitted here.


## 5. Numerical Examples

Now we give numerical experiments for the proposed global optimization algorithm to illustrate its efficiency.Example 12.
(33)
min
G
(
x
)
=
(
x
1
+
2
x
2
-
2
)
(
-
2
x
1
-
x
2
+
3
)
+
(
3
x
1
-
2
x
2
+
3
)
(
x
1
-
x
2
-
1
)
s
.
t
.
-
2
x
1
+
3
x
2
⩽
6
,
4
x
1
-
5
x
2
⩽
8
,
5
x
1
+
3
x
2
⩽
15
,
-
4
x
1
-
3
x
2
⩽
-
12
,
x
1
⩾
0
,
x
2
⩾
0
.
Prior to initiating the algorithm, we use Theorem1 to find a simplex S0 containing X. By solving three linear programs, we determine that the vertices S0 are given by v0=y¯0=(-1.6667,1.1351),v1=y¯1=(3.8649,1.1351),v2=y¯2=(-1.6667,6.6667). Also, for each i=1,2, we compute the minimum li and the maximum Li of 〈di,x〉+di0 over X for use in the deletion by infeasiblity test (25) and (26). This entails solving four linear programs and get l1=-2.8919,l2=-2.6667,L1=-1.6667,L2=1.1351.
Initialization. By solving the following linear programming (LP(S0)), we get LB(S0)=-49.7086 and the dual variables w0=(1.2857,2.8571),
(34)max3θ1-θ2-6λ1-8λ2-15λ3+12λ4+ts.t.-2θ1+θ2-2λ1+4λ2+5λ3-4λ4⩾-1.7386,-θ1-θ2+3λ1-5λ2+3λ3-3λ4⩾16.6668,-1.6667θ1+1.1351θ2+t⩽10.71153.8649θ1+1.1351θ2+t⩽-0.35165,-1.6667θ1+6.6667θ2+t⩽46.6669,θ⩾0,λ⩾0,tfree.
We set x0=w*,UB0=-16.224,LB0=-49.7086,G0={S0}, and k=1. Select the convergence tolerance to be equal to ε=10-2.
Iteration 1. Since UB0-LB0<ε, S0 is split by simplicial bisection into S11 and S21 where the vertices of S11 are (-1.6667,1.1351),(1.0991,3.9009),(-1.6667,6.6667) and the vertices of S21 are (-1.6667,1.1351),(3.8649,1.1351),(1.0991,3.9009). Neither S11 nor S21 is deleted by the deletion by infeasibility test. By solving problem (LP(S11)), we obtain the lower bound LB(S11)=-38.6454 and the dual variable w=(1.2857,2.8571). Since h(w)=-16.224=h(x1), where x1=x0, we do not update y1 and UB1=UB0. By solving problem (LP(S21)), we obtain the lower bound LB(S21)=-18.09944 and the dual variable w=(1.2857,2.8571). With problem (LP(S11)), the dual to problem (LP(S21)) does not lead to an update of y1 and UB1. We have Q1={S11,S21}. and neither S11 nor S21 is deleted by Step 8 from Q1. At the end of Iteration 1, x1=(1.2857,2.8571),UB1=-16.224,LB1=-38.6454,G1={S11,S21}.
The algorithm finds a globalε-optimal value −16.2837 after 7 iterations at the global ε-optimal solution x*=(1.547,2.421).Example 13.
(35)
min
G
(
x
)
=
(
-
x
1
+
2
x
2
-
0.5
)
(
-
2
x
1
+
x
2
+
6
)
+
(
3
x
1
-
2
x
2
+
6.5
)
(
x
1
+
x
2
-
1
)
s
.
t
.
-
5
x
1
+
8
x
2
⩽
24
,
5
x
1
+
8
x
2
⩽
44
,
6
x
1
-
3
x
2
⩽
15
,
-
4
x
1
-
5
x
2
⩽
-
10
,
x
1
⩾
0
,
x
2
⩾
0
.
Prior to initiating the algorithm, we use Theorem1 to find a simplex S0 containing X. By solving three linear programs, we determine that the vertices S0 are given by v0=y¯0=(9,6),v1=y¯1=(-6.5,6),v2=y¯2=(9,3.5). Also, for each i=1,2, we compute the minimum li and the maximum Li of 〈di,x〉+di0 over X for use in the deletion by infeasiblity test (25) and (26). This entails solving four linear programs and get l1=1,l2=1,L1=9,L2=6.
The algorithm terminates at the beginning of Iteration 29 with the globalε-optimal solution x*=(1.5549,0.7561) and ε-optimal value 10.6756 for problem (35).Example 14.
In this example, we solve 10 different random instances for various sizes and objective function structures. These test problems are generated by fixingε=10-5. And then all elements of A, ci,di,ci0 and di0 are randomly generated, whose ranges are [1,10]. Since the test problems are coded in C++ and the experiments are conducted on a Pentium IV (3.06 GHZ) microcomputer, the computational results of five problems are summarized in Table 1. The following indices characterize the performance in algorithm: Iter: the average number of iterations; Time: the average execution time in seconds.Table 1
Computational results of test problems.
Example
p
(
m
,
n
)
Iter
Time
1
4
(
10
,
10
)
39.8
28.7
2
4
(
10
,
20
)
44.2
30.3
3
4
(
20
,
20
)
69.1
38.5
4
5
(
10
,
10
)
43.6
29.9
5
5
(
10
,
20
)
50.7
35.0
6
5
(
20
,
20
)
82.8
45.7
7
6
(
10
,
20
)
56.2
30.4
8
7
(
10
,
20
)
67.0
34.5
9
8
(
10
,
20
)
85.6
49.9
10
9
(
10
,
20
)
116.7
78.0


## 6. Conclusion

We have presented and validated a new simplicial branch and bound algorithm globally to the linear multiplicative programming. The algorithm implements a simplicial branch and bound search, finding a global optimal solution to the problem that is equivalent to the LMP. We believe that the new algorithm has advantage in several potentially practical and computational cases. Besides, numerical examples show that the proposed algorithm is feasible.



---

*Source: 984168-2013-04-08.xml*