# Generating Efficient Outcome Points for Convex Multiobjective

Authors: Le Quang Thuy; Nguyen Thi Bach Kim; Nguyen Tuan Thien
Journal: Journal of Applied Mathematics
 (2011)

---

## Abstract

Convex multiobjective programming problems and multiplicative programming problems have important applications in areas such as finance, economics, bond portfolio optimization,
engineering, and other fields. This paper presents a quite easy algorithm for generating a number of efficient outcome solutions for convex multiobjective programming problems. As an application, we propose an outer approximation
algorithm in the outcome space for solving the multiplicative convex program. The computational results are provided on several test problems.


---

## Body

## 1. Introduction

The convex multiobjective programming problem involves the simultaneously minimizep≥2 noncomparable convex objective functions fj:ℝn→ℝ, j=1,…,p, over nonempty convex feasible region X in ℝn and may be written by(VPX)Min⁡⁡f(x),s.t.x∈X,
where f(x)=(f1(x),f2(x),…,fp(x))T. When X⊂ℝn is a polyhedral convex set and fj, j=1,…,p are linear functions, problem (VPX) is said to be a linear multiobjective programming problem(LPX).For a nonempty setQ⊂ℝp, we denote by QE and QWE the sets of all efficient points and weakly efficient points of Q, respectively, that are(1.1)QE:={q*∈Q∣∄q∈Qsuchthatq*≥qandq*≠q}={q*∈Q∣(q*-R+p)∩Q={q*}},QWE:={q*∈Q∣∄q∈Qsuchthatq*≫q}={q*∈Q∣(q*-int⁡R+p)∩Q=∅}.Here for any two vectorsa,b∈ℝp, the notations a≥b and a≫b mean a-b∈ℝ+p and a-b∈intℝ+p, respectively, where ℝ+p is the nonnegative orthant of ℝp, and intℝ+p is the interior of ℝ+p. By definition, QE⊆QWE.The set(1.2)Yimage=f(X)={f(x)∣x∈X}
is called the outcome set (or image) ofXunderf. A point x0∈X is said to be an efficient solution for problem (VPX) if f(x0)∈YEimage. For simplicity of notation, let XE denote the set of all efficient solutions for problem (VPX). When f(x0)∈YWE, x0 is called weakly efficient solution for problem (VPX) and the set of all weakly efficient solutions is denoted by XWE, it is clear that XE and XWE are the preimage of YEimage and YWEimage under f, respectively. We will refer to YEimage and YWEimage as the efficient outcome set and weakly efficient outcome set for problem (VPX), respectively.The goal of problem(VPX) is to generate the sets XE and XWE or at least their subsets. However, it has been shown that, in practice, the decision maker prefers basing his or her choice of the most preferred solution primarily on YEimage and YWEimage rather than XE and XWE. Arguments to this effect are given in [1].It is well known that the task of generatingXE, XWE, YEimage, YWEimage, or significant portions of these sets for problem (VPX) is a difficult problem. This is because they are, in general, nonconvex sets, even in the case of linear multiobjective programming problem (LPX).Problem(VPX) arises in a wide variety of applications in engineering, economics, network planning, production planning, operations research, especially in multicriteria design and in multicriteria decision making (see, for instance, [2, 3]). Many of the approaches for analyzing convex multiobjective programming problems involve generating either the sets XE, XWE, YEimage, and YWEimage or a subset thereof, without any input from decision maker (see, e.g., [1, 2, 4–13] and references therein). For a survey of recent developments see [6].This paper has two purposes:(i)
the first is to propose an algorithm for generating a number of efficient outcome points for convex multiobjective programming problem(VPX) depending on the requirements of decision makers (Algorithm 1 in Section 2). Computational experiments show that this algorithm is quite efficient;(ii)
as an application, we present an outer approximation algorithm for solving the convex multiplicative programming problem(CPX) associated with the problem (VPX) in outcome space ℝp (Algorithm 2 in Section 3), where the problem (CPX) can be formulated as
(CPX)min⁡∏j=1pfj(x),s.t.x∈X.It is well known that problem(CPX) is a global optimization problem and is known to be NP-hard, even special cases such as when p=2, X is a polyhedron, and fj is linear for each j=1,2 (see [14]). Because of the wide range of its applications, this problem attracts a lot of attention from both researchers and practitioners. Many algorithms have been proposed for globally solving the problem (CPX), (see, e.g., [10, 14–20] and references therein).The paper is organized as follows. In Section2, we present Algorithm 1 for generating efficient outcome points for convex multiobjective programming problem (VPX) and its theoretical basis. To illustrate the performance of Algorithm 1, we use it to generate efficient points for a sample problem. The Algorithm 2 for solving the convex multiplicative programming (CPX) associated with the problem (VPX), and numerical examples are described in Section 3.


## 2. Generating Efficient Outcome Points for Problem(VPX)

### 2.1. Theoretical Basis

