This paper deals with a constraint multiobjective programming problem and its dual problem in the lexicographic order. We establish some duality theorems and present several existence results of a Lagrange multiplier and a lexicographic saddle point theorem. Meanwhile, we study the relations between the lexicographic saddle point and the lexicographic solution to a multiobjective programming problem.

1. Introduction

Duality assertions are very important in optimization researches from the theoretical as well as from the numerical point of view. Duality theorems in mathematical programming establish typical connections between a constrained minimization problem and a constrained maximization problem. The relationship is such that the existence of a solution to one of these problems ensures the existence of a solution to other, both having the same optimal value. In the past centuries, many authors have studied the duality problems of vector optimization problems; see, for example, [1–11] and reference therein.

On the other hand, it is well known that partial order plays an important role in multiobjective optimization theory. But partial efficient points are usually large, so that one needs certain additional rules to reduce them. One of the possible approaches is to utilize the lexicographic order, which is introduced by the lexicographic cone. The main reason is that the lexicographic order is a total ordering and it can overcome the shortcoming that not all points can be compared in partial order. The lexicographic order has been investigated in connection with its applications in optimization and decision making theory; see, for example, [12–19] and references therein. However, the lexicographic cone is neither open nor closed. Note that a lot of results for vector optimization problems are gotten under the assumption that the ordering cone is open or closed. Therefore, it is valuable to investigate multiobjective optimization problems in the lexicographic order. Konnov [12] first discussed the vector equilibrium problems in lexicographic order. Recently, Li et al. [13] studied the minimax inequality problem and have obtained minmax theorems in the lexicographic order.

The rest of the paper is organized as follows. In Section 2, we first recall some definitions and their properties. In Section 3, with respect to the lexicographic order, we first establish weak duality theorem and the Lagrangian multiplier rules for a multiobjective programming. In Section 4, we investigate a lexicographic saddle point of a vector-valued Lagrangian function and discuss the connection between the lexicographic saddle point and the lexicographic solution to a multiobjective programming problem.

2. Preliminaries and Notations

Throughout this paper, unless otherwise specified, let X be an arbitrarily nonempty subset of a topology space Y and ℝ^ℓn-dimensional Euclidean space. Let . Let ℒ(ℝ^m, ℝⁿ) be the space of continuous linear operator from ℝ^m to ℝⁿ and . By 0_ℓ denote the zero vector of ℝ^ℓ.

For convenience, we set I_n = {1,2, …, n}. As usual, for any v ∈ ℝⁿ and i ∈ I_n, v_i will denote the ith coordinate of v with respect to the canonical basis {e₁, e₂, …, e_n}. The lexicographic cone of ℝⁿ is defined as the set of all vectors whose first nonzero coordinate (if any) is positive:

()

Note that the lexicographic cone C_lex is neither closed nor open. However, it is convex, pointed and C_lex ∪ (−C_lex) = ℝⁿ. Thus the binary relation defined for any u, v ∈ ℝⁿ by

()

is a total order on ℝⁿ (i.e., it is reflexive, transitive, antisymmetric and any two vectors are comparable). The binary relation induced by C_lex is called a lexicographic order.

Now we recall the definitions of efficient points of a nonempty subset in the lexicographic order.

Definition 1 (see [13], [14].)Let Z ⊂ ℝⁿ be a nonempty subset.

(i)
A point z₀ ∈ Z is called a lexicographic maximal point of Z if Z ⊂ z₀ − C_lex; that is, for any z ∈ Z, z ≤_lex z₀; by max _lexZ, we denote the set of all lexicographic maximal points of Z.
(ii)
A point z₀ ∈ Z is called a lexicographic minimal point of Z if Z ⊂ z₀ + C_lex; that is, for any z ∈ Z, z₀ ≤_lex z; by min _lexZ, we denote the set of all lexicographic minimal points of Z.

Obviously, if max _lexZ ≠ ∅, max _lexZ is a single point set and so is min _lexZ.

Lemma 2 (see [13].)If Z ⊂ ℝⁿ is a nonempty compact set, then min _lex Z ≠ ∅ and max _lex Z ≠ ∅.

Proposition 3. If C, D ⊂ ℝⁿ are two nonempty compact subsets, then

(i)
min _lex(C + D) = min _lex(C) + min _lex(D),
(ii)
max _lex(C + D) = max _lex(C) + max _lex(D).

Proof. It suffices to verify (i) since (ii) is evident by max _lex(C) = −min _lex(−C). Indeed, let and . Then and ; and . Hence, and , and y ∈ D. Namely, and the proof is complete.

