# Global Optimization for the Sum of Certain Nonlinear Functions

Authors: Mio Horai; Hideo Kobayashi; Takashi G. Nitta
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

We extend work by Pei-Ping and Gui-Xia, 2007,  to a global optimization problem for more general functions. Pei-Ping and Gui-Xia treat the optimization problem for the linear sum of polynomial fractional functions, using a branch and bound approach. We prove that this extension makes possible to solve the following nonconvex optimization problems which Pei-Ping and Gui-Xia, 2007, cannot solve, that the sum of the positive (or negative) first and second derivatives function with the variable defined by sum of polynomial fractional function by using branch and bound algorithm.


---

## Body

## 1. Introduction

The optimization problem is widely used in sciences, especially in engineering and economy [1–3]. In 2007, Pei-Ping and Gui-Xia considered one global optimization problem in [4]:
(P)min⁡ω(x)=∑j=1P‍cjbj(x)aj(x)s.t.Kgkx≤0,x∈X,
where X:={x∈RN∣0<x_i≤xi≤x¯i<∞(i=1,2,…,N)}, aj(x), bj(x), gk(x) are given generalized polynomial. One has
(1)ajx≔∑t=1Tja‍βjta∏i=1N‍xiγjtia,bjx≔∑t=1Tjb‍βjtb∏i=1N‍xiγjtib,gkx:=∑t=1Tkg‍βkta∏i=1N‍xiγktig.Sum of rations problems like(P) attract a lot of attention, and the reason is that these problems are applied to various economical problems [4].Pei-Ping and Gui-Xia proposed the method to solve these problems globally by using branch and bound algorithm in [4]. In the above problem, the objective function and constrained function are sums of generalized polynomial fractional functions. We extend these functions to more general functions like below:
(P0)min⁡w(x)=∑j=1Phjbjxajxs.t.Kgkx=∑j´=1Pkhkj´dkj´xckj´x≤0kkkkkj´=1,…,PK,k=1,…,M,kkkkkx∈X,
where aj(x)>0, bj(x)>0, ckj´(x)>0, dkj´(x)>0  x∈X; that is,
(2)aj(x)∶=∑t=1Tja‍βjta∏i=1N‍xiγjtia,bj(x):=∑t=1Tjb‍βjtb∏i=1N‍xiγjtib,ckj´(x)∶=∑t=1Tkj´c‍βkj´tc∏i=1N‍xiγkj´tc,dkj´(x)∶=∑t=1Tkj´d‍βkj´td∏i=1N‍xiγkj´td,j=1,2,…,P,j´=1,2,…,Pk,k=1,2,…,M,
where Tja, Tjb, Tkj´c, Tkj´d are natural numbers, and βjta, βjtb, βkj´tc, βkj´td are real constants not zero, and γjtia, γjtib, γkj´tc, γkj´td are real constants.We assume thathj(yj), hkj´(ykj´):R↦R are secondly differentiable functions and monotone increasing or monotone decreasing functions. We divide these functions to monotone increasing or monotone decreasing as follows:
(3)hj′>0j=1,…,K,hj′<0(j=K+1,…,P),hkj´′>0j´=1,…,Kk,hkj´′<0(j´=Kk+1,…,Pk).Furthermore, we assume the following conditions for the second derivatives:(4)hj∘exp⁡zj′′>0,hj∘exp⁡zj′′<0,hkj´∘exp⁡zkj´′′>0,hkj´∘exp⁡zkj´′′<0j=1,…,P,j´=1,…,Pk,k=1,…,M.
To solve the above problem (P0), we transform the problem (P0) to the equivalent problems (P1), (P2) and transform (P2) into the linear relaxation problem. We prove the equivalency of the problems under above assumption, and we calculate the equivalent problem using branch and bound algorithm corresponding to [4–6].For example, according to this extension at approach, we can calculate the following global optimization problem:(5)min⁡sinx12+3x2-2x22+1x12+x2+2kkkkk+cos⁡-x22+2x1+2x2x1+2.5ks.t.kx12-x1x2-1≤0kkWWx1+3x2x1-5≤0kkkkkkX=x:1≤x1≤3,1≤x2≤3.In this paper, we explain how to make equivalent relaxation linear problem from original problem in Section2. In Section 3, we present the branch and bound algorithm and its convergence. In Section 4, we introduce numerical experiments result.


## 2. Equivalence Transformation and Linear Relaxation

In this section we firstly transform the problem(P0) to the equivalent problems (P1) and secondly transform (P1) to (P2). Thirdly we linearize the problem (P2) corresponding to [4].


### 2.1. Translation of the Problem(P0) into (P1)