Assume henceforth thatX⊂ℝn is a nonempty, compact convex set given by(2.1)X:={x∈Rn∣gi(x)≤0,i=1,…,m},
where all the g1,g2,…,gm are convex functions on ℝn. Then the set(2.2)G0=Yimage+R+p
is nonempty full-dimensional convex set in ℝp. Furthermore, from Yu [21, page 22, Theorem  3.2], we know that YEimage=GE0.For eachk=1,…,p, we consider the following problem:(P0(k))min⁡⁡yk,s.t.y∈G0.
We denote the optimal value for the problem (P0(k)) by ykopt and the optimal solution for this problem by yk=(y1k,…,ypk)∈ℝp.Letym=(y1m,y2m,…,ypm), where(2.3)ykm=ykopt∀k=1,2,…,p.
As usual, the point ym is said to be an ideal efficient point of G0. It is clear that if ym∈G0 then YEimage=GE0={ym}. Therefore, we suppose that ym∉G0. Obviously, by definition, if (x*,y*)∈ℝn+p is an optimal solution for the problem (P(k)) given by (P(k))min⁡yks.t.fj(x)-yj≤0,j=1,…,p,gi(x)≤0,i=1,…,m,
then yk=y* is an optimal solution for the problem (P0(k)), and the optimal values of these two problems are equal.To generate various efficient outcome points inYEimage, the algorithm will rely upon the point yM=(y1M,y2M,…,ypM), where for each j=1,2,…,p,yjM=α, and α is any real number satisfying(2.4)α>max⁡⁡{yjk,k=1,…,p,j=1,…,p}.We consider the setG given by(2.5)G=G0∩(yM-R+p).
It is obvious that G is a nonempty, full-dimensional compact convex set in ℝp. The set G is instrumental in Algorithm 1 to be presented in Section 2.2 for generating efficient outcome points for problem (VPX).Remark 2.1.
In 1998, Benson [1] presented the outer approximation algorithm for generating all efficient extreme points in the outcome set of a multiobjective linear programming problem. Here, the G seems to be analogous with the set Y considered by Benson [1]. However, note that Y⊃Yimage and Yimage is not necessarily a subset of G. The Figure 1 illustrates the set G in the case of p=2.Figure 1Proposition 2.2.
YEimage=GE.Proof.
This result is easy to show by using Yu [21, page 22, Theorem  3.2] and the definition of the point yM. Therefore, the proof is omitted.Let(2.6)B0=(ym+R+p)∩(yM-R+p).
It is clear that G⊂B0. The following fact will play an important role in establishing the validity of our algorithm.Proposition 2.3.
For each pointy¯∈B0∖G, let yw denote the unique point on the boundary of G that belongs to the line segment connecting y¯ and yM. Then yw∈GE.Proof.
LetD=G-yw. Since G is the compact convex set and yw belongs to the boundary of G, the set D is also the compact convex set containing the origin 0 of the outcome space ℝp and 0 belongs to the boundary of D. According to the separation theorem [22], there is a nonzero vector q∈ℝp such that
(2.7)〈q,u〉≥0∀u∈D.
Let S⊂ℝp be a p-simplex with vertices 0, e1,e2,…,ep, where e1,e2,…,ep are the unit vectors of ℝp. By definition, we can choose the point yM such that (yw+S)⊂G. This implies that S⊂D. From (2.7), by taking u to be e1,e2,…,ep to see that
(2.8)q≥0.
Furthermore, the expression (2.7) can be written by
(2.9)〈q,y-yw〉≥0∀y∈G,
that is,
(2.10)〈q,y〉≥〈q,yw〉∀y∈G.
According to [23, Chapter 4, Theorem  2.10], a point y*∈G is a weakly efficient point of G if and only if there is a nonzero vector v∈ℝp and v≥0 such that y* is an optimal solution to the convex programming problem(2.11)min⁡⁡{〈v,y〉∣y∈G}.
Combining this fact, (2.8) and (2.10) give yw∈GWE. To complete the proof, it remains to show that yw∈GE. Assume the contrary that
(2.12)yw∈GWE∖GE.
By the definition, we have
(2.13)GWE=GE∪(⋃k=1pFk),
where for each k=1,…,p, Fk is the optimal solution set for the following problem:
(PG(k))min⁡⁡yk,s.t.y∈G.
It is easy to see that the optimal values of two problems (PG(k)) and (P0(k)) are the same. From this fact and the definition of the point ym, it follows that
(2.14)Fk={y∈G∣yk=ykm}.
Therefore, if yw∈GWE∖GE then there is i0∈{1,2,…,p} such that yi0w=yi0m. Since y¯∈B0∖G, we always have y¯≥ym and yw=λyM+(1-λ)y¯ with 0<λ<1. By the choice of the point yM, we have yM≫ym. Hence,
(2.15)yi0m=yi0w=λyi0M+(1-λ)y¯i0>yi0m.
This contradiction proves that yw must belong to the efficient outcome set GE.Remark 2.4.
This Proposition2.3 can be viewed as an Benson's extension in [1, Proposition  2.4].  Benson showed that the unique point on the boundary of Y (which is considered in [1]) and corresponding segment belongs to the weakly efficient outcome set YWE, here we prove that yw belongs to the efficient outcome set GE.Remark 2.5.
Lety¯ be a given point in B0∖G. From Propositions 2.3 and 2.2, the line segment connecting y¯ and yM contains a unique point yw∈YEimage which lies on the boundary of G. To determine this efficient outcome point yw, we have to find the unique value λ* of λ, 0<λ<1, such that
(2.16)yw=λ*yM+(1-λ*)y¯=y¯+λ*(yM-y¯)
belongs to the boundary of G (see Figure 2). It means that λ* is the optimal value for the problemFigure 2(2.17)min⁡λs.t.y¯+λ(yM-y¯)∈G,0≤λ≤1.
By definition, it is easy to see that λ* is also the optimal value for the following convex programming problem with linear objective function(T(y¯))min⁡λs.t.f(x)-λ(yM-y¯)-y¯≤0,gi(x)≤0,i=1,…,m,0≤λ≤1.
Note that λ* exists because the feasible region of problem (T(y¯)) is a nonempty, compact convex set. Furthermore, by the definition, it is easy to show that if (x*,λ*)∈ℝn+1 is an optimal solution for Problem (T(y¯)), then x* is an efficient solution for the convex multiobjective programming problem (VPX), that is, x*∈XE. For the sake of convenience, x* is said to be an efficient solution associated withyw, and yw is said to be an efficient outcome point generated byy¯. It is easily seen that by varying the choices of points y¯∈B0∖G, the decision maker can generate multiple points in YEimage. In theory, if y¯ could vary over all of B0∖G, we could generate all of the properly efficient points of Y (see [24]) in this way.The following Proposition2.6 shows that for each efficient outcome point yw generated by a given point y¯, we can determine p new points which belong to B0∖G and differ y¯. This work is accomplished by a technique called cutting reverse polyblock.A set of the formB=⋃y∈V[y,yM]⊂ℝp, where [y,yM]:={y¯|y≤y¯≤yM}, V⊂B0=[ym,yM], and |V|<+∞, is called a reverse polyblock in hyperrectangle B0 with vertex setV. A vertex y∈V is said to be proper if there is no y′∈V∖{y} such that [y,yM]⊂[y′,yM]. It is clear that a reverse polyblock is completely determined by its proper vertices.Proposition 2.6 (see, e.g., [20]).
LetG=(Yimage+ℝ+p)∩(yM-ℝ+p) be a nonempty compact convex set contained in a reverse polyblock B=⋃y∈V[y,yM] with vertex set V⊂B0. Let v∈V∖G and yw is the unique point on the boundary of G that belongs to the line segment connecting v and yM. Then, B¯=B∖[v,yw] is a reverse polyblock with vertex set V¯=(V∖{v})∪{v1,v2,…,vp}, where
(2.18)vi=yw-(yiw-vi)ei,i=1,2,…,p,
where, as usual, ei denotes the ith unit vector of ℝp, and
(2.19)G⊂B¯⊂B,v∈B∖B¯.Remark 2.7.
By Proposition2.3, the point yw as described in Proposition 2.6 belongs to GE. From (2.18), it is easy to see that vi≠v for all i=1,…,p and for each i=1,…,p, the vertex vi∈B0∖G because yw≥vi and yw≠vi. The points v1,…,vp are called new vertices corresponding toyw.


### 2.2. The Algorithm

After the initialization step, the algorithm can execute the iteration step many times to generate a number of efficient outcome points for problem (CMP) depending on the user's requirements. Note that the construction of the boxB0 in Substep 1.1 of Algorithm 1 involves solving p convex programming problems, each of which has a simple linear objective function and the same feasible region. Let NumExpect be a positive integer number. The algorithm for generating NumExpect efficient outcome points to the problem (VPX) and NumExpect efficient solutions associated with them are described as follows.Algorithm 1.
Step 1 (Initialization).
(1.1)
ConstructB0=[ym,yM], where ym and yM are described in Section 2.1. Set B=B0.(1.2)
SetYEout=∅ (the set of efficient outcome points),XEout=∅ (the set of efficient solutions),Nef:=NumExpect,k:=0 (the number of elements of the set YEout),S={ym}.Step 2 (Iteration).
See Steps 2.1 through 2.3 below.(2.1)
SetS¯=∅.(2.2)
For each y¯∈Sdobegink:=k+1.Find an optimal solution(x*,λ*)∈ℝn+1 and the optimal value λ* to the problem (T(y¯)).Set wk=y¯+λ*(yM-y¯),YEout=YEout∪{wk} and XEout=XEout∪{x*} (see Remark 2.5),B¯=B∖[v,yw] with v=y¯ and yw=wk.Determinep vertices v1,…,vp corresponding to yw via formula (2.18).SetS¯=S¯∪{v1,…,vp} and B=B¯.end(2.3)
Ifk≥NefThen Terminate the algorithmElse Set S=S¯ and return the Step 2.


### 2.3. Example