Definition 4. A vector-valued mapping g : X → ℝ^ℓ is called lower semicontinuous if, for any z ∈ ℝ^ℓ, the set is closed in X.

Definition 5. A vector-valued mapping g : X → ℝ^ℓ is called convex on Y if and only if, for any x₁, x₂ ∈ X, t ∈ [0,1], and i = 1,2, …, ℓ, g_i(tx₁ + (1 − t)x₂) ≤ tg_i(x₁)+(1 − t)g_i(x₂).

Consider the following multiobjective programming problem:

()

where f_i : X → ℝ (i = 1,2, …, n) and g(x) = (g₁(x), g₂(x), …, g_m(x)) ^T, and g_j : X → ℝ (j = 1,2, …, m).

Let E denote the set of all feasible points for the multiobjective optimization problem (MP); that is,

()

And let E_i denote the set of all minimal points for f_i on E; that is,

()

Then, we write f(E) = ⋃_x∈E f(x). Throughout this paper, we always assume that E ≠ ∅ and E_i ≠ ∅ (i = 1,2, …, n).

A vector-valued Lagrangian function for (MP) is defined from E × R^n×m → Rⁿ by

()

where Λ ∈ ℒ⁺(R^m, Rⁿ); that is, Λ_n×m = (λ₁, λ₂, …, λ_n) ^T;

Then the Lagrangian dual problem is defined as the following multiobjective programming problem:

()

where ϕ(Λ) = min_lex{L(x, Λ) : x ∈ X}.

Definition 6. (i) A point is said to be a lexicographic minimal solution to (MP) if and . By min _lexE and min _lexf(E) denote the set of all lexicographic minimal solutions and the lexicographic minimal value to (MP), respectively.

(ii) A point is said to be a strong minimal solution to (MP) if and ; that is, . The set of all strong minimal solutions to (MP) is denoted by .

Remark 7. (1) From [14], it is easy to verify that (i) of Definition 6 is equivalent and refers to the following concept: a point is said to be a lexicographic minimal solution to (MP) if and .

(2) If is a strong solution to (MP), then is a lexicographic solution to (MP). However, the converse generally is not valid.

3. Duality Results

The following result shows that, with respect to lexicographic order, the objective value of any feasible point to the dual problem (DMP) is less than or equal to the objective value of any feasible point to the primal problem (MP).

Theorem 8 (weak duality theorem). Consider the primal problem (MP) given by (3) and its Lagrangian dual problem (DMP) given by (7). Let x be a feasible point of (MP); that is, . Also, let Λ be a feasible point of (DMP); that is, Λ ∈ ℒ⁺(R^m, Rⁿ). Then

()

Proof. Since , and Λ ∈ ℒ⁺(R^m, Rⁿ), we obtain that ; that is, Λg(x) ≤_lex 0_n. Then, it follows from the definition of ϕ(Λ) that

()

and the proof is complete.

As a corollary of the previous theorem, we have the following result.

Corollary 9. Assume that max _lex {ϕ(Λ) : Λ ∈ L⁺(Rⁿ, R^m) ≠ ∅. Then,

()

Before stating the Lagrangian multiplier rule to (MP) in lexicographic sense, we need the following result.

Lemma 10. Assume that . A point is a lexicographic solution for (MP) if and only if is a strong solution for (MP).

Proof. If is a lexicographic solution for (MP), then . Assume that . Then each is a strong solution for (MP), which implies that . Since ∈min _lexf(E) is singleton, we have . That is, is a strong solution for (MP).

Conversely, suppose that is a lexicographic solution for (MP). Since , there exists which is a strong solution for (MP). By induction, we can show that which means that is a strong solution for (MP). Let D_k = {x ∈ D_k−1 : f_k(x) ≤ f_k(y), ∀ y ∈ D_k−1} for k = 1,2, …, n and D₀ = E. Obviously, D_n ⊂ D_n−1 ⊂ ⋯⊂D₀. Noting that is a lexicographic solution for (MP), we have . Then, ; that is,

()

Taking

in the above inequality, we get

()

On the other hand,

since

is a strong solution and

. Therefore,

and

. Suppose that

for i = 1,2, …, n − 1. Obviously,

. Similarly, we can verify that

and

. The proof is complete.

Theorem 11 (Lagrangian multiplier rule). Suppose that the following conditions are satisfied:

(i)
X is a nonempty convex subset of R^ℓ;
(ii)
f : X → Rⁿ is a -convex vector function; that is, f_i : X → R, i = 1,2, …, n, are convex functions;
(iii)
g : X → R^m is a -convex vector function; that is, g_j : X → R, j = 1,2, …, m, are convex functions;
(iv)
the Slater constraint qualification is satisfied; that is, there exists x₀ ∈ X such that , where is the topology interior of ;
(v)
.

is a lexicographic solution to (MP), then there exists

such that

()

Proof. Let be a lexicographic solution of the problem (MP). By Lemma 10, is a strong solution for (MP). Then, for any ,

()

Then, the inequality system for some x ∈ X has no solution. Define the following set:

()

The set S₁ is convex subset since X, f₁, and g are convex. Since the above inequality system has no solution, we have (0, 0_m) ∉ S₁. By the standard separation theorem, there exists a nonzero vector

such that

()

That is,

()

Now, fix an x ∈ X. From the definition of S₁, we have that p and q can be arbitrarily large. In order to satisfy (17), we must have . We will next show that . On the contrary, suppose that . By the Slater constraint qualification, there exists x₀ ∈ X such that . Then, letting x = x₀ in (17), we have . But, since and is only possible if . Thus, it has been shown that , , 0_m), which is a contradiction.

