# Global Optimization for Sum of Linear Ratios Problem Using New Pruning Technique

Authors: Hongwei Jiao; Qigao Feng; Peiping  Shen; Yunrui Guo
Journal: Mathematical Problems in Engineering
 (2008)

---

## Abstract

A global optimization algorithm is proposed for solving sum of general linear ratios problem (P) using new pruning technique. Firstly, an equivalent problem (P1) of the (P) is derived by exploiting the characteristics
of linear constraints. Then, by utilizing linearization method the relaxation linear programming (RLP) of the (P1) can be constructed and the proposed algorithm is convergent to the global minimum of the (P) through the successive refinement of the linear relaxation of feasible region and solutions of a series of (RLP). Then, a new pruning technique is proposed, this technique
offers a possibility to cut away a large part of the current investigated feasible region by the optimization algorithm, which can be utilized as an accelerating device for global optimization of problem (P). Finally, the numerical experiments are given to illustrate the feasibility of the proposed algorithm.


---

## Body

## 1. Introduction

Consider  the
following sum of general linear ratios  problem:(1.1)(P):{minh(x)=∑j=1pcj0+cjTxdj0+djTx,s.t.Ax≤b,x∈RN,where A∈RM×N,b∈RM,  p is a natural number, cj0+cjTxanddj0+djTx are all finite affine functions on RN such that dj0+djTx≠0 for all x∈X={x∣Ax≤b},j=1,…,p.Problem (P) has attracted the interest of researchers
for many years. This is because problem (P) has a
number of important applications, including multistage shipping problems,
cluster analysis, and multiobjective bond portfolio [1, 2]. However, some
computational difficulties can be encountered, since multiple local optima of
problem (P) that are not globally optimal exist.In the last decades, many solution algorithms have
been proposed for globally solving special cases of the (P), which are intended
only for the sum of positive linear ratios problem with assumption thatcj0+cjTx≥0 and  dj0+djTx>0 for all x∈X={x∣Ax≤b}  [2, 3]. In [4], Kuno proposed a new method for
solving the maximization of sum of linear ratios, which used a concave function
to overestimate the optimal value of the original problem. A global
optimization method was considered by Jiao et al. [5] by introducing
parameters, then the global optimal solution can be derived using linear
relaxation and branch and bound algorithm. Recently, in [6], Ji et al.
presented a deterministic global optimization algorithm for the linear
sum-of-ratios problem, and Jiao and Chen [7] give a short extensive application
for the algorithm proposed in [6].  Though
optimization methods for special forms of the (P)
are ubiquitous,  to our
knowledge, little work has been done in the literature for globally solving the
sum of general linear ratios problem (P) which the numerators and denominators
of the ratios may be arbitrary value except that the denominators of the ratios
are nonzero over the feasible region considered in this paper.The purpose of this paper is to develop a
deterministic algorithm for solving sum of general linear ratios problem (P) which
the numerators and denominators of the ratios may be arbitrary value except
that the denominators of the ratios are nonzero over the feasible region. The
main feature of the algorithm is described as follows. (1) An equivalent
optimization problem (P1) of the (P) is derived by exploiting the
characteristics of this linear constraints. (2) A new linearization method is
proposed to linearize the objective function of the (P1), and the linear
relaxation of the (P1) is easier to be obtained and need not introduce new
variables and constraints compared with the method in [5, 8]. (3) A new pruning
technique is given, and this technique offers the possibility to cut away a
large part of the current investigated feasible region. Using the new technique
as an accelerating device and applying it to the proposed algorithm, we can
largely reduce current investigated feasible region to improve the convergence
of the algorithm. (4) The proposed algorithm is convergent to the global
minimum through the successive refinement of the linear relaxation of feasible
region of the objective function and solutions of a series of (RLP). Finally,
the numerical results show the feasibility and effectiveness of the proposed
algorithm.The organization of this article is as follows. In
Section2, we show how to convert the (P) into equivalent problem (P1), and
generate the relaxed linear programing (RLP) of the (P1). In Section 3, the
proposed branch-and-bound algorithm in which the relaxed subproblems are
embedded is described, and its convergence is shown. Some numerical results are
reported in Section 4 and Section 5 provides some concluding remarks.


## 2. Linear Relaxation Programing

In this
section, first we convert the (P) into an equivalent nonconvex programing
problem (P1). In order to globally solve the (P), the branch and bound
algorithm to be presented can be applied to the (P1).Firstly, we solve the following2N+p linear programing problems:(2.1)x¯i={minxi,s.t.Ax≤b,x¯i={minxi,s.t.Ax≤b,rj={mincj0+cjTx,s.t.Ax≤b,where i=1,2,…,N,j=1,…,p.
Then, we can get initial partition rectangle X0={x∣x¯i≤xi≤x¯i,i=1,2,…,N}.
Without loss of generality, assume rj≥0(j=1,…,q),rj<0(j=q+1,…,p), the problem (P) can be rewritten in the
following form:(2.2)(P1):{minh(x)=∑j=1qcj0+cjTxdj0+djTx+∑j=q+1pcj0+cjTx−rjdj0+djTx−∑j=q+1p−rjdj0+djTx,s.t.Ax≤b,x∈X0.Obviously, we have cj0+cjTx≥0 for each j∈{1,…,q},
and cj0+cjTx−rj≥0 and −rj>0 for each j∈{q+1,…,p}.Theorem 2.1.
Problems (P) and the (P1) have the same global
optimal solution.Proof.
Obviously, ifx is feasible to the (P), then x∈X0.
Conversely, if x is feasible to the (P1), then Ax≤b.
So they have the same feasible region, then conclusion is followed.
The linear relaxation of the (P1) can be realized by
underestimating functionh(x) with a linear function hl(x).
All the details of this linearization technique for generating relaxations will
be given in the following theorems.
Given anyX=[x¯,x¯]⊆X0 and  for all x=(xi)n×1∈X,
the following notations are introduced:(2.3)hl(x)=∑j=1qcj0+cjTxdju+∑j=q+1pcj0+cjTx−rjdju−∑j=q+1p−rjdjl,(2.4)hu(x)=∑j=1γcj0+cjTxdjl+∑j=q+1pcj0+cjTx−rjdjl−∑j=q+1p−rjdju,(2.5)djl=minx∈X(dj0+djTx),dju=maxx∈X(dj0+djTx),j=1,…,p.Theorem 2.2.
Letdj(x)≠0 for any x∈X and let djl and dju defined in (2.5). Then, 1/dju≤1/dj(x)≤1/djl(j=1,…,p), for all x∈X.Proof.
Obviously, by the continuity of the functiondj(x),
there must exist some x1∈X and x2∈X,
such that dj(x1)=djl and dj(x2)=dju.
If djudjl<0,
then djl<0 and dju>0,
that is, dj(x1)<0 and dj(x2)>0.
Then, there must exist one positive number σ∈(0,1) such that dj(x1+σ(x2−x1))=0,
where x1+σ(x2−x1)∈X,
which contradicts dj(x)≠0 for any x∈X.
Therefore, we have djudjl>0,
that is, dju≥djl>0 or djl≤dju<0.
Obviously, for ∀x∈X,
the following two conclusions hold.
(i)
Ifdju≥djl>0,
then dju≥dj(x)≥djl>0,
we have 0<1/dju≤1/dj(x)≤1/djl.(ii)
Ifdjl≤dju<0,
then djl≤dj(x)≤dju<0,
we have 1/dju≤1/dj(x)≤1/djl<0. By (i) and (ii), for for all x∈X,
we have 1/dju≤1/dj(x)≤1/djl.Theorem 2.3.
For anyx∈X,
consider the functions h(x),hl(x), and hu(x) defined in (2.3) and (2.4). Then, the following
two statements hold.
(i)
The functionsh(x),hl(x), and hu(x) satisfy hl(x)≤h(x)≤hu(x).(ii)
The maximal errors of boundingh(x) using hl(x) and hu(x) satisfy(2.6)lim∥x¯−x¯∥→0ErrormaxL=lim∥x¯−x¯∥→0ErrormaxU=0,where(2.7)ErrormaxL=maxx∈X(h(x)−hl(x)),ErrormaxU=maxx∈X(hu(x)−h(x)).Proof.
The proof the theorem can be found in [7].For convenience in exposition, in the following we
assume thatXk=[x¯k,x¯k] represents either the initial bounds on the
variables of the problem (P1), or modified bounds as defined for some
partitioned subproblem in a branch-and-bound scheme. By means of Theorem 2.3, we
can give the linear relaxation of the (P1). Let Xk=[x¯k,x¯k]⊆X0,
consequently we construct the corresponding approximation relaxation linear
programing (RLP) of (P1) in Xk as follows:(2.8)RLP(Xk):{minhl(x)=∑j=1qcj0+cjTxdju+∑j=q+1pcj0+cjTx−rjdju−∑j=q+1p−rjdjl,s.t.Ax≤b,x∈Xk.Based on the above linear underestimators, every
feasible point of (P1) in subdomainXk is feasible in (RLP); and the value of the
objective function for (RLP) is less than or equal to that of (P1) for all
points in Xk.
Thus, (RLP) provides a valid lower bound for the solution of (P1) over the
partition set Xk.
It should be noted that problem (RLP) contains only the necessary constraints
to guarantee convergence of the algorithm.


## 3. New Pruning Technique

In this
section, we pay more attention to how to form the new pruning technique to
delete or reduce a large part of regions in which there
exists no global optimal solution so that we can
accelerate the convergence of the proposed algorithm. LetX=(Xi)N×1 with Xi=[x¯i,x¯i] be
a subrectangle of X0, that is, X⊆X0.
Moreover, assume that h¯ are currently known upper bound of optimal
objective value h* of problem (P1). For convenience of the
following discussions, we introduce some notations as follows:(3.1)E=∑j=1pcj0dju+∑j=q+1p(rjdjl−rjdju),βi=∑j=1pcjidju,i=1,2,…,N,S=∑i=1Nmin{βix¯i,βix¯i},Lt=∑i=1Nmin{atix¯i,atix¯i},t=1,2,…,M,sm=minx∈X∑i=1,i≠mNβixi,zm=h¯−sm−Eβm,ztm1=bt−Lt+atmx¯matm,ztm2=bt−Lt+atmx¯matm.Theorem 3.1.
Consider the subrectangleX=(Xi)N×1⊆X0, we have the following conclusions.
(i)
IfS+E>UB, then minx∈Xh(x)>h*.(ii)
IfS+E≤UB, then if there exists some index m(m∈{1,2,…,N}) such that βm>0 and zm<x¯m, then  minx∈X^1h(x)>h*;
if there exists some index m(m∈{1,2,…,N}) such that βm<0 and zm>x¯m, then minx∈X^2h(x)>h*, where(3.2)X^1=(X^i1)N×1⊆X,X^2=(X^i2)N×1⊆X,X^i1={Xi,ifi≠m,i=1,2,…,N,(zm,x¯m]∩Xm,ifi=m,X^i2={Xi,ifi≠m,i=1,2,…,N,[x¯m,zm)∩Xm,ifi=m.Proof.
(i) By
assumption and definitions ofβi,S,E in (3.1), if S+E>UB, then hl(x)≥S+E>UB≥h* for any x∈X,
that is, minx∈Xh(x)>h* for any x∈X.
(ii) By assumption and definitions ofβi,S,E in (3.1), if S+E≤UB, then we have the following two conclusions:
(a)
If there exists some indexm(m∈{1,2,…,N}) such that βm>0 and zm<x¯m, then for any x=(xi)N×1∈X^1,
let βm>0 and zm<x¯m for some m,
we first show that h(x)≥h¯.
By assumption and definitions of βm,sm, and zm in (3.1), we have xm>zm, that
is, xm>(h¯−sm−E)/βm. Furthermore, from the definitions of hl(x),
we get(3.3)h¯<βmxm+sm+E=βmxm+minx∈X∑i=1,i≠mNβixi+E≤∑i=1Nβixi+E=∑i=1N∑j=1pcjidjuxi+∑j=1pcj0dju+∑j=q+1p(rjdjl−rjdju)=∑j=1p∑i=1Ncjidjuxi+∑j=1pcj0dju+∑j=q+1p(rjdjl−rjdju)=hl(x).
By the above discussion and assumption, it follows
thath*≤h¯<hl(x)≤h(x) for any x∈X^1. Therefore, minx∈X^1h(x)>h¯≥h*,
that is, there exists no global optimal solution in X^1.
This proof of part (a) is completed.(b)
If  there exists some indexm(m∈{1,2,…,N}) such that βm<0 and zm>x¯m, then minx∈X^2h(x)>h*,
since the proof of the part (b) is similar to the part (a) of the theorem, it
is omitted here.Theorem 3.2.
Consider the subrectangleX=(Xi)N×1⊆X0, we have the following conclusions.
(i)
If there exists  somet(t∈{1,…,M}) such that Lt>bt on the subrectangle X,
then there exists no global optimization solution
in X.(ii)
IfLt≤bt(t∈{1,…,M) on the subrectangle X,
then if there exists some index m(m∈{1,2,…,N}) such that atm>0 and ztm1<x¯m,
then there exists  no global optimization solution
in X^3;
if there exists some index m(m∈{1,2,…,N}) such that atm<0 and ztm2>x¯m,
then there exists no global optimization solution
in X^4,
where(3.4)X^3=(X^i3)N×1⊆X,X^4=(X^i4)N×1⊆X,X^i3={Xi,ifi≠m,i=1,2,…,N,(ztm1,x¯m]∩Xm,ifi=m,X^i4={Xi,ifi≠m,i=1,2,…,N,[x¯m,ztm2)∩Xm,ifi=m.Proof.
Since the
proof of Theorem3.2 is similar to that of Theorem 3.1, it is omitted here.Based on Theorems3.1 and 3.2, we can give new pruning
technique to cut away or reduce a large part of region in which there exists no
optimal solution.Next, we will show how this new pruning technique is
formed, that is, we provide a process that show how a subrectangleX⊆X0 can be deleted or reduced, where X=(Xi)N×1 with Xi=[x¯i,x¯i].
Let Ym denote the discarded interval in Xm.
First, we calculate E,βm,S,sm,zm,Lt,ztm1,ztm2 according to (3.1). Then, the eliminated
interval Ym can be determined according to the following
rules, which is called new pruning technique.Rule 1
IfS+E>UB, then(3.5)Ym=[x¯m,x¯m],m=1,…,N.Rule 2
IfS+E≤UB, then
(a)
Ifβm>0  and zm<x¯m,
then (3.6)Ym={(zm,x¯m],ifx¯m≤zm,[x¯m,x¯m],ifzm≤x¯m,(b)
Ifβm<0  and zm>x¯m,
then(3.7)Ym={[x¯m,zm),ifzm≤x¯m,[x¯m,x¯m],ifzm≥x¯m.Rule 3
IfLt>bt for some  t(t∈{1,…,M}),
then (3.8)Ym=[x¯m,x¯m],m=1,…,N.Rule 4
IfLt≤bt for some t(t∈{1,…,M}),
then
(c)
Ifatm>0  and ztm1<x¯m, then (3.9)Ym={[x¯m,x¯m],ifztm1<x¯m,(ztm1,x¯m],ifztm1≥x¯m,(d)
Ifatm<0 and ztm2>x¯m,
then (3.10)Ym={[x¯m,x¯m],ifztm2>x¯m,[x¯m,ztm2),ifztm2≤x¯m.Consequently, under some assumption the discarded part
ofXm is Xm∩Ym for some m(m∈{1,2,…,N}), the new rectangle reducing tactics provides
the possibility to cut away or reduce a large part of the rectangle that is
currently investigated by the procedure. The rest part of X denoted by X=(Xi)N×1 is left for further considering, where Xi=Xi if i≠m(i=1,2,…,N);Xm=Xm∖Ym if i=m.


## 4. Algorithm and Its Convergence

In this
section, by connecting the former branch-and-bound algorithm with new pruning
technique a global optimization algorithm is proposed for solving problem (P1).
This algorithm needs to solve a sequence of relaxation linear programing over
partitioned subsets ofX0 in order to find a global optimum solution.The branch and bound approach is based on partitioning
the setX0 into
sub-hyperrectangles, each concerned with a node of the branch and
bound tree, and each node is associated with a relaxation linear subproblem in
each sub-hyperrectangle. Hence, at any stage k of the algorithm, suppose that we have a
collection of active nodes denoted by Qk,
say, each associated with a hyperrectangle X⊆X0, for all X∈Qk.
For each such node X,
we will have computed a lower bound of the optimal value of (P1) via the
solution LB(X) of the RLP, so that the lower bound of optimal
value of (P1) on the whole initial box region X0 at stage k is given by LBk=min{LB(X), for all X∈Qk. Whenever the solution
of the relaxation linear programing (RLP) turns out to be feasible to the
problem (P1), we update the upper bound of incumbent solution UB if necessary. Then, the active nodes
collection Qk will satisfy LB(X)<UB, for all X∈Qk,
for each stage k.
We now select an active node to partition its associated hyperrectangle into
two sub-hyperrectangles as described below, computing the lower bounds for each
new node as before. Upon fathoming any nonimproving nodes, we obtain a
collection of active nodes for the next stage, and this process is repeated
until convergence is obtained.The critical element in guaranteeing convergence to a
global minimum is the choice of a suitable partitioning strategy. In our paper,
we choose a simple and standard bisection rule. This method is sufficient to
ensure convergence since it drives all the intervals to zero for all variables.
This branching rule is given as follows.Assume that the sub-hyperrectangleX′=[x′¯,x¯′]⊆X0 is going to be divided. Then, we select the
branching variable xγ′, satisfying γ=argmax{x¯i′−x¯i′:i=1,…,N} and partition X′ by bisection the interval [x¯γ′,x¯γ′] into the subintervals [x¯γ′,(x¯γ′+x¯γ′)/2] and [(x¯γ′+x¯γ′)/2,x¯γ′].The basic steps of the proposed algorithm are
summarized as follows. LetLB(Xk) refer to the optimal objective function value
of P1 for the sub-hyperrectangles Xk and xk=x(Xk) refer to an element of corresponding argmin.Algorithm Statement
Step 1 (initialization).
Initialize the iteration counterk:=0,
the set of all active node Q0={X0},
the upper bound UB=∞,
and the set of feasible points F:=∅.
Solve the problem (RLP) for X=X0,
obtaining LB0:=LB(X) and x0:=x(X).
If x0 is feasible to (P1) update F and UB,
if necessary. If UB≤LB0+ϵ,
where ϵ>0 is some accuracy tolerance, then stop with x0 as the prescribed solution to problem (P1).
Otherwise, proceed to Step 2.Step 2 (midpoint check).
Select the midpointxm of Xk,
if xm is feasible to the (P1), then F:=F∪{xm}.
Define the upper bound UB:=minx∈Fh(x).
If F≠∅,
the best known feasible point is denoted b:=argminx∈Fh(x).Step 3 (branching).
Choose a branching variablexγ to partition Xk to get two new sub-hyperrectangles according
to the above selected branching rule. Call the set of new partition rectangles
as X¯k.Step 4 (pruning).
(1) IfX¯k≠∅,
then calculate E,βi,S,Lt,sm,zm,ztm1,
and ztm2 for each X∈X¯k.
If one of assumption conditions in rules 1–4 is satisfied, then the proposed
new pruning technique can be applied into each X∈X¯k,
the rest parts of X and X¯k are denoted by X and Xk,
respectively.
(2) IfXk≠∅,
solve RLP to obtain LB(X) and x(X), for each X∈Xk.
If LB(X)>UB,
set Xk:=Xk∖X,
otherwise, update the best available solution UB,F and b if possible, as in Step 2.Step 5 (updating lower bound).
The partition set remaining is nowQk:=(Qk∖Xk)∪Xk giving a new lower bound LBk:=infX∈QkLB(X).Step 6 (convergence check).
Fathom any nonimproving nodes by settingQk+1=Qk∖{X:UB−LB(X)≤ϵ,X∈Qk}.
If Qk+1=∅, then stop with UB is the solution of (P1), and b is an optimal solution. Otherwise, k:=k+1,
and select an active node Xk such that Xk=argminX∈QkLB(X), xk:=x(Xk),
and return to Step 2.Convergence of The Algorithm
LetXa be the set of accumulation points of {xk},
and let X* be argminx∈Gh(x),
where G≠∅ is the feasible space of the (P1).Theorem 4.1.
The above algorithm either terminates finitely with
the incumbent solution being optimal to the (P1) or generates an infinite
sequence of iteration such that along any infinite branch of the branch and bound
tree, any accumulation point of the sequence{LBk} will be global minimum of the (P1).Proof.
If the above proposed algorithm terminates finitely
at some iterationk,
obviously, UB is global optimal value and x(Xk) is optimal solution for the (P1). If the
algorithm is infinite, it generates at least one infinitely sequence {Xk} such that Xk+1⊂Xk for any k.
In the case, since partition sets used by the proposed algorithm are all
rectangular and compact, by Tuy [9], it follows that this rectangular
subdivision is exhaustive. Hence, for every iteration, k=0,1,2,…,
by design of the algorithm, we have(4.1)LBk≤minx∈Gh(x),Xk∈argminX∈QkLB(X),xk=x(Xk)∈Xk⊆X0.Horst [10] gives that {LBk} is a nondecreasing sequence bounded above by minx∈Gh(x),
which guarantees the existence of the limit LB:=limk→∞LBk≤minx∈Gh(x).{xk} is a sequence on a compact set, therefore, it
has a convergent subsequence. For any x^∈Xa,
suppose that there exists a subsequence {xr} of {xk} with limr→∞xr=x^.
By the proposed algorithm and [9], it follows that the subdivision of partition
sets in Step 3 is exhaustive on X0,
and the selection of elements to be partitioned in Step 3 is bound improving.
Thus, there exists a decreasing subsequence {Xq}⊂Xr,
where Xr∈Qr with xq∈Xq,LBq=LB(xq)=hl(xq),limq→∞xq=x^. From the construction method of linear lower
bound relaxation functions for objective function of the (P1), we know that the
linear subfunctions hl(x) used in (RLP) are strongly consistent on X0.
Thus, it follows that limq→∞LBq=LB=h(x^).


## 5. Numerical Experiments

To verify
performance of the proposed algorithm, some common used test problems are
implemented on Pentium IV (433 MHZ) microcomputer. The algorithm is coded in
C++ language and each linear programing is solved by simplex method, and the
convergence toleranceϵc set to 10−8 in our experiment. Below, we describe some of
these sample problems and solution results are summarized in Table 1. In Table 1, the notations have been used for column headers.
Iter: number of algorithm iteration; maxnode: the maximal number of active
nodes necessary; time: execution time in seconds; ϵf:
feasibility tolerance.Table 1
Computational results of test
examples.
Exampleoptimal solutionoptimal valueIterMaxnodeTimeϵcx1x2x31.  [3]0.00.2821651.6231883616<110−6This
paper0.00.2832431801.623183349115010−82. [2]100−4.081481383210−6This
paper0.9999999910.0000000560.000000237−4.0814814832211<110−83.1.01.01.0−0.534313724355382655610−84.1.01.01.0−0.634523829056992<310−8Example 5.1 (see [3]).
We have(5.1)min−x1+2x2+23x1−4x2+5+4x1−3x2+4−2x1+x2+3,s.t.x1+x2≤1.5,x1−x2≤0,0≤x1,x2≤1.Example 5.2 (see [2]).
We have(5.2)min−4x1+3x2+3x3+503x2+3x3+50−3x1+4x3+504x1+4x2+5x3+50−x1+2x2+5x3+50x1+5x2+5x3+50−x1+2x2+4x3+505x2+4x3+50,s.t.2x1+x2+5x3≤10,x1+6x2+3x3≤10,5x1+9x2+2x3≤10,9x1+7x2+3x3≤10,x1,x2,x3≥0.If there exists sum of
general linear ratios in constraint functions of problem (P1), by using the
same linear relaxation method proposed in Section2, we can construct the
corresponding linear relaxation programing of problem (P1). Therefore, the
above proposed algorithm can be extensively applied to solve the following sum
of linear ratios problem with sum of linear ratios constraints.Example 5.3.
We have(5.3)min2x1+x2+x3+1x1+2x2+x3+2+x1+2x2+x3+22x1+2x2+x3+3−x1+x2+3x3+5x1+2x2+3x3+4−1.5x1+x2+x3+6x1+x2+1.5x3+5,s.t.2x1+x2+x3+22x1+x2+x3+3−2x1+2x2+x3+5x1+2x2+x3+4−2x1+3x2+x3+6x1+2x2+2x3+5−1.5x1+x2+2x3+71.5x1+2x2+x3+6≤−2.4,1.5x1+x2+x3+3x1+1.5x2+x3+4+2x1+x2+x3+4x1+x2+2x3+5+x1+2x2+x3+5x1+2x2+x3+6+x1+x2+3x3+6x1+3x2+x3+7≤3.8,x1+x2+x3+4x1+x2+x3+5+x1+x2+x3+5x1+x2+x3+6+x1+x2+3x3+6x1+x2+x3+7+x1+x2+x3+7x1+x2+x3+8≤3.9,x1+x2+x3+5x1+x2+x3+6+x1+x2+x3+6x1+x2+x3+7−x1+x2+x3+9x1+x2+x3+8−x1+x2+x3+10x1+x2+x3+9≤0.1,1.0≤x1≤3.0,1.0≤x2≤3.0,1.0≤x3≤3.0.Example 5.4.
We have(5.4)minx1+x2+x3+1x1+x2+x3+2+x1+x2+x3+2x1+x2+x3+3−x1+x2+x3+5x1+2x2+2x3+4−x1+x2+x3+6x1+x2+x3+5,s.t.x1+x2+x3+2x1+x2+x3+3−x1+x2+x3+5x1+x2+x3+4−x1+x2+x3+6x1+x2+x3+5−x1+x2+x3+7x1+x2+x3+6≤−2.0,x1+x2+x3+3x1+x2+x3+4+x1+x2+x3+4x1+x2+x3+5+x1+x2+x3+5x1+x2+x3+6+x1+x2+x3+6x1+x2+x3+7≤3.59,x1+x2+x3+4x1+x2+x3+5+x1+x2+x3+5x1+x2+x3+6+x1+x2+3x3+6x1+x2+x3+7+x1+x2+x3+7x1+x2+x3+8≤3.6,x1+x2+x3+5x1+x2+x3+6+x1+x2+x3+6x1+x2+x3+7+x1+x2+x3+7x1+x2+x3+8+x1+x2+x3+8x1+x2+x3+9≤3.7,1.0≤x1≤3.0,1.0≤x2≤3.0,1.0≤x3≤3.0.From Table1, numerical results show that our
algorithm can globally solve sum of general linear ratios problem (P) on a
microcomputer.


## 6. Concluding Remarks

A global
optimization algorithm is proposed for solving sum of general linear ratios
problem (P). To globally solve the (P), we first convert (P) into an equivalent
problem (P1), then one new linearization method is proposed to construct the
linear relaxation programing of the (P1). Then, a new pruning technique is proposed,
this technique offers a possibility to cut away a large part of the current
investigated feasible region by the algorithm, which can be utilized as an
accelerating device for global optimization of problem (P). The proposed
algorithm is convergent to the global minimum of (P1) through the successive
refinement of linear relaxation of the feasible region and the subsequent
solutions of a series of (RLP). Finally, the numerical experiments are given to
illustrate the feasibility and effectiveness of the proposed algorithm.



---

*Source: 646205-2009-02-16.xml*