A monotonic optimization approach for solving strictly quasiconvex multiobjective programming problems

Abstract

In this article, we use a monotonic optimization approach to propose an outcome-space outer approximation by copolyblocks for solving strictly quasiconvex multiobjective programming problems which include many classes of captivating problems, for example when the criterion functions are nonlinear fractional. After the algorithm is terminated, with any given tolerance, an approximation of the weakly efficient solution set is obtained containing the whole weakly efficient solution set of the problem. The algorithm is proved to be convergent and it is suitable to be implemented in parallel using convex programming tools. Some computational experiments are reported to show the accuracy and efficiency of the algorithm.

Keywords

Multiobjective programming monotonic optimization strictly quasiconvex outcome space outer approximation

1 Introduction

Solving a multiobjective programming problem (MOP) is to optimize simultaneously many objectives over a solution set in a decision space. Instead of finding optimal solutions, we find efficient solutions where the value of any objective cannot be improved without degrading other objectives. Solving (MOP) is commonly understood as determining a part of or the entire efficient solution set. There are many proposed work for solving problem (MOP) in the linear or convex case when both the criterion function and the constraint set are linear or convex responsively (see the survey [23] and references therein).

For convex multiobjective programming problems, the algorithms are established based on the convexity for approximating the value set, i.e. the image of the constraint set, by the polyhedron, then approximating the efficient value set by the efficient set of polyhedrons. However, in many application fields such as economy, finance or technology, the criterion functions are nonconvex in practice. For instance, they are the indicators which are presented by ratios or fractional functions, such as the ratios of output to input, return to risk, profit to cost, or the rate of growth... (see [5 , 22]). These functions are the special cases of quasiconvex functions. Without the convexity, solving nonconvex multiobjective programming problems in general and particularly quasiconvex multiobjective programming problems with quasiconvex criterion functions and convex constraint sets, is a difficult task.

There are some algorithms for determining a part of efficient solution set or a finite number of efficient solutions, such as [5 , 16],... These methods do not guarantee to consider all efficient solutions, then miss some solutions when making decisions. By using the concepts of approximate ɛ-efficient solutions, there are some methods recently for approximating entire efficient solution set of nonconvex multiobjective programming problems such as [8, 13]. By the same approach, we also propose an algorithm for determining an approximated set of the entire efficient solution set of quasiconvex multiobjective programming problems.

Several authors have studied the structure of the efficient value set of quasiconvex multiobjective programming problems (see [2 , 18]). Although the efficient value set are nonconvex, its equivalently efficient set has some nice property that is a conormal set. By the monotonic analysis, a conormal set can be approximated enough closely by a copolyblock (see Section 2.2). Therefore, we establish an algorithm for outer approximating the equivalently efficient set as well as its weakly efficient set. After the algorithm is terminated, we obtain we obtain the outer and inner approximation of the weakly efficient value set.

The main distinction between our and previous methods are the way to establish the algorithm based on the concepts of monotonic optimization. Moreover, the proposed algorithms can be implemented easily by using software packages for solving convex programming problems and is suitable to parallelize. More importantly, an approximation of the efficient solution set with an arbitrary tolerance is also obtained and it also contains the whole efficient solution set. The convergent proof of the main algorithm is the important contribution of this paper.

The paper content is summarized as follows. The theoretical bases and algorithms to generate a nondominated outcome point and a weakly efficient solution of problem (QVP) is presented in the next section. We also present the cutting cones and outer approximate outcome sets to establish the outer approximation algorithm for solving (QVP) in Section 3. The convergent proof of the algorithms is presented in the fourth section, and the last provides the computational experiment. Some remarks and the future work are concluded is the last section.

2 Theoretical preliminaries

The strictly quasiconvex multiobjective programming problem is stated as follows $\begin{matrix} V \min f (x) (QVP) \\ s . t . x \in S, \end{matrix}$ where the feasible solution set $S \subset R^{n}$ , $n \in ℕ^{*}$ is a nonempty, convex, compact set and the criterion function $f : ℝ^{n} \to ℝ^{p}$ , $2 ⩽ p \in ℕ^{*}$ is a strictly quasiconvex vector function on $S$ , i.e. f_i, i = 1, . . . , p are strictly quasiconvex functions on $S$ (see [1 , 14]). It is easily seen that if f is convex, i.e. its component functions are convex, then f is strictly quasiconvex. Therefore, a convex multiobjective programming problem is a special case of (QVP).

For two vectors $a, b \in ℝ^{r}$ with some integer r ⩾ 2, we denote a ⩽ b if a_i ⩽ b_i for all i = 1, . . . , r. We also write a < b when a_i < b_i for all i = 1, . . . , r. Let a feasible solution $\bar{x}$ satisfy that there is no solution $x \in S$ such that $f (x) ⩽ f (\bar{x})$ and $f (\bar{x}) \neq f (x)$ (resp., $f (x) < f (\bar{x})$ ). Then $\bar{x}$ is said to be an efficient solution (resp., weakly efficient solution, abbreviated as w.e.s.) of (QVP).

Given a vector $ɛ \in ℝ_{+}^{p}$ , $\bar{x}$ is said to be a weakly ɛ-efficient solution of (QVP) if there is no solution $x \in S$ such that $f (\bar{x}) - ɛ > f (x)$ . The sets of all efficient solutions, weakly efficient and weakly ɛ-efficient solutions of (QVP) are respectively denoted by $S_{E}$ and $S_{WE}$ and $S_{ɛ}$ .

Denote the positive orthant of $ℝ^{p}$ by $ℝ_{+}^{p}$ and its interior by $i nt ℝ_{+}^{p}$ . Let $Q \subset ℝ^{p}$ be a nonempty set. The sets MinQ, WMinQ and Q_ɛ contain nondominated points, weakly nondominated points and weakly ɛ-nondominated points of Q, respectively. Namely, $M inQ = {q^{0} \in Q | (q^{0} - ℝ_{+}^{p}) \cap Q = {q^{0}}},$ $W MinQ = {q^{0} \in Q | (q^{0} - i nt ℝ_{+}^{p}) \cap Q = \emptyset},$ $Q_{ɛ} = {q^{0} \in Q | (q^{0} - ɛ - i nt ℝ_{+}^{p}) \cap Q = \emptyset} .$