After dividing (17) by and denoting , we obtain

()

From (18), letting

, we get

. Since

and

, we obtain

Similarly, we can show that there exist such that, for any x ∈ X,

()

Set

. Then, it follows from

, (18), and (19) that

()

Namely,

()

Thus, (21) and weak duality theorem (Theorem 8) together yield that

()

And the proof is complete.

Now, we give an example to illustrate that Theorem 11 is applicable.

Example 12. Let X = [−2, 2] ⊂ R; g : X → R is defined by g(x) = x² − 1 and f = (f₁, f₂) ^T : X → R² is defined by

()

Consider the following convex multiobjective programming problem: min _lex {f(x) : g(x) ≤ 0, x ∈ X}. Direct computation shows that E = {x ∈ x : g(x) ≤ 0} = [−1, 1], E₁ = [−1, 1], and E₂ = {1}. Obviously, is a lexicographic solution of the multiobjective programming problem. Therefore, Theorem 11 is applicable. Indeed, by directly computing, there exists such that

()

From Theorem 11, we get a sufficient condition for the existence of Lagrangian multiplier rule for the problem (MP). But this is not a necessary condition, as the following example shows.

Example 13. Let X ⊂ R, and g(x) is given as in Example 12. Let f = (f₁, f₂) : X → R² be defined by

()

Clearly, the following problem:

()

is a convex multiobjective programming. It follows from direct computation that E = [−1, 1]E₁ = {1}, and E₂ = {−1}, and

is a unique lexicographic solution for (MP). Thus, the assumption (v) of Theorem 11 is not satisfied. However, we can verify that there exists

such that, for any x ∈ E,

()

In order to obtain another sufficient condition for the existence of Lagrangian multiplier rule, we consider the following assumptions.

Theorem 14 (Lagrangian multiplier rule). Assume that all conditions of Theorem 11 are satisfied except for the hypothesis (v) of Theorem 11 which is replaced by the following hypothesis:

(v^′) f₁ : X → R is a strict convex function; that is, for any x₁, x₂ ∈ X with x₁ ≠ x₂ and θ ∈ (0,1), f₁(θx₁ + (1 − θ)x₂) < θf₁(x₁)+(1 − θ)f₁(x₂).

If is a lexicographic solution to (MP), then there exists such that

()

Proof. Since X is convex and g(x) is -convex, the set is convex. Noting that f₁(x) is strict convex, we obtain is singleton. Obviously, is a lexicographic solution to (MP). Following the same arguments as in Theorem 11, there exists such that , . Since g(x) is -convex and , we obtain that is a convex function (R⁺-convex function). By hypothesis (v^′), is a strict convex function. Thus, the solution to is also singleton. Let in Theorem 11. Therefore, is also a lexicographic solution to and . It completes the proof.

Remark 15. The hypothesis (v^′) in Theorem 14 is redundant if f is a real-valued function. Under this case, the hypothesis (v) in Theorem 11 always holds.

From Theorems 8 and 11, we have the following strong duality theorem. The following result shows that, under suitable assumptions, there is no duality gap between the primal and dual lexicographic optimal objective function values.