To illustrate the Algorithm1, we consider the convex multiobjective programming problem (VPX) (see, Benson in [14]) with p=n=2, where(2.20)f1(x)=(x1-2)2+1,f2(x)=(x2-4)2+1,
and X⊂ℝ2 that satisfies the constraints(2.21)g1(x)=25x12+4x22-100≤0,g2(x)=x1+2x2-4≤0.What follows is a brief summary of the results of executing Algorithm1 for determining NumExpect=7 different efficient outcome points for this sample problem, and 7 efficient solutions associated with them.Step 1.
By solving the problem(P(1)), we obtain the optimal solution (1.0,0.0,1.0,100.0) and the optimal value y1opt=1.0. Then, y1=(1.0,100.0) is the optimal solution for the problem (P0(1)).
By solving problem(P(2)), we obtain the optimal value y2opt=2.380437 and the optimal solution (-1.6501599,2.8250799,100.0,2.380437). Hence, y2=(100.0,2.380437) is the optimal solution for the problem (P0(2)). From (2.4), we choose
(2.22)α=110.0>max⁡⁡{y11,y21,y12,y22}=max⁡⁡{1.0,100.0,100.0,2.380437}.
Then ym=(y1opt,y2opt)=(1.0,2.380437),andyM=(α,α)=(110.0,110.0). Set B=B0=[ym,yM], YEout:=∅, XEout:=∅,Nef:=NumExpect=7; k:=0 and S:={ym}.Step 2 (The first time).
Substep 2.1.
SetS¯=∅.Substep 2.2 (The setS has only one element (1.0, 2.380437)).
Lety¯:=(1.0,2.380437) and k=1. By solving the problem (T(y¯)), we obtain the optimal solution (x*,λ*)=(0.230078,1.884961,0.028740) and the optimal value λ*=0.028740. Then,(2.23)w1=y¯+λ*(yM-y¯)=(4.132625,5.473389)
(the first efficient outcome point),(2.24)x1=x*=(0.230078,1.884961)
(the first efficient solution).Set(2.25)YEout:=YEout∪{w1}={w1},XEout:=XEout∪{x1}={x1},B¯=B∖[v,yw]withv=y¯,yw=w1.Using formula (2.18), we obtain p=2 new vertices v1=(1.0,5.473389) and v2=(4.132625,2.380437) corresponding to yw.SetS¯=S¯∪{v1,v2}={(1.0,5.473389),(4.132625,2.380437)} and B=B¯.Substep 2.3.
Sincek=1<Nef=7, set S=S¯ and return to the Step 2.Step 2 (The second time).
Substep 2.1.
S¯:=∅.Substep 2.2.
(The setS has 2 elements:s1=(1.0,5.473389),s2=(4.132625,2.380437)) (i)
Lety¯=s1=(1.0,5.473389) and k=2. The problem (T(y¯)) has the optimal solution (x*,λ*)=(0.820117,1.589942,0.012772), and the optimal value λ*=0.012772. We have
(2.26)w2=(2.392125,6.808381),(thesecondefficientoutcomepoint),x2=(0.820117,1.589942),(thesecondefficientsolution).Set(2.27)YEout=YEout∪{w2}={w1,w2},XEout=XEout∪{x2}={x1,x2},B¯=B∖[v,yw]withv=y¯,yw=w2.Two new vertices corresponding toyw are v1=(1.0,6.808381), and v2=(2.392125,5.473389).SetS¯=S¯∪{v1,v2}={(1.0,6.808381),(2.392125,5.473389) and B=B¯.(ii)
Lety¯=s2=(4.132625,2.380437) and k=3. Then,(x*,λ*)=(-0.276796,2.138398,0.019375), and λ*=0.019375 are the optimal solution and the optimal value for the problem (T(y¯)), respectively. Then,
(2.28)w3=(6.183801,4.465562),(thethirdefficientoutcomepoint),x3=(-0.276796,2.138398),(thethirdefficientsolution).Set(2.29)YEout=YEout∪{w3}={w1,w2,w3},XEout=XEout∪{x3}={x1,x2,x3},B¯=B∖[v,yw]withv=y¯,yw=w3.Two new vertices corresponding toyw are    v1=(4.132625,4.465562), and v2=(6.1838011,2.380437).SetS¯=S¯∪{v1,v2}={(1.0,6.808381),(2.392125,5.473389),(4.132625,4.465562),(6.1838011,2.380437)}, and B=B¯.Substep 2.3.
Sincek=3<Nef=7, set S:=S¯ and return to the Step 2.Step 2 (The third time).
Substep 2.1.
S¯:=∅.Substep 2.2.
(The setS has 4 elements: s1=(1.0,6.808381), s2=(2.392125,5.473389), s3=(4.132625,4.465562), s4=(6.1838011,2.380437)).
By a calculation analogous to above, we yield four next efficient outcome pointsw4, w5, w6, and w7 generated by y¯=s1, y¯=s2, y¯=s3, y¯=s4, respectively, and four next efficient solution x4, x5, x6, x7 associated with w4, w5, w6, w7, respectively. Namely,
(2.30)w4=(1.779439,7.546285);x4=(1.117142,1.441430);w5=(3.109453,6.170177);x5=(0.547605,1.726198);w6=(4.780944,5.111841);x6=(0.055535,1.972232);w7=(7.668913,3.919957);x7=(-0.582424,2.291212).
Since k=Nef=7, the algorithm is terminated. Thus, after 3 iterations, we obtain YEout={w1,w2,…,w7}, and XEout={x1,x2,…,x7}.


## 2.1. Theoretical Basis

Assume henceforth thatX⊂ℝn is a nonempty, compact convex set given by(2.1)X:={x∈Rn∣gi(x)≤0,i=1,…,m},
where all the g1,g2,…,gm are convex functions on ℝn. Then the set(2.2)G0=Yimage+R+p
is nonempty full-dimensional convex set in ℝp. Furthermore, from Yu [21, page 22, Theorem  3.2], we know that YEimage=GE0.For eachk=1,…,p, we consider the following problem:(P0(k))min⁡⁡yk,s.t.y∈G0.
We denote the optimal value for the problem (P0(k)) by ykopt and the optimal solution for this problem by yk=(y1k,…,ypk)∈ℝp.Letym=(y1m,y2m,…,ypm), where(2.3)ykm=ykopt∀k=1,2,…,p.
As usual, the point ym is said to be an ideal efficient point of G0. It is clear that if ym∈G0 then YEimage=GE0={ym}. Therefore, we suppose that ym∉G0. Obviously, by definition, if (x*,y*)∈ℝn+p is an optimal solution for the problem (P(k)) given by (P(k))min⁡yks.t.fj(x)-yj≤0,j=1,…,p,gi(x)≤0,i=1,…,m,
then yk=y* is an optimal solution for the problem (P0(k)), and the optimal values of these two problems are equal.To generate various efficient outcome points inYEimage, the algorithm will rely upon the point yM=(y1M,y2M,…,ypM), where for each j=1,2,…,p,yjM=α, and α is any real number satisfying(2.4)α>max⁡⁡{yjk,k=1,…,p,j=1,…,p}.We consider the setG given by(2.5)G=G0∩(yM-R+p).
It is obvious that G is a nonempty, full-dimensional compact convex set in ℝp. The set G is instrumental in Algorithm 1 to be presented in Section 2.2 for generating efficient outcome points for problem (VPX).Remark 2.1.
In 1998, Benson [1] presented the outer approximation algorithm for generating all efficient extreme points in the outcome set of a multiobjective linear programming problem. Here, the G seems to be analogous with the set Y considered by Benson [1]. However, note that Y⊃Yimage and Yimage is not necessarily a subset of G. The Figure 1 illustrates the set G in the case of p=2.Figure 1Proposition 2.2.
YEimage=GE.Proof.
This result is easy to show by using Yu [21, page 22, Theorem  3.2] and the definition of the point yM. Therefore, the proof is omitted.Let(2.6)B0=(ym+R+p)∩(yM-R+p).
It is clear that G⊂B0. The following fact will play an important role in establishing the validity of our algorithm.Proposition 2.3.
For each pointy¯∈B0∖G, let yw denote the unique point on the boundary of G that belongs to the line segment connecting y¯ and yM. Then yw∈GE.Proof.
LetD=G-yw. Since G is the compact convex set and yw belongs to the boundary of G, the set D is also the compact convex set containing the origin 0 of the outcome space ℝp and 0 belongs to the boundary of D. According to the separation theorem [22], there is a nonzero vector q∈ℝp such that
(2.7)〈q,u〉≥0∀u∈D.
Let S⊂ℝp be a p-simplex with vertices 0, e1,e2,…,ep, where e1,e2,…,ep are the unit vectors of ℝp. By definition, we can choose the point yM such that (yw+S)⊂G. This implies that S⊂D. From (2.7), by taking u to be e1,e2,…,ep to see that
(2.8)q≥0.
Furthermore, the expression (2.7) can be written by
(2.9)〈q,y-yw〉≥0∀y∈G,
that is,
(2.10)〈q,y〉≥〈q,yw〉∀y∈G.
According to [23, Chapter 4, Theorem  2.10], a point y*∈G is a weakly efficient point of G if and only if there is a nonzero vector v∈ℝp and v≥0 such that y* is an optimal solution to the convex programming problem(2.11)min⁡⁡{〈v,y〉∣y∈G}.
Combining this fact, (2.8) and (2.10) give yw∈GWE. To complete the proof, it remains to show that yw∈GE. Assume the contrary that
(2.12)yw∈GWE∖GE.
By the definition, we have
(2.13)GWE=GE∪(⋃k=1pFk),
where for each k=1,…,p, Fk is the optimal solution set for the following problem:
(PG(k))min⁡⁡yk,s.t.y∈G.
It is easy to see that the optimal values of two problems (PG(k)) and (P0(k)) are the same. From this fact and the definition of the point ym, it follows that
(2.14)Fk={y∈G∣yk=ykm}.
Therefore, if yw∈GWE∖GE then there is i0∈{1,2,…,p} such that yi0w=yi0m. Since y¯∈B0∖G, we always have y¯≥ym and yw=λyM+(1-λ)y¯ with 0<λ<1. By the choice of the point yM, we have yM≫ym. Hence,
(2.15)yi0m=yi0w=λyi0M+(1-λ)y¯i0>yi0m.
This contradiction proves that yw must belong to the efficient outcome set GE.Remark 2.4.
This Proposition2.3 can be viewed as an Benson's extension in [1, Proposition  2.4].  Benson showed that the unique point on the boundary of Y (which is considered in [1]) and corresponding segment belongs to the weakly efficient outcome set YWE, here we prove that yw belongs to the efficient outcome set GE.Remark 2.5.
Lety¯ be a given point in B0∖G. From Propositions 2.3 and 2.2, the line segment connecting y¯ and yM contains a unique point yw∈YEimage which lies on the boundary of G. To determine this efficient outcome point yw, we have to find the unique value λ* of λ, 0<λ<1, such that
(2.16)yw=λ*yM+(1-λ*)y¯=y¯+λ*(yM-y¯)
belongs to the boundary of G (see Figure 2). It means that λ* is the optimal value for the problemFigure 2(2.17)min⁡λs.t.y¯+λ(yM-y¯)∈G,0≤λ≤1.
By definition, it is easy to see that λ* is also the optimal value for the following convex programming problem with linear objective function(T(y¯))min⁡λs.t.f(x)-λ(yM-y¯)-y¯≤0,gi(x)≤0,i=1,…,m,0≤λ≤1.
Note that λ* exists because the feasible region of problem (T(y¯)) is a nonempty, compact convex set. Furthermore, by the definition, it is easy to show that if (x*,λ*)∈ℝn+1 is an optimal solution for Problem (T(y¯)), then x* is an efficient solution for the convex multiobjective programming problem (VPX), that is, x*∈XE. For the sake of convenience, x* is said to be an efficient solution associated withyw, and yw is said to be an efficient outcome point generated byy¯. It is easily seen that by varying the choices of points y¯∈B0∖G, the decision maker can generate multiple points in YEimage. In theory, if y¯ could vary over all of B0∖G, we could generate all of the properly efficient points of Y (see [24]) in this way.The following Proposition2.6 shows that for each efficient outcome point yw generated by a given point y¯, we can determine p new points which belong to B0∖G and differ y¯. This work is accomplished by a technique called cutting reverse polyblock.A set of the formB=⋃y∈V[y,yM]⊂ℝp, where [y,yM]:={y¯|y≤y¯≤yM}, V⊂B0=[ym,yM], and |V|<+∞, is called a reverse polyblock in hyperrectangle B0 with vertex setV. A vertex y∈V is said to be proper if there is no y′∈V∖{y} such that [y,yM]⊂[y′,yM]. It is clear that a reverse polyblock is completely determined by its proper vertices.Proposition 2.6 (see, e.g., [20]).
LetG=(Yimage+ℝ+p)∩(yM-ℝ+p) be a nonempty compact convex set contained in a reverse polyblock B=⋃y∈V[y,yM] with vertex set V⊂B0. Let v∈V∖G and yw is the unique point on the boundary of G that belongs to the line segment connecting v and yM. Then, B¯=B∖[v,yw] is a reverse polyblock with vertex set V¯=(V∖{v})∪{v1,v2,…,vp}, where
(2.18)vi=yw-(yiw-vi)ei,i=1,2,…,p,
where, as usual, ei denotes the ith unit vector of ℝp, and
(2.19)G⊂B¯⊂B,v∈B∖B¯.Remark 2.7.
By Proposition2.3, the point yw as described in Proposition 2.6 belongs to GE. From (2.18), it is easy to see that vi≠v for all i=1,…,p and for each i=1,…,p, the vertex vi∈B0∖G because yw≥vi and yw≠vi. The points v1,…,vp are called new vertices corresponding toyw.


## 2.2. The Algorithm

After the initialization step, the algorithm can execute the iteration step many times to generate a number of efficient outcome points for problem (CMP) depending on the user's requirements. Note that the construction of the boxB0 in Substep 1.1 of Algorithm 1 involves solving p convex programming problems, each of which has a simple linear objective function and the same feasible region. Let NumExpect be a positive integer number. The algorithm for generating NumExpect efficient outcome points to the problem (VPX) and NumExpect efficient solutions associated with them are described as follows.Algorithm 1.
Step 1 (Initialization).
(1.1)
ConstructB0=[ym,yM], where ym and yM are described in Section 2.1. Set B=B0.(1.2)
SetYEout=∅ (the set of efficient outcome points),XEout=∅ (the set of efficient solutions),Nef:=NumExpect,k:=0 (the number of elements of the set YEout),S={ym}.Step 2 (Iteration).
See Steps 2.1 through 2.3 below.(2.1)
SetS¯=∅.(2.2)
For each y¯∈Sdobegink:=k+1.Find an optimal solution(x*,λ*)∈ℝn+1 and the optimal value λ* to the problem (T(y¯)).Set wk=y¯+λ*(yM-y¯),YEout=YEout∪{wk} and XEout=XEout∪{x*} (see Remark 2.5),B¯=B∖[v,yw] with v=y¯ and yw=wk.Determinep vertices v1,…,vp corresponding to yw via formula (2.18).SetS¯=S¯∪{v1,…,vp} and B=B¯.end(2.3)
Ifk≥NefThen Terminate the algorithmElse Set S=S¯ and return the Step 2.


## 2.3. Example

To illustrate the Algorithm1, we consider the convex multiobjective programming problem (VPX) (see, Benson in [14]) with p=n=2, where(2.20)f1(x)=(x1-2)2+1,f2(x)=(x2-4)2+1,
and X⊂ℝ2 that satisfies the constraints(2.21)g1(x)=25x12+4x22-100≤0,g2(x)=x1+2x2-4≤0.What follows is a brief summary of the results of executing Algorithm1 for determining NumExpect=7 different efficient outcome points for this sample problem, and 7 efficient solutions associated with them.Step 1.
By solving the problem(P(1)), we obtain the optimal solution (1.0,0.0,1.0,100.0) and the optimal value y1opt=1.0. Then, y1=(1.0,100.0) is the optimal solution for the problem (P0(1)).
By solving problem(P(2)), we obtain the optimal value y2opt=2.380437 and the optimal solution (-1.6501599,2.8250799,100.0,2.380437). Hence, y2=(100.0,2.380437) is the optimal solution for the problem (P0(2)). From (2.4), we choose
(2.22)α=110.0>max⁡⁡{y11,y21,y12,y22}=max⁡⁡{1.0,100.0,100.0,2.380437}.
Then ym=(y1opt,y2opt)=(1.0,2.380437),andyM=(α,α)=(110.0,110.0). Set B=B0=[ym,yM], YEout:=∅, XEout:=∅,Nef:=NumExpect=7; k:=0 and S:={ym}.Step 2 (The first time).
Substep 2.1.
SetS¯=∅.Substep 2.2 (The setS has only one element (1.0, 2.380437)).
Lety¯:=(1.0,2.380437) and k=1. By solving the problem (T(y¯)), we obtain the optimal solution (x*,λ*)=(0.230078,1.884961,0.028740) and the optimal value λ*=0.028740. Then,(2.23)w1=y¯+λ*(yM-y¯)=(4.132625,5.473389)
(the first efficient outcome point),(2.24)x1=x*=(0.230078,1.884961)
(the first efficient solution).Set(2.25)YEout:=YEout∪{w1}={w1},XEout:=XEout∪{x1}={x1},B¯=B∖[v,yw]withv=y¯,yw=w1.Using formula (2.18), we obtain p=2 new vertices v1=(1.0,5.473389) and v2=(4.132625,2.380437) corresponding to yw.SetS¯=S¯∪{v1,v2}={(1.0,5.473389),(4.132625,2.380437)} and B=B¯.Substep 2.3.
Sincek=1<Nef=7, set S=S¯ and return to the Step 2.Step 2 (The second time).
Substep 2.1.
S¯:=∅.Substep 2.2.
(The setS has 2 elements:s1=(1.0,5.473389),s2=(4.132625,2.380437)) (i)
Lety¯=s1=(1.0,5.473389) and k=2. The problem (T(y¯)) has the optimal solution (x*,λ*)=(0.820117,1.589942,0.012772), and the optimal value λ*=0.012772. We have
(2.26)w2=(2.392125,6.808381),(thesecondefficientoutcomepoint),x2=(0.820117,1.589942),(thesecondefficientsolution).Set(2.27)YEout=YEout∪{w2}={w1,w2},XEout=XEout∪{x2}={x1,x2},B¯=B∖[v,yw]withv=y¯,yw=w2.Two new vertices corresponding toyw are v1=(1.0,6.808381), and v2=(2.392125,5.473389).SetS¯=S¯∪{v1,v2}={(1.0,6.808381),(2.392125,5.473389) and B=B¯.(ii)
Lety¯=s2=(4.132625,2.380437) and k=3. Then,(x*,λ*)=(-0.276796,2.138398,0.019375), and λ*=0.019375 are the optimal solution and the optimal value for the problem (T(y¯)), respectively. Then,
(2.28)w3=(6.183801,4.465562),(thethirdefficientoutcomepoint),x3=(-0.276796,2.138398),(thethirdefficientsolution).Set(2.29)YEout=YEout∪{w3}={w1,w2,w3},XEout=XEout∪{x3}={x1,x2,x3},B¯=B∖[v,yw]withv=y¯,yw=w3.Two new vertices corresponding toyw are    v1=(4.132625,4.465562), and v2=(6.1838011,2.380437).SetS¯=S¯∪{v1,v2}={(1.0,6.808381),(2.392125,5.473389),(4.132625,4.465562),(6.1838011,2.380437)}, and B=B¯.Substep 2.3.
Sincek=3<Nef=7, set S:=S¯ and return to the Step 2.Step 2 (The third time).
Substep 2.1.
S¯:=∅.Substep 2.2.
(The setS has 4 elements: s1=(1.0,6.808381), s2=(2.392125,5.473389), s3=(4.132625,4.465562), s4=(6.1838011,2.380437)).
By a calculation analogous to above, we yield four next efficient outcome pointsw4, w5, w6, and w7 generated by y¯=s1, y¯=s2, y¯=s3, y¯=s4, respectively, and four next efficient solution x4, x5, x6, x7 associated with w4, w5, w6, w7, respectively. Namely,
(2.30)w4=(1.779439,7.546285);x4=(1.117142,1.441430);w5=(3.109453,6.170177);x5=(0.547605,1.726198);w6=(4.780944,5.111841);x6=(0.055535,1.972232);w7=(7.668913,3.919957);x7=(-0.582424,2.291212).
Since k=Nef=7, the algorithm is terminated. Thus, after 3 iterations, we obtain YEout={w1,w2,…,w7}, and XEout={x1,x2,…,x7}.


## 3. Application to Problem(CPX)

Consider convex multiplicative programming problem(CPX) associated with the convex multiobjective programming problem (VPX)(CPX)min⁡⁡∏j=1pfj(x)s.t.x∈X,
where X⊂ℝn is a nonempty compact convex set defined by (2.1) and (fj:ℝn→ℝ) is convex on ℝn and positive on X, j=1,2,…,p.One of the direct reformulations of the problem(CPX) as an outcome-space problem is given by(OPY)min⁡h(y)=∏j=1pyjs. t.y∈Yimage,
where Yimage={f(x)=(f1(x),…,fp(x))T|x∈X} is the outcome set of X under f. By assumption, we have Yimage⊂intℝ+p.The following proposition tells us a link between the global solution to the problem(OPY) and the efficient outcome set YEimage for the problem (VPX).Proposition 3.1.
Any global optimal solution to problem(OPY) must belong to the efficient outcome set YEimage.Proof.
The proposition follows directly from the definition.Remark 3.2.
We invoke Propositions3.1 and 2.2 to deduce that problem (OPY) is equivalent to the following problem:
(OPGE)min⁡h(y)=∏j=1pyjs.t.y∈GE.
The relationship between two problems (CPX) and (OPY) is described by the following theorem and was given in [14, Theorem  2.2]. However, we give here a full proof for the reader's convenience.Theorem 3.3.
Ify* is a global optimal solution to problem (OPY), then any x*∈X such that f(x*)≤y* is a global optimal solution to problem (CPX). Furthermore, the global optimal values of two problems (CPX) and (OPY) are equal, that is,
(3.1)h(y*)=∏j=1pyj*=∏j=1pfj(x*).Proof.
Suppose thaty* is a global optimal solution to problem (OPY) and x*∈X satisfies
(3.2)f(x*)≤y*.
By Proposition 3.1, y*∈YEimage. Since f(x*)∈Yimage and y*∈YEimage, from (3.2), we have f(x*)=y*. Thus, h(y*)=∏j=1pyj*=∏j=1pfj(x*). Now, we show that x* is a global optimal solution of the problem (CPX). Indeed, assume the contrary that there is a point x∈X such that ∏j=1pfj(x)<∏j=1pfj(x*). Combining this fact and (3.2) gives
(3.3)∏j=1pfj(x)<∏j=1pfj(x*)≤∏j=1pyj*.
Since x∈X, we have y=f(x)∈Yimage. Therefore, ∏j=1pyj<∏j=1pyj*. This contradicts the hypothesis that y* is a global optimal solution to problem (OPY) and proves that x* is a global optimal solution to problem (CPX). This completes the proof.By Theorem3.3 and Proposition 3.1, solving the problem (CPX) can be carried out in two stages:(1)
finding a global optimal solutiony* to the problem (OPGE). Then y* is also a global optimal solution to the problem (OPY),(2)
finding a global optimal solutionx*∈X to the problem (CPX) which satisfies f(x*)≤y*.In the next section, the outer approximation algorithm is developed for solving the problem(OPGE).


### 3.1. Outer Approximation Algorithm for Solving Problem(OPGE)

Starting with the polyblockB0=[ym,yM] (see Section 2.1), the algorithm will iteratively generate a sequence of reverse polyblocks Bk, k=1,2,…, such that(3.4)B0⊃B1⊃B2⊃⋯⊃G⊃GE.
For each k=0,1,2,…, the new reverse polyblock Bk+1 is constructed via the formula(3.5)Bk+1:=Bk∖[v,yw],
where v=yk,yk is a global optimal solution to the problem min{h(y)∣y∈Bk}, and yw is the efficient outcome point generated by y¯=yk.For eachk, let Vk denote the vertex set of the reverse polyblock Bk. The following Proposition 3.4 shows that the function h(y) achieves a minimum over the reverse polyblock Bk at a proper vertex.Proposition 3.4.
Leth(y)=∏j=1pyj, and let Bk be a reverse polyblock. Consider the problem to minimize h(y) subject to y∈Bk. An optimal solution yk to the problem then exists, where yk is a proper vertex of Bk.Proof.
By definition, note that the objective functionh(y) is a continuous function on ℝp, and Bk is a compact, and the problem min{h(y)∣y∈Bk} has an optimal solution yk∈Bk. For each y∈Bk, there is a proper vertex v of Bk such that y∈[v,yM]. That means v≤y. By definition of the function h(y), we have h(v)≤h(y). This shows that h(yk)=min{h(y)|y∈Vk}, where Vk is the vertex set of Bk, and the proof is completed.Remark 3.5.
By Proposition3.4, instead of solving problem min{h(y)|y∈Bk}, we solve the simple problem min{h(y)|y∈Vk}. From (3.4), it is clear that for each k=0,1,2…, the optimal value
(3.6)βk=min⁡⁡{h(y)=∏j=1pyj|y∈Bk}
is a lower bound for the problem (OPGE), and {βk} is an increasing sequence, that is, βk+1>βk for all k=0,1,2,….Letɛ be a given sufficient small real number. Let y*∈GE. Then h(y*) is an upper bound for the problem (OPGE). A point y* is said to be an ɛ-optimal solution to problem (OPGE) if there is a lower bound β* for this problem such that h(y*)-β*<ɛ.Below, we will present an algorithm for findingɛ-optimal solution to problem (OPGE).At the beginning of a typical iterationk≥0 of the algorithm, we have from the previous iteration an available nonempty reverse polyblock Bk⊂ℝp that contains G and an upper bound θk for the problem (OPGE). In iteration k, firstly problem min{h(y)|y∈Vk} is solved to obtain the optimal solution set Tkopt. By the construction, Tkopt⊂(B0∖G). Take any yk∈Tkopt. The optimal value βk=h(yk) is the best currently lower bound. Then, we solve the convex programming problem (T(y¯)) with y¯:=yk to receive the optimal value λ*. By Proposition 2.3, the feasible solution ωk=y¯+λ*(yM-y¯)∈GE is an outcome efficient point generated by y¯=yk (see Remark 2.5). Now, the best currently upper bound is θk=min{θk,h(ωk)} and the feasible solution ybest satisfying h(ybest)=θk is said to be a currently best feasible solution. If θk-βk<ɛ, then the algorithm terminates, and ybest is anɛ-optimal solution for the problem(OPGE). Otherwise, set Bk+1:=Bk∖[v,yw], where v:=yk and yω=ωk. According to Proposition 2.6, the vertex set Vk+1 of the reverse polyblock Bk+1 is(3.7)Vk+1=(Vk∖{v})∪{v1,v2,…,vp},
where v1,…,vp are determined by formula (2.18). Figure 3 illustrates two beginning steps of the algorithm in the case of p=2.Figure 3By the construction, it is easy to see that{θk} (the sequence of upper bounds for the problem (OPGE) is the nonincreasing sequence, that is, θk+1≤θk for all k=0,1,2,…Now, the outer approximation algorithm for solving(OPGE) is stated as follows.Algorithm 2 (Outer approximation algorithm).
Initialization Step
ConstructB0=[ym,yM], where ym and yM are described in Section 2.1. Choose ɛ>0 (ɛ>0 is a sufficient small number). Set V0={ym} and θ0:=Numlarge (Numlarge is a sufficient large number. This number can be viewed as an initialization the upper bound). Set k=0 and go to Iteration step k.
Iteration Stepk [k=0,1,2,…]. See Steps k.1 through k.5 below.k.1
Determine the optimal solution setTkopt:=Argmin{h(y)|y∈Vk}. Choose an arbitrary yk∈Tkopt and set βk:=h(yk) (currently best lower bound).k.2
Lety¯=yk. Find the optimal value λ* to the problem (T(y¯)). And set ωk=y¯+λ*(yM-y¯)∈GE.k.3
(Update the upper bound)Ifh(ωk)<θkThenθk=h(ωk) (currently best upper bound)andybest=ωk (currently best feasible point).k.4
If  θk-βk≤ɛThen Terminate the algorithm: ybest is an ɛ-optimal solutionElse Set Bk+1:=Bk∖[v,yw] where v:=yk and yω=ωkand determine the setVk+1 by formula (2.18).k.5
Setθk+1:=θk; k:=k+1 and go to iteration step k.Theorem 3.6.
The algorithm terminates after finitely many steps and yields anɛ-optimal solution to problem (OPGE).Proof.
Letɛ be a given positive number. Since the function h(y) is uniformly continuous on the compact set B0, we can choose an enough small number δ>0 such that if y,y′∈B0 and ∥y-y′∥<δ, then |h(y)-h(y′)|<ɛ. Then, to prove the termination of the algorithm, we need to show only that
(3.8)lim⁡k→∞‖wk-yk‖=0.
Observe first that the positive series∑k=1∞Vol[yk,wk] is convergent, since the open boxes int[yk,wk] are disjoint, and all of them are contained in the closure of B0∖G. It follows that(3.9)lim⁡k→∞Vol[yk,wk]=0.
Now, by the construction of wk and yk, we have
(3.10)wk-yk=λk(yM-yk),(3.11)Vol[yk,wk]=λkpVol[yk,yM],
for λk∈(0,1). Note that all of the points yk are contained in the set B0∖G. Furthermore, by the choice of yM (see (2.4)), the closure of B0∖G is a compact subset of the interior of the cone yM-ℝ+p. This observation implies that Vol[yk,yM] has a lower bound far from zero. Combining this fact, (3.9) and (3.11) imply that limk→∞λk=0. Also, the observation implies that ∥yM-yk∥ is bounded. Finally, by (3.10), we have limk→∞∥wk-yk∥=0.


### 3.2. Computational Results

First, the Algorithm2 has been applied for solving the test example given by Benson in [14] (see the example in Section 2.3)(3.12)min⁡{f1(x)f2(x)∣g1(x)≤0,g2(x)≤0},
where f1(x)=(x1-2)2+1, f2(x)=(x2-4)2+1, and g1(x)=25x12+4x22-100, g2(x)=x1+2x2-4.The calculation process for solving this example is described as follows.Initialization.
Similarly, the example in Section2.3, we have B0=[ym,yM] with ym=(1.00000,2.380437), and yM=(110.000000,110.000000). We choose ɛ=0.025 and set V0={ym=(1.00000,2.380437)}, θ0=10000 (the initialization upper bound), k=0 and go to iteration step k=0.Iteration (k=0).
Step 1.
We haveT0opt:=argmin{h(y)|y∈V0}={ym}. Choose y0:=ym∈T0opt, and set β0:=h(y0)=2.380437 (currently best lower bound).Step 2.
Lety¯=y0. Solving the problem (T(y¯)), we obtain the optimal solution (x*,λ*)=(0.230078,1.884961,0.028740)) and the optimal value λ*=0.028740. Then, w0=y¯+λ*(yM-y¯)=(4.132625,5.473389)∈GE.Step 3.
Sinceh(w0)=22.619464<θ0, we have θ0=h(w0)=22.619464 (currently best upper bound), and ybest=w0 (currently best feasible point).Step 4.
Sinceθ0-β0=20.239027>ɛ, we set B1:=B0∖[v,yw], where v:=y0, yw=w0 and determine the set
(3.13)V1={(1.000000,5.473389),(4.132625,2.380437)}.Step 5.
Setθ1:=θ0=22.619464;k:=0+1=1, and go to iteration step k=1.Iteration (k=1).
Step 1.
We haveT1opt:=argmin{h(y)|y∈V1}={y1=(1.000000,5.473389)}. Choose y1∈T1opt and set β1:=h(y1)=5.473389 (the currently lower bound).Step 2.
Lety¯=y1. The convex programming (T(y¯)) has the optimal solution (x*,λ*)=(0.82011,1.589942,0.012772)), and the optimal value λ*=0.012772. Then, we have w1=(2.392125,6.808381)∈GE.Step 3.
Sinceh(w1)=16.286498<θ1, we set θ1=h(w1) (the currently best upper bound), and ybest=w1 (the currently best feasible point).Step 4.
Now,θ1-β1=10.813109>ɛ. Therefore, B2:=B1∖[v,yw], where v:=y1,yw=w1, and V2={(4.132625,2.380437),(1.000000,6.808381),(2.392125,5.473389)}.Step 5.
Setθ2=θ1=16.286498;k:=1+1=2, and go to iteration step k=2.Iteration (k=2).
Step 1.
We haveT2opt=argmin{h(y)|y∈V2}={y2=(1.000000,6.808381)}, choose y2:=(1.000000,6.808381)∈T2opt, and set β2:=h(y2)=6.808381.Step 2.
Lety¯=y2. The problem (T(y¯)) has the optimal solution (x*,λ*)=(1.117142,1.441429,0.007151)), and the optimal value λ*=0.007151. Then w2=(1.779439,7.546285)∈GE.Step 3.
Sinceh(w2)=13.428154<θ2, the currently best upper bound θ2:=h(w2) and the currently best feasible point ybest=w2=(1.779439,7.546285).Step 4.
Sinceθ2-β2=6.619773>ɛ, we set B3:=B2∖[v,yw],  where v:=y2, yw=w2, and determine the set V3={(4.132625,2.380437),(2.392125,5.473389),(1.000000,7.546285),(1.779439,6.808381)}.Step 5.
Setθ3:=θ2=13.428154,k:=2+1=3, and go to iteration step k=3.After 42 iterations, the algorithm terminates withθ42=9.770252094 and β42=9.745596873, where θ42=h(w20). Then, the ɛ-optimal solution for the problem (OPY) and for the problem (CPX) are given by (3.14)y*=ybest=w20=(1.023846379,9.542693410),
and x*=(1.845577271,1.077211364). The approximate optimal value of problem (3.12) is 9.770252094.Below, we present the results of computational experiment for two types of problem. We takeɛ=0.025 in the numerical experiments. We tested our algorithm for each problem with random data for several times. Then, we took results in average. Numerical results are summarized in Tables 1 and 2.Table 1
Computational results on the problem of Type 1.
Problem no.pmnAverage number of iterationsAverage CPU time (sec)131010110.832320209.92.0833305019.219.443406017.524.42536010026.2109.664202023.14.374203014.14.8784305026.22094406059.661.641046010036.6142.32Table 2
Computational results on the problem of Type 2.
Problem no.pmnAverage number of iterationsAverage CPU time (sec)132020145.1823203026.914.643330504051.3543406042.677.38536010059.5316.7964202034.87.5774203089.835.2784305080.786.8394406078.4112.231046010085.5372.59Type 1.
(3.15)min⁡∏j=1pfj(x),s.t.Ax≤b,x≥0,
where fj(x)=〈αj,x〉+μj, αj∈ℝn, μj∈ℝ,j=1,…,p, A is an (m×n)-matrix, and b∈ℝm.Type 2.
(3.16)min⁡∏j=1pfj(x),s.t.Ax≤b,x≥0,
where fj(x)=(α1jx1+β1j)2+⋯+(αnjxn+βnj)2+νj, with αj,βj∈ℝn, νj∈ℝ, j=1,…,p, A is an (m×n)-matrix, and b∈ℝm.
Our program was coded in Matlab R2007a and was executed on our own PC with the configuration, CPU Intel Core 2 T5300 1.73 GHz, 1 G Ram. On the two above problems, the parameters are defined as follows:
(i)
A=(aij)∈ℝm×n is a randomly generated matrix with elements in [-1,1];(ii)
b=(b1,…,bm)T is a random vector satisfying the formula
(3.17)bi=∑j=1naij+b0iwithb0i being a random number in [0,2] for i=1,…,m;(iii)
αj=(α1j,…,αnj) and βj=(β1j,…,βnj), j=1,…,p are vectors with elements randomly distributed on [0,1];(iv)
the coefficientsμj, νj, j=1,…,p are uniformly distributed on [0,1].