We denote $Y : = f (S) = {y \in R^{p} | \exists x \in R^{n}, f (x) = y}$ the outcome set or the value set of problem (QVP). With above notations, the sets $M in Y, W Min Y$ and $Y_{ɛ}$ are the efficient, weakly efficient and weakly ɛ-efficient outcome sets of (QVP), respectively. They also respectively are the images of $S_{E}, S_{WE}$ and $S_{ɛ}$ under function f.

2.1 Generating a nondominated outcome point and a w.e.s. of (QVP)

Since the objective function $S_{ɛ}$ is continuous and $S$ is bounded, the outcome set $Y$ is also bounded. Now we determine a box containing $ES \subseteq S_{ɛ}$ .

By the compactness of $Y$ , for each i = 1, . . . , p, the problems of minimizing and maximizing $S_{WE} \subseteq ES \subseteq S_{ɛ}$ on the feasible set $Y$ have optimal solutions. It is easy to transform these problems into $min {f_{i} (x) | x \in S}, (P_{i}^{m})$ and the problem $max {f_{i} (x) | x \in S} . (P_{i}^{M})$

To solve problem $(P_{i}^{m})$ , we utilize the strictly quasiconvexity of the criterion function associated with the following remark.

Remark 2.1 Any solution x optimizes locally a strictly quasiconvex programming problem (Q). Then x also optimizes globally problem (Q) [15]. Therefore, (Q) can be solved by using suitable algorithms for convex programming problems [4].

