# Lagrangian Duality for Multiobjective Programming Problems in Lexicographic Order

Authors: X. F. Hu; L. N. Wang
Journal: Abstract and Applied Analysis
 (2013)

---

## Abstract

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.


---

## Body

## 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 Section2, 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, letX be an arbitrarily nonempty subset of a topology space Y and ℝℓn-dimensional Euclidean space. Let ℝ+ℓ:={x∈ℝℓ:xi≥0,∀i}. Let ℒ(ℝm,ℝn) be the space of continuous linear operator from ℝm to ℝn and ℒ+(ℝm,ℝn):={Λ∈ℒ(ℝm,ℝn):Λ(ℝ+m)⊂ℝ+n}. By 0ℓ denote the zero vector of ℝℓ.For convenience, we setIn={1,2,…,n}. As usual, for any v∈ℝn and i∈In, vi will denote the ith coordinate of v with respect to the canonical basis {e1,e2,…,en}. The lexicographic cone of ℝn is defined as the set of all vectors whose first nonzero coordinate (if any) is positive:
(1)Clex={0}∪{∄j∈In,j<isuchthatvj≠0}v∈Rn:∃i∈Insuchthatvi>0;hhhhhhhi∄j∈In,j<isuchthatvj≠0}.Note that the lexicographic coneClex is neither closed nor open. However, it is convex, pointed and Clex∪(-Clex)=ℝn. Thus the binary relation defined for any u,v∈ℝn by
(2)u≤lexv⟺u∈v-Clex
is a total order on ℝn (i.e., it is reflexive, transitive, antisymmetric and any two vectors are comparable). The binary relation induced by Clex 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]).
LetZ⊂ℝn be a nonempty subset. (i)
A pointz0∈Z is called a lexicographic maximal point of Z if  Z⊂z0-Clex; that is, for any z∈Z,z≤lexz0; by maxlexZ, we denote the set of all lexicographic maximal points of Z.(ii)
A pointz0∈Z is called a lexicographic minimal point of Z if Z⊂z0+Clex; that is, for any z∈Z,z0≤lexz; by minlexZ, we denote the set of all lexicographic minimal points of Z.Obviously, ifmaxlexZ≠∅, maxlexZ is a single point set and so is minlexZ.Lemma 2 (see [13]).
IfZ⊂ℝn is a nonempty compact set, then minlexZ≠∅ and maxlexZ≠∅.Proposition 3.
IfC,D⊂ℝn are two nonempty compact subsets, then (i)
minlex(C+D)=minlex(C)+minlex(D),(ii)
maxlex(C+D)=maxlex(C)+maxlex(D).Proof.
It suffices to verify (i) since (ii) is evident bymaxlex(C)=-minlex(-C). Indeed, let x-=minlex(C) and y-=minlex(D). Then x-∈C and x-≤lexx,forallx∈C; y-∈D and y-≤lexy,forally∈D. Hence, x-+y-∈C+D and x-+y-≤lexx+yforallx∈C, and y∈D. Namely, {x-+y-}=minlex(C+D) and the proof is complete.Definition 4.
A vector-valued mappingg:X→ℝℓ is called lower semicontinuous if, for any z∈ℝℓ, the set {x∈X:g(x)∈z-ℝ+ℓ} is closed in X.Definition 5.
A vector-valued mappingg:X→ℝℓ is called convex on Y if and only if, for any x1,x2∈X, t∈[0,1], and i=1,2,…,ℓ, gi(tx1+(1-t)x2)≤tgi(x1)+(1-t)gi(x2).Consider the following multiobjective programming problem:(3)(MP)minlexhhf(x)=(f1(x),f2(x),…,fn(x))Ts.t.hg(x)∈-R+m,x∈X,
where fi:X→ℝ(i=1,2,…,n) and g(x)=(g1(x),g2(x),…,gm(x))T, and gj:X→ℝ(j=1,2,…,m).LetE denote the set of all feasible points for the multiobjective optimization problem (MP); that is,
(4)E={x∈X:g(x)∈-R+m}.
And let Ei denote the set of all minimal points for fi on E; that is,
(5)Ei={x∈E:fi(x)=miny∈Efi(y)},fori=1,2,…,n.
Then, we write f(E)=⋃x∈E‍f(x). Throughout this paper, we always assume that E≠∅ and Ei≠∅(i=1,2,…,n).A vector-valued Lagrangian function for (MP) is defined fromE×Rn×m→Rn by
(6)L(x,Λ)=f(x)+Λg(x),
where Λ∈ℒ+(Rm,Rn); that is, Λn×m=(λ1,λ2,…,λn)T; λi=(λi1,λi2,…,λim)∈R+m,i=1,2,…,n.Then the Lagrangian dual problem is defined as the following multiobjective programming problem:(7)(DMP)maxlexlexϕ(Λ)s.t.hiΛ∈ℒ+(Rm,Rn),
where ϕ(Λ)=minlex{L(x,Λ):x∈X}.Definition 6.
(i) A pointx-∈E is said to be a lexicographic minimal solution to (MP) if x-∈E and f(x-)≤lexf(x),forallx∈E. By minlexEandminlexf(E) denote the set of all lexicographic minimal solutions and the lexicographic minimal value to (MP), respectively.
(ii) A pointx-∈E is said to be a strong minimal solution to (MP) if x-∈E and f(x-)∈f(x)-R+n,forallx∈E; that is, fi(x-)≤fi(x),andx∈E,andi=1,2,…,n. The set of all strong minimal solutions to (MP) is denoted by minR+nf(E).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 x-∈E is said to be a lexicographic minimal solution to (MP) if x-∈E and {f(x-)-Clex∖{0}}∩f(E)=∅.
(
2
) If x-∈E is a strong solution to (MP), then x- 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, x∈Xandg(x)∈-R+m. Also, let Λ be a feasible point of (DMP); that is, Λ∈ℒ+(Rm,Rn). Then
(8)f(x)≥lexϕ(Λ).Proof.
Sincex∈X,g(x)∈-R+m, and Λ∈ℒ+(Rm,Rn), we obtain that Λg(x)∈-R+n⊂-Clex; that is, Λg(x)≤lex0n. Then, it follows from the definition of ϕ(Λ) that
(9)ϕ(Λ)=minlex{f(x~)+Λg(x~):x~∈X}≤lexf(x)+Λg(x)≤lexf(x),
and the proof is complete.As a corollary of the previous theorem, we have the following result.Corollary 9.
Assume thatmaxlex{ϕ(Λ):Λ∈L+(Rn,Rm)≠∅. Then,
(10)minlex{f(x):g(x)∈-R+m,x∈X}≥lexmaxlex{ϕ(Λ):Λ∈L+(Rn,Rm)}.Before stating the Lagrangian multiplier rule to (MP) in lexicographic sense, we need the following result.Lemma 10.
Assume that⋂i=1n‍Ei≠∅. A point x-∈E is a lexicographic solution for (MP) if and only if x-∈E is a strong solution for (MP).Proof.
Ifx- is a lexicographic solution for (MP), then f(x-)∈minlexf(E). Assume that ⋂i=1n‍Ei≠∅. Then each x^∈⋂i=1n‍Ei is a strong solution for (MP), which implies that f(x^)∈minlexf(E). Since ∈minlexf(E) is singleton, we have f(x^)=f(x-). That is, x- is a strong solution for (MP).
Conversely, suppose thatx- is a lexicographic solution for (MP). Since ⋂i=1n‍Ei≠∅, there exists x^∈E which is a strong solution for (MP). By induction, we can show that f(x-)=f(x^) which means that x- is a strong solution for (MP). Let Dk={x∈Dk-1:fk(x)≤fk(y),∀y∈Dk-1} for k=1,2,…,n and D0=E. Obviously, Dn⊂Dn-1⊂⋯⊂D0. Noting that x- is a lexicographic solution for (MP), we have x-∈Dn. Then, x-∈D1; that is,
(11)f1(x)≥f1(x-),∀x∈D0.
Taking x=x^ in the above inequality, we get
(12)f1(x^)≥f1(x-).
On the other hand, f1(x-)≥f1(x^) since x^∈D0 is a strong solution and x-∈Xn⊂D0. Therefore, f1(x-)=f1(x^) and x^∈D1. Suppose that fi(x-)=fi(x^) for i=1,2,…,n-1. Obviously, x-∈Dn-1. Similarly, we can verify that fn(x-)=fn(x^) and x^∈Dn. 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→Rn is a R+n-convex vector function; that is, fi:X→R, i=1,2,…,n, are convex functions;(iii)
g:X→Rm is a R+m-convex vector function; that is, gj:X→R,j=1,2,…,m, are convex functions;(iv)
the Slater constraint qualification is satisfied; that is, there existsx0∈X such that g(x0)∈-intR+m, where intR+m is the topology interior of R+m;(v)
⋂i=1n‍Ei≠∅.If x- is a lexicographic solution to (MP), then there exists Λ-∈ℒ+(Rm,Rn) such that
(13)f(x-)=minlex{f(x)+Λ-g(x):x∈E},Λ-g(x-)=0n.Proof.
Letx- be a lexicographic solution of the problem (MP). By Lemma 10, x- is a strong solution for (MP). Then, for any x∈E:={x∈X:g(x)∈-R+m},
(14)f1(x)≥f1(x-),f2(x)≥f2(x-),⋮fn(x)≥fn(x-).
Then, the inequality systemf1(x)<f1(x-),g(x)∈-R+m for some x∈X has no solution. Define the following set:
(15)S1∶={(p,q)∈R×Rm:f1(x)-f1(x-)<p,g(x)∈q-R+m,forsomex∈X}.
The set S1 is convex subset since X,f1, and g are convex. Since the above inequality system has no solution, we have (0,0m)∉S1. By the standard separation theorem, there exists a nonzero vector (μ^1,λ^1) such that
(16)μ^1(f1(x)-f1(x-))+λ^1Tg(x)≥0,∀x∈X.
That is,
(17)μ^1f1(x)+λ^1Tg(x)≥μ^1f1(x-),∀x∈X.
Now, fix anx∈X. From the definition of S1, we have that p and q can be arbitrarily large. In order to satisfy (17), we must have (μ^1,λ^1)∈R+×R+m. We will next show that μ^1>0. On the contrary, suppose that μ^1=0. By the Slater constraint qualification, there exists x0∈X such that g(x0)∈-intR+m. Then, letting x=x0 in (17), we have λ^1g(x0)≥0. But, since g(x0)∈-intR+m and λ^1∈R+m,λ^1g(x0)≥0 is only possible if λ^1=0m. Thus, it has been shown that (μ^1, λ^1)=(0, 0m), which is a contradiction.
After dividing (17) by μ^1 and denoting λ-1=λ^1/μ^1, we obtain
(18)f1(x)+λ-1Tg(x)≥f1(x-),∀x∈X.
From (18), letting x=x-, we get λ-1Tg(x-)≥0. Since g(x-)∈-R+m and λ-1∈R+m, we obtain λ-1Tg(x-)=0.
Similarly, we can show that there existλ-2,λ-3,…,λ-n∈R+m such that, for any x∈X,
(19)f2(x)+λ-2Tg(x)≥f2(x-),λ-2Tg(x-)=0,f3(x)+λ-3Tg(x)≥f3(x-),λ-3Tg(x-)=0,⋮fn(x)+λ-nTg(x)≥fn(x-),λ-nTg(x-)=0.
Set Λ-=(λ-1,λ-2,…,λ-n)T. Then, it follows from R+n⊂Clex, (18), and (19) that
(20)f(x)+Λ-g(x)∈f(x-)+R+n∈f(x-)+Clex,∀x∈X,Λ-g(x-)=0n.
Namely,
(21)f(x)+Λ-g(x)≥lexf(x-),∀x∈X,(22)Λ-g(x-)=0n.
Thus, (21) and weak duality theorem (Theorem 8) together yield that
(23)f(x-)=minlex{f(x)+Λ-g(x):x∈E}.
And the proof is complete.Now, we give an example to illustrate that Theorem11 is applicable.Example 12.
LetX=[-2, 2]⊂R; g:X→R is defined by g(x)=x2-1 and f=(f1, f2)T:X→R2 is defined by
(24)f1(x)={-2x+1,if-2≤x<-1,3,if-1≤x≤1,2x+1,if1<x≤2,f2(x)=(x-2)2+1.
Consider the following convex multiobjective programming problem:minlex{f(x):g(x)≤0,x∈X}. Direct computation shows that E={x∈x:g(x)≤0}=[-1,1], E1=[-1,1], and E2={1}. Obviously, x-=1∈E1∩E2 is a lexicographic solution of the multiobjective programming problem. Therefore, Theorem 11 is applicable. Indeed, by directly computing, there exists Λ-=(0,1)T such that
(25)minlex{f(x)+Λ-g(x):x∈X}=f(x-)=(3,-1)T,Λ-g(x-)=02.From Theorem11, 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.
LetX⊂R, and g(x) is given as in Example 12. Let f=(f1,f2):X→R2 be defined by
(26)f1(x)=(x-2)2+1,f2(x)=x.
Clearly, the following problem:
(27)minlex{f(x):g(x)≤0,x∈X},
is a convex multiobjective programming. It follows from direct computation that E=[-1,1]E1={1}, and E2={-1}, and x-=1 is a unique lexicographic solution for (MP). Thus, the assumption (v) of Theorem 11 is not satisfied. However, we can verify that there exists Λ-=(1,0)T such that, for any x∈E,
(28)minlex{f(x)+Λ-g(x):x∈X}=f(x-)=(2,1)T,Λ-g(x-)=02.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 Theorem11 are satisfied except for the hypothesis (v) of Theorem 11 which is replaced by the following hypothesis: (v') f1:X→R is a strict convex function; that is, for any x1,x2∈X with x1≠x2 and θ∈(0,1), f1(θx1+(1-θ)x2)<θf1(x1)+(1-θ)f1(x2).
Ifx- is a lexicographic solution to (MP), then there exists Λ-∈L+(Rm,Rn) such that
(29)f(x-)=minlex{f(x)+Λ-g(x):x∈E},Λ-g(x-)=0n.Proof.
SinceX is convex and g(x) is R+m-convex, the set E={x∈X:g(x)∈-R+m} is convex. Noting that f1(x) is strict convex, we obtain E1={x-∈E:f1(x-)=minf1(E)} is singleton. Obviously, x-∈E1={x-} is a lexicographic solution to (MP). Following the same arguments as in Theorem 11, there exists λ-∈R+m such that f1(x-)=min{f1(x)+λ-Tg(x):x∈X}, λ-Tg(x-)=0. Since g(x) is R+m-convex and λ-∈R+m, we obtain that λ-Tg(x) is a convex function (R+-convex function). By hypothesis (v′), f1(x)+λ-Tg(x) is a strict convex function. Thus, the solution to min{f1(x)+λ-Tg(x):x∈X} is also singleton. Let λ-1=λ-,λ-2=⋯=λ-n=0m in Theorem 11. Therefore, x- is also a lexicographic solution to minlex{f(x)+Λ-Tg(x):x∈X} and Λ-g(x-)=0n. 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 Theorems8 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 thatmaxlex{ϕ(Λ):Λ∈L+(Rn,Rm)≠∅. If all conditions of Theorem 11 or Theorem 14 are satisfied, then
(30)minlex{f(x):g(x)∈-R+m,x∈X}=maxlex{ϕ(Λ):Λ∈L+(Rn,Rm)}.
And there exists Λ- such that Λ-g(x-)=0n, where x-∈{x∈X:f(x)=minlexf(E)}.The following example is to illustrate that there is no duality gap if all conditions of Theorem16 are satisfied.Example 17.
LetX⊂R,g(x) is given as in Example 12. Let f(x) be defined by
(31)f1(x)=(x-2)2+1,f2(x)=-x.
Direct computation shows that(32)minlex{f(x):g(x)∈-R+m,x∈X}=maxlex{ϕ(Λ):Λ∈L+(Rn,Rm)}=(2,-1)T=f(1).
And there exists Λ-=(1,1/2)Tor(1,0)T such that Λ-g(1)=02.


## 4. Lexicographic Saddle Point

Now, we introduce the notion of lexicographic saddle point for the vector-valued Lagrangian mapL(·,·) in terms of lexicographic order and give some optimality conditions.Definition 18.
A pair(x-,Λ-)∈E×ℒ(Rn,Rm) is said to be a lexicographic saddle point for the vector-valued Lagrangian function L(x,Λ) if, for all x∈E and Λ∈ℒ+(Rm,Rn),
(33)L(x-,Λ)≤lexL(x-,Λ-)≤lexL(x,Λ-).By Theorem11 or Theorem 14, we directly have the following result.Theorem 19.
Suppose that all conditions of Theorem11 or Theorem 14 are satisfied. If x- is a lexicographic solution to (MP), then there exists Λ-∈ℒ+(Rm,Rn) such that (x-,Λ-) 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 functionL(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(x-,Λ-)∈E×ℒ(Rm,Rn) is a lexicographic saddle point for the vector-valued Lagrangian function L(x,Λ), then x- is a lexicographic solution for (MP), and Λ-g(x-)=0n.Proof.
Assume that(x-,Λ-) is a lexicographic saddle point of L(x,Λ). Then, from the first inequality of (33), we get
(34)f(x-)+Λ-g(x-)≥lexf(x-)+Λg(x-),∀Λ∈ℒ+(Rm,Rn).
This implies that
(35)Λ-g(x-)≥lexΛg(x-),∀Λ∈ℒ+(Rm,Rn).
We claim that g(x-)∈-R+m. Otherwise, we suppose that g(x-)∉-R+m. Since Λ∈ℒ+(Rm,Rn) can be taken arbitrarily to be large, Λg(x-) can be large enough, which contradicts (35).
Therefore, we also get(36)Λ-g(x-)∈-R+n⊂-Clex
since g(x-)∈-R+m and Λ-∈ℒ+(Rm,Rn). This implies that
(37)Λ-g(x-)≤lex0n.
On the other hand, by takingΛ=0 in (35), we can get
(38)Λ-g(x-)≥lex0n.
Noting the reflexivity of the lexicographic order ≤lex, (37) and (38) together yields
(39)Λ-g(x-)=0n.
Sinceg(x-)∈-R+m, x- is a feasible point of (MP). Let x be any feasible point of (MP); that is, g(x)∈-R+m. Then, it follows from the second inequality of (33) and (39) that
(40)f(x-)=f(x-)+Λ-g(x-)≤lexf(x)+Λ-g(x)≤lexf(x),
which implies that x- is a lexicographic solution to (MP).



---

*Source: 573408-2013-11-14.xml*