## 3.1. Outer Approximation Algorithm for Solving Problem(OPGE)

Starting with the polyblockB0=[ym,yM] (see Section 2.1), the algorithm will iteratively generate a sequence of reverse polyblocks Bk, k=1,2,…, such that(3.4)B0⊃B1⊃B2⊃⋯⊃G⊃GE.
For each k=0,1,2,…, the new reverse polyblock Bk+1 is constructed via the formula(3.5)Bk+1:=Bk∖[v,yw],
where v=yk,yk is a global optimal solution to the problem min{h(y)∣y∈Bk}, and yw is the efficient outcome point generated by y¯=yk.For eachk, let Vk denote the vertex set of the reverse polyblock Bk. The following Proposition 3.4 shows that the function h(y) achieves a minimum over the reverse polyblock Bk at a proper vertex.Proposition 3.4.
Leth(y)=∏j=1pyj, and let Bk be a reverse polyblock. Consider the problem to minimize h(y) subject to y∈Bk. An optimal solution yk to the problem then exists, where yk is a proper vertex of Bk.Proof.
By definition, note that the objective functionh(y) is a continuous function on ℝp, and Bk is a compact, and the problem min{h(y)∣y∈Bk} has an optimal solution yk∈Bk. For each y∈Bk, there is a proper vertex v of Bk such that y∈[v,yM]. That means v≤y. By definition of the function h(y), we have h(v)≤h(y). This shows that h(yk)=min{h(y)|y∈Vk}, where Vk is the vertex set of Bk, and the proof is completed.Remark 3.5.
By Proposition3.4, instead of solving problem min{h(y)|y∈Bk}, we solve the simple problem min{h(y)|y∈Vk}. From (3.4), it is clear that for each k=0,1,2…, the optimal value
(3.6)βk=min⁡⁡{h(y)=∏j=1pyj|y∈Bk}
is a lower bound for the problem (OPGE), and {βk} is an increasing sequence, that is, βk+1>βk for all k=0,1,2,….Letɛ be a given sufficient small real number. Let y*∈GE. Then h(y*) is an upper bound for the problem (OPGE). A point y* is said to be an ɛ-optimal solution to problem (OPGE) if there is a lower bound β* for this problem such that h(y*)-β*<ɛ.Below, we will present an algorithm for findingɛ-optimal solution to problem (OPGE).At the beginning of a typical iterationk≥0 of the algorithm, we have from the previous iteration an available nonempty reverse polyblock Bk⊂ℝp that contains G and an upper bound θk for the problem (OPGE). In iteration k, firstly problem min{h(y)|y∈Vk} is solved to obtain the optimal solution set Tkopt. By the construction, Tkopt⊂(B0∖G). Take any yk∈Tkopt. The optimal value βk=h(yk) is the best currently lower bound. Then, we solve the convex programming problem (T(y¯)) with y¯:=yk to receive the optimal value λ*. By Proposition 2.3, the feasible solution ωk=y¯+λ*(yM-y¯)∈GE is an outcome efficient point generated by y¯=yk (see Remark 2.5). Now, the best currently upper bound is θk=min{θk,h(ωk)} and the feasible solution ybest satisfying h(ybest)=θk is said to be a currently best feasible solution. If θk-βk<ɛ, then the algorithm terminates, and ybest is anɛ-optimal solution for the problem(OPGE). Otherwise, set Bk+1:=Bk∖[v,yw], where v:=yk and yω=ωk. According to Proposition 2.6, the vertex set Vk+1 of the reverse polyblock Bk+1 is(3.7)Vk+1=(Vk∖{v})∪{v1,v2,…,vp},
where v1,…,vp are determined by formula (2.18). Figure 3 illustrates two beginning steps of the algorithm in the case of p=2.Figure 3By the construction, it is easy to see that{θk} (the sequence of upper bounds for the problem (OPGE) is the nonincreasing sequence, that is, θk+1≤θk for all k=0,1,2,…Now, the outer approximation algorithm for solving(OPGE) is stated as follows.Algorithm 2 (Outer approximation algorithm).
Initialization Step
ConstructB0=[ym,yM], where ym and yM are described in Section 2.1. Choose ɛ>0 (ɛ>0 is a sufficient small number). Set V0={ym} and θ0:=Numlarge (Numlarge is a sufficient large number. This number can be viewed as an initialization the upper bound). Set k=0 and go to Iteration step k.
Iteration Stepk [k=0,1,2,…]. See Steps k.1 through k.5 below.k.1
Determine the optimal solution setTkopt:=Argmin{h(y)|y∈Vk}. Choose an arbitrary yk∈Tkopt and set βk:=h(yk) (currently best lower bound).k.2
Lety¯=yk. Find the optimal value λ* to the problem (T(y¯)). And set ωk=y¯+λ*(yM-y¯)∈GE.k.3
(Update the upper bound)Ifh(ωk)<θkThenθk=h(ωk) (currently best upper bound)andybest=ωk (currently best feasible point).k.4
If  θk-βk≤ɛThen Terminate the algorithm: ybest is an ɛ-optimal solutionElse Set Bk+1:=Bk∖[v,yw] where v:=yk and yω=ωkand determine the setVk+1 by formula (2.18).k.5
Setθk+1:=θk; k:=k+1 and go to iteration step k.Theorem 3.6.
The algorithm terminates after finitely many steps and yields anɛ-optimal solution to problem (OPGE).Proof.
Letɛ be a given positive number. Since the function h(y) is uniformly continuous on the compact set B0, we can choose an enough small number δ>0 such that if y,y′∈B0 and ∥y-y′∥<δ, then |h(y)-h(y′)|<ɛ. Then, to prove the termination of the algorithm, we need to show only that
(3.8)lim⁡k→∞‖wk-yk‖=0.
Observe first that the positive series∑k=1∞Vol[yk,wk] is convergent, since the open boxes int[yk,wk] are disjoint, and all of them are contained in the closure of B0∖G. It follows that(3.9)lim⁡k→∞Vol[yk,wk]=0.
Now, by the construction of wk and yk, we have
(3.10)wk-yk=λk(yM-yk),(3.11)Vol[yk,wk]=λkpVol[yk,yM],
for λk∈(0,1). Note that all of the points yk are contained in the set B0∖G. Furthermore, by the choice of yM (see (2.4)), the closure of B0∖G is a compact subset of the interior of the cone yM-ℝ+p. This observation implies that Vol[yk,yM] has a lower bound far from zero. Combining this fact, (3.9) and (3.11) imply that limk→∞λk=0. Also, the observation implies that ∥yM-yk∥ is bounded. Finally, by (3.10), we have limk→∞∥wk-yk∥=0.


## 3.2. Computational Results

First, the Algorithm2 has been applied for solving the test example given by Benson in [14] (see the example in Section 2.3)(3.12)min⁡{f1(x)f2(x)∣g1(x)≤0,g2(x)≤0},
where f1(x)=(x1-2)2+1, f2(x)=(x2-4)2+1, and g1(x)=25x12+4x22-100, g2(x)=x1+2x2-4.The calculation process for solving this example is described as follows.Initialization.
Similarly, the example in Section2.3, we have B0=[ym,yM] with ym=(1.00000,2.380437), and yM=(110.000000,110.000000). We choose ɛ=0.025 and set V0={ym=(1.00000,2.380437)}, θ0=10000 (the initialization upper bound), k=0 and go to iteration step k=0.Iteration (k=0).
Step 1.
We haveT0opt:=argmin{h(y)|y∈V0}={ym}. Choose y0:=ym∈T0opt, and set β0:=h(y0)=2.380437 (currently best lower bound).Step 2.
Lety¯=y0. Solving the problem (T(y¯)), we obtain the optimal solution (x*,λ*)=(0.230078,1.884961,0.028740)) and the optimal value λ*=0.028740. Then, w0=y¯+λ*(yM-y¯)=(4.132625,5.473389)∈GE.Step 3.
Sinceh(w0)=22.619464<θ0, we have θ0=h(w0)=22.619464 (currently best upper bound), and ybest=w0 (currently best feasible point).Step 4.
Sinceθ0-β0=20.239027>ɛ, we set B1:=B0∖[v,yw], where v:=y0, yw=w0 and determine the set
(3.13)V1={(1.000000,5.473389),(4.132625,2.380437)}.Step 5.
Setθ1:=θ0=22.619464;k:=0+1=1, and go to iteration step k=1.Iteration (k=1).
Step 1.
We haveT1opt:=argmin{h(y)|y∈V1}={y1=(1.000000,5.473389)}. Choose y1∈T1opt and set β1:=h(y1)=5.473389 (the currently lower bound).Step 2.
Lety¯=y1. The convex programming (T(y¯)) has the optimal solution (x*,λ*)=(0.82011,1.589942,0.012772)), and the optimal value λ*=0.012772. Then, we have w1=(2.392125,6.808381)∈GE.Step 3.
Sinceh(w1)=16.286498<θ1, we set θ1=h(w1) (the currently best upper bound), and ybest=w1 (the currently best feasible point).Step 4.
Now,θ1-β1=10.813109>ɛ. Therefore, B2:=B1∖[v,yw], where v:=y1,yw=w1, and V2={(4.132625,2.380437),(1.000000,6.808381),(2.392125,5.473389)}.Step 5.
Setθ2=θ1=16.286498;k:=1+1=2, and go to iteration step k=2.Iteration (k=2).
Step 1.
We haveT2opt=argmin{h(y)|y∈V2}={y2=(1.000000,6.808381)}, choose y2:=(1.000000,6.808381)∈T2opt, and set β2:=h(y2)=6.808381.Step 2.
Lety¯=y2. The problem (T(y¯)) has the optimal solution (x*,λ*)=(1.117142,1.441429,0.007151)), and the optimal value λ*=0.007151. Then w2=(1.779439,7.546285)∈GE.Step 3.
Sinceh(w2)=13.428154<θ2, the currently best upper bound θ2:=h(w2) and the currently best feasible point ybest=w2=(1.779439,7.546285).Step 4.
Sinceθ2-β2=6.619773>ɛ, we set B3:=B2∖[v,yw],  where v:=y2, yw=w2, and determine the set V3={(4.132625,2.380437),(2.392125,5.473389),(1.000000,7.546285),(1.779439,6.808381)}.Step 5.
Setθ3:=θ2=13.428154,k:=2+1=3, and go to iteration step k=3.After 42 iterations, the algorithm terminates withθ42=9.770252094 and β42=9.745596873, where θ42=h(w20). Then, the ɛ-optimal solution for the problem (OPY) and for the problem (CPX) are given by (3.14)y*=ybest=w20=(1.023846379,9.542693410),
and x*=(1.845577271,1.077211364). The approximate optimal value of problem (3.12) is 9.770252094.Below, we present the results of computational experiment for two types of problem. We takeɛ=0.025 in the numerical experiments. We tested our algorithm for each problem with random data for several times. Then, we took results in average. Numerical results are summarized in Tables 1 and 2.Table 1
Computational results on the problem of Type 1.
Problem no.pmnAverage number of iterationsAverage CPU time (sec)131010110.832320209.92.0833305019.219.443406017.524.42536010026.2109.664202023.14.374203014.14.8784305026.22094406059.661.641046010036.6142.32Table 2
Computational results on the problem of Type 2.
Problem no.pmnAverage number of iterationsAverage CPU time (sec)132020145.1823203026.914.643330504051.3543406042.677.38536010059.5316.7964202034.87.5774203089.835.2784305080.786.8394406078.4112.231046010085.5372.59Type 1.
(3.15)min⁡∏j=1pfj(x),s.t.Ax≤b,x≥0,
where fj(x)=〈αj,x〉+μj, αj∈ℝn, μj∈ℝ,j=1,…,p, A is an (m×n)-matrix, and b∈ℝm.Type 2.
(3.16)min⁡∏j=1pfj(x),s.t.Ax≤b,x≥0,
where fj(x)=(α1jx1+β1j)2+⋯+(αnjxn+βnj)2+νj, with αj,βj∈ℝn, νj∈ℝ, j=1,…,p, A is an (m×n)-matrix, and b∈ℝm.
Our program was coded in Matlab R2007a and was executed on our own PC with the configuration, CPU Intel Core 2 T5300 1.73 GHz, 1 G Ram. On the two above problems, the parameters are defined as follows:
(i)
A=(aij)∈ℝm×n is a randomly generated matrix with elements in [-1,1];(ii)
b=(b1,…,bm)T is a random vector satisfying the formula
(3.17)bi=∑j=1naij+b0iwithb0i being a random number in [0,2] for i=1,…,m;(iii)
αj=(α1j,…,αnj) and βj=(β1j,…,βnj), j=1,…,p are vectors with elements randomly distributed on [0,1];(iv)
the coefficientsμj, νj, j=1,…,p are uniformly distributed on [0,1].