By Remark 2.1, problem $(P_{i}^{m})$ can be easily solved using convex programming tools. Although $(P_{i}^{M})$ is a nonconvex problem, it is possible to find an upper bound of this problem without having to solve ((see [3] for details and illustration). Namely, for each j = 1, . . . , n, set $α_{j} = min {x_{j} | x \in S}$ . Let α⁰ = (α₁, α₂, . . . , α_n) and $U = max {〈 e, x 〉 | x \in S}$ , where e is the vector of ones. Because $S$ is a compact set, U is a finite number. Notice also that convex programming tools are applicable to find α⁰ and U. For each j = 1, 2, . . . , n, define $α^{j} = (α_{1}^{j}, α_{2}^{j}, . . ., α_{n}^{j})^{T}$ by $α_{k}^{j} = {\begin{matrix} α_{k}^{0}, & if k \neq j \\ U - \sum_{kj} α_{k}^{0}, & if k = j \end{matrix}$

Let Δ be a simplex with the vertex set V (Δ) = {α⁰, α¹, . . . , αⁿ}. It can be verified that $S \subseteq Δ$ (see Fig. 1). Therefore, $max {f_{i} (x) | x \in S} ⩽ max {f_{i} (x) | x \in Δ}$ . Since f_i (x) , i = 1, . . . , p, are quasi-convex and Δ is a simplex, we have max {f_i (x) |x ∈ Δ} = max {f_i (x) |x ∈ V (Δ)}.

Fig. 1

A 2D example of $S$ and a simplex containing it.

For each i = 1, . . . , p, choose a real number M_i such that M_i = max {f_i (x) |x ∈ V (Δ)}. Then $M_{i} ⩾ max {f_{i} (x) | x \in S}$ .

Denote the optimal value of problem $(P_{i}^{m})$ by m_i, for i = 1, . . . , p. Let m = (m₁, m₂, . . . , m_p) and M = (M₁, M₂, . . . , M_p). Then we get the box [m, M] such that $Y \subseteq [m, M]$ . The point m is also known as the ideal point of the outcome set. If $m \in Y$ , the set $M in Y$ consists of this point only. From now on, we assume that $m Y$ .

Let $P^{0} = [m, M] = (m + R_{+}^{p}) \cap (M - R_{+}^{p});$ $Y^{+} = Y + R_{+}^{p};$ $Y^{♦} = Y^{+} \cap (M - R_{+}^{p})$ . It is obvious that $Y^{+}$ and $Y^{♦}$ have interior points and $Y^{♦} \subset P^{0}$ . The following evident properties of $Y^{+}$ and $Y^{♦}$ will be used in the sequel.

Proposition 2.1 [3] We have

$M in Y = M in Y^{+} = M in Y^{♦}$ ;

$W Min Y = W Min Y^{+} \cap Y = W Min Y^{♦} \cap Y$ .

Let $\hat{d} \in i nt ℝ_{+}^{p}$ , i.e. $\hat{d} > 0$ be a fixed vector and choose an arbitrary point $v \in ℝ^{p}$ . We denote $ℓ (v) = {v + t \hat{d} | t \in ℝ}$ to be the line through v with direction $\hat{d}$ . The intersection of ℓ (v) and the boundary of $Y^{+}$ is determined by $w_{v} = v + t_{v} \hat{d},$ (1) where t_v is the optimal solution of the problem $min t (P^{0} (v))$ $s . t . v + t \hat{d} \in Y^{+}, t \in ℝ .$

The following assertion shows the way to determine a weakly nondominated outcome point.

Lemma 2.1.[14] Letvbe an arbitrary point in $ℝ^{p}$ . Then there exists the unique pointw_vdetermined by Equation (1) and it is a weakly nondominated point of $Y^{+}$ .

The explicit form of (P⁰ (v)) is as follows $\begin{matrix} min t (P^{1} (v)) \\ s . t . f (x) - t \hat{d} - v ⩽ 0, \\ x \in S, t \in R . \end{matrix}$

This problem is nonconvex in general. Therefore, it is difficult to determine a weakly nondominated outcome point as well as a w.e.s. of (QVP). However, we can transform problem (P⁰ (v)) into the form $min max {\frac{f_{j} (x) - v_{j}}{{\hat{d}}_{j}} | j = 1, . . ., p} (P^{2} (v))$ $s . t . x \in S .$

It is worthy to note that the criterion function (P² (v)) can be viewed as a weighted Chebyshev function of which weights are $\frac{1}{{\hat{d}}_{j}}$ (see [9]). The following lemma shows that (P² (v)) is equivalent to (P⁰ (v)) and it is a problem of minimizing a strictly quasiconvex function over a convex set.

Lemma 2.2.Problems (P⁰ (v)) and (P² (v)) are equivalent, i.e. if (x^*, t^*) is minimal of (P⁰ (v)) thenx^*is minimal of (P² (v)); conversely, ifx^*is minimal andt^*is the minimal value of (P² (v)) then (x^*, t^*) is minimal of (P⁰ (v)). Moreover, (P² (v)) is a strictly quasiconvex programming problem.

The next theorem is crucial for the method to generate a nondominated outcome point and a weakly efficient solution of (QVP).

Theorem 2.3.For any point $v \in ℝ^{p}$ , letx_vbe minimal andt_vbe the respected value of (P² (v)). Then, $w_{v} = v + t_{v} \hat{d}$ is a weakly nondominated point of $Y^{+}$ andx_vis a w.e.s. of (QVP).

Proof. According to Lemma 2.2, (x_v, t_v) is also the optimal solution of (P⁰ (v)). By Lemma 2.1, we conclude that $w_{v} \in W Min Y^{+}$ . The feasible domain of (P¹ (v)) suggests that x_v satisfies $f (x_{v}) ⩽ v + t_{v} \hat{d} = w_{v}$ . Thus, $f (x_{v}) - int ℝ_{+}^{p} \subseteq w_{v} - int ℝ_{+}^{p}$ so that $(f (x_{v}) - int R_{+}^{p}) \cap Y^{+} = \emptyset$ . Since $f (x_{v}) \in W Min Y^{+}$ , ɛ = 0.1, 0.05, 0.02, 0.01 is therefore a w.e.s. of the problem (QVP). Similar result to Theorem 2.3 in different descriptions can be found in [7, 13].

Remark 2.2. From Lemma 2.2, problem (P² (v)) is a strictly quasiconvex programming problem. Therefore, by Remark 2.1, solving (P² (v)) is implemented by using some algorithms for convex programming problems.

The following corollary presents the way to verify the weakly efficient condition of any point in the decision space.

Corollary 2.1.The point $x^{*} \in ℝ^{n}$ is a weakly efficient solution of (QVP) if and only if (P² (f (x^*)) has the optimal valuet^* = 0.

Proof. Let v^* = f (x^*) ∈ R^p. If t^* = 0 is the optimal value of (P² (v^*)), using the equivalence in Lemma 2.2, and from Lemma 2.1, we have $w^{*} = v^{*} + t^{*} \hat{d} \equiv v^{*} = f (x^{*}) \in W Min Y^{+}$ . Hence, $x^{*} \in S_{WE}$ . Conversely, suppose that x^* is a w.e.s. of (QVP). Then $v^{*} = f (x^{*}) \in \partial Y^{+}$ . It is obvious that for t < 0 we have $v^{*} + t \hat{d} \notin Y^{+}$ and t^* = 0 is the smallest value of t which satisfies the feasible condition of (P⁰ (v)).

Procedure 1 shows the way to generate a w.e.s. of (QVP) from a point $v \in ℝ^{p}$ . Due to Corollary 2.1, an arbitrary point $x \in ℝ^{n}$ can be verified to be a w.e.s. of (QVP) by Procedure 2.

2.2 The cutting cones and outer approximate outcome sets

For convenience, we first recall some concepts of monotonic optimization which have been developed in [19] and [20]. Consider a set $Q \subset ℝ^{p}$ contained in box [m, M]. The set Q is called normal if [m, y] ⊂ Q for all y ∈ Q, and is called conormal if [y, M] ⊂ Q for all y ∈ Q. Throughout this paper, we only consider the concepts related to conormal sets.

The conormal hull of Q denoted by $N (Q)$ is the intersection of all conormal sets which contains the set Q. The conormal hull of a point set V ⊂ [m, M] is said to be copolyblockP, with vertex set V, i.e. P = ⋃ _d∈V [d, M] or $P = N (V)$ . A vertex d ∈ P is called improper if there exists some vertex d′ ∈ P satisfying d′ ≠ d and d′ ⩽ d. The points of P except from improper points are proper vertices. Then, a copolyblock is represented by its proper vertices, i.e. the conormal hull of its proper vertex set.

The following propositions recall main properties of copolyblocks and will be used in the sequel.

Proposition 2.2. [19] Any compact conormal set is the intersection of a family of copolyblocks.

It is easily seen that the outcome set $Y^{♦}$ is compact conormal in the box [m, M]. Let a point v ∈ [m, M] and $v \notin Y$ . Then, by Lemma 2.1, the point w_v determined by Equation (1) is a weakly nondominated point of $Y^{♦}$ and $w_{v} \in \partial Y^{♦}$ . Moreover, since $\hat{d} > 0$ , we have w_v > v. By Proposition 2.3 in [21], the cone $C (w_{v}) : = w_{v} - R_{+}^{p}$ separates v strictly from $Y^{♦}$ . We refer to the cone $C (w_{v})$ as the cutting cone of $Y^{♦}$ atw_v.

Proposition 2.3.[20] LetPbe a copolyblock in the box [m, M] with proper vertex setVsuch that $Y^{♦} \subseteq P$ . For a given $v \in [m, M] ∖ Y^{♦}$ andw_vdetermined by Equation (1), new copolyblockP′ obtained by applying the cutting cone of $Y^{♦}$ atw_vhas vertex setV′, where $V^{'} = (V ∖ {v}) \cup {v - (w_{i} - v_{i}) e^{i}}, i = 1, . . ., p .$

By Proposition 2.2, we can approximate any compact conormal set by a copolyblock as closely as desired, similarly to approximating a compact convex set by a polytope. Therefore, the compact conormal set $Y^{♦}$ can be approximated by a family of copolyblocks. Specifically, a nested sequence of copolyblocks is generated that outer-approximates the outcome set $Y^{♦}$ , i.e. $P^{0} \supset P^{1} \supset . . . \supset P^{k} \supset P^{k + 1} \supset . . . \supset Y^{♦},$ where the initial copolyblock $P^{0} = [m, M]$ as constructed in Section 2.1. The copolyblock P^k+1 is generated from P^k by applying the cutting cone procedure in Proposition 2.3. The copolyblocks $P^{k}$ are said to be the approximate outcome sets. From these outer approximate sets, we shall establish an outer approximation algorithm for solving (QVP).

3 The algorithm for solving (QVP)

By the outcome space approach, the solution set of| is achieved by determining an approximation set contained in $Y_{ɛ}^{♦}$ . Firstly, we find the set of weakly nondominated points $Y_{WN}$ and the set of the outer approximation vertices V_ɛ. Then we can determine the inner and outer approximation set $L$ and $U$ of $Y^{♦}$ . We propose an outer approximation algorithm to determine weakly nondominated points of the outcome set $Y$ . Starting from the copolyblock $P^{0} = [m, M]$ , we iteratively construct a sequence of copolyblocks ${P^{k}}$ such that $P^{0} \supset P^{1} \supset . . . \supset P^{k} \supset P^{k + 1} \supset . . . \supset Y^{♦} .$

We will make use of the following notations:

V^k is the proper vertex set which determines $P^{k}$ ;

V_ɛ is a collection of outer approximate weakly nondominated points;

$Y_{WN}$ is a collection of weakly efficient values.

At the initial step with k = 0, we have V⁰ = {m}, V_ɛ =∅ and $Y_{WN} = \emptyset$ . In a typical iteration k, if every vertex in V^k is an outer approximate weakly nondominated point, the algorithm terminates. Otherwise, there is some v^k ∈ V^k ∖ V_ɛ. In this case, by solving (P² (v^k)), we find a new weakly efficient value f (x^k) of (QVP) and add it into the set $Y_{WN}$ . We also obtain a weakly nondominated point $w^{k} = v^{k} + t_{k} \hat{d}$ of $Y^{+}$ , where (x^k, t_k) is the optimal solution of (P (v^k)). If v^k is close enough to w^k, v^k is an outer approximate weakly nondominated point and is added to V_ɛ. Otherwise, a new approximation $P^{k + 1}$ is determined by applying the cutting cone procedure in Proposition 2.3. As proved later, for sufficiently large k, all vertices of $P^{k}$ are close enough to $Y^{♦}$ and the algorithm terminates. This algorithm is described in Algorithm Solve(QVP) and Procedure RIV(V^k+1, v^k, w^k) as follows.

Suppose the algorithm is terminated at Iteration K. Then, we obtain two sets $Y_{WN}$ and V_ɛ. From these sets, we define $L : = N (Y_{WN})$ and $U : = N (V_{ɛ}) \equiv P^{K}$ . It can be verified that $L$ and $U$ are inner and outer approximation of $Y^{♦}$ respectively, and their weakly nondominated sets are approximate weakly nondominated sets of $Y^{♦}$ . Based on the outer approximation $U$ , we can establish the outer approximation ES of the w.e.s. set $S_{WE}$ of problem (QVP), that is $ES : = ⋃_{y \in U_{ɛ} \cap Y^{♦}} {x \in S | f (x) ⩽ y}$ .

By Corollary 4.7 in the following section, it is proved that ES contains the weakly ɛ-efficient solution of (QVP) and also contains the whole w.e.s. set of this problem.

4 The convergent proof of the algorithm

Recall that Hausdorff distance between two closed sets $Q_{1}, Q_{2} \subset ℝ^{p}$ define as follows $\begin{matrix} {dis}_{H} (Q_{1}, Q_{2}) \\ = \inf {t > 0 : Q_{1} \subseteq Q_{2} + {tU}_{p}, Q_{2} \subseteq Q_{1} + {tU}_{p}} \\ = \max {\sup_{v_{1} \in Q_{1}} dis (v_{1}, Q_{2}), \sup_{v_{2} \in Q_{2}} dis (v_{2}, Q_{1})}, \end{matrix}$ where U_p is the closed ball of radius 1 in $ℝ^{p}$ and the distance from v to a set $Q \subset ℝ^{p}$ is defined by $dis (v, Q) = \inf_{y \in Q} | | v - y | |$ . We say that ${Q_{h}}_{h = 1}^{\infty} \subseteq ℝ^{p}$ converges to Q if lim_h→∞dis_H (Q_h, Q) =0 and write lim_h→∞Q_h = Q.

Lemma 4.1.For each $v \in P^{0} \ Y^{♦}$ , we have $dis (v, Y^{♦}) = dis (v, Y^{+})$ .

Proof. The distance between a point $v \in P^{0} \ Y^{♦}$ and $Y^{+}$ is $dis (v, Y^{+}) = min {dis (v, y) | y \in Y^{+}} = min {dis (v, y) | y ⩽ f (x), x \in S}$ .

Because $S$ is compact, an optimal solution of the above minimization problem always exists. In other words, the distance between v and $Y^{+}$ is finite, and therefore there exists a closed ball V_r (v) of radius r > 0 centered at v satisfying

$\begin{matrix} min_{y \in Y^{+}} dis (v, y) = min_{y \in Y^{+} \cap V_{r} (v)} dis (v, y) \\ \Leftrightarrow dis (v, Y^{+}) = dis (v, Y^{+} \cap V_{r} (v)) . \end{matrix}$ (2)

Let Q be a compact conormal set which does not contain v, and z^* be the projection of v onto Q. Then, there exists a closed ball V_||z^*-v|| (v) centered at v having z^* a boundary point.

Suppose that $z^{*} \notin v + ℝ_{+}^{p}$ , then there exists a point $\tilde{z} \neq z^{*}, \tilde{z} \notin z^{*} + ℝ_{+}^{p}$ satisfying $\tilde{z} \in V_{| | z^{*} - v | |} (v)$ . Since Q is a conormal set, $\tilde{z} \in Q$ . This contradicts the assumption of z^* because $dis (v, \tilde{z}) < dis (v, z^{*})$ . Thus, $z^{*} \in v + ℝ_{+}^{p} .$ (3)

Now for each $y^{'} \in (v + ℝ_{+}^{p}) \cap Q$ , let V_||v-y′|| (v) be the closed ball centered at v having a boundary point y′. Since $y^{'} \in v + ℝ_{+}^{P}$ , it is clear that $((y^{'} + ℝ_{+}^{p}) ∖ y^{'}) \cap V_{| | v - y^{'} | |} (v) = \emptyset$ . Thus, $dis (v, y) > dis (v, y^{'}), \forall y \in y^{'} + ℝ_{+}^{p}$ . Therefore, dis (v, y) is a continuous, increasing function of variable y on $(v + ℝ_{+}^{p}) \cap Q$ . From [19], its global minimum is achieved at a nondominated point of the domain. We now apply this argument twice, with Q replaced by $Y^{♦}$ and $Y^{+} \cap V_{r} (v)$ . It is worth noting from Proposition 2.1 that $M in Y^{◊} \subseteq W Min Y^{◊} \cap Y$ and $M in Y^{+} \subseteq W Min Y^{+} \cap Y$ . Combining these facts with Equations (2) and (3), we deduce that the projection of v on $Y^{♦}$ must be the optimal solution of min dis (v, y) subject to $y \in W Min Y^{♦} \cap Y \cap (v + ℝ_{+}^{p})$ . Similarly, the projection of v on $Y^{+}$ must be the optimal solution of min dis (v, y) subject to $y \in W Min Y^{+} \cap Y \cap (v + ℝ_{+}^{p})$ . It is followed by Proposition 2.1(ii) that the feasible domains of the two problems are exactly the same. The proof is complete.

Lemma 4.2.At Iterationh^thof the algorithm, letw_vbe the weakly nondominated point obtained by solving (P² (v)) with somev ∈ V^h, then ${dis}_{H} (P^{h}, Y^{♦}) ⩽ max_{v \in V^{h}} | | w_{v} - v | |$ .

Proof. Since V^h contains all vertices of $P^{h}$ , it becomes clear that $max {dis (v, Y^{♦}) | v \in P^{h}} = max_{z \in V^{h}} {max {dis (v, Y^{♦}) | v \in (z + ℝ_{+}^{p}) \cap (M - ℝ_{+}^{p})}}$ . Because $dis (v, Y^{♦})$ is convex and the box $(z + ℝ_{+}^{p}) \cap (M - ℝ_{+}^{p})$ is convex, $max {dis (v, Y^{♦}) | v \in$ $(z + ℝ_{+}^{p}) \cap (M - ℝ_{+}^{p})} = dis (z, Y^{♦})$ . Therefore, ${dis}_{H} (P^{h}, Y^{♦}) = max_{v \in P^{h}} dis (v, Y^{♦}) = max_{v \in V^{h}} dis$ $(v, Y^{♦})$ . Since $w_{v} \in Y^{+}$ for all v ∈ V^h and from the result of Lemma 4.1, we infer that $max_{v \in V^{h}} dis (v, Y^{♦}) = max_{v \in V^{h}} dis (v, Y^{+})$ This completes the proof.□

Lemma 4.3.For each $v \in P^{0} ∖ Y^{♦}$ , there exists a pointM′ > Msuch that the weakly nondominated pointw_vof $Y^{+}$ obtained by solving (P² (v)) lies in box [m, M′].

Denote $N_{d} (Q) : = (Q + R_{+}^{p}) \cap (d - R_{+}^{p})$ the conormal hull of Q in the box [m, d] where Q is some set contained in the box [m, M]. Let us rewrite (P¹ (v)), the equivalent problem to (P² (v)) $\begin{matrix} min & t \\ s . t . & f (x) \in N_{v + t \hat{d}} (Y^{+}), \\ x \in S, t ⩾ 0 . \end{matrix}$

We denote t_m and t_v to be the optimal values of (P² (m)) and (P² (v)), respectively. The existence of these values has been proved in Lemma 2.1. Since m < v for all $v \in P^{0} ∖ Y^{♦}$ , the feasible domain of (P² (m)) is a subset of the feasible domain of (P² (v)) for any $v \in P^{0} ∖ Y^{♦}$ . Therefore, the relation t_v ⩽ t_m holds for such v. We can therefore write $w_{v} = v + t_{v} \hat{d} ⩽ v + t_{m} \hat{d} ⩽ M + t_{m} \hat{d} = M^{'}$ .

Moreover, it is obvious that m ⩽ v ⩽ w_v, which completes the proof.□

Lemma 4.4.Forɛ = 0 either of two following statements is true.

There exists a finite number h such that $max_{v \in V^{h}} | | w_{v} - v | | = 0;$

The number h tends to infinity and $lim_{h \to \infty} max_{v \in V^{h}} | | w_{v} - v | | = 0,$

whereV^his the proper vertex set determining

P^{h}

andw_vis corresponding weakly nondominated point of

Y^{+}

obtained by solving (P² (v)).

Proof. Let ${\hat{P}}^{0} = [m, M^{'}]$ , with $M^{'} = M + t_{m} \hat{d}$ . At the h^th iteration, we can also determine a copolyblock ${\hat{P}}^{h + 1}$ in box [m, M′] along with $P^{h + 1}$ . It is clear that $P^{h} \subseteq {\hat{P}}^{h}$ and ${\hat{P}}^{h + 1} \subseteq {\hat{P}}^{h}$ for any h ⩾ 0. From Lemma 4.3, $w_{v} \in {\hat{P}}^{h}$ , for each $v \in P^{h} ∖ Y^{♦}$ . Now consider $v^{h} \in P^{h}$ chosen at the h^th iteration and t_h the optimal values of (P² (v^h)). As before, let $w_{v^{h}} = v^{h} + t_{h} \hat{d}$ . We have $Vol [v^{h}, w_{v^{h}}] = (t_{h})^{p} Vol [0, \hat{d}] .$ (4)

The lemma holds if $max_{v \in V^{h}} | | w_{v} - v | | = 0$ at some h ⩾ 0. Otherwise, there exists v^h ∈ V^h such that $| | w_{v^{h}} - v^{h} | | = max_{v \in V^{h}} | | w_{v} - v | | > 0$ . We also have $P^{h + 1} \subseteq P^{h} ∖ (v^{h} - int R_{+}^{p})$ , noting that the equality holds when no improper vertex appears during the cut. Since $[v^{h}, w_{v^{h}}] \subseteq {\hat{P}}^{h}$ followed by the definition of w_{v
^h}, the volume of ${\hat{P}}^{h}$ satisfies $Vol {\hat{P}}^{h} - Vol {\hat{P}}^{h + 1} ⩾ Vol [v^{h}, w_{v^{h}}] .$ (5)

Combining Equation (5) with Equation (4), we obtain $Vol {\hat{P}}^{h} - Vol {\hat{P}}^{h + 1} ⩾ (t_{h})^{p} Vol [0, \hat{d}]$ . Therefore, it has $\sum_{i = 0}^{h} (Vol {\hat{P}}^{i} - Vol {\hat{P}}^{i + 1}) ⩾ (\sum_{i = 0}^{h} (t_{i})^{p}) Vol [0, \hat{d}]$ .

We deduce $\begin{matrix} Vol {\hat{P}}^{0} & ⩾ (\sum_{i = 0}^{h} (t_{i})^{p}) Vol [0, \hat{d}] + Vol {\hat{P}}^{h + 1} \\ ⩾ (\sum_{i = 0}^{h} (t_{i})^{p}) Vol [0, \hat{d}], \end{matrix}$ for all h ⩾ 1. Thus, by letting h→ ∞, the positive series $\sum_{i = 0}^{\infty} (t_{i})^{p}$ is upper bounded by $Vol {\hat{P}}^{0} / Vol [0, \hat{d}]$ , and therefore converges. Since $| | \hat{d} | |$ is bounded, for i ⩾ 1, we have $\begin{matrix} lim_{i \to \infty} max_{v \in V^{i}} | | w_{v} - v | | = lim_{i \to \infty} | | w_{v^{i}} - v^{i} | | \\ = lim_{i \to \infty} t_{i} | | \hat{d} | | = 0 . □ \end{matrix}$

Lemma 4.5.With anyɛ ⩾ 0, the sets $P^{h}$ withh ⩾ 0 satisfy $Y^{♦} \subseteq P^{h + 1} \subseteq P^{h}$ . Moreover, by settingɛ = 0, we have $\begin{matrix} Y^{♦} & = & lim_{h \to \infty} P^{h} & = & ⋂_{h ⩾ 1} P^{h}, \\ W Min Y^{♦} & = & lim_{h \to \infty} W Min P^{h} . \end{matrix}$ (6)

Proof. The proof falls naturally into three parts. From the formulation of $P^{h}, h ⩾ 0$ , the first part of the lemma is immediate. We deduce directly from Lemmas 4.2 and 4.4 that $\begin{matrix} lim_{h \to \infty} {dis}_{H} (P^{h}, Y^{♦}) \\ ⩽ lim_{h \to \infty} max_{v \in V^{h}} | | w_{v} - v | | = 0 . \end{matrix}$

Therefore, ${P^{h}}_{h ⩾ 0}$ converges to $Y^{♦}$ when h goes to infinity. Since $P^{h + 1} \subseteq P^{h}$ for any h ⩾ 0, it follows easily that $lim_{h \to \infty} P^{h} = ⋂_{h ⩾ 1} P^{h}$ . What is left is to prove the second equation of Equation (6). Let Q be a copolyblock in box [m, M], and recall the notation $Q^{+} = Q + R_{+}^{p}$ , we first prove $W MinQ = \partial Q^{+} \cap (M - R_{+}^{p}) .$ (7)

If $\bar{w} \in W MinQ$ then of course $\bar{w} \in (M - R_{+}^{P})$ . Since the cone $\bar{w} - i {ntR}_{+}^{p} ⊈ Q^{+}$ , it is clear that $\bar{w} \in \partial Q^{+}$ . This yields $W MinQ \subseteq \partial Q^{+} \cap (M - R_{+}^{p})$ . Conversely, if $\bar{w} \in \partial Q^{+} \cap (M - R_{+}^{p})$ . By the property of a copolyblock, $\bar{w} - i {ntR}_{+}^{p} ⊈ Q^{+}$ . This also means that $\bar{w}$ is a weakly nondominated point of Q⁺. Because $\bar{w} < M$ , we also have $\bar{w} \in W MinQ$ . Hence, Equation (7) is proved.

Applying Equation (7) on $Y^{♦}$ gives $W Min Y^{♦} = \partial Y^{+} \cap (M - R_{+}^{p}) .$ (8)

Let $\partial P^{h +}$ be the boundary set of $P^{h +} : = P^{h} + R_{+}^{p}$ . We now apply Equation (7) again, with $Y^{♦}$ replaced by $P^{h +}$ , to obtain $W Min P^{h} = \partial P^{h +} \cap (M - R_{+}^{p}) \subseteq P^{h} .$ (9)

Moreover, since $Y^{+} \subseteq P^{h +}$ , ${dis}_{H} (\partial P^{h +} \cap (M - R_{+}^{p})$ , $\begin{matrix} \partial Y^{+} \cap (M - R_{+}^{p})) = max {dis (v, \partial Y^{+} \cap (M - R_{+}^{p})) | \\ v \in \partial P^{h +} \cap (M - R_{+}^{p})} \end{matrix}$ . From Lemma 4.1, for each v inside the box [m, M] which does not belong to $Y^{♦}$ , we have $dis (v, Y^{♦}) = dis (v, Y^{+}) = dis (v, \partial Y^{+}) = dis (v, \partial Y^{+} \cap (M - R_{+}^{p}))$ . Thus, ${dis}_{H} (\partial P^{h +} \cap (M - R_{+}^{p}), \partial Y^{+} \cap (M - R_{+}^{p})) ⩽ max_{v \in V^{h}} dis (v, Y^{♦})$ . From Equation (7), Equation (9) and the first equation of Equation (6), it follows that $lim_{h \to \infty} W Min P^{h} = W Min Y^{♦}$ which is the desired conclusion.□

Consider the sets $Y_{WN}$ and V_ɛ obtained from the algorithm. Recall that $L = N (Y_{WN})$ and $U = N (V_{ɛ})$ . The following assertion shows that these sets are the inner and outer approximate sets of $Y^{♦}$ , respectively.

Theorem 4.6.Letɛ = ɛe, whereedenotes the vector of ones in $ℝ^{p}$ . We have the following properties:

$L \subseteq Y^{♦} \subseteq U$ ;

$W Min Y^{♦} \subseteq U_{ɛ} \cap Y^{♦} \subseteq Y_{ɛ}^{♦}$ ;

$W Min L \subseteq Y_{ɛ}^{♦}$ .

Proof. i) is straightforward.

We now prove ii). When the algorithm terminates at the H^th iteration, with a tolerance level ɛ, $U \equiv P^{H}$ is close enough to $Y^{♦}$ , namely $U \subseteq Y^{♦} + ɛ U_{p}$ . Let $y \in W Min Y^{♦}$ , it is necessary to prove $y \in U_{ɛ}$ . For this purpose, by definition of $U_{ɛ}$ , we need to show that $[(y - ɛ e) - int R_{+}^{p}] \cap U = \emptyset .$ (10)

Indeed, since $U \subseteq Y^{♦} + ɛ U_{p} \subseteq Y^{♦} - ɛ e + R_{+}^{p}$ , it is sufficient to see that the two sets in the left hand side of Equation (10) do not intersect. Moreover, if $y \in U_{ɛ} \cap Y^{♦}$ , obviously, (10) is now true. Because $Y^{♦} \subseteq P^{H}$ , $[(y - ɛ e) - int R_{+}^{p}] \cap Y^{♦} = \emptyset$ , concluding that $y \in Y_{ɛ}^{♦}$ .

The proof for iii) is similar.□

Theorem 4.7.Givenɛ > 0 andɛ = ɛe, after the limited iterations, Algorithm Solve(QVP) is terminated and generates the approximate solution setESsuch that $S_{WE} \subseteq ES \subseteq S_{ɛ}$ .

Proof. Since ɛ > 0, from Lemma 4.4, there exists H > 0 such that ||w_v - v|| ⩽ ɛ for all v ∈ V^H at which iteration the algorithm terminates. Moreover, the necessary and sufficient condition of a w.e.s. $x \in S_{WE}$ is that there exists some $y \in W Min Y^{♦}$ such that f (x) ⩽ y. Theorem 4.6(ii) enables us to write $\begin{matrix} S_{WE} & \subseteq ⋃_{y \in W Min Y^{♦}} {x \in S | f (x) ⩽ y} \\ \subseteq ⋃_{y \in U_{ɛ} \cap Y^{♦}} {x \in S | f (x) ⩽ y} = ES . \end{matrix}$

Moreover, from definition of $S_{ɛ}$ , we have $ES \subseteq S_{ɛ}$ , so $S_{WE} \subseteq ES \subseteq S_{ɛ}$ . This completes the proof.□

5 Computational experiments

This section is used to illustrate our proposed algorithm through several numerical examples. We also want to compare our results with other related works of [5].

Example 5.1. The following is a linear fractional programming problem $\begin{matrix} Vmin & f_{1} (x) & = & \frac{- x_{1}}{x_{1} + x_{2}}, \\ f_{2} (x) & = & \frac{3 x_{1} - 2 x_{2}}{x_{1} - x_{2} + 3} \\ s . t . & x_{1}, x_{2} \in R, \\ x_{1} - 2 x_{2} & ⩽ & 2, \\ - x_{1} - 2 x_{2} & ⩽ & - 2, \\ - x_{1} + x_{2} & ⩽ & 1, \\ x_{1} & ⩽ & 6 . \end{matrix}$

Since both objectives of this problem are a ratio of two linear functions, it is clearly a multiobjective strictly quasiconvex programming problem. Thus, we can use our algorithm to solve this problem. Let us demonstrate below the detailed computation for the case ɛ = 0.5.

We compute the results in other cases of ɛ and show them in Table 1, where T, V and C denote the average computation time, number of weakly efficient values (or the number of vertices in $L$ ) and number of vertices of the outer approximate copolyblock, respectively. The computational result is visualized in Fig. 2.

Table 1
Computational results in Example 5.1

ɛ T V C

0.1 1.894534 35 18

0.05 2.167836 67 34

0.025 2.644173 117 59

0.0125 4.124381 231 116

ɛ	T	V	C
0.1	1.894534	35	18
0.05	2.167836	67	34
0.025	2.644173	117	59
0.0125	4.124381	231	116

Fig. 2

The outer approximation $U$ of $Y^{♦}$ with different values of ɛ ∈ {0.1, 0.05} in Example 5.1.

Example 5.2. The following is a convex fractional minimization problem $\begin{matrix} Vmin & f_{1} (x) & = & \frac{x_{1} + 1}{- x_{1}^{2} + 3 x_{1} - x_{2}^{2} + 3 x_{2} + 3.50}, \\ f_{2} (x) & = & \frac{x_{1}^{2} - 2 x_{1} + x_{2}^{2} - 8 x_{2} + 20.00}{x_{2}} \\ s . t . & x_{1}, x_{2} \in R, \\ 2 x_{1} + x_{2} & ⩽ & 6, \\ 3 x_{1} + x_{2} & ⩽ & 8, \\ x_{1} - x_{2} & ⩽ & 1, \\ x_{1}, x_{2} & ⩾ & 1 . \end{matrix}$

Since both f₁ (x) and f₂ (x) are convex fractions and the feasible domain of this problem is a polyhedron, the above problem is a strictly quasiconvex multiobjective programming problem.

By choosing $ɛ = 0.1, \hat{d} = (1, 1)$ , the algorithm stops after 19 iterations. We obtain the V_ɛ set of 10 vertices of the approximate copolyblock and the $Y_{WN}$ set including 19 weakly nondominated points.

The computational results with other values of ɛ are presented in Table 2 with all notations having the same meaning as in Table 1. The computational results are illustrated in Fig. 3. Two green small circles in the figure are the nondominated outcome points as stated in [5] after running its algorithm twice with different initial conditions.

Table 2

Computational results in Example 5.2

ɛ	T	V	C
0.08	1.764705	25	13
0.04	2.156274	70	35
0.02	2.628011	110	55
0.01	3.529236	170	84

Fig. 3

The image of outer approximation $U$ of $Y^{♦}$ with several values of $\overset{`}{o} = 0.02, 0.01$ in Example 5.2.

Example 5.3. $\begin{matrix} Vmin & f_{1} (x) & = & x_{1}^{2} + x_{2}^{2} + x_{3}^{2} + 10 x_{2} - 120 x_{3}, \\ f_{2} (x) & = & x_{1}^{2} + x_{2}^{2} + x_{3}^{2} + 80 x_{1} - 448 x_{2} + 80 x_{3}, \\ f_{3} (x) & = & x_{1}^{2} + x_{2}^{2} + x_{3}^{2} + 448 x_{1} + 80 x_{2} + 80 x_{3} \end{matrix}$ $\begin{matrix} s . t . & x_{1}^{2} + x_{2}^{2} + x_{3}^{2} & ⩽ & 100, \\ 0 & ⩽ & x_{1} ⩽ 10, \\ 0 & ⩽ & x_{2} ⩽ 10, \\ 0 & ⩽ & x_{3} ⩽ 10 . \end{matrix}$

In the initial step, we obtain m₁ = (-1100, - 4380, - 4380) by solving convex programming problems $(P_{1}^{m}), (P_{2}^{m}), (P_{3}^{m})$ . Instead of solving $(P_{1}^{M})$ , $(P_{2}^{M})$ , $(P_{3}^{M})$ , we only need to find an upper boundary $\hat{y} = (473.2051, 1685.6406, 1685.6406)$ . We find m = (-1110, - 4390, - 4390) , M = (2000, 2000, 2000) and a positive direction $\hat{d} = (0.2, 1, 1) > 0$ .

Computational results with different values of ɛ are presented in Table 3 with the same notation meaning as in Example 5.1 and is visualized in Fig. 4.

Table 3

Computational results in Example 5.3

ɛ	T	V	C
800	4.748950	606	1,122
400	29.800921	13,450	24,982
200	4,766.430489	1,011,221	1,907,464

Fig. 4

The distribution of the approximation $U$ of $Y^{♦}$ with $\overset{`}{o} = 2400$ and 400.

6 Conclusion

In this work, an new algorithm is proposed for solving the strictly quasiconvex multiobjective programming problem (QVP) based on the monotonic approach. Firstly, we generate a weakly efficient solution of (QVP) associated with a nondominated outcome point by using strictly quasiconvex programming. Then, we apply the cutting cones in monotonic optimization to outer approximate the outcome set. From the sets of outer approximation outcome points and nondominated outcome points, we have established the outer and inner approximation set of outcome set and obtained the approximation of weakly solution set that contains the whole weakly solution set of (QVP) with any tolerance. These properties are guaranteed by the convergence theorems. We also develop a parallel version of the proposed algorithm, that is more efficient than the former. The numerical results show that the main algorithm is flexible for many cases and the computational time is acceptable for a feasible tolerance. In the future, the main algorithm can be developped for solving many problems related to the multiobjective programming problem (QVP).

Footnotes

Acknowledgments

This research is funded by Hanoi University of Science and Technology (HUST) under grant number T2018-TT-007.

References

Avriel

, Diewert

W.E.

, Schaible

and Zang

, Generalized Concavity, Plenum Press, New York, (1988).

Benoist

, Contractibility of the efficient set in strictly quasi-concave vector maximization, Journal of Optimization Theory and Applications110 (2001), 325–336.

Benson

H.P.

, An outer approximation algorithm for generating all efficient extreme points in the outcome set of a multiple objective linear programming problem, Journal of Global Optimization13 (1998), 1–24.

Benson

H.P.

, On the global optimization of sums of linear fractional functions over a convex set, Journal of Optimization Theory and Applications121 (2004), 19–39.

Benson

H.P.

, A global optimization approach for generating efficient points for multiobjective concave fractional programs, Journal of Multi-Criteria Decision Analysis13 (2005), 15–28.

Das

and Dennis

J.E.

, Normal-boundary intersection: a new method for generating the Pareto surface in nonlinear multicriteria optimization problems, SIAM Journal on Optimization8 (1998), 631–657.

Ehrgott

, Shao

and Schobel

, An Approximation Algorithm for Convex Multi-objective Programming Problems, Journal of Global Optimization50 (2011), 397–416.

Gourion

and Luc

D.T.

, Finding efficient solutions by free disposal outer approximation, SIAM Journal on Optimization20 (2010), 2939–2958.

Kaliszewski

, Miroforidis

and Podkopaev

, Interactive multiple criteria decision making based on preference driven evolutionary multiobjective optimization with controllable accuracy, European Journal of Operational Research216(1) (2012), 188–199.

10.

Klamroth

, Tind

and Wiecek

M.M.

, Unbiased approximation in multicriteria optimization, Mathematical Methods of Operations Research56 (2002), 413–457.

11.

Konno

and Inori

, Bond portfolio optimization by bilinear fractional programming, Journal of the Operations Research Society of Japan32 (1989), 143–158.

12.

Nobakhtian

and Shafiei

, A Benson type algorithm for nonconvex multiobjective programming problems, TOP25 (2017), 271–287.

13.

Luc

D.T.

, Generalized Convexity in Vector Optimization, in: Handbook of Generalized Convexity and Generalized Monotonicity, Springer-Verlag, New York, (2005), pp. 195–136.

14.

Mangasarian

O.L.

, Nonlinear Programming, McGraw-Hill, New York, (1969).

15.

Ruzika

and Wiecek

M.M.

, Approximation methods in multiobjective programming, Journal of Optimization Theory and Applications126 (2005), 473–501.

16.

Singh

, Weakly fuzzy efficient conditions for multiobjective fractional programming problem, Journal of Intelligent and Fuzzy Systems26 (2014), 1383–1392.

17.

Stancu-Minasian

I.M.

, Fractional Programming: Theory, Methods and Applications, Kluwer Academic Publishers, Netherlands, (1997).

18.

Tuy

, Normal sets, polyblocks and monotonic optimization, Vietnam Journal of Mathematics27 (1999), 277–300.

19.

Tuy

, Monotonic Optimization: Problems and Solution Approaches, SIAM Journal on Optimization2 (2000), 464–494.

20.

Tuy

, Al-Khayyal

and Thach

P.T.

, Monotonic Optimization: Branch and Cuts Methods, in: Essays and Surveys on Global Optimization, Springer-Verlag, New York, (2005), pp. 39–78.

21.

Veeramani

and Sumathi

, A new method for solving fuzzy linear fractional programming problems, Journal of Intelligent and Fuzzy Systems31 (2016), 1831–1843.

22.

Wiecek

M.M.

, Ehrgott

and Engau

, Continuous multiobjective programming, in: Multiple criteria decision analysis: State of the art surveys, Oper Res Manag Sci Springer, New York, (2016), pp. 739–815.

A monotonic optimization approach for solving strictly quasiconvex multiobjective programming problems

Abstract

Keywords

1 Introduction

2 Theoretical preliminaries

2.1 Generating a nondominated outcome point and a w.e.s. of (QVP)

3 The algorithm for solving (QVP)

4 The convergent proof of the algorithm

Table 1 Computational results in Example 5.1 ɛ T V C 0.1 1.894534 35 18 0.05 2.167836 67 34 0.025 2.644173 117 59 0.0125 4.124381 231 116

Footnotes

Acknowledgments

References

Table 1
Computational results in Example 5.1

ɛ T V C

0.1 1.894534 35 18

0.05 2.167836 67 34

0.025 2.644173 117 59

0.0125 4.124381 231 116