Theorem 16 (strong duality theorem). Assume that max _lex{ϕ(Λ) : Λ ∈ L⁺(Rⁿ, R^m) ≠ ∅. If all conditions of Theorem 11 or Theorem 14 are satisfied, then

()

And there exists

such that

, where

The following example is to illustrate that there is no duality gap if all conditions of Theorem 16 are satisfied.

Example 17. Let X ⊂ R, g(x) is given as in Example 12. Let f(x) be defined by

()

Direct computation shows that

()

And there exists

such that

4. Lexicographic Saddle Point

Now, we introduce the notion of lexicographic saddle point for the vector-valued Lagrangian map L(·, ·) in terms of lexicographic order and give some optimality conditions.

Definition 18. A pair is said to be a lexicographic saddle point for the vector-valued Lagrangian function L(x, Λ) if, for all x ∈ E and Λ ∈ ℒ⁺(R^m, Rⁿ),

()

By Theorem 11 or Theorem 14, we directly have the following result.

Theorem 19. Suppose that all conditions of Theorem 11 or Theorem 14 are satisfied. If is a lexicographic solution to (MP), then there exists such that is a lexicographic saddle point of the vector Lagrangian function L(x, Λ).

Thus, we have verified the existence of a lexicographic saddle point for the vector-valued Lagrangian function L(x, Λ) under the appropriate conditions. We conclude this result by showing that the saddle point condition is sufficient for optimality for problem (MP).

Theorem 20. If is a lexicographic saddle point for the vector-valued Lagrangian function L(x, Λ), then is a lexicographic solution for (MP), and .

Proof. Assume that is a lexicographic saddle point of L(x, Λ). Then, from the first inequality of (33), we get

()

This implies that

()

We claim that

. Otherwise, we suppose that

. Since Λ ∈ ℒ⁺(R^m, Rⁿ) can be taken arbitrarily to be large,

can be large enough, which contradicts (35).

Therefore, we also get

()

since

and

. This implies that

()

On the other hand, by taking Λ = 0 in (35), we can get

()

Noting the reflexivity of the lexicographic order ≤_lex, (37) and (38) together yields

()

Since , is a feasible point of (MP). Let x be any feasible point of (MP); that is, . Then, it follows from the second inequality of (33) and (39) that

()

which implies that

is a lexicographic solution to (MP).

Acknowledgments

The authors would like to express their deep gratitude to the anonymous referee and the associate editor for their valuable comments and suggestions which helped improve the paper. This research was partially supported by the National Natural Science Foundation of China (Grant no. 11201509).

References

1 Corley H. W., Duality theory for maximizations with respect to cones, Journal of Mathematical Analysis and Applications. (1981) 84, no. 2, 560–568, https://doi.org/10.1016/0022-247X(81)90188-8, MR639684, ZBL0474.90081.
10.1016/0022-247X(81)90188-8
Web of Science® Google Scholar
2 Corley H. W., Existence and lagrangian duality for maximizations of set-valued functions, Journal of Optimization Theory and Applications. (1987) 54, no. 3, 489–501, https://doi.org/10.1007/BF00940198, MR906165.
10.1007/BF00940198
Web of Science® Google Scholar
3 Fishburn P. C., Lexicographic orders, utilities and decision rules: a survey, Management Science. (1974) 20, 1442–1471, MR0363428.
10.1287/mnsc.20.11.1442
Web of Science® Google Scholar
4 Hsia W.-S. and Lee T. Y., Lagrangian function and duality theory in multiobjective programming with set functions, Journal of Optimization Theory and Applications. (1988) 57, no. 2, 239–251, https://doi.org/10.1007/BF00938538, MR938873, ZBL0619.90072.
10.1007/BF00938538
Web of Science® Google Scholar
5 Hernández E. and Rodríguez-Marín L., Lagrangian duality in set-valued optimization, Journal of Optimization Theory and Applications. (2007) 134, no. 1, 119–134, https://doi.org/10.1007/s10957-007-9237-6, MR2341498, ZBL1129.49029.
10.1007/s10957-007-9237-6
Web of Science® Google Scholar
6 Jahn J., Mathematical Vector Optimization in Partially Ordered Linear Spaces, 1986, 31, Peter Lang, Frankfurt, Germany, Methoden und Verfahren der Mathematischen Physik, MR830661.
Google Scholar
7 Li Z.-F. and Chen G.-Y., Lagrangian multipliers, saddle points, and duality in vector optimization of set-valued maps, Journal of Mathematical Analysis and Applications. (1997) 215, no. 2, 297–316, https://doi.org/10.1006/jmaa.1997.5568, MR1490753, ZBL0893.90150.
10.1006/jmaa.1997.5568
Web of Science® Google Scholar
8 Li Z. F. and Wang S. Y., Lagrange multipliers and saddle points in multiobjective programming, Journal of Optimization Theory and Applications. (1994) 83, no. 1, 63–81, https://doi.org/10.1007/BF02191762, MR1298857, ZBL0823.90107.
10.1007/BF02191762
Web of Science® Google Scholar
9 Song W., Lagrangian duality for minimization of nonconvex multifunctions, Journal of Optimization Theory and Applications. (1997) 93, no. 1, 167–182, https://doi.org/10.1023/A:1022658019642, MR1443102, ZBL0901.90161.
10.1023/A:1022658019642
Web of Science® Google Scholar
10 Sawaragi Y., Nakayama H., and Tanino T., Theory of Multiobjective Optimization, 1985, 176, Academic Press, Orlando, Fla, USA, Mathematics in Science and Engineering, MR807529.
Google Scholar
11 Tanino T. and Sawaragi Y., Duality theory in multiobjective programming, Journal of Optimization Theory and Applications. (1979) 27, no. 4, 509–529, https://doi.org/10.1007/BF00933437, MR533118, ZBL0378.90100.
10.1007/BF00933437
Web of Science® Google Scholar
12 Konnov I. V., On lexicographic vector equilibrium problems, Journal of Optimization Theory and Applications. (2003) 118, no. 3, 681–688, https://doi.org/10.1023/B:JOTA.0000004877.39408.80, MR2027323, ZBL1061.90101.
10.1023/B:JOTA.0000004877.39408.80
Web of Science® Google Scholar
13 Li X. B., Li S. J., and Fang Z. M., A minimax theorem for vector-valued functions in lexicographic order, Nonlinear Analysis: Theory, Methods & Applications. (2010) 73, no. 4, 1101–1108, https://doi.org/10.1016/j.na.2010.04.047, MR2653777, ZBL1204.49021.
10.1016/j.na.2010.04.047
Web of Science® Google Scholar
14 Mäkelä M. M. and Nikulin Y., On cone characterizations of strong and lexicographic optimality in convex multiobjective optimization, Journal of Optimization Theory and Applications. (2009) 143, no. 3, 519–538, https://doi.org/10.1007/s10957-009-9570-z, MR2558644, ZBL1184.90156.
10.1007/s10957-009-9570-z
Web of Science® Google Scholar
15 Martínez-Legaz J. E., P. Thoft-Christensen, Lexicographical order, inequality systems and optimization, System Modelling and Optimization, 1984, 59, Springer, Berlin, Germany, 203–212, Lecture Notes in Control and Information Sciences, https://doi.org/10.1007/BFb0008893, MR769668, ZBL0563.90084.
10.1007/BFb0008893
Google Scholar
16 Martínez-Legaz J.-E., Lexicographical order and duality in multiobjective programming, European Journal of Operational Research. (1988) 33, no. 3, 342–348, https://doi.org/10.1016/0377-2217(88)90178-6, MR925068, ZBL0646.90076.
10.1016/0377-2217(88)90178-6
Web of Science® Google Scholar
17 Podinovskii V. V. and Gavrilov V. M., Optimization with Respect to Sequentially Applied Criteria, 1976, Sovetskoe Radio, Moscow, Russia, (Russian).
Google Scholar
18 Pourkarimi L. and Zarepisheh M., A dual-based algorithm for solving lexicographic multiple objective programs, European Journal of Operational Research. (2007) 176, no. 3, 1348–1356, https://doi.org/10.1016/j.ejor.2005.10.046, MR2270850, ZBL1102.90063.
10.1016/j.ejor.2005.10.046
Web of Science® Google Scholar
19 Popovici N., Structure of efficient sets in lexicographic quasiconvex multicriteria optimization, Operations Research Letters. (2006) 34, no. 2, 142–148, https://doi.org/10.1016/j.orl.2005.03.003, MR2192371.
10.1016/j.orl.2005.03.003
Web of Science® Google Scholar

All articles

Lagrangian Duality for Multiobjective Programming Problems in Lexicographic Order

Abstract

1. Introduction

2. Preliminaries and Notations

3. Duality Results

4. Lexicographic Saddle Point

Acknowledgments

References

References

Information

About Wiley Online Library

Help & Support

Opportunities

Connect with Wiley

Lagrangian Duality for Multiobjective Programming Problems in Lexicographic Order

Abstract

1. Introduction

2. Preliminaries and Notations

3. Duality Results

4. Lexicographic Saddle Point

Acknowledgments

References

References

Related

Information