For the problem(P0), we put new variables mj, lj, tkj´ and skj´, and the function ρ(l,m) and ξk(s,t) depending on hj, hkj´ in the original problem (P0):
(6)ρl,m∶=∑j=1P‍hjmjljj=1,2,…,P,ξk(s,t)∶=∑j´=1Pk‍hkj´tkj´skj´(j´=1,…,Pk,k=1,…,M).
Since aj(x), bj(x), ckj´(x), dkj´(x) are polynomials on closed interval X, it is easy to calculate the minimums and maximums of the functions on X; we denote them by a_j, a¯j, b_j, b¯j, c_kj´, c¯kj´, d_kj´, d¯kj´.LetH be the closed interval:
(7)H∶=d_kj´≤tkj´≤d¯kj´l,m,s,t∈RPsum∣kka_j≤lj≤a¯j,b_j≤mj≤b¯j,kkc_kj´≤skj´≤c¯kj´,d_kj´≤tkj´≤d¯kj´,
where Psum=2P+∑k=1MPk.LetZH be the following closed domain in X×H; that is,
(8)ZH≔j´=Kk+1,…,Pk,k=1,…,Mx,l,m,s,t∈X×H∣kkkξk(s,t)≤0k=1,…,M,kkkklj-aj(x)≤0,bjx-mj≤0kkkkkkkkkkkkkkkkkj=1,…,K,kkkkaj(x)-lj≤0,mj-bj(x)≤0kkkkkkkkkkkkkkkkkkj=K+1,…,P,kkkkkkskj´-ckj´(x)≤0,dkj´(x)-tkj´≤0kkkkkkkkkkkkj´=1,…,Kk,k=1,…,M,kkkkkkckj´(x)-skj´≤0,tkj´-dkj´(x)≤0kkkkkkj´=Kk+1,…,Pk,k=1,…,M.
We give the problem (P1) on ZH. Consider
(P1)min⁡ρ(l,m)s.t.lξks,t≤0,k=1,…,M,kkkkkl(x,l,m,s,t)∈ZH.
Now we obtain Theorem 1 that proves the equivalence of (P0) and (P1).Theorem 1.
The problem(P0) on X is equivalent to the problem (P1) on ZH.Proof.
Letx* be the optimal solution for (P0); we denote
(9)lj*:=aj(x*),mj*:=bj(x*),skj´*:=ckj´x*,tkj´*:=dkj´x*,
and then
(10)∑j=1Phjbj(x*)aj(x*)=∑j=1Phjmj*lj*,∑j´=1Pk‍hkj´dkj´(x*)ckj´(x*)=∑j´=1Pk‍hkj´tkj´*skj´*.
Furthermore let(x♯,l♯,m♯,s♯,t♯) be the optimal solution for (P1). Then by the restricted condition we have the following: forj=1,…,K, 0<lj♯≤aj(x♯) and 0<bj(x♯)≤mj♯; that is, 0<bj(x♯)/aj(x♯)≤mj♯/lj♯;forj=K+1,…,P, 0<aj(x♯)≤lj♯ and 0<mj♯≤bj(x♯); that is, 0<mj♯/lj♯≤bj(x♯)/aj(x♯);forj´=1,…,Kk and k=1,…,M, 0<skj´♯≤ckj´(x♯) and 0<dkj´(x♯)≤tkj´♯; that is, 0<dkj´(x♯)/ckj´(x♯)≤tkj´♯/skj´♯;forj´=Kk+1,…,Pk and k=1,…,M, 0<ckj´(x♯)≤skj´♯ and 0<tkj´♯≤dkj´(x♯); that is, 0<tkj´♯/skj´♯≤dkj´(x♯)/ckj´(x♯).
The conditionshj′>0j=1,…,K, or hj′<0j=K+1,…,P and hkj´′>0(j´=1,…,Kk), or hkj´′<0(j´=Kk+1,…,Pk) lead to
(11)hjbj(x♯)aj(x♯)≤hjmj♯lj♯(j=1,…,P),hkj´dkj´(x♯)ckj´(x♯)≤hkj´tkj´♯skj´♯(j´=1,…,Pk,k=1,…,M).
Therefore we obtain
(12)∑j=1P‍hjbj(x♯)aj(x♯)≤∑j=1P‍hjmj♯lj♯,∑j´=1Pk‍hkj´dkj´(x♯)ckj´(x♯)≤∑j´=1Pk‍hkj´tkj´♯skj´♯.
Now,
(13)∑j´=1Pk‍hkj´dkj´(x♯)ckj´(x♯)≤∑j´=1Pk‍hkj´tkj´♯skj´♯≤0,
that is, x♯ satisfied constant for (P0).
Since the optimal solution for(P0) is x*, we obtain
(14)hjbj(x*)aj(x*)≤hjbj(x♯)aj(x♯),
so
(15)∑j=1P‍hjmj*lj*=∑j=1P‍hjbjx*ajx*≤∑j=1P‍hjmj♯lj♯,∑j=1P‍hjmj*lj*≤∑j=1P‍hjmj♯lj♯.
For the optimal solution x* of (P0), we denote
(16)lj*:=aj(x*),mj*:=bj(x*),skj´*:=ckj´x*,tkj´*:=dkj´x*;
then
(17)ρl*,m*=wx*,ξk(s*,t*)=g(x*).
The element (x*,l*,m*,s*,t*) satisfies the conditions for ZH. Since (x♯,l♯,m♯,s♯,t♯) is the optimal solution for (P1), it satisfies ∑j=1Phjmj♯/lj♯≤∑j=1Phjmj*/lj*.
Hence∑j=1Phjmj♯/lj♯=∑j=1Phjmj*/lj*; that is, the two problems are equivalent.


### 2.2. Translation of the Problem(P1) into (P2)

We change the variables by the logarithmic functionlog⁡. Since xi, lj, mj, skj´, tkj´ are positive, we can write xi, lj, mj, skj´, tkj´ as exp⁡(yn) are using new variables yn(n=1,…,N+Psum); that is, yi:=ln⁡xi, yN+j:=ln⁡lj, yN+P+j:=ln⁡mj, yN+2P+(k-1)Pk+j´:=ln⁡skj´, and yN+2P+(M+k-1)Pk+j´:=ln⁡tkj´.The closed domainZH corresponds to the following S0, where
(18)S0∶=y∈RN+Psum∣kkln⁡x_i≤yi≤ln⁡x¯i,kkkkln⁡a_j≤yN+j≤ln⁡a¯j,kkkkln⁡b_j≤yN+P+j≤ln⁡b¯j,kkkkln⁡c_kj´≤yN+2P+k-1Pk+j´≤ln⁡c¯kj´,kkkkln⁡d_kj´≤yN+2P+M+k-1Pkj´≤ln⁡d¯kj´.
Using such transformation of variables, the objective function and the restricted functions of (P1) are changed to the following:
(19)∑j=1Phjmjlj=∑j=1Phj∘exp⁡⁡yN+P+j-yN+j,∑j´=1Pkhkj´tkj´skj´=∑j´=1Pkhkj´∘exp⁡⁡yN+2P+M+k-1Pk+j´-yN+2P+k-1Pk-j´,lj-ajx=exp⁡⁡yN+j-∑t=1Tjaβjtaexp⁡⁡∑i=1Nγjtiayi,bjx-mj=∑t=1Tjbβjtbexp⁡⁡∑i=1Nγjtibyi-exp⁡⁡yN+P+j,skj´-ckj´x=exp⁡⁡yN+2P+k-1Pk+j´-∑t=1Tjcβjtcexp⁡⁡∑i=1Nγjticyi,dkj´x-tkj´=∑t=1Tjdβjtdexp⁡⁡∑i=1Nγjtidyi-exp⁡⁡yN+2P+M+k-1PK+j´.Nowρ(l,m), ξk(s,t), lj-aj(x), bj(x)-mj, skj´-ckj´(x), dkj´(x)-tkj´, are represented as
(20)∑t=1TmΨmt∘exp⁡∑i=1N+Psumλmtiyi,
where λmti is real number and Ψmt satisfies Ψmt′(x)>0 or Ψmt′(x)<0, and Ψmt∘exp⁡y′′>0 or Ψmt∘exp⁡y′′<0.Letfmt(y) be Ψmt∘exp⁡(y) and let μm(y) be ∑t=1Tmfmt∑i=1N+Psumλmtiyi.Then the objective functionρ(l,m) and the restricted functions are changed functions which are changed to μ0(y) and μm(y)m=1,…,M+2P+∑k=1MPk.Now we put(21)Sμ0∶=m=1,2,…,M+2P+∑k=1M‍Pky∈S0∣kkkkkμmy≤0m=1,2,…,M+2P+∑k=1M‍Pk.
Then the problem (P1) is transformed naturally to the following problem (P2):
(P2)min⁡μ0(y)is.t.ky∈Sμ0.


### 2.3. Linearization of the Problem(P2)