## 4. Conclusion

In this paper, we have presented Algorithm1 for generating a finite set YEout of efficient outcome points for the convex multiobjective programming problem (VPX). The number of such points depends on the requirement of the decision makers. When the selected number is large enough, the convex set conv(YEout+ℝ+p), where conv(YEout+ℝ+p) is convex hull of the set (YEout+ℝ+p), may be viewed as an inner approximation of G0=Y+ℝ+p and the efficient set (conv(YEout+ℝ+p))E may be viewed as an inner approximation of the efficient outcome set YEimage for the problem (VPX). For each efficient outcome point yw∈YEimage to be generated by a given y¯∈B0∖G, the algorithm calls for solving a convex programming problem with linear objective function (T(y¯)). Note that by solving problem (T(y¯)), we also obtain the efficient solution x* associated with yw, where (x*,λ*) is the optimal solution for the problem (T(y¯)).In [7], Ehrgott et al. have proposed an outer approximation algorithm for representing an inner approximation of G0. This algorithm is the combination of an extension of Benson's outer approximation algorithm [1] for multiobjective linear programming problems and linearization technique. In each iteration step of these algorithms, a polyhedron is obtained from the previous one by adding a new hyperplane to it. The vertices of the new polyhedron can be calculated from those of the previous polyhedron by some available global optimization methods. Unlike those algorithms, our algorithm constructs a reverse polyblock at each iteration step from the previous one by cutting out a box, and its vertices can be easily determined by the formula (2.18).As an application, we have proposed the outer approximation algorithm (Algorithm2) for solving the convex multiplicative programming problem (CPX) associated with the problem (VPX) in outcome space. Since the number of terms p in the objective function of problem (VPX) is, in practice, often much smaller than the number of variables n, we hope that the algorithms help to reduce considerably the size of the problems.



---

*Source: 464832-2011-08-07.xml*