# A New Global Optimization Algorithm for Solving Generalized Geometric Programming

Authors: San-Yang Liu; Chun-Feng Wang; Li-Xia Liu
Journal: Mathematical Problems in Engineering
 (2010)

---

## Abstract

A global optimization algorithm for solving generalized geometric
programming (GGP) problem is developed based on a new linearization
technique. Furthermore, in order to improve the convergence speed of this algorithm,
a new pruning technique is proposed, which can be used to cut away a
large part of the current investigated region in which the global optimal solution
does not exist. Convergence of this algorithm is proved, and some experiments
are reported to show the feasibility of the proposed algorithm.


---

## Body

## 1. Introduction

This paper considers generalized geometric programming GGP problem in the following form:(1.1)(GGP){min⁡ϕ0(x)s.t.ϕj(x)≤βj,j=1,…,m,X0={x:0<l0≤x≤u0},
where ϕj(x)=∑t=1Tjcjt∏i=1nxiγjti,cjt,βj,γjti∈R,t=1,…,Tj,i=1,2,…,n,j=0,1,…,m.Generally speaking, GGP problem is a non convex programming problem, which has a wide variety of applications, such as in engineering design, economics and statistics, manufacturing, and distribution contexts in risk management problems [1–4].During the past years, many local optimization approaches for solving GGP problem have been presented [5, 6], but global optimization algorithms based on the characteristics of GGP problem are scarce. Maranas and Floudas [7] proposed a global optimization algorithm for solving GGP problem based on convex relaxation. Shen and Zhang [8] presented a method to globally solve GGP problem by using linear relaxation. Recently, several branch and bound algorithms have been developed [9, 10].The purpose of this paper is to introduce a new global optimization algorithm for solving GGP problem. In this algorithm, by utilizing the special structure of GGP problem, a new linear relaxation technique is presented. Based on this technique, the initial GGP problem is systematically converted into a series of linear programming problems. The solutions of these converted problems can approximate the global optimal solution of GGP problem by successive refinement process.The main features of this algorithm are: (1) a new linearization technique for solving GGP problem is proposed, which applies more information of the functions of GGP problem, (2) the generated relaxation linear programming problems are embedded within a branch and bound algorithm without increasing the number of variables and constraints, (3) a new pruning technique is presented, which can be used to improve the convergence speed of the proposed algorithm, and (4) numerical experiments are given, which show that the proposed algorithm can treat all of the test problems in finding global optimal solution within a prespecified tolerance.The structure of this paper is as follows. In Section2, first, we construct the lower approximate linear functions for the objective function and the constraint functions of GGP problem; then, we derive the relaxation linear programming (RLP) problem of GGP problem; finally, to improve the convergence speed of our algorithm, we present a new pruning technique. In Section 3, the proposed branch and bound algorithm is described, and the convergence of the algorithm is established. Some numerical results are reported in Section 4.


## 2. Linear Relaxation and Pruning Technique

The principal structure in the development of a solution procedure for solving GGP problem is the construction of lower bounds for this problem, as well as for its partitioned subproblems. A lower bound of GGP problem and its partitioned subproblems can be obtained by solving a linear relaxation problem. The proposed strategy for generating this linear relaxation problem is to underestimate every nonlinear functionϕj(x)(j=0,…,m) with a linear function. In what follows, all the details of this procedure will be given.LetX=[x̲,x¯] represents either the initial box X0, or modified box as defined for some partitioned subproblem in a branch and bound scheme.Consider term∏i=1nxiγjti in ϕj(x)(j=0,…,m). Let ∏i=1nxiγjti=exp(yjt), then, we have (2.1)yjt=∑i=1nγjtiln⁡xi.From (2.1), we can obtain the lower bound and upper bound of yjt as follows: (2.2)y̲jt=∑i=1nmin⁡{γjtiln⁡x̲i,γjtiln⁡x¯i},y¯jt=∑i=1nmax⁡{γjtiln⁡x̲i,γjtiln⁡x¯i}.To derive the linear relaxation problem, we will use a convex separation technique and a two-part relaxation technique.


### 2.1. First-Part Relaxation

Letyj=(yj1,…,yjTj), then ϕj(x) can be expressed in the following form: (2.3)ϕj(x)=∑t=1Tjcjt∏i=1nxiγjti=∑t=1Tjcjtexp⁡(yjt)≜fj(yj).
For fj(yj), we can derive its gradient and the Hessian matrix: (2.4)∇fj(yj)=(cj1exp⁡(yj1)⋮cjTjexp⁡(yjTj)),∇2fj(yj)=(cj1exp⁡(yj1)cj2exp⁡(yj2)⋱cjTjexp⁡(yjTj)).
Therefore, by (2.4), the following relation holds: (2.5)‖∇2fj(yj)‖≤max⁡1≤t≤Tj|cjt|max⁡1≤t≤Tjexp⁡(y¯jt).
Let λj=max1≤t≤Tj|cjt|max1≤t≤Tjexp(y¯jt)+0.1, then, for all yj∈Yj≜[y̲j,y¯j], we have (2.6)‖∇2fj(yj)‖<λj.
Thus, the function (1/2)λj∥yj∥2+fj(yj) is a convex function on Yj. Consequently, the function fj(yj) can be decomposed into the difference of two convex functions, that is,  fj(yj) is a d.c. function, which admits the following d.c. decomposition:(2.7)fj(yj)=gj(yj)-hj(yj),
where (2.8)gj(yj)=12λj‖yj‖2+fj(yj),hj(yj)=12λj‖yj‖2.
Let yjmid=(1/2)(y̲j+y¯j). Since gj(yj) is a convex function, we have (2.9)gj(yj)≥gj(yjmid)+∇gj(yjmid)T(yj-yjmid)≜gjl(yj).
In addition, for yjt∈[y̲jt,y¯jt], it is not difficult to show (2.10)(y̲jt+y¯jt)yjt-y̲jty¯jt≥yjt2.
Furthermore, we can obtain (2.11)∑t=1Tj[(y̲jt+y¯jt)yjt-y̲jty¯jt]≥‖yj‖2.
Since λj>0, it follows that (2.12)hjl(yj)≜12λj∑t=1Tj[(y̲jt+y¯jt)yjt-y̲jty¯jt]≥12λj‖yj‖2=hj(yj).
Thus, from (2.7), (2.9), and (2.12), we have (2.13)fjl(yj)≜gjl(yj)-hjl(yj)≤fj(yj).
Hence, by (2.1), (2.3), and (2.13), the first-part relaxation Lj(x) of ϕj(x) can be obtained as follows (2.14)ϕj(x)=fj(yj)=gj(yj)-hj(yj)≥gjl(yj)-hjl(yj)=gj(yjmid)+∇gj(yjmid)T(yj-yjmid)-12λj∑t=1Tj[(y̲jt+y¯jt)yjt-y̲jty¯jt]=∑t=1Tj[cjtexp⁡(yjmid(t))+λjyjmid(t)-12λj(y̲jt+y¯jt)]yjt+gj(yjmid)-∇gj(yjmid)Tyjmid+12λj∑t=1Tjy̲jty¯jt=∑t=1Tj[cjtexp⁡(yjmid(t))+λjyjmid(t)-12λj(y̲jt+y¯jt)]∑i=1nγjtiln⁡xi+gj(yjmid)-∇gj(yjmid)Tyjmid+12λj∑t=1Tjy̲jty¯jt=∑i=1n(∑t=1Tj(cjtexp⁡(yjmid(t))+λjyjmid(t)-12λj(y̲jt+y¯jt))γjti)ln⁡xi+gj(yjmid)-∇gj(yjmid)Tyjmid+12λj∑t=1Tjy̲jty¯jt≜Lj(x).


### 2.2. Second-Part Relaxation

Consider the functionlnxi on the interval [x̲i,x¯i]. As we all know, its linear lower bound function and upper bound function can be derived as follows: (2.15)Ki(xi-x̲i)+ln⁡x̲i≤ln⁡xi≤Kixi-1-ln⁡Ki,
where Ki=(lnx¯i-lnx̲i)/(x¯i-x̲i).InLj(x)(j=0,…,m), let (2.16)αji=∑t=1Tj(cjtexp⁡((yjmid(t))+λjyjmid(t)-12λj(y̲jt+y¯jt))),i=1,…,n.
Then, from (2.14) and (2.15),we can obtain the linear lower bound function of ϕj(x) denoted by ϕjl(x) as follows: (2.17)ϕjl(x)≜∑i=1nαjiφi(xi)+gj(yjmid)+∇gj(yjmid)Tyjmid+12λj∑t=1Tjy̲jty¯jt,
where (2.18)φi(xi)={Ki(xi-x̲i)+ln⁡x̲i,ifαji≥0,Kixi-1-ln⁡Ki,else.
Obviously, ϕjl(x)≤Lj(x)≤ϕj(x).Consequently, the corresponding approximation relaxation linear programming (RLP) problem of GGP problem onX can be obtained (2.19)(RLP){min⁡ϕ0l(x)s.t.ϕjl(x)≤βj,j=1,…,m,x∈X.Theorem 2.1.
Letδi=x̲i-x¯i,i=1,…,n. Then, for all x∈X, the difference of ϕj(x) and ϕjl(x) satisfies ϕj(x)-ϕjl(x)→0 as δi→0, i=1,…,n,j=0,…,m.Proof.
For allx∈X, let
(2.20)Δ=ϕj(x)-ϕjl(x)=ϕj(x)-Lj(x)+Lj(x)-ϕjl(x),
and let Δ1=ϕj(x)-Lj(x),Δ2=Lj(x)-ϕjl(x). Then, it is obvious that we only need to prove
(2.21)Δ1⟶0,Δ2⟶0,asδi⟶0.
To this end, first, we consider the difference Δ1=ϕj(x)-Lj(x). By (2.7), (2.13), and (2.14), it follows that
(2.22)Δ1=ϕj(x)-Lj(x)=∑t=1Tjcjt∏i=1nxiγjti-[∑t=1Tj(cjtexp⁡((yjmid(t))+λjyjmid(t)-12λj(y̲jt+y¯jt)))×∑i=1nγjtiln⁡xi+gj(yjmid)-∇gj(yjmid)Tyjmid+12λj∑t=1Tjy̲jty¯jt]=∑t=1Tjcjtexp⁡(yjt)-[∑t=1Tj(cjtexp⁡((yjmid(t))+λjyjmid(t)-12λj(y̲jt+y¯jt)))yjt+gj(yjmid)-∇gj(yjmid)Tyjmid+12λj∑t=1Tjy̲jty¯jt]=fj(yj)-fjl(yj)=gj(yj)-gjl(yj)+12λj‖yj‖2-12λj∑t=1Tj[(y̲jt+y¯jt)yjt-y̲jty¯jt]≤(∇gj(ξ)-∇gj(yjmid))T(yj-yjmid)+12λj‖y¯j-y̲j‖2≤2λj‖ξ-yjmid‖‖yj-yjmid‖+12λj‖y¯j-y̲j‖2≤52λj‖y¯j-y̲j‖2,
where ξ is a constant vector, and satisfies gj(yj)-gj(yjmid)=∇gj(ξ)T(yj-yjmid).
By the definition ofyjt, we have ∥y¯j-y̲j∥→0 as δi→0(i=1,…,n). Thus, we have Δ1→0 as δi→0(i=1,…,n).
Second, we consider the differenceΔ2=Lj(x)-ϕjl(x). From the definitions of Lj(x) and ϕjl(x), it follows that
(2.23)Δ2=Lj(x)-ϕjl(x)=∑i=1nαji(ln⁡xi-φi(xi))=∑αji≥0αji(ln⁡xi-Ki(xi-x̲i)-ln⁡x̲i)+∑αji<0αji(ln⁡xi-Kixi+1+ln⁡Ki).
By [8], we know that |lnxi-Ki(xi-x̲i)-lnx̲i|→0 and |lnxi-Kixi+1+lnKi|→0, as δi→0(i=1,…,n). Thus, we have Δ2→0 as δi→0(i=1,…,n).
Taken togethe the above, it implies that(2.24)Δ=Δ1+Δ2⟶0,asδi⟶0(i=1,…,n),
and this completes the proof.From Theorem2.1, it follows that ϕjl(x) will approximate the function ϕj(x) as δi→0(i=1,…,n).Based on the above discussion, it can be seen that the optimal value of RLP problem is smaller than or equal to that of GGP problem for all feasible points, that is, the optimal value of  RLP problem provides a valid lower bound for the optimal value of GGP problem. Thus, for any problem (P), let us denote the optimal value of (P) byV(P), then we have V(RLP)≤V(GGP).


### 2.3. Pruning Technique

In order to improve the convergence speed of this algorithm, we present a new pruning technique, which can be used to eliminate the region in which the global optimal solution of GGP problem does not exist.Assume that UB is current known upper bound of the optimal valueϕ0* of GGP problem. Let (2.25)τi=α0iKi,i=1,…,n,T¯=∑i=1nT¯i,whereT¯i={α0i(ln⁡x̲i-Kix̲i),ifα0i≥0,α0i(-1-ln⁡Ki),else,T=T¯+g0(y0mid)-∇g0(y0mid)Ty0mid+12λ0∑t=1T0y̲0ty¯0t.Theorem 2.2.
For any subrectangleX=(Xi)n×1⊆X0 with Xi=[x̲i,x¯i]. Let
(2.26)ρk=UB-∑i=1,i≠knmin⁡{τix̲i,τix¯i}-T,k=1,…,n.
If there exists some index k∈{1,…,n} such that τk>0 and ρk<τkx¯k, then there is no globally optimal solution of GGP problem on X1; if τk<0 and ρk<τkx̲k, then there is no globally optimal solution of GGP problem on X2, where
(2.27)X1=(Xi1)n×1⊆X,withXi1={Xi,i≠k,(ρkτk,x¯k]⋂Xi,i=k,X2=(Xi2)n×1⊆X,withXi2={Xi,i≠k,[x̲k,ρkτk)⋂Xi,i=k.Proof.
First, we show that for allx∈X1, ϕ0(x)>UB. When x∈X1, consider the kth component xk of x. Since xk∈(ρk/τk,x¯k]⋂Xk, it follows that
(2.28)ρkτk<xk≤x¯k.
Note τk>0, we have ρk<τkxk. From the definition of ρk and the above inequality, we obtain
(2.29)UB<∑i=1,i≠knmin⁡{τix̲i,τix¯i}+τkxk+T≤∑i=1nτixi+T=∑i=1nτiφi(xi)+g0(y0mid)-∇g0(y0mid)Ty0mid+12λ0∑t=1T0y̲0ty¯0t.=ϕ0l(x).
This implies that, for all x∈X1, ϕ0(x)≥ϕ0l(x)>UB≥ϕ0*. In other words, for all x∈X1, ϕ0(x) is always greater than the optimal value of GGP problem. Therefore, there is no globally optimal solution of GGP problem on X1.
For allx∈X2, if τk<0 and ρk<τkx̲k with some k, by arguments similar to the above, we can derive that there is no globally optimal solution of GGP problem on X2.


## 2.1. First-Part Relaxation

Letyj=(yj1,…,yjTj), then ϕj(x) can be expressed in the following form: (2.3)ϕj(x)=∑t=1Tjcjt∏i=1nxiγjti=∑t=1Tjcjtexp⁡(yjt)≜fj(yj).
For fj(yj), we can derive its gradient and the Hessian matrix: (2.4)∇fj(yj)=(cj1exp⁡(yj1)⋮cjTjexp⁡(yjTj)),∇2fj(yj)=(cj1exp⁡(yj1)cj2exp⁡(yj2)⋱cjTjexp⁡(yjTj)).
Therefore, by (2.4), the following relation holds: (2.5)‖∇2fj(yj)‖≤max⁡1≤t≤Tj|cjt|max⁡1≤t≤Tjexp⁡(y¯jt).
Let λj=max1≤t≤Tj|cjt|max1≤t≤Tjexp(y¯jt)+0.1, then, for all yj∈Yj≜[y̲j,y¯j], we have (2.6)‖∇2fj(yj)‖<λj.
Thus, the function (1/2)λj∥yj∥2+fj(yj) is a convex function on Yj. Consequently, the function fj(yj) can be decomposed into the difference of two convex functions, that is,  fj(yj) is a d.c. function, which admits the following d.c. decomposition:(2.7)fj(yj)=gj(yj)-hj(yj),
where (2.8)gj(yj)=12λj‖yj‖2+fj(yj),hj(yj)=12λj‖yj‖2.
Let yjmid=(1/2)(y̲j+y¯j). Since gj(yj) is a convex function, we have (2.9)gj(yj)≥gj(yjmid)+∇gj(yjmid)T(yj-yjmid)≜gjl(yj).
In addition, for yjt∈[y̲jt,y¯jt], it is not difficult to show (2.10)(y̲jt+y¯jt)yjt-y̲jty¯jt≥yjt2.
Furthermore, we can obtain (2.11)∑t=1Tj[(y̲jt+y¯jt)yjt-y̲jty¯jt]≥‖yj‖2.
Since λj>0, it follows that (2.12)hjl(yj)≜12λj∑t=1Tj[(y̲jt+y¯jt)yjt-y̲jty¯jt]≥12λj‖yj‖2=hj(yj).
Thus, from (2.7), (2.9), and (2.12), we have (2.13)fjl(yj)≜gjl(yj)-hjl(yj)≤fj(yj).
Hence, by (2.1), (2.3), and (2.13), the first-part relaxation Lj(x) of ϕj(x) can be obtained as follows (2.14)ϕj(x)=fj(yj)=gj(yj)-hj(yj)≥gjl(yj)-hjl(yj)=gj(yjmid)+∇gj(yjmid)T(yj-yjmid)-12λj∑t=1Tj[(y̲jt+y¯jt)yjt-y̲jty¯jt]=∑t=1Tj[cjtexp⁡(yjmid(t))+λjyjmid(t)-12λj(y̲jt+y¯jt)]yjt+gj(yjmid)-∇gj(yjmid)Tyjmid+12λj∑t=1Tjy̲jty¯jt=∑t=1Tj[cjtexp⁡(yjmid(t))+λjyjmid(t)-12λj(y̲jt+y¯jt)]∑i=1nγjtiln⁡xi+gj(yjmid)-∇gj(yjmid)Tyjmid+12λj∑t=1Tjy̲jty¯jt=∑i=1n(∑t=1Tj(cjtexp⁡(yjmid(t))+λjyjmid(t)-12λj(y̲jt+y¯jt))γjti)ln⁡xi+gj(yjmid)-∇gj(yjmid)Tyjmid+12λj∑t=1Tjy̲jty¯jt≜Lj(x).


## 2.2. Second-Part Relaxation

Consider the functionlnxi on the interval [x̲i,x¯i]. As we all know, its linear lower bound function and upper bound function can be derived as follows: (2.15)Ki(xi-x̲i)+ln⁡x̲i≤ln⁡xi≤Kixi-1-ln⁡Ki,
where Ki=(lnx¯i-lnx̲i)/(x¯i-x̲i).InLj(x)(j=0,…,m), let (2.16)αji=∑t=1Tj(cjtexp⁡((yjmid(t))+λjyjmid(t)-12λj(y̲jt+y¯jt))),i=1,…,n.
Then, from (2.14) and (2.15),we can obtain the linear lower bound function of ϕj(x) denoted by ϕjl(x) as follows: (2.17)ϕjl(x)≜∑i=1nαjiφi(xi)+gj(yjmid)+∇gj(yjmid)Tyjmid+12λj∑t=1Tjy̲jty¯jt,
where (2.18)φi(xi)={Ki(xi-x̲i)+ln⁡x̲i,ifαji≥0,Kixi-1-ln⁡Ki,else.
Obviously, ϕjl(x)≤Lj(x)≤ϕj(x).Consequently, the corresponding approximation relaxation linear programming (RLP) problem of GGP problem onX can be obtained (2.19)(RLP){min⁡ϕ0l(x)s.t.ϕjl(x)≤βj,j=1,…,m,x∈X.Theorem 2.1.
Letδi=x̲i-x¯i,i=1,…,n. Then, for all x∈X, the difference of ϕj(x) and ϕjl(x) satisfies ϕj(x)-ϕjl(x)→0 as δi→0, i=1,…,n,j=0,…,m.Proof.
For allx∈X, let
(2.20)Δ=ϕj(x)-ϕjl(x)=ϕj(x)-Lj(x)+Lj(x)-ϕjl(x),
and let Δ1=ϕj(x)-Lj(x),Δ2=Lj(x)-ϕjl(x). Then, it is obvious that we only need to prove
(2.21)Δ1⟶0,Δ2⟶0,asδi⟶0.
To this end, first, we consider the difference Δ1=ϕj(x)-Lj(x). By (2.7), (2.13), and (2.14), it follows that
(2.22)Δ1=ϕj(x)-Lj(x)=∑t=1Tjcjt∏i=1nxiγjti-[∑t=1Tj(cjtexp⁡((yjmid(t))+λjyjmid(t)-12λj(y̲jt+y¯jt)))×∑i=1nγjtiln⁡xi+gj(yjmid)-∇gj(yjmid)Tyjmid+12λj∑t=1Tjy̲jty¯jt]=∑t=1Tjcjtexp⁡(yjt)-[∑t=1Tj(cjtexp⁡((yjmid(t))+λjyjmid(t)-12λj(y̲jt+y¯jt)))yjt+gj(yjmid)-∇gj(yjmid)Tyjmid+12λj∑t=1Tjy̲jty¯jt]=fj(yj)-fjl(yj)=gj(yj)-gjl(yj)+12λj‖yj‖2-12λj∑t=1Tj[(y̲jt+y¯jt)yjt-y̲jty¯jt]≤(∇gj(ξ)-∇gj(yjmid))T(yj-yjmid)+12λj‖y¯j-y̲j‖2≤2λj‖ξ-yjmid‖‖yj-yjmid‖+12λj‖y¯j-y̲j‖2≤52λj‖y¯j-y̲j‖2,
where ξ is a constant vector, and satisfies gj(yj)-gj(yjmid)=∇gj(ξ)T(yj-yjmid).
By the definition ofyjt, we have ∥y¯j-y̲j∥→0 as δi→0(i=1,…,n). Thus, we have Δ1→0 as δi→0(i=1,…,n).
Second, we consider the differenceΔ2=Lj(x)-ϕjl(x). From the definitions of Lj(x) and ϕjl(x), it follows that
(2.23)Δ2=Lj(x)-ϕjl(x)=∑i=1nαji(ln⁡xi-φi(xi))=∑αji≥0αji(ln⁡xi-Ki(xi-x̲i)-ln⁡x̲i)+∑αji<0αji(ln⁡xi-Kixi+1+ln⁡Ki).
By [8], we know that |lnxi-Ki(xi-x̲i)-lnx̲i|→0 and |lnxi-Kixi+1+lnKi|→0, as δi→0(i=1,…,n). Thus, we have Δ2→0 as δi→0(i=1,…,n).
Taken togethe the above, it implies that(2.24)Δ=Δ1+Δ2⟶0,asδi⟶0(i=1,…,n),
and this completes the proof.From Theorem2.1, it follows that ϕjl(x) will approximate the function ϕj(x) as δi→0(i=1,…,n).Based on the above discussion, it can be seen that the optimal value of RLP problem is smaller than or equal to that of GGP problem for all feasible points, that is, the optimal value of  RLP problem provides a valid lower bound for the optimal value of GGP problem. Thus, for any problem (P), let us denote the optimal value of (P) byV(P), then we have V(RLP)≤V(GGP).


## 2.3. Pruning Technique

In order to improve the convergence speed of this algorithm, we present a new pruning technique, which can be used to eliminate the region in which the global optimal solution of GGP problem does not exist.Assume that UB is current known upper bound of the optimal valueϕ0* of GGP problem. Let (2.25)τi=α0iKi,i=1,…,n,T¯=∑i=1nT¯i,whereT¯i={α0i(ln⁡x̲i-Kix̲i),ifα0i≥0,α0i(-1-ln⁡Ki),else,T=T¯+g0(y0mid)-∇g0(y0mid)Ty0mid+12λ0∑t=1T0y̲0ty¯0t.Theorem 2.2.
For any subrectangleX=(Xi)n×1⊆X0 with Xi=[x̲i,x¯i]. Let
(2.26)ρk=UB-∑i=1,i≠knmin⁡{τix̲i,τix¯i}-T,k=1,…,n.
If there exists some index k∈{1,…,n} such that τk>0 and ρk<τkx¯k, then there is no globally optimal solution of GGP problem on X1; if τk<0 and ρk<τkx̲k, then there is no globally optimal solution of GGP problem on X2, where
(2.27)X1=(Xi1)n×1⊆X,withXi1={Xi,i≠k,(ρkτk,x¯k]⋂Xi,i=k,X2=(Xi2)n×1⊆X,withXi2={Xi,i≠k,[x̲k,ρkτk)⋂Xi,i=k.Proof.
First, we show that for allx∈X1, ϕ0(x)>UB. When x∈X1, consider the kth component xk of x. Since xk∈(ρk/τk,x¯k]⋂Xk, it follows that
(2.28)ρkτk<xk≤x¯k.
Note τk>0, we have ρk<τkxk. From the definition of ρk and the above inequality, we obtain
(2.29)UB<∑i=1,i≠knmin⁡{τix̲i,τix¯i}+τkxk+T≤∑i=1nτixi+T=∑i=1nτiφi(xi)+g0(y0mid)-∇g0(y0mid)Ty0mid+12λ0∑t=1T0y̲0ty¯0t.=ϕ0l(x).
This implies that, for all x∈X1, ϕ0(x)≥ϕ0l(x)>UB≥ϕ0*. In other words, for all x∈X1, ϕ0(x) is always greater than the optimal value of GGP problem. Therefore, there is no globally optimal solution of GGP problem on X1.
For allx∈X2, if τk<0 and ρk<τkx̲k with some k, by arguments similar to the above, we can derive that there is no globally optimal solution of GGP problem on X2.


## 3. Algorithm and Its Convergence

In this section, based on the former relaxation linear programming (RLP) problem, a branch and bound algorithm is presented to globally solve GGP problem. In order to ensure convergence to the global optimal solution, this algorithm needs to solve a sequence of (RLP) problems over partitioned subsets ofX0.In this algorithm, the setX0 will be partitioned into subrectangles. Each subrectangle is concerned with a node of the branch and bound tree, and is associated with a relaxation linear subproblem.At stagek of the algorithm, suppose that we have a collection of active nodes denoted by Qk. For each node X∈Qk, we will have computed a lower bound for the optimal value of GGP problem via solution LB(X) of RLP problem, so that the lower bound of the optimal value of GGP problem on the whole initial box region X0 at stage k is given by LBk=min{LB(X),forallX∈Qk}. Whenever the solution of RLP problem for any node subproblem turns out to be feasible to GGP problem, we update the upper bound UB if necessary. Then, for each stage k, the active nodes collection Qk will satisfy LB(X)<UB, for all  X∈Qk. We now select an active node to partition its associated rectangle into two subrectangles according to the following branching rule. For such two subrectangles, the fathoming step is applied in order to identify whether the subrectangles should be eliminated. In the end, we obtain a collection of active nodes for the next stage. This process is repeated until convergence is obtained.


### 3.1. Branching Rule

As we all know, the critical element in guaranteeing convergence to the global optimal solution is the choice of a suitable partitioning strategy. In this paper, we choose a simple and standard bisection rule. This rule is sufficient to ensure convergence since it drives all the intervals to a singleton for all variables. Consider any node subproblem identified by rectangle(3.1)X={x∈Rn∣x̲i≤xi≤x¯i,i=1,…,n}⊆X0.The branching rule is as follows.(a)
Lets=argmax{x¯i-x̲i,i=1,…,n}.(b)
Letγs satisfy γs=(1/2)(x̲s+x¯s).(c)
Let(3.2)X1={x∈Rn∣x̲i≤xi≤x¯i,i≠s,x̲s≤xs≤γs},X2={x∈Rn∣x̲i≤xi≤x¯i,i≠s,γs≤xs≤x¯s}.
Through this branching rule, the rectangle X is partitioned into two subrectangles X1 and X2.


### 3.2. Algorithm Statement

Based on the former results, the basic steps of the proposed global optimization algorithm are summarized as follows. LetLB(X) refer to the optimal value of RLP problem on the rectangle X.Step 1.
Chooseϵ>0. Find an optimal solution x0 and the optimal value LB(X0) for RLP problem with X=X0. Set LB0=LB(X0). If x0 is feasible to GGP problem, then update the upper bound UB0=ϕ0(x0). If UB0-LB0≤ϵ, then stop: x0 is a global ϵ-optimal solution of GGP problem. Otherwise, set Q0={X0},F=∅,k=1.Step 2.
SetLBk=LBk-1. Subdivide Xk-1 into two rectangles Xk,1,Xk,2 via the branching rule. Let F=F⋃{Xk-1}.Step 3.
For each new subrectangleXk,t,t=1,2, utilize the pruning technique of Theorem 2.2 to prune box Xk,t,t=1,2. Update the corresponding parameters Ki,y̲j,y¯j(i=1,…,n,j=0,…,m). Compute LB(Xk,t) and find an optimal solution xk,t for RLP problem with X=Xk,t, where t=1,2. If possible, update the upper bound UBk=min{UBk,ϕ0(xk,t)}, and let xk denote the point which satisfies UBk=ϕ0(xk,t).Step 4.
IfUBk≤LB(Xk,t), then set F=F⋃{Xk,t}.Step 5.
F=F⋃{X∈Qk-1∣UBk≤LB(X)}.Step 6.
SetQk={X∣X∈Qk-1⋃{Xk,1,Xk,2},X∉F}.Step 7.
SetLBk=min{LB(X)∣X∈Qk}, and let Xk∈Qk satisfy LBk=LB(Xk). If UBk-LBk≤ϵ, then stop: xk is a global ϵ-optimal solution of GGP problem. Otherwise, set k=k+1, and go to Step 2.


### 3.3. Convergence of the Algorithm

The convergence properties of the algorithm are given in the following theorem.Theorem 3.1.
(a) If the algorithm is finite, then upon termination,xk is a global ϵ-optimal solution of GGP problem.
(b) If the algorithm is infinite, then, along any infinite branch of the branch and bound tree, an infinite sequence of iterations will be generated, and any accumulation point of the sequence{xk} will be a global solution of GGP problem.Proof.
(a) If the algorithm is finite, then it terminates in some stagek,k≥0. Upon termination, by the algorithm, it follows that UBk-LBk≤ϵ. From Steps 1 and 3, this implies that ϕ0(xk)-LBk≤ϵ. Let ϕ0* denote the optimal value of GGP problem, then, by Section 2, we know that LBk≤ϕ0*. Since xk is a feasible solution of GGP problem, ϕ0(xk)≥ϕ0*.
Taken together above, this implies thatϕ0*≤ϕ0(xk)≤LBk+ϵ≤ϕ0*+ϵ. Therefore, ϕ0*≤ϕ0(xk)≤ϕ0*+ϵ, and the proof of part (a) is complete.
(b) LetD denote the feasible region of GGP problem. When the algorithm is infinite, from the construction of the algorithm, we know that LBk is a nondecreasing sequence bounded above by minx∈Dϕ0(x), which guarantees the existence of the limit LB=limk→∞LBk≤minx∈Dϕ0(x). Since {xk} is contained in a compact set X0, there exists one convergent subsequence {xs}⊆{xk}, and suppose lims→∞xs=x¯. Then, from the proposed algorithm, there exists a decreasing subsequence {Xr}⊆{Xs}, where xr∈Xr,LBr=LB(Xr)=ϕ0l(xr), and limr→∞Xr=x¯. According to Theorem 2.1, we have
(3.3)lim⁡r→∞ϕ0l(xr)=lim⁡r→∞ϕ0(xr)=ϕ0(x¯).
The only remaining problem is to prove thatx¯∈D. Since X0 is a closed set, it follows that x¯∈X0. Assume that x¯∉D, then there exists some ϕj(x)(j=1,…,m) such that ϕj(x¯)>βj. Since ϕjl(x) is continuous, by Theorem 2.1, the sequence {ϕjl(xr)} will convergent to ϕj(x¯). By the definition of convergence, there exists r¯, such that for any r>r¯, |ϕjl(xr)-ϕj(x¯)|<ϕj(x¯)-βj. Therefore, for any r>r¯, we have ϕjl(xr)>βj, which implies that RLP(Xr) is infeasible. This contradicts the assumption of xr=x(Xr). Therefore, x¯∈D, that is,  x¯ is a global solution of GGP problem, and the proof of part (b) is complete.


## 3.1. Branching Rule

As we all know, the critical element in guaranteeing convergence to the global optimal solution is the choice of a suitable partitioning strategy. In this paper, we choose a simple and standard bisection rule. This rule is sufficient to ensure convergence since it drives all the intervals to a singleton for all variables. Consider any node subproblem identified by rectangle(3.1)X={x∈Rn∣x̲i≤xi≤x¯i,i=1,…,n}⊆X0.The branching rule is as follows.(a)
Lets=argmax{x¯i-x̲i,i=1,…,n}.(b)
Letγs satisfy γs=(1/2)(x̲s+x¯s).(c)
Let(3.2)X1={x∈Rn∣x̲i≤xi≤x¯i,i≠s,x̲s≤xs≤γs},X2={x∈Rn∣x̲i≤xi≤x¯i,i≠s,γs≤xs≤x¯s}.
Through this branching rule, the rectangle X is partitioned into two subrectangles X1 and X2.


## 3.2. Algorithm Statement

Based on the former results, the basic steps of the proposed global optimization algorithm are summarized as follows. LetLB(X) refer to the optimal value of RLP problem on the rectangle X.Step 1.
Chooseϵ>0. Find an optimal solution x0 and the optimal value LB(X0) for RLP problem with X=X0. Set LB0=LB(X0). If x0 is feasible to GGP problem, then update the upper bound UB0=ϕ0(x0). If UB0-LB0≤ϵ, then stop: x0 is a global ϵ-optimal solution of GGP problem. Otherwise, set Q0={X0},F=∅,k=1.Step 2.
SetLBk=LBk-1. Subdivide Xk-1 into two rectangles Xk,1,Xk,2 via the branching rule. Let F=F⋃{Xk-1}.Step 3.
For each new subrectangleXk,t,t=1,2, utilize the pruning technique of Theorem 2.2 to prune box Xk,t,t=1,2. Update the corresponding parameters Ki,y̲j,y¯j(i=1,…,n,j=0,…,m). Compute LB(Xk,t) and find an optimal solution xk,t for RLP problem with X=Xk,t, where t=1,2. If possible, update the upper bound UBk=min{UBk,ϕ0(xk,t)}, and let xk denote the point which satisfies UBk=ϕ0(xk,t).Step 4.
IfUBk≤LB(Xk,t), then set F=F⋃{Xk,t}.Step 5.
F=F⋃{X∈Qk-1∣UBk≤LB(X)}.Step 6.
SetQk={X∣X∈Qk-1⋃{Xk,1,Xk,2},X∉F}.Step 7.
SetLBk=min{LB(X)∣X∈Qk}, and let Xk∈Qk satisfy LBk=LB(Xk). If UBk-LBk≤ϵ, then stop: xk is a global ϵ-optimal solution of GGP problem. Otherwise, set k=k+1, and go to Step 2.


## 3.3. Convergence of the Algorithm

The convergence properties of the algorithm are given in the following theorem.Theorem 3.1.
(a) If the algorithm is finite, then upon termination,xk is a global ϵ-optimal solution of GGP problem.
(b) If the algorithm is infinite, then, along any infinite branch of the branch and bound tree, an infinite sequence of iterations will be generated, and any accumulation point of the sequence{xk} will be a global solution of GGP problem.Proof.
(a) If the algorithm is finite, then it terminates in some stagek,k≥0. Upon termination, by the algorithm, it follows that UBk-LBk≤ϵ. From Steps 1 and 3, this implies that ϕ0(xk)-LBk≤ϵ. Let ϕ0* denote the optimal value of GGP problem, then, by Section 2, we know that LBk≤ϕ0*. Since xk is a feasible solution of GGP problem, ϕ0(xk)≥ϕ0*.
Taken together above, this implies thatϕ0*≤ϕ0(xk)≤LBk+ϵ≤ϕ0*+ϵ. Therefore, ϕ0*≤ϕ0(xk)≤ϕ0*+ϵ, and the proof of part (a) is complete.
(b) LetD denote the feasible region of GGP problem. When the algorithm is infinite, from the construction of the algorithm, we know that LBk is a nondecreasing sequence bounded above by minx∈Dϕ0(x), which guarantees the existence of the limit LB=limk→∞LBk≤minx∈Dϕ0(x). Since {xk} is contained in a compact set X0, there exists one convergent subsequence {xs}⊆{xk}, and suppose lims→∞xs=x¯. Then, from the proposed algorithm, there exists a decreasing subsequence {Xr}⊆{Xs}, where xr∈Xr,LBr=LB(Xr)=ϕ0l(xr), and limr→∞Xr=x¯. According to Theorem 2.1, we have
(3.3)lim⁡r→∞ϕ0l(xr)=lim⁡r→∞ϕ0(xr)=ϕ0(x¯).
The only remaining problem is to prove thatx¯∈D. Since X0 is a closed set, it follows that x¯∈X0. Assume that x¯∉D, then there exists some ϕj(x)(j=1,…,m) such that ϕj(x¯)>βj. Since ϕjl(x) is continuous, by Theorem 2.1, the sequence {ϕjl(xr)} will convergent to ϕj(x¯). By the definition of convergence, there exists r¯, such that for any r>r¯, |ϕjl(xr)-ϕj(x¯)|<ϕj(x¯)-βj. Therefore, for any r>r¯, we have ϕjl(xr)>βj, which implies that RLP(Xr) is infeasible. This contradicts the assumption of xr=x(Xr). Therefore, x¯∈D, that is,  x¯ is a global solution of GGP problem, and the proof of part (b) is complete.


## 4. Numerical Experiment

In this section, we report some numerical results to verify the performance of the proposed algorithm. The test problems are implemented on a Pentium IV (1.66 GHZ) microcomputer. The algorithm is coded in Matlab 7.1 and uses simplex method to solve the relaxation linear programming problems. In our experiments, the convergence tolerance set toϵ=1.0e-3.Example 4.1 (see [8]).
We have the following:(4.1)min⁡0.5x1x2-1-x1-5x2-1s.t.0.01x2x3-1+0.01x2+0.0005x1x3≤1,x∈X0={x∣70≤x1≤150,1≤x2≤30,0.5≤x3≤21}.
By using the method in this paper, the optimal solution is(150,30,1.3189), the optimal value is −147.6667, and the number of algorithm iterations is 557. But using the method in [8], the optimal solution is (88.72470,7.67265,1.31786), the optimal value is −83.249728406, and the number of algorithm iterations is 1829.Example 4.2 (see [10]).
We have the following:(4.2)min⁡x1s.t.4x2-4x12≤1,-x1-x2≤-1,x∈X0={x∣0.01≤x1≤15,0.01≤x2≤15}.
Through using the method in this paper, the optimal solution (0.5, 0.5) with optimal value 0.5 is found after 16 iterations. But using the method in [10], the optimal solution (0.5, 0.5) with optimal value 0.5 is found after 96 iterations.Example 4.3.
We have the following:(4.3)min⁡-x1+x11.2x20.5-x20.8s.t.-6x1x23+8x20.5≤3,3x1-x2≤3,x∈X0={x∣0.5≤x1≤15,0.5≤x2≤15}.
By utilizing the method in this paper, the optimal value −1.3501 is found after 14 iterations at an optimal solution (0.5, 1.5).Example 4.4.
We have the following:(4.4)min⁡0.3578x30.1+0.8357x1x5s.t.0.00002584x3x5-0.00006663x2x5-0.0000734x1x4≤5,0.00085303x2x5+0.00009395x1x4-0.00033085x3x5≤5,1.3294x2-1x5-1-0.4200x1x5-1-0.30586x2-1x32x5-1≤5,0.00024186x2x5+0.00010159x1x2+0.00007379x32≤5,2.1327x3-1x5-1-0.26680x1x5-1-0.40584x4x5-1≤5,0.00029955x3x5+0.00007992x1x3+0.00012157x3x4≤5,x∈X0={x∣1≤x1≤60,1≤x2≤60,1≤x3≤60,1≤x4≤60,1≤x5≤60}.
Utilizing the method in this paper, we find the optimal value 1.1935  after 15 iterations at an optimal solutionx*=(1.0,30.2734,1.0,17.4640,1.0).
In the future work, we will do more numerical experiments to test the performance of the proposed algorithm.



---

*Source: 346965-2011-01-18.xml*