The objective and restricted function for(P2) are nonlinear. On Sμ0, we approximate μm(y) to lower bounded linear functions, and we can transform (P2) into the linear optimization problem. The solution of it is lower bound of the optimal value on (P2). We denote y_i, y¯i, y_N+j, y¯N+j, y_N+P+j, y¯N+P+j, y_N+2P+k-1Pk+j´, y¯N+2P+(k-1)Pk+j´, y_N+2P+M+k-1Pk+j´, y¯N+2P+(M+k-1)Pk+j´ as minimums and maximums for ln⁡x_i, ln⁡x¯i, ln⁡a_j, ln⁡a¯j, ln⁡b_j, ln⁡b¯j, ln⁡c_kj´, ln⁡c¯kj´, ln⁡d_kj´, ln⁡d¯kj´j=1,…,P,j´=1,…,Pk,k=1,…,M.And we denoteSq⊂Sμ0; that is,
(22)Sq∶=y∈RN+Psum∣KKKKy_i≤y_iq≤yi≤y¯iq≤y¯iKKKKi=1,…,N+PsumRN+Psum,YmtSq∶=∑i=1N+Psum‍λmtiyi,Y_mtSq∶=∑i=1N+Psum‍min⁡λmtiy_iq,λmtiy¯iq,Y¯mtSq∶=∑i=1N+Psum‍max⁡λmtiy_iq,λmtiy¯iq,m=0,1,2,…,M+2P+∑k=1M‍Pk,t=1,…,Tm.Now,fmt′(y)>0 or fmt′(y)<0, and fmt′′(y)>0 or fmt′′(y)<0, and fmtYmtSq is monotonic convex function on Y_mtSq,Y¯mtSq. And there exist the upper and lower bounded linear functions (FmtSqYmtSq and GmtSqYmtSq) of fmtYmtSq.We denote(23)FmtSqYmtSq≔fmtY¯mtSq-fmtY_mtSqY¯mtSq-Y_mtSqYmtSq-Y_mtSq+fmtY_mtSq.
As fmtYmtSq is continuous on Y_mtSq,Y¯mtSq and differentiable on Y_mtSq,Y¯mtSq, there exists cmtSq∈Y_mtSq,Y¯mtSq, such that
(24)fmt′cmtSq=fmtY¯mtSq-fmtY_mtSqY¯mtSq-Y_mtSq,
by the mean value theorem.Sincefmt′(y)>0 or fmt′(y)<0, fmtYmtSq is monotonic function on Y_mtSq,Y¯mtSq, there exists the inverse function of fmtY_mtSq. Hence cmtSq is uniquely decided, fmt-1YmtSq, such that
(25)cmtSq=fmt-1fmtY¯mtSq-fmtY_mtSqY¯mtSq-Y_mtSq,
and we define
(26)GmtSqYmtSq∶=fmtY¯mtSq-fmtY_mtSqY¯mtSq-Y_mtSqYmtSq-cmtSq+fmtcmtSq,LmtSq(YmtSq)∶=GmtSq(YmtSq)(fmt′′(y)>0)FmtSq(YmtSq)(fmt′′(y)<0).
By the definition, fmt(YmtSq)≥Lmt(YmtSq).For ally∈Sq, μm(y):=∑t=1Tm‍fmt(y)≥∑t=1Tm‍LmtSq(y).LetLmSq(y):=∑t=1Tm‍LmtSq(y)0≤m≤M+2P+∑k=1M‍Pk. Then L0(y) is a linear function which is lower function for the convex envelope of μ0(y) on the rectangle.LRP
S
q is the linear problem of (P2) by the lower bounded function of μm(y):
LRPSqmin⁡L0Sq(y)is.t.kLmSq(y)≤0KKKkm=1,2,…,M+2P+∑k=1M‍Pk.
By the definition LRPSq, any y in Sq satisfying the restricted condition of (P2) satisfy the restricted condition of LRPSq.Lemma 2.
The value ofLRPSq is less than the optimal value for the problem (P2) on Sq.Proof.
The definition ofLRPSq implies the statement naturally.Lemma 3.
Assume thatSq+1⊂Sq⊂⋯⊂S0⊂RN+Psum, and ⋂q=0∞‍Sq={y*}. For each m=0,1,2,…,M+2P+∑k=1M‍Pk and t=1,2,…,Tm, lim⁡q→∞max⁡y∈SqFmtSq(y)-fmt(y)=0 and lim⁡q→∞max⁡y∈SqGmtSq(y)-fmt(y)=0.Proof.
Lety_q:={y∈Sq∣min⁡(λmtiy_iq,λmtiy¯iq)(i=1,…,N+Psum)} and y¯q:={y∈Sq∣max⁡(λmtiy_iq,λmtiy¯iq)(i=1,…,N+Psum)}.
Since⋂q=0∞‍Sq={y*}, the values y_q and y¯q satisfy lim⁡q→∞y_q=lim⁡q→∞y¯q=y*.
Hence,Y¯mtSq-Y_mtSq=∑i=1N+Psum‍λmti(y¯iq-y_iq)→q→∞0.
Now,(27)FmtSqy-fmty=FmtSq(YmtSq)-fmt(YmtSq)=fmt(Y¯mtSq)-fmt(Y_mtSq)Y¯mtSq-Y_mtSq(YmtSq-Y_mtSq)kkkkk+fmt(Y_mtSq)-fmt(YmtSq)fmt(Y¯mtSq)-fmt(Y_mtSq)Y¯mtSq-Y_mtSq.
The function FmtSq(y)-fmt(y) is concave on Y_mtSq,Y¯mtSq; therefore cmtSq attains the maximum value of FmtSq(y)-fmt(y):max⁡y∈SqFmtSq(y)-fmt(y)(28)max⁡y∈SqFmtSqy-fmty=FmtSq(cmtSq)-fmt(cmtSq)=fmtY¯mtSq-fmtY_mtSqY¯mtSq-Y_mtSqcmtSq-Y_mtSqkkkkk+fmtY_mtSq-fmtcmtSqfmtY¯mtSq-fmtY_mtSqY¯mtSq-Y_mtSq.
We denote(29)ImtSq=Y¯mtSq-Y_mtSq,cmtSq=Y_mtSq+θmtSqImtSq(0<θmtSq<1).
Since ImtSq→0 for q→∞,
(30)fmtY¯mtSq-fmtY_mtSqY¯mtSq-Y_mtSqcmtSq-Y_mtSqkk+fmtY_mtSq-fmtcmtSqfmtY¯mtSq-fmtY_mtSqY¯mtSq-Y_mtSq=fmt(Y_mtSq+ImtSq)-fmt(Y_mtSq)Y_mtSq+ImtSq-Y_mtSq(Y_mtSq+θmtSqImtSq-Y_mtSq)kkk+fmt(Y_mtSq)-fmt(Y_mtSq+θmtSqImtSq)fmt(Y_mtSq+ImtSq)-fmt(Y_mtSq)Y_mtSq+ImtSq-Y_mtSq=fmt(Y_mtSq+ImtSq)-fmt(Y_mtSq)Y_mtSq+ImtSq-Y_mtSq(θmtSqImtSq)kkk+fmt(Y_mtSq)-fmt(Y_mtSq+θmtSqImtSq)fmt(Y_mtSq+ImtSq)-fmt(Y_mtSq)Y_mtSq+ImtSq-Y_mtSq=fmt(Y_mtSq+ImtSq)θmtSq-fmt(Y_mtSq)θmtSq+fmt(Y_mtSq)kkk-fmt(Y_mtSq+θmtSqImtSq)→q→∞fmtY_mtSqθmtSq-fmtY_mtSqθmtSqkkkkkk+fmtY_mtSq-fmtY_mtSq=0.
Thus
(31)GmtSqy-fmty=GmtSq(YmtSq)-fmt(YmtSq)=fmtY¯mtSq-fmtY_mtSqY¯mtSq-Y_mtSqYmtSq-cmtSqkkkkk+fmtcmtSq-fmtYmtSqfmtY¯mtSq-fmtY_mtSqY¯mtSq-Y_mtSq.
On the other hand GmtSq(y)-fmt(y) is a convex function by the same argument, and we obtain the following max⁡y∈SqGmtSq(y)-fmt(y)→0 for q→∞.Lemma 4.
Under the same assumption of Lemma3  max⁡y∈SqLmSqy-μmy→0 for q→∞ and each m=0,1,2,…,M+2P+∑k=1MPk.Proof.
Lemma3 and the definitions LmSq(y), μm(y) imply Lemma 4, standardly.


## 2.1. Translation of the Problem(P0) into (P1)

For the problem(P0), we put new variables mj, lj, tkj´ and skj´, and the function ρ(l,m) and ξk(s,t) depending on hj, hkj´ in the original problem (P0):
(6)ρl,m∶=∑j=1P‍hjmjljj=1,2,…,P,ξk(s,t)∶=∑j´=1Pk‍hkj´tkj´skj´(j´=1,…,Pk,k=1,…,M).
Since aj(x), bj(x), ckj´(x), dkj´(x) are polynomials on closed interval X, it is easy to calculate the minimums and maximums of the functions on X; we denote them by a_j, a¯j, b_j, b¯j, c_kj´, c¯kj´, d_kj´, d¯kj´.LetH be the closed interval:
(7)H∶=d_kj´≤tkj´≤d¯kj´l,m,s,t∈RPsum∣kka_j≤lj≤a¯j,b_j≤mj≤b¯j,kkc_kj´≤skj´≤c¯kj´,d_kj´≤tkj´≤d¯kj´,
where Psum=2P+∑k=1MPk.LetZH be the following closed domain in X×H; that is,
(8)ZH≔j´=Kk+1,…,Pk,k=1,…,Mx,l,m,s,t∈X×H∣kkkξk(s,t)≤0k=1,…,M,kkkklj-aj(x)≤0,bjx-mj≤0kkkkkkkkkkkkkkkkkj=1,…,K,kkkkaj(x)-lj≤0,mj-bj(x)≤0kkkkkkkkkkkkkkkkkkj=K+1,…,P,kkkkkkskj´-ckj´(x)≤0,dkj´(x)-tkj´≤0kkkkkkkkkkkkj´=1,…,Kk,k=1,…,M,kkkkkkckj´(x)-skj´≤0,tkj´-dkj´(x)≤0kkkkkkj´=Kk+1,…,Pk,k=1,…,M.
We give the problem (P1) on ZH. Consider
(P1)min⁡ρ(l,m)s.t.lξks,t≤0,k=1,…,M,kkkkkl(x,l,m,s,t)∈ZH.
Now we obtain Theorem 1 that proves the equivalence of (P0) and (P1).Theorem 1.
The problem(P0) on X is equivalent to the problem (P1) on ZH.Proof.
Letx* be the optimal solution for (P0); we denote
(9)lj*:=aj(x*),mj*:=bj(x*),skj´*:=ckj´x*,tkj´*:=dkj´x*,
and then
(10)∑j=1Phjbj(x*)aj(x*)=∑j=1Phjmj*lj*,∑j´=1Pk‍hkj´dkj´(x*)ckj´(x*)=∑j´=1Pk‍hkj´tkj´*skj´*.
Furthermore let(x♯,l♯,m♯,s♯,t♯) be the optimal solution for (P1). Then by the restricted condition we have the following: forj=1,…,K, 0<lj♯≤aj(x♯) and 0<bj(x♯)≤mj♯; that is, 0<bj(x♯)/aj(x♯)≤mj♯/lj♯;forj=K+1,…,P, 0<aj(x♯)≤lj♯ and 0<mj♯≤bj(x♯); that is, 0<mj♯/lj♯≤bj(x♯)/aj(x♯);forj´=1,…,Kk and k=1,…,M, 0<skj´♯≤ckj´(x♯) and 0<dkj´(x♯)≤tkj´♯; that is, 0<dkj´(x♯)/ckj´(x♯)≤tkj´♯/skj´♯;forj´=Kk+1,…,Pk and k=1,…,M, 0<ckj´(x♯)≤skj´♯ and 0<tkj´♯≤dkj´(x♯); that is, 0<tkj´♯/skj´♯≤dkj´(x♯)/ckj´(x♯).
The conditionshj′>0j=1,…,K, or hj′<0j=K+1,…,P and hkj´′>0(j´=1,…,Kk), or hkj´′<0(j´=Kk+1,…,Pk) lead to
(11)hjbj(x♯)aj(x♯)≤hjmj♯lj♯(j=1,…,P),hkj´dkj´(x♯)ckj´(x♯)≤hkj´tkj´♯skj´♯(j´=1,…,Pk,k=1,…,M).
Therefore we obtain
(12)∑j=1P‍hjbj(x♯)aj(x♯)≤∑j=1P‍hjmj♯lj♯,∑j´=1Pk‍hkj´dkj´(x♯)ckj´(x♯)≤∑j´=1Pk‍hkj´tkj´♯skj´♯.
Now,
(13)∑j´=1Pk‍hkj´dkj´(x♯)ckj´(x♯)≤∑j´=1Pk‍hkj´tkj´♯skj´♯≤0,
that is, x♯ satisfied constant for (P0).
Since the optimal solution for(P0) is x*, we obtain
(14)hjbj(x*)aj(x*)≤hjbj(x♯)aj(x♯),
so
(15)∑j=1P‍hjmj*lj*=∑j=1P‍hjbjx*ajx*≤∑j=1P‍hjmj♯lj♯,∑j=1P‍hjmj*lj*≤∑j=1P‍hjmj♯lj♯.
For the optimal solution x* of (P0), we denote
(16)lj*:=aj(x*),mj*:=bj(x*),skj´*:=ckj´x*,tkj´*:=dkj´x*;
then
(17)ρl*,m*=wx*,ξk(s*,t*)=g(x*).
The element (x*,l*,m*,s*,t*) satisfies the conditions for ZH. Since (x♯,l♯,m♯,s♯,t♯) is the optimal solution for (P1), it satisfies ∑j=1Phjmj♯/lj♯≤∑j=1Phjmj*/lj*.
Hence∑j=1Phjmj♯/lj♯=∑j=1Phjmj*/lj*; that is, the two problems are equivalent.


## 2.2. Translation of the Problem(P1) into (P2)

We change the variables by the logarithmic functionlog⁡. Since xi, lj, mj, skj´, tkj´ are positive, we can write xi, lj, mj, skj´, tkj´ as exp⁡(yn) are using new variables yn(n=1,…,N+Psum); that is, yi:=ln⁡xi, yN+j:=ln⁡lj, yN+P+j:=ln⁡mj, yN+2P+(k-1)Pk+j´:=ln⁡skj´, and yN+2P+(M+k-1)Pk+j´:=ln⁡tkj´.The closed domainZH corresponds to the following S0, where
(18)S0∶=y∈RN+Psum∣kkln⁡x_i≤yi≤ln⁡x¯i,kkkkln⁡a_j≤yN+j≤ln⁡a¯j,kkkkln⁡b_j≤yN+P+j≤ln⁡b¯j,kkkkln⁡c_kj´≤yN+2P+k-1Pk+j´≤ln⁡c¯kj´,kkkkln⁡d_kj´≤yN+2P+M+k-1Pkj´≤ln⁡d¯kj´.
Using such transformation of variables, the objective function and the restricted functions of (P1) are changed to the following:
(19)∑j=1Phjmjlj=∑j=1Phj∘exp⁡⁡yN+P+j-yN+j,∑j´=1Pkhkj´tkj´skj´=∑j´=1Pkhkj´∘exp⁡⁡yN+2P+M+k-1Pk+j´-yN+2P+k-1Pk-j´,lj-ajx=exp⁡⁡yN+j-∑t=1Tjaβjtaexp⁡⁡∑i=1Nγjtiayi,bjx-mj=∑t=1Tjbβjtbexp⁡⁡∑i=1Nγjtibyi-exp⁡⁡yN+P+j,skj´-ckj´x=exp⁡⁡yN+2P+k-1Pk+j´-∑t=1Tjcβjtcexp⁡⁡∑i=1Nγjticyi,dkj´x-tkj´=∑t=1Tjdβjtdexp⁡⁡∑i=1Nγjtidyi-exp⁡⁡yN+2P+M+k-1PK+j´.Nowρ(l,m), ξk(s,t), lj-aj(x), bj(x)-mj, skj´-ckj´(x), dkj´(x)-tkj´, are represented as
(20)∑t=1TmΨmt∘exp⁡∑i=1N+Psumλmtiyi,
where λmti is real number and Ψmt satisfies Ψmt′(x)>0 or Ψmt′(x)<0, and Ψmt∘exp⁡y′′>0 or Ψmt∘exp⁡y′′<0.Letfmt(y) be Ψmt∘exp⁡(y) and let μm(y) be ∑t=1Tmfmt∑i=1N+Psumλmtiyi.Then the objective functionρ(l,m) and the restricted functions are changed functions which are changed to μ0(y) and μm(y)m=1,…,M+2P+∑k=1MPk.Now we put(21)Sμ0∶=m=1,2,…,M+2P+∑k=1M‍Pky∈S0∣kkkkkμmy≤0m=1,2,…,M+2P+∑k=1M‍Pk.
Then the problem (P1) is transformed naturally to the following problem (P2):
(P2)min⁡μ0(y)is.t.ky∈Sμ0.


## 2.3. Linearization of the Problem(P2)

The objective and restricted function for(P2) are nonlinear. On Sμ0, we approximate μm(y) to lower bounded linear functions, and we can transform (P2) into the linear optimization problem. The solution of it is lower bound of the optimal value on (P2). We denote y_i, y¯i, y_N+j, y¯N+j, y_N+P+j, y¯N+P+j, y_N+2P+k-1Pk+j´, y¯N+2P+(k-1)Pk+j´, y_N+2P+M+k-1Pk+j´, y¯N+2P+(M+k-1)Pk+j´ as minimums and maximums for ln⁡x_i, ln⁡x¯i, ln⁡a_j, ln⁡a¯j, ln⁡b_j, ln⁡b¯j, ln⁡c_kj´, ln⁡c¯kj´, ln⁡d_kj´, ln⁡d¯kj´j=1,…,P,j´=1,…,Pk,k=1,…,M.And we denoteSq⊂Sμ0; that is,
(22)Sq∶=y∈RN+Psum∣KKKKy_i≤y_iq≤yi≤y¯iq≤y¯iKKKKi=1,…,N+PsumRN+Psum,YmtSq∶=∑i=1N+Psum‍λmtiyi,Y_mtSq∶=∑i=1N+Psum‍min⁡λmtiy_iq,λmtiy¯iq,Y¯mtSq∶=∑i=1N+Psum‍max⁡λmtiy_iq,λmtiy¯iq,m=0,1,2,…,M+2P+∑k=1M‍Pk,t=1,…,Tm.Now,fmt′(y)>0 or fmt′(y)<0, and fmt′′(y)>0 or fmt′′(y)<0, and fmtYmtSq is monotonic convex function on Y_mtSq,Y¯mtSq. And there exist the upper and lower bounded linear functions (FmtSqYmtSq and GmtSqYmtSq) of fmtYmtSq.We denote(23)FmtSqYmtSq≔fmtY¯mtSq-fmtY_mtSqY¯mtSq-Y_mtSqYmtSq-Y_mtSq+fmtY_mtSq.
As fmtYmtSq is continuous on Y_mtSq,Y¯mtSq and differentiable on Y_mtSq,Y¯mtSq, there exists cmtSq∈Y_mtSq,Y¯mtSq, such that
(24)fmt′cmtSq=fmtY¯mtSq-fmtY_mtSqY¯mtSq-Y_mtSq,
by the mean value theorem.Sincefmt′(y)>0 or fmt′(y)<0, fmtYmtSq is monotonic function on Y_mtSq,Y¯mtSq, there exists the inverse function of fmtY_mtSq. Hence cmtSq is uniquely decided, fmt-1YmtSq, such that
(25)cmtSq=fmt-1fmtY¯mtSq-fmtY_mtSqY¯mtSq-Y_mtSq,
and we define
(26)GmtSqYmtSq∶=fmtY¯mtSq-fmtY_mtSqY¯mtSq-Y_mtSqYmtSq-cmtSq+fmtcmtSq,LmtSq(YmtSq)∶=GmtSq(YmtSq)(fmt′′(y)>0)FmtSq(YmtSq)(fmt′′(y)<0).
By the definition, fmt(YmtSq)≥Lmt(YmtSq).For ally∈Sq, μm(y):=∑t=1Tm‍fmt(y)≥∑t=1Tm‍LmtSq(y).LetLmSq(y):=∑t=1Tm‍LmtSq(y)0≤m≤M+2P+∑k=1M‍Pk. Then L0(y) is a linear function which is lower function for the convex envelope of μ0(y) on the rectangle.LRP
S
q is the linear problem of (P2) by the lower bounded function of μm(y):
LRPSqmin⁡L0Sq(y)is.t.kLmSq(y)≤0KKKkm=1,2,…,M+2P+∑k=1M‍Pk.
By the definition LRPSq, any y in Sq satisfying the restricted condition of (P2) satisfy the restricted condition of LRPSq.Lemma 2.
The value ofLRPSq is less than the optimal value for the problem (P2) on Sq.Proof.
The definition ofLRPSq implies the statement naturally.Lemma 3.
Assume thatSq+1⊂Sq⊂⋯⊂S0⊂RN+Psum, and ⋂q=0∞‍Sq={y*}. For each m=0,1,2,…,M+2P+∑k=1M‍Pk and t=1,2,…,Tm, lim⁡q→∞max⁡y∈SqFmtSq(y)-fmt(y)=0 and lim⁡q→∞max⁡y∈SqGmtSq(y)-fmt(y)=0.Proof.
Lety_q:={y∈Sq∣min⁡(λmtiy_iq,λmtiy¯iq)(i=1,…,N+Psum)} and y¯q:={y∈Sq∣max⁡(λmtiy_iq,λmtiy¯iq)(i=1,…,N+Psum)}.
Since⋂q=0∞‍Sq={y*}, the values y_q and y¯q satisfy lim⁡q→∞y_q=lim⁡q→∞y¯q=y*.
Hence,Y¯mtSq-Y_mtSq=∑i=1N+Psum‍λmti(y¯iq-y_iq)→q→∞0.
Now,(27)FmtSqy-fmty=FmtSq(YmtSq)-fmt(YmtSq)=fmt(Y¯mtSq)-fmt(Y_mtSq)Y¯mtSq-Y_mtSq(YmtSq-Y_mtSq)kkkkk+fmt(Y_mtSq)-fmt(YmtSq)fmt(Y¯mtSq)-fmt(Y_mtSq)Y¯mtSq-Y_mtSq.
The function FmtSq(y)-fmt(y) is concave on Y_mtSq,Y¯mtSq; therefore cmtSq attains the maximum value of FmtSq(y)-fmt(y):max⁡y∈SqFmtSq(y)-fmt(y)(28)max⁡y∈SqFmtSqy-fmty=FmtSq(cmtSq)-fmt(cmtSq)=fmtY¯mtSq-fmtY_mtSqY¯mtSq-Y_mtSqcmtSq-Y_mtSqkkkkk+fmtY_mtSq-fmtcmtSqfmtY¯mtSq-fmtY_mtSqY¯mtSq-Y_mtSq.
We denote(29)ImtSq=Y¯mtSq-Y_mtSq,cmtSq=Y_mtSq+θmtSqImtSq(0<θmtSq<1).
Since ImtSq→0 for q→∞,
(30)fmtY¯mtSq-fmtY_mtSqY¯mtSq-Y_mtSqcmtSq-Y_mtSqkk+fmtY_mtSq-fmtcmtSqfmtY¯mtSq-fmtY_mtSqY¯mtSq-Y_mtSq=fmt(Y_mtSq+ImtSq)-fmt(Y_mtSq)Y_mtSq+ImtSq-Y_mtSq(Y_mtSq+θmtSqImtSq-Y_mtSq)kkk+fmt(Y_mtSq)-fmt(Y_mtSq+θmtSqImtSq)fmt(Y_mtSq+ImtSq)-fmt(Y_mtSq)Y_mtSq+ImtSq-Y_mtSq=fmt(Y_mtSq+ImtSq)-fmt(Y_mtSq)Y_mtSq+ImtSq-Y_mtSq(θmtSqImtSq)kkk+fmt(Y_mtSq)-fmt(Y_mtSq+θmtSqImtSq)fmt(Y_mtSq+ImtSq)-fmt(Y_mtSq)Y_mtSq+ImtSq-Y_mtSq=fmt(Y_mtSq+ImtSq)θmtSq-fmt(Y_mtSq)θmtSq+fmt(Y_mtSq)kkk-fmt(Y_mtSq+θmtSqImtSq)→q→∞fmtY_mtSqθmtSq-fmtY_mtSqθmtSqkkkkkk+fmtY_mtSq-fmtY_mtSq=0.
Thus
(31)GmtSqy-fmty=GmtSq(YmtSq)-fmt(YmtSq)=fmtY¯mtSq-fmtY_mtSqY¯mtSq-Y_mtSqYmtSq-cmtSqkkkkk+fmtcmtSq-fmtYmtSqfmtY¯mtSq-fmtY_mtSqY¯mtSq-Y_mtSq.
On the other hand GmtSq(y)-fmt(y) is a convex function by the same argument, and we obtain the following max⁡y∈SqGmtSq(y)-fmt(y)→0 for q→∞.Lemma 4.
Under the same assumption of Lemma3  max⁡y∈SqLmSqy-μmy→0 for q→∞ and each m=0,1,2,…,M+2P+∑k=1MPk.Proof.
Lemma3 and the definitions LmSq(y), μm(y) imply Lemma 4, standardly.


## 3. Branch and Bound Algorithm and Its Convergence

In Section2, we transformed the initial problem (P0) into the equivalent problem (P2), and we make the linear relaxation problem (LRP) of (P2) to find the approximate value of (P2) easily. Now we get it by using branch and bound algorithm.


### 3.1. Branch and Bound Algorithm

We solve the linear relaxation problem on initial domainS0 to get the linear optimal value as lower bound of (P2) and upper bound of (P2). For preparing to separate the active domains, we let the active domains set be Qq and active domain Sq(k)⊂S0. q presents the times of the cutting domains and stage number and k presents the number of active domains on stage q. If Sq(k) is active domain, we divide Sq(k) into half domains Sq(k)·1, Sq(k)·2 and linearize (P2) on each domain and solve the linear problems. After the above calculations, we get the lower and upper bound value of (P2). After the repeat calculations, we get the convergence for the sequences of the lower and upper bound values, and we get the optimal value and solution.


#### 3.1.1.  Branching Rule

We denote thatSq(k)={y∣y_nqk≤ynqk≤y¯nqk,n=1,…,N+Psum}⊆S0. We select the branching variable i such that i=nmax⁡{y¯nqk-y_nqk,n=1,2,…,N+Psum}, and we divide the interval y_iqk,y¯iqk into half intervals: y_iqk,y_iqk+y¯iqk/2 and y_iqk+y¯iqk/2,y¯iqk.


#### 3.1.2.  Algorithm Statement

Step
0. Firstly, we let q be 0 and let k be 1. And we set an appropriate ϵ-value as a convergence tolerance, the initial upper bound V*=∞, and Q0=S0(1). We solve LRP(S0(1)), and we denote the linear optimal solution and optimal value by y^(S0(1)) and LB0(1). If y^(S0(1)) is feasible for (P2), then update V*=μ0(y^(S0(1))) and we set the initial lower bound LB=LB0(1). If V*-LB≤ϵ, then we get the ϵ-approximate optimal value μ0(y^(S0(1))) and optimal solution y^(S0(1)) of (P2), so we stop this algorithm. Otherwise, we proceed to Step 1.Step
1. For all k, we divide Sq(k) to get two half domains, Sq(k)·1 and Sq(k)·2, according to the above branching rule.Step
2. For all k and each domain Sq(k)·v(v=1,2), we calculate
(32)μ_mv=∑t=1,cmt>0Γm‍cmtexp⁡(Y_mtSq(k)·v)+∑t=1,cmt<0Γm‍cmtexp⁡Y¯mtSqk·vkkkkkkkkkkm=1,…,M+2P+∑k=1M‍Pk,
where cmt, Y_mtSq(k)·v, and Y¯mtSq(k)·v are defined in Section 2.3.If there is theμ_m(v) that satisfy μ_m(v)>0 for some m∈{1,2,…,M+2P+∑k=1M‍Pk}, Sq(k)v is infeasible domain for (P2), then we delete the domain from Qq. If Sq(k)·v(v=1,2) are all deleted for all k, then the problem has no feasible solutions.Step
3. For left domains, we compute AmtSq(k)·v, BmtSq(k)·v, Y_mtSq(k)·v, and Y¯mtSq(k)·v as defined in Sections 2.2 and 2.3. We solve the LRP(Sq(k)·v) by simplex algorithm, and we denote the obtained linear optimal solutions and values by (y^(Sq(k)·v),LBq(k)·v). Then if y^(Sq(k)·v) is feasible for (P2), we update V*=min⁡{V*,μ0(y^(Sq(k)·v))}. If LBq(k)·v>V*, then delete the corresponding domains from Qq. If V*-LBq(k)·v≤ϵ, then we get the ϵ-approximate optimal value μ0(y^(Sq(k)·v)) and optimal solution y^(Sq(k)·v) of (P2), so we stop this algorithm. Otherwise, we proceed to Step 4.Step
4. We update the index of left domains Sq(k)·v to Sq+1(k); then we initialize k. And we settle that Qq+1 is a set of Sq+1(k), and go to Step 1.


### 3.2. The Convergence of the Algorithm

Corresponding to [4], we obtain the convergence of the algorithm (cf. [4]).Theorem 5.
Suppose that problem(P2) has a global optimal solution, and let μ0* be the global optimal value of (P2). Then one has the following:(i)
for the caseϵ>0, the algorithm always terminates after finitely many iterations yielding a global ϵ-optimal solution y* and a global ϵ-optimal value V* for problem (P2) in the sense that
(33)y*∈S,V*-ϵ≤μ0*withV*=μ0(y*);(ii)
for the caseϵ→0, we assume the sequence ϵn is convergence tolerance, such that ϵ1>ϵ2>,…,>ϵn>ϵn+1>,…,>0; that is, lim⁡n→∞ϵn=0. And we assume the sequence yn* is optimal solution of (P2) corresponding to ϵn. Then the accumulation point of yn* is global optimal solution of (P2).Proof.
(i) It is obvious by algorithm statement.
(ii) We assume that the upper bound corresponding toϵn is Vn*:
(34)μ0yn*∈Vn*-ϵ,Vn*;yn* is the point sequence on bounded closed set, so yn* has a converge subsequence yni*. We assume that lim⁡i→∞yni*=y*; then
(35)Vni*-ϵni≤μ0Vni*≤Vni*i⟶∞,thenni⟶∞,solim⁡ni→∞ϵni=0.
V
n
* is monotone decreasing sequence, so it converges. We assume that lim⁡n→∞Vn*=μ0*:
(36)lim⁡i→∞Vni*-ϵni≤lim⁡i→∞μ0(yni*)≤lim⁡i→∞Vni*;μ0(y) is continuous function, so lim⁡i→∞μ0(yni)=μ0(y*). And μ0*≤μ0y*≤μ0*; that is, μ0(y*)=μ0*. For ∀m, μm(yn*)≤0. As μm(y*) is continuous, lim⁡n→∞⁡μm(yn*)=μm(y*)≤0.


## 3.1. Branch and Bound Algorithm

We solve the linear relaxation problem on initial domainS0 to get the linear optimal value as lower bound of (P2) and upper bound of (P2). For preparing to separate the active domains, we let the active domains set be Qq and active domain Sq(k)⊂S0. q presents the times of the cutting domains and stage number and k presents the number of active domains on stage q. If Sq(k) is active domain, we divide Sq(k) into half domains Sq(k)·1, Sq(k)·2 and linearize (P2) on each domain and solve the linear problems. After the above calculations, we get the lower and upper bound value of (P2). After the repeat calculations, we get the convergence for the sequences of the lower and upper bound values, and we get the optimal value and solution.


### 3.1.1.  Branching Rule

We denote thatSq(k)={y∣y_nqk≤ynqk≤y¯nqk,n=1,…,N+Psum}⊆S0. We select the branching variable i such that i=nmax⁡{y¯nqk-y_nqk,n=1,2,…,N+Psum}, and we divide the interval y_iqk,y¯iqk into half intervals: y_iqk,y_iqk+y¯iqk/2 and y_iqk+y¯iqk/2,y¯iqk.


### 3.1.2.  Algorithm Statement

Step
0. Firstly, we let q be 0 and let k be 1. And we set an appropriate ϵ-value as a convergence tolerance, the initial upper bound V*=∞, and Q0=S0(1). We solve LRP(S0(1)), and we denote the linear optimal solution and optimal value by y^(S0(1)) and LB0(1). If y^(S0(1)) is feasible for (P2), then update V*=μ0(y^(S0(1))) and we set the initial lower bound LB=LB0(1). If V*-LB≤ϵ, then we get the ϵ-approximate optimal value μ0(y^(S0(1))) and optimal solution y^(S0(1)) of (P2), so we stop this algorithm. Otherwise, we proceed to Step 1.Step
1. For all k, we divide Sq(k) to get two half domains, Sq(k)·1 and Sq(k)·2, according to the above branching rule.Step
2. For all k and each domain Sq(k)·v(v=1,2), we calculate
(32)μ_mv=∑t=1,cmt>0Γm‍cmtexp⁡(Y_mtSq(k)·v)+∑t=1,cmt<0Γm‍cmtexp⁡Y¯mtSqk·vkkkkkkkkkkm=1,…,M+2P+∑k=1M‍Pk,
where cmt, Y_mtSq(k)·v, and Y¯mtSq(k)·v are defined in Section 2.3.If there is theμ_m(v) that satisfy μ_m(v)>0 for some m∈{1,2,…,M+2P+∑k=1M‍Pk}, Sq(k)v is infeasible domain for (P2), then we delete the domain from Qq. If Sq(k)·v(v=1,2) are all deleted for all k, then the problem has no feasible solutions.Step
3. For left domains, we compute AmtSq(k)·v, BmtSq(k)·v, Y_mtSq(k)·v, and Y¯mtSq(k)·v as defined in Sections 2.2 and 2.3. We solve the LRP(Sq(k)·v) by simplex algorithm, and we denote the obtained linear optimal solutions and values by (y^(Sq(k)·v),LBq(k)·v). Then if y^(Sq(k)·v) is feasible for (P2), we update V*=min⁡{V*,μ0(y^(Sq(k)·v))}. If LBq(k)·v>V*, then delete the corresponding domains from Qq. If V*-LBq(k)·v≤ϵ, then we get the ϵ-approximate optimal value μ0(y^(Sq(k)·v)) and optimal solution y^(Sq(k)·v) of (P2), so we stop this algorithm. Otherwise, we proceed to Step 4.Step
4. We update the index of left domains Sq(k)·v to Sq+1(k); then we initialize k. And we settle that Qq+1 is a set of Sq+1(k), and go to Step 1.


## 3.1.1.  Branching Rule

We denote thatSq(k)={y∣y_nqk≤ynqk≤y¯nqk,n=1,…,N+Psum}⊆S0. We select the branching variable i such that i=nmax⁡{y¯nqk-y_nqk,n=1,2,…,N+Psum}, and we divide the interval y_iqk,y¯iqk into half intervals: y_iqk,y_iqk+y¯iqk/2 and y_iqk+y¯iqk/2,y¯iqk.


## 3.1.2.  Algorithm Statement

Step
0. Firstly, we let q be 0 and let k be 1. And we set an appropriate ϵ-value as a convergence tolerance, the initial upper bound V*=∞, and Q0=S0(1). We solve LRP(S0(1)), and we denote the linear optimal solution and optimal value by y^(S0(1)) and LB0(1). If y^(S0(1)) is feasible for (P2), then update V*=μ0(y^(S0(1))) and we set the initial lower bound LB=LB0(1). If V*-LB≤ϵ, then we get the ϵ-approximate optimal value μ0(y^(S0(1))) and optimal solution y^(S0(1)) of (P2), so we stop this algorithm. Otherwise, we proceed to Step 1.Step
1. For all k, we divide Sq(k) to get two half domains, Sq(k)·1 and Sq(k)·2, according to the above branching rule.Step
2. For all k and each domain Sq(k)·v(v=1,2), we calculate
(32)μ_mv=∑t=1,cmt>0Γm‍cmtexp⁡(Y_mtSq(k)·v)+∑t=1,cmt<0Γm‍cmtexp⁡Y¯mtSqk·vkkkkkkkkkkm=1,…,M+2P+∑k=1M‍Pk,
where cmt, Y_mtSq(k)·v, and Y¯mtSq(k)·v are defined in Section 2.3.If there is theμ_m(v) that satisfy μ_m(v)>0 for some m∈{1,2,…,M+2P+∑k=1M‍Pk}, Sq(k)v is infeasible domain for (P2), then we delete the domain from Qq. If Sq(k)·v(v=1,2) are all deleted for all k, then the problem has no feasible solutions.Step
3. For left domains, we compute AmtSq(k)·v, BmtSq(k)·v, Y_mtSq(k)·v, and Y¯mtSq(k)·v as defined in Sections 2.2 and 2.3. We solve the LRP(Sq(k)·v) by simplex algorithm, and we denote the obtained linear optimal solutions and values by (y^(Sq(k)·v),LBq(k)·v). Then if y^(Sq(k)·v) is feasible for (P2), we update V*=min⁡{V*,μ0(y^(Sq(k)·v))}. If LBq(k)·v>V*, then delete the corresponding domains from Qq. If V*-LBq(k)·v≤ϵ, then we get the ϵ-approximate optimal value μ0(y^(Sq(k)·v)) and optimal solution y^(Sq(k)·v) of (P2), so we stop this algorithm. Otherwise, we proceed to Step 4.Step
4. We update the index of left domains Sq(k)·v to Sq+1(k); then we initialize k. And we settle that Qq+1 is a set of Sq+1(k), and go to Step 1.


## 3.2. The Convergence of the Algorithm

Corresponding to [4], we obtain the convergence of the algorithm (cf. [4]).Theorem 5.
Suppose that problem(P2) has a global optimal solution, and let μ0* be the global optimal value of (P2). Then one has the following:(i)
for the caseϵ>0, the algorithm always terminates after finitely many iterations yielding a global ϵ-optimal solution y* and a global ϵ-optimal value V* for problem (P2) in the sense that
(33)y*∈S,V*-ϵ≤μ0*withV*=μ0(y*);(ii)
for the caseϵ→0, we assume the sequence ϵn is convergence tolerance, such that ϵ1>ϵ2>,…,>ϵn>ϵn+1>,…,>0; that is, lim⁡n→∞ϵn=0. And we assume the sequence yn* is optimal solution of (P2) corresponding to ϵn. Then the accumulation point of yn* is global optimal solution of (P2).Proof.
(i) It is obvious by algorithm statement.
(ii) We assume that the upper bound corresponding toϵn is Vn*:
(34)μ0yn*∈Vn*-ϵ,Vn*;yn* is the point sequence on bounded closed set, so yn* has a converge subsequence yni*. We assume that lim⁡i→∞yni*=y*; then
(35)Vni*-ϵni≤μ0Vni*≤Vni*i⟶∞,thenni⟶∞,solim⁡ni→∞ϵni=0.
V
n
* is monotone decreasing sequence, so it converges. We assume that lim⁡n→∞Vn*=μ0*:
(36)lim⁡i→∞Vni*-ϵni≤lim⁡i→∞μ0(yni*)≤lim⁡i→∞Vni*;μ0(y) is continuous function, so lim⁡i→∞μ0(yni)=μ0(y*). And μ0*≤μ0y*≤μ0*; that is, μ0(y*)=μ0*. For ∀m, μm(yn*)≤0. As μm(y*) is continuous, lim⁡n→∞⁡μm(yn*)=μm(y*)≤0.


## 4. Numerical Experiment

In this chapter, we show the numerical experiments of these optimization problems according to the former rules. We make the algorithms coded with MATLAB. In these codes, we use MATLAB’s unique function code “linprog” to solve the linear optimization problems.Example 1.
Consider(37)min⁡h(x)=sinx12+3x2-2x22+1x12+x2+2kkkkkkkkkk+cos⁡-x22+2x1+2x2x1+2.5is.t.x12-x1x2-1≤0kkkkkx1+3x2x1-5≤0kkkkkX=x:1≤x1≤3,1≤x2≤3.
We set ϵ=0.0001. After the algorithm, we found a global ϵ-optimal value V*=1.0748 when the global ϵ-optimal solution is x1,x2T=(1.34977,1.64232).Example 2.
Consider(38)min⁡exp⁡-x12+3x1+2x22+3x2+3.5x1+1kkk-exp⁡x2x12-2x1+x22-8x2+20s.t.kx1-x2x1≤1kkkkk2x1x2+x2+≤6kkkkk2x1+x2≤8kkkkkX=x:1≤x1≤3,1≤x2≤3.
We set ϵ=0.0001. After the algorithm, we found a global ϵ-optimal value V*=58.2723 when the global ϵ-optimal solution is x1,x2T=(1,1.6180).Example 3.
Consider(39)min⁡sinx12+2x2-2x1+x22+1x1+x22+2kkkkk+cos⁡3x12-3x2+2x1+x22+5x12+2x22+10s.t.ksinx12+3x2-2x22+2x12+x2+2kkkkkk+cos⁡-x22+2x1+2x2x1+2.5≤2kkkkkkX=x:1≤x1≤2,1≤x2≤2.
We set ϵ=0.0001. After the algorithm, we found a global ϵ-optimal value V*=1.09133 when the global ϵ-optimal solution is x1,x2T=(2,1).Example 4.
Consider(40)min⁡exp⁡x12-2x22+82x12+x2+1kkkkk+exp⁡3x1-x22+5x12-x1+x22-3x2+10s.t.kx12-2x2≤1kkkkkx1-x2x1≤1kkkkk2x1+x22≤6kkkkkX=x:1.5≤x1≤2,1.5≤x2≤2.
We set ϵ=0.0001. After the algorithm, we found a global ϵ-optimal value V*=3.9378 when the global ϵ-optimal solution is x1,x2T=(1.5,1.7321).


## 5. Concluding Remarks

In this paper, we proved that we can solve the nonconvex optimization problems which [4] cannot solve that the sum of the positive (or negative) first and second derivatives function with the variable defined by sum of polynomial fractional function by using branch and bound algorithm.



---

*Source: 408918-2014-11-10.xml*