# Strong and Total Lagrange Dualities for Quasiconvex Programming

Authors: Donghui Fang; XianFa Luo; Xianyun Wang
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

We consider the strong and total Lagrange dualities for infinite quasiconvex optimization problems. By using the epigraphs of thez-quasi-conjugates and the Greenberg-Pierskalla subdifferential of these functions, we introduce some new constraint qualifications. Under the new constraint qualifications, we provide some necessary and sufficient conditions for infinite quasiconvex optimization problems to have the strong and total Lagrange dualities.


---

## Body

## 1. Introduction

Consider the following infinite optimization problem:(1)
Minimize
f
(
x
)
,
s
.
t
.
g
h
h
h
g
s
.
t
.
l
l
l
l
l
l
h
h
h
f
t
(
x
)
≤
0
,
t
∈
T
,
j
j
j
j
j
j
j
j
j
j
h
x
∈
C
,
where T is an arbitrary (possibly infinite) index set, C is a nonempty convex subset of a locally convex (Hausdorff topological vector) space X, and f, f
t
:
X
→
R
¯
:
=
R
∪
{
+
∞
}
,
t
∈
T, are proper functions. This problem has been studied extensively under various degrees of restrictions imposed on the involved functions or on the underlying space and many problems in optimization and approximation theory such as linear semi-infinite optimization and the best approximation with restricted ranges can be recast into the form (1); see, for example, [1–12].Observe that most works in the literature mentioned above were done under the assumptions that the involved functions are convex. Indeed, in mathematical programming, many of the problems naturally involve nonconvex functions. Recently, the quasiconvex programming, for which the involved functions are quasiconvex, has received much attention (cf. [13–18] and the references therein). Inspired by the works mentioned above, we continue to study the optimization problem (1) but with f and f
t being quasiconvex functions. The present paper is centered around the strong Lagrange duality and the total Lagrange duality for this quasiconvex programming. Usually for the strong Lagrange duality, one finds conditions ensuring the following equality:
(2)
inf
⁡
x
∈
A
f
(
x
)
=
max
⁡
λ
∈
R
+
(
T
)
inf
⁡
x
∈
C
{
f
(
x
)
+
∑
t
∈
T
‍
λ
t
f
t
(
x
)
}
,
and for the total Lagrange duality, one seeks conditions ensuring that the following implication holds for x
0
∈
A
:
=
{
x
∈
C
:
f
t
(
x
)
≤
0
,
∀
t
∈
T
}:
(3)
[
f
(
x
0
)
=
min
⁡
x
∈
A
f
(
x
)
]
⟹
[
s
.
t
.
inf
⁡
x
∈
C
{
∑
t
∈
T
‍
f
(
x
)
+
∑
t
∈
T
‍
λ
t
f
t
(
x
)
}
∃
λ
∈
R
+
(
T
)
,
s
.
t
.
inf
⁡
x
∈
C
{
∑
t
∈
T
‍
f
(
x
)
+
∑
t
∈
T
‍
λ
t
f
t
(
x
)
}
j
ffffffffffu
s
=
f
(
x
0
)
{
∑
t
∈
T
‍
f
(
x
)
]
,
where
(4)
R
+
(
T
)
:
=
{
λ
=
(
λ
t
)
∈
R
T
:
λ
t
≥
0
for
each
t
∈
T
h
h
h
and
only
finitely
many
λ
t
≠
0
λ
=
(
λ
t
)
∈
R
T
λ
λ
}
.
To our knowledge, not many results are known to provide complete characterizations for the strong and total Lagrange dualities for quasiconvex programming.Constraint qualifications involving epigraphs of the conjugate functions have been studied extensively. Our main aim in the present paper is to use these constraint qualifications (or their variations) to provide complete characterizations for the strong Lagrange duality and for the total Lagrange duality. It is well known that the Fenchel conjugate provides dual problems of convex minimization problems. In a similar way, different notions of conjugate for quasiconvex functions can be introduced in order to obtain dual problems of quasiconvex minimization problems. Note that thez-quasi-conjugate (
z
∈
R
), defined by Greenberg and Pierskalla [13], plays in quasiconvex optimization the same role as the one Fenchel conjugate plays in convex optimization. Thus, by using the z-quasi-conjugate, we introduce a new constraint qualification which completely characterizes the strong Lagrange duality. Furthermore, many authors introduced some constraint qualifications involving the subdifferentials to establish the total Lagrange duality for convex programming. Similar to the convex case, we introduce the Greenberg-Pierskalla subdifferential to consider the total Lagrange duality for the quasiconvex programming.The paper is organized as follows. The next section contains the necessary notations and preliminary results. In Section3, some new constraint qualifications are provided and some relationships among them are given. In Section 4, we provide characterizations for the quasiconvex programming to have the strong Lagrange duality and the total Lagrange duality.


## 2. Notations and Preliminary Results

The notations used in this paper are standard (cf. [19]). In particular, we assume throughout the whole paper that X is a real locally convex space and let X
* denote the dual space of X. For x
∈
X and x
*
∈
X
*, we write 〈
x
*
,
x
〉 for the value of x
* at x; that is, 〈
x
*
,
x
〉
:
=
x
*
(
x
). Let Z be a set in X. The indicator function δ
Z of Z is defined by
(5)
δ
Z
(
x
)
:
=
{
0
,
x
∈
Z
,
+
∞
,
otherwise
.
The normal cone of Z at z
0
∈
Z is denoted by N
Z
(
z
0
) and is defined by
(6)
N
Z
(
z
0
)
:
=
{
x
*
∈
X
*
:
〈
x
*
,
z
-
z
0
〉
≤
0
∀
z
∈
Z
}
.
Following [2], we use R
(
T
) to denote the space of real tuples λ
=
(
λ
t
)
t
∈
T with only finitely many λ
t
≠
0, and let R
+
(
T
) denote the nonnegative cone in R
(
T
); that is,
(7)
R
+
(
T
)
:
=
{
(
λ
t
)
t
∈
T
∈
R
(
T
)
:
λ
t
≥
0
for
each
t
∈
T
}
.Letf
:
X
→
R
¯ be a proper function. The effective domain, convex conjugate function, and epigraph of f are denoted by dom
⁡
f, f
*, and epi
⁡
f, respectively; they are defined by
(8)
dom
⁡
f
:
=
{
x
∈
X
:
f
(
x
)
<
+
∞
}
,
f
*
(
x
*
)
:
=
sup
⁡
{
〈
x
*
,
x
〉
-
f
(
x
)
:
x
∈
X
}
ffffffffffffffffffff
hh
kk
hh
for
each
x
*
∈
X
*
,
epi
⁡
f
:
=
{
(
x
,
r
)
∈
X
×
R
:
f
(
x
)
≤
r
}
.
Recall that a function f is said to be quasiconvex if, for all x
,
y
∈
R and α
∈
(
0,1
), the following inequality holds:
(9)
f
(
α
x
+
(
1
-
α
)
y
)
≤
max
⁡
{
f
(
x
)
,
f
(
y
)
}
,
or equivalently its sublevel sets
(10)
{
x
∈
X
:
f
(
x
)
≤
r
}
for
each
r
∈
R
are convex. Obviously, each convex function is quasiconvex. The following definition is taken from [13].Definition 1.
Letz
∈
R. The z-quasi-conjugate of f is a function f
z
*
:
X
*
→
R
¯ defined by
(11)
f
z
*
(
x
*
)
=
z
-
inf
⁡
{
f
(
y
)
:
〈
x
*
,
y
〉
≥
z
}
.Note that (11) implies that
(12)
f
z
*
(
x
*
)
≥
z
-
f
(
y
)
for
each
y
∈
{
y
∈
X
:
〈
x
*
,
y
〉
≥
z
}
.
Then the z-quasi-conjugate function f
z
* provides a lower bound for the corresponding conjugate function f
* and, indeed, the conjugate function f
* is the supremum of the z-quasi-conjugates f
z
* over z. Moreover, by the definition, one finds that f
z
* is quasiconvex for each z
∈
R; that is,
(13)
f
z
*
(
α
x
1
*
+
(
1
-
α
)
x
2
*
)
≤
max
⁡
{
f
z
*
(
x
1
*
)
,
f
z
*
(
x
2
*
)
}
d
d
d
d
d
d
d
d
d
h
for
each
x
1
*
,
x
2
*
∈
X
*
,
α
∈
(
0,1
)
.
For quasiconvex functions, several types of subdifferentials have been defined and observed by many researchers, for example, GP-subdifferential [13], R-quasi-subdifferential [20], MLS-subdifferential [21], and so on. The classical Greenberg-Pierskalla subdifferential is among the simplest concepts, which is given as follows (cf. [13]).Definition 2.
The Greenberg-Pierskalla subdifferential off at x
∈
dom
⁡
f is defined by
(14)
∂
*
f
(
x
)
:
=
{
x
*
∈
X
*
:
f
(
x
)
+
f
〈
x
*
,
x
〉
*
(
x
*
)
=
〈
x
*
,
x
〉
}
.We also define(15)
dom
⁡
∂
*
f
:
=
{
x
∈
X
:
∂
*
f
(
x
)
≠
∅
}
,
im
∂
*
f
:
=
{
x
*
∈
X
*
:
x
*
∈
∂
*
f
(
x
)
for
some
x
∈
X
}
.
By definition,
(16)
∂
*
f
(
x
)
=
{
x
*
∈
X
*
:
〈
x
*
,
y
-
x
〉
≥
0
⟹
f
(
y
)
≥
f
(
x
)
}
,
which is equivalent to the following equivalence, holds:
(17)
x
*
∈
∂
*
f
(
x
)
⟺
〈
x
*
,
y
-
x
〉
<
0
for
each
y
∈
S
f
(
x
)
,
where S
f
(
x
) denotes the strict sublevel sets
(18)
S
f
(
x
)
:
=
{
y
∈
X
:
f
(
y
)
<
f
(
x
)
}
.
Moreover, the following equivalence holds:
(19)
0
∈
∂
*
f
(
x
)
⟺
x
is
a
mimimizer
of
f
on
⁡
X
.
Recall that the subdifferential of function g at x
∈
dom
⁡
g is defined by
(20)
∂
g
(
x
)
:
=
{
x
*
∈
X
*
:
g
(
x
)
+
〈
x
*
,
y
-
x
〉
g
g
g
≤
g
(
y
)
for
each
y
∈
X
}
.
Then,
(21)
∂
g
(
x
)
⊆
∂
*
g
(
x
)
for
each
x
∈
dom
⁡
g
.
By definition, we can obtain the following lemma easily, which was proved in [13] when X
=
R
n.Lemma 3.
Letg, h be proper quasiconvex functions on X and let x
0
∈
dom
⁡
g
∩
dom
⁡
h. Then the following statements hold.(i)
Ifg
≤
h, then g
z
*
≥
h
z
* and hence epi
⁡
g
z
*
⊆
epi
⁡
h
z
* for each z
∈
R.
(ii)
Ifg
≤
h and g
(
x
0
)
=
h
(
x
0
), then ∂
*
g
(
x
0
)
⊆
∂
*
h
(
x
0
).The following lemma is known in [19, Theorem  2.8.7].Lemma 4.
Letg, h
:
X
→
R
¯ be proper convex functions. If g or h is continuous at some point of dom
⁡
g
∩
dom
⁡
h, then
(22)
epi
⁡
(
g
+
h
)
*
=
epi
⁡
g
*
+
epi
⁡
h
*
,
∂
(
g
+
h
)
(
x
)
=
∂
g
(
x
)
+
∂
h
(
x
)
f
o
r
e
a
c
h
x
∈
dom
⁡
g
∩
dom
⁡
h
;
consequently, if h
∈
X
*, then
(23)
epi
⁡
(
g
+
h
)
*
=
epi
⁡
g
*
+
{
h
}
×
[
0
,
+
∞
)
,
∂
(
g
+
h
)
(
x
)
=
∂
g
(
x
)
+
h
f
o
r
e
a
c
h
x
∈
dom
⁡
g
.The following example shows that (22) do not necessarily hold if g is a quasiconvex function even in the case when h
∈
X
*.Example 5.
LetX
:
=
R and define the function g
:
R
→
R by
(24)
g
(
x
)
:
=
{
1
,
x
≥
0
,
0
,
x
<
0
.
Then
(25)
epi
⁡
g
0
*
=
(
(
0
,
+
∞
)
×
[
-
1
,
+
∞
)
)
∪
(
(
-
∞
,
0
]
×
[
0
,
+
∞
)
)
,
∂
*
g
(
0
)
=
{
x
*
∈
R
:
x
*
·
x
<
0
for
each
x
<
0
}
=
(
0
,
+
∞
)
.
Take p
=
2. Then for each x
*
∈
R,
(26)
(
g
+
p
)
0
*
(
x
*
)
=
{
-
1
,
x
*
>
0
,
+
∞
,
x
*
≤
0
,
p
0
*
(
x
*
)
=
{
+
∞
,
x
*
>
0
,
0
,
x
*
≤
0
,
and hence
(27)
epi
⁡
(
g
+
p
)
0
*
=
(
0
,
+
∞
)
×
[
-
1
,
+
∞
)
,
epi
⁡
p
0
*
=
(
-
∞
,
0
]
×
[
0
,
+
∞
)
,
Therefore,
(28)
epi
⁡
(
g
+
p
)
0
*
≠
epi
⁡
g
0
*
+
epi
⁡
p
0
*
.
On the other hand, takep
=
-
2. Then S
g
+
p
(
0
)
=
(
-
∞
,
0
) and S
p
(
0
)
=
∅. Hence,
(29)
∂
*
(
g
+
p
)
(
0
)
=
{
(
0
)
S
g
+
p
x
*
∈
R
:
x
*
·
x
<
0
s
s
s
s
s
s
s
s
s
s
s
s
s
s
d
d
for
each
x
∈
S
g
+
p
(
0
)
}
=
(
0
,
+
∞
)
,
∂
*
p
(
0
)
=
{
x
*
∈
R
:
x
*
·
x
<
0
for
each
x
∈
S
p
(
0
)
}
=
R
.
Therefore,
(30)
∂
*
(
g
+
p
)
(
0
)
≠
∂
*
g
(
0
)
+
∂
*
p
(
0
)
.


## 3. New Regularity Conditions for Lagrange Dualities

Unless explicitly stated otherwise, letT
,
C
,
f
,
{
f
t
:
t
∈
T
} and A be as in Section 1; namely, T is an index set, C
⊆
X is a convex set, f and f
t
,
t
∈
T are proper quasiconvex functions such that f
+
δ
C
+
∑
t
∈
T
‍
λ
t
f
t is quasiconvex for each λ
∈
R
+
(
T
), and A
≠
∅ is the solution set of the following system:
(31)
x
∈
C
;
f
t
(
x
)
≤
0
for
each
t
∈
T
.
Then, A is a convex set. Throughout we also assume that dom
⁡
f
∩
A
≠
∅. For each x
∈
X, let T
(
x
) be the active index set of system (31); that is,
(32)
T
(
x
)
:
=
{
t
∈
T
:
f
t
(
x
)
=
0
}
.
To study the strong Lagrange duality and the total Lagrange duality, we need the following regularity conditions.Definition 6.
The family{
δ
C
;
f
t
:
t
∈
T
} is said to have (a)
the quasi-(
WEHP
) if
(33)
epi
⁡
(
f
+
δ
A
)
0
*
∩
(
{
0
}
×
R
)
=
⋃
λ
∈
R
+
(
T
)
‍
epi
⁡
(
f
+
δ
C
+
∑
t
∈
T
‍
λ
t
f
t
)
0
*
∩
(
{
0
}
×
R
)
;
(b)
the quasi-(
WBCQ
) at x
∈
dom
⁡
f
∩
A if
(34)
∂
*
(
f
+
δ
A
)
(
x
)
∩
{
0
}
=
⋃
λ
∈
R
+
(
T
)
∑
t
∈
T
λ
t
f
t
(
x
)
=
0
∂
*
(
f
+
δ
C
+
∑
t
∈
T
‍
λ
t
f
t
)
(
x
)
∩
{
0
}
;
(c)
the quasi-(
WBCQ
) if it has the quasi-(
WBCQ
) at each point in dom
⁡
f
∩
A.Remark 7.
Note thatf
+
δ
C
+
∑
t
∈
T
‍
λ
t
f
t
≤
f
+
δ
A holds for each λ
∈
R
+
(
T
). Then, by Lemma 3(i), (
f
+
δ
C
+
∑
t
∈
T
‍
λ
t
f
t
)
z
*
≥
(
f
+
δ
A
)
z
* for each z
∈
R and hence
(35)
⋃
λ
∈
R
+
(
T
)
‍
epi
⁡
(
f
+
δ
C
+
∑
t
∈
T
‍
λ
t
f
t
)
z
*
⊆
epi
⁡
(
f
+
δ
A
)
z
*
ggggggggggggggggggggggggggg
for
each
z
∈
R
.
Moreover, for each λ
∈
R
+
(
T
) satisfying ∑
t
∈
T
‍
λ
t
f
t
(
x
)
=
0,
(36)
f
(
x
)
+
δ
A
(
x
)
=
f
(
x
)
=
f
(
x
)
+
δ
C
(
x
)
+
∑
t
∈
T
‍
λ
t
f
t
(
x
)
hhhhhhhhhhhhhhhhhhhhhhhhhhh
for
each
x
∈
A
.
Thus, by Lemma 3(ii), we have
(37)
⋃
λ
∈
R
+
(
T
)
∑
t
∈
T
λ
t
f
t
(
x
)
=
0
∂
*
(
f
+
δ
C
+
∑
t
∈
T
‍
λ
t
f
t
)
(
x
)
⊆
∂
*
(
f
+
δ
A
)
(
x
)
.
Therefore, (33) holds if and only if
(38)
epi
⁡
(
f
+
δ
A
)
0
*
∩
(
{
0
}
×
R
)
⊆
⋃
λ
∈
R
+
(
T
)
‍
epi
⁡
(
f
+
δ
C
+
∑
t
∈
T
‍
λ
t
f
t
)
0
*
∩
(
{
0
}
×
R
)
;
and (34) holds if and only if the following inclusion holds:
(39)
∂
*
(
f
+
δ
A
)
(
x
)
∩
{
0
}
⊆
⋃
λ
∈
R
+
(
T
)
∑
t
∈
T
λ
t
f
t
(
x
)
=
0
∂
*
(
f
+
δ
C
+
∑
t
∈
T
‍
λ
t
f
t
)
(
x
)
∩
{
0
}
.
The following proposition describes the relationship between the quasi-(
WEHP
) and the quasi-(
WBCQ
).Proposition 8.
The following implication holds:(40)
t
h
e
q
u
a
s
i
-
(
W
E
H
P
)
⟹
t
h
e
q
u
a
s
i
-
(
W
B
C
Q
)
.
Furthermore, if 0
∈
i
m
∂
*
(
f
+
δ
A
), then
(41)
t
h
e
q
u
a
s
i
-
(
W
E
H
P
)
⟺
t
h
e
q
u
a
s
i
-
(
W
B
C
Q
)
.Proof.
Suppose that the quasi-(
WEHP
) holds. To show the quasi-(
WBCQ
), by Remark 7, it suffices to show (39) holds. To do this, let x
0
∈
dom
⁡
f
∩
A and let 0
∈
∂
*
(
f
+
δ
A
)
(
x
0
). Then by (19), f
(
x
0
)
≤
f
(
x
) for each x
∈
A. Hence, by the definition of 0-conjugate function,
(42)
(
0
,
-
f
(
x
0
)
)
∈
epi
⁡
(
f
+
δ
A
)
0
*
=
⋃
λ
∈
R
+
(
T
)
‍
epi
⁡
(
f
+
δ
C
+
∑
t
∈
T
‍
λ
t
f
t
)
0
*
,
thanks to the assumed quasi-(
WEHP
). This implies that there exists λ
∈
R
+
(
T
) such that
(43)
(
0
,
-
f
(
x
0
)
)
∈
epi
⁡
(
f
+
δ
C
+
∑
t
∈
J
‍
λ
t
f
t
)
0
*
,
where J
⊆
T is a finite subset and (
λ
t
)
∈
R
+
(
T
) with J
=
{
t
∈
T
:
λ
t
≠
0
}. By definition, (43) is equivalent to
(44)
(
f
+
δ
C
+
∑
t
∈
J
‍
λ
t
f
t
)
(
x
)
≥
f
(
x
0
)
≥
(
f
+
δ
C
+
∑
t
∈
J
‍
λ
t
f
t
)
(
x
0
)
ddddddddddddddddddddddddddddddd
j
j
jj
.
for
each
x
∈
X
,
where the last inequality holds because f
t
(
x
0
)
≤
0 for each t
∈
J, while, by (19), (44) holds if and only if
(45)
0
∈
∂
*
(
f
+
δ
C
+
∑
t
∈
J
‍
λ
t
f
t
)
(
x
0
)
.
Below we show that J
⊆
T
(
x
0
). Note by (43) that
(46)
(
f
+
δ
C
+
∑
t
∈
J
‍
λ
t
f
t
)
0
*
(
0
)
≤
-
f
(
x
0
)
,
while, by definition,
(47)
(
f
+
δ
C
+
∑
t
∈
J
‍
λ
t
f
t
)
0
*
(
0
)
≥
-
(
f
+
δ
C
+
∑
t
∈
J
‍
λ
t
f
t
)
(
x
0
)
.
Hence, by the above inequalities, one has that
(48)
(
f
+
δ
C
+
∑
t
∈
J
‍
λ
t
f
t
)
(
x
0
)
≥
f
(
x
0
)
.
Since λ
t
>
0 and f
t
(
x
)
≤
0 for each t
∈
J, this implies that λ
t
f
t
(
x
)
=
0; that is, f
t
(
x
)
=
0 for each t
∈
J. Thus J
⊆
T
(
x
), and hence, (39) holds.
Conversely, suppose that0
∈
Im
⁡
∂
*
(
f
+
δ
A
). To show the quasi-(
WEHP
), by Remark 7, we only need to show (38) holds. To do this, note that 0
∈
Im
⁡
∂
*
(
f
+
δ
A
). Then there exists x
0
∈
dom
⁡
f
∩
A such that
(49)
0
∈
∂
*
(
f
+
δ
A
)
(
x
0
)
⊆
⋃
λ
∈
R
+
(
T
)
∑
t
∈
T
λ
t
f
t
(
x
0
)
=
0
∂
*
(
f
+
δ
C
+
∑
t
∈
T
‍
λ
t
f
t
)
(
x
0
)
,
thanks to the assumed quasi-(
WBCQ
). Therefore, there exists λ
∈
R
+
(
T
) such that
(50)
x
*
∈
∂
*
(
f
+
δ
C
+
∑
t
∈
T
‍
λ
t
f
t
)
(
0
)
with
(51)
∑
t
∈
T
‍
λ
t
f
t
(
x
0
)
=
0
.
These two relations imply that
(52)
f
(
x
0
)
+
(
f
+
δ
C
+
∑
t
∈
T
‍
λ
t
f
t
)
0
*
(
0
)
=
0
.
Moreover, since 0
∈
∂
*
(
f
+
δ
A
)
(
x
0
), it follows that
(53)
f
(
x
0
)
+
(
f
+
δ
A
)
0
*
(
0
)
=
0
.
Combining (53) with (52), we have that
(54)
(
f
+
δ
A
)
0
*
(
0
)
=
(
f
+
δ
C
+
∑
t
∈
T
‍
λ
t
f
t
)
0
*
(
0
)
.
Hence, for each r
∈
R satisfying (
0
,
r
)
∈
epi
⁡
(
f
+
δ
A
)
0
*, we have
(55)
(
0
,
r
)
∈
epi
⁡
(
f
+
δ
C
+
∑
t
∈
T
‍
λ
t
f
t
)
0
*
⊆
⋃
λ
∈
R
+
(
T
)
‍
epi
⁡
(
f
+
δ
C
+
∑
t
∈
T
‍
λ
t
f
t
)
0
*
.
Thus, (38) holds and the proof is complete.


## 4. Strong and Total Lagrange Dualities for Infinite Quasiconvex Programming

Consider the following quasiconvex programming:(56)
(
P
)
sssss
Minimize
f
(
x
)
,
iiiiii
s
.
t
.
iiiiiiiiiii
l
f
t
(
x
)
≤
0
,
t
∈
T
,
j
j
j
j
j
j
j
j
g
g
g
g
g
g
g
g
x
∈
C
.Its dual problem is defined by(57)
(
D
)
sup
⁡
λ
∈
R
+
(
T
)
inf
⁡
x
∈
C
{
f
(
x
)
+
∑
t
∈
T
‍
λ
t
f
t
(
x
)
}
.
We denote by v
(
P
) and v
(
D
) the optimal objective values of (
P
) and (
D
), respectively. Clearly, v
(
P
)
≥
v
(
D
); that is, the weak Lagrange duality holds between (
P
) and (
D
). We say that the strong Lagrange duality between (
P
) and (
D
) holds if there is no duality gap (i.e., v
(
P
)
=
v
(
D
)) and the dual problem (
D
) has an optimal solution. The following theorem gives some sufficient and necessary conditions to ensure that the strong Lagrange duality holds.Theorem 9.
The following statements are equivalent.(i)
For eachα
∈
R,
(58)
(
0
,
-
α
)
∈
epi
⁡
(
f
+
δ
A
)
0
*
⟺
[
∑
t
∈
T
‍
∃
(
λ
t
)
t
∈
T
∈
R
+
(
T
)
s
.
t
.
(
0
,
-
α
)
fffffffff
gg
∈
epi
⁡
(
f
+
δ
C
+
∑
t
∈
T
‍
λ
t
f
t
)
0
*
]
.
(ii)
The family{
δ
C
;
f
t
:
t
∈
T
} has the quasi-(
W
E
H
P
).
(iii)
The strong Lagrange duality holds between(
P
) and (
D
).Proof.
It is evident that (i)⇔(ii). Below we show that (i) ⇔(iii). To do this, note that, for each α
∈
R,
(59)
(
0
,
-
α
)
∈
epi
⁡
(
f
+
δ
A
)
0
*
⟺
(
f
+
δ
A
)
0
*
(
0
)
≤
-
α
⟺
f
(
x
)
≥
α
for
each
x
∈
A
,
(
0
,
-
α
)
∈
⋃
λ
∈
R
+
(
T
)
‍
epi
⁡
(
f
+
δ
C
+
∑
t
∈
T
‍
λ
t
f
t
)
0
*
⟺
∃
(
λ
t
)
t
∈
T
∈
R
+
(
T
)
,
gggg
kk
s
.
t
.
f
(
x
)
+
∑
t
∈
T
‍
λ
t
f
t
(
x
)
≥
α
for
each
x
∈
C
.
Suppose that (i) holds. Letr
:
=
v
(
P
)
∈
R (if v
(
P
)
=
-
∞, then the result holds trivially). Then, by (59), (
0
,
-
r
)
∈
epi
⁡
(
f
+
δ
A
)
0
* and (
0
,
-
r
)
∈
⋃
λ
∈
R
+
(
T
)
‍
epi
⁡
(
f
+
δ
C
+
∑
t
∈
T
‍
λ
t
f
t
)
0
* by (i). Hence, using (59) and the definition of v
(
D
), we see that v
(
D
)
≥
r and the problem (
D
) has an optimal solution. This together with the weak Lagrange duality implies that the strong Lagrange duality holds.
Conversely, suppose that the strong Lagrange duality holds. To show (i), by Remark7, we only need to show that (38) holds. To do this, let (
0
,
-
r
)
∈
epi
⁡
(
f
+
δ
A
)
0
*. Then, by (59), v
(
p
)
≥
r and v
(
D
)
≥
r by (iii). Hence, by (59), we see that (
0
,
-
r
)
∈
⋃
λ
∈
R
+
(
T
)
‍
epi
⁡
(
f
+
δ
C
+
∑
t
∈
T
‍
λ
t
f
t
)
0
*. Therefore, (38) is proved and the proof is complete.The following two examples illustrate Theorem9.Example 10.
LetX
=
C
:
=
R and let T
:
=
{
1
}. Define the function f, f
1
:
R
→
R by
(60)
f
(
x
)
:
=
{
1
,
x
≥
0
,
0
,
x
<
0
,
f
1
(
x
)
:
=
x
2
-
1
for
each
x
∈
R
.
Then f is quasiconvex and A
=
[
-
1,1
]. Note that, for each x
∈
R and each λ
≥
0,
(61)
(
f
+
δ
A
)
(
x
)
=
{
1
,
0
≤
x
≤
1
,
0
,
-
1
≤
x
<
0
,
+
∞
,
x
>
1
or
x
<
-
1
,
(
f
+
δ
C
+
λ
f
1
)
(
x
)
=
{
1
+
λ
(
x
2
-
1
)
,
x
≥
0
,
λ
(
x
2
-
1
)
,
x
<
0
.
Then for each x
*
∈
R, it is easy to see that
(62)
(
f
+
δ
A
)
0
*
(
x
*
)
=
-
inf
⁡
{
(
f
+
δ
A
)
(
x
)
:
x
*
x
≥
0
}
=
{
-
1
,
x
*
>
0
,
0
,
x
*
≤
0
,
and for each λ
≥
0,
(63)
(
f
+
δ
C
+
λ
f
1
)
0
*
(
x
*
)
=
-
inf
⁡
{
(
f
+
δ
C
+
λ
f
1
)
(
x
)
:
x
*
x
≥
0
}
=
{
-
1
+
λ
,
x
*
>
0
,
λ
,
x
*
≤
0
.
Hence,
(64)
epi
⁡
(
f
+
δ
A
)
0
*
=
⋃
λ
≥
0
‍
epi
⁡
(
f
+
δ
C
+
λ
f
1
)
0
*
=
(
(
-
∞
,
0
]
×
R
+
)
∪
(
(
0
,
+
∞
)
×
[
-
1
,
+
∞
)
)
.
Therefore, by Theorem 9, we see that the strong Lagrange duality holds. In fact, v
(
P
)
=
v
(
D
)
=
0 and λ
=
0 is an optimal solution to (
D
).Example 11.
LetX
=
C
:
=
R and let T
:
=
{
1
}. Define the function f, f
1
:
R
→
R by
(65)
f
(
x
)
:
=
{
1
,
x
≥
0
,
0
,
x
<
0
,
f
1
(
x
)
:
=
-
x
for
each
x
∈
R
.
Then f is quasiconvex and A
=
[
0
,
+
∞
). Note that, for each x
∈
R and each λ
≥
0,
(66)
(
f
+
δ
A
)
(
x
)
=
{
1
,
x
≥
0
,
+
∞
,
x
<
0
,
(
f
+
δ
C
+
λ
f
1
)
(
x
)
=
{
1
-
λ
x
,
x
≥
0
,
-
λ
x
,
x
<
0
.
Then for each x
*
∈
R, it is easy to see that
(67)
(
f
+
δ
A
)
0
*
(
x
*
)
=
-
inf
⁡
{
(
f
+
δ
A
)
(
x
)
:
x
*
x
≥
0
}
=
-
1
,
and for each λ
≥
0,
(68)
(
f
+
δ
C
+
λ
f
1
)
0
*
(
x
*
)
=
-
inf
⁡
{
(
f
+
δ
C
+
λ
f
1
)
(
x
)
:
x
*
x
≥
0
}
=
{
-
1
,
x
*
>
0
,
λ
=
0
,
+
∞
,
x
*
>
0
,
λ
>
0
,
0
,
x
*
≤
0
.
Hence,
(69)
epi
⁡
(
f
+
δ
A
)
0
*
=
R
×
[
-
1
,
+
∞
)
,
⋃
λ
≥
0
‍
epi
⁡
(
f
+
δ
C
+
λ
f
1
)
0
*
=
(
(
0
,
+
∞
)
×
[
-
1
,
+
∞
)
)
∪
(
(
-
∞
,
0
]
×
[
0
,
+
∞
)
)
.
Therefore, the quasi-(
WEHP
) does not hold and, by Theorem 9, the strong Lagrange duality does not hold (in fact, v
(
P
)
=
1 and v
(
D
)
=
-
∞).Remark 12.
(a) In [5, Theorem  5.1], the authors showed that the strong Lagrange duality holds between (
P
) and (
D
) if and only if the following condition holds:
(70)
(
iv
)
epi
⁡
(
f
+
δ
A
)
*
∩
(
{
0
}
×
R
)
=
⋃
λ
∈
R
+
(
T
)
‍
epi
⁡
(
f
+
δ
C
+
∑
t
∈
T
‍
λ
t
f
t
)
*
∩
(
{
0
}
×
R
)
.
Thus, by Theorem 9, the statements (i), (ii), and (iii) of Theorem 9 are equivalent to (iv).
(b) Recall from [5] that the stable strong Lagrange duality holds between (
P
) and (
D
) if, for each p
*
∈
X
*, the following equality holds:
(71)
inf
⁡
x
∈
A
{
f
(
x
)
+
〈
p
,
x
〉
}
=
max
⁡
λ
∈
R
+
(
T
)
inf
⁡
x
∈
C
{
f
(
x
)
+
〈
p
,
x
〉
+
∑
t
∈
T
‍
λ
t
f
t
(
x
)
}
.
In [5], the authors show that the stable strong Lagrange duality holds if and and only if the family {
δ
C
;
f
t
:
t
∈
T
} has the conical (
WEHP
)
f; that is,
(72)
epi
⁡
(
f
+
δ
A
)
*
=
⋃
λ
∈
R
+
(
T
)
‍
epi
⁡
(
f
+
δ
C
+
∑
t
∈
T
‍
λ
t
f
t
)
*
.
Naturally, we wonder if the equivalence still holds if we replace the convex conjugate function by the z-quasi-conjugate function. However, the following example shows that the stable strong Lagrange duality is not equivalent to
(73)
epi
⁡
(
f
+
δ
A
)
0
*
=
⋃
λ
∈
R
+
(
T
)
‍
epi
⁡
(
f
+
δ
C
+
∑
t
∈
T
‍
λ
t
f
t
)
0
*
.Example 13.
LetX
=
C
:
=
R and T
:
=
{
1
}. Define f, f
1
:
R
→
R as in Example 10. Then by (64), we see that (73) holds. However, it is easy to see that, for each y
∈
R,
(74)
(
f
+
δ
A
)
*
(
y
)
=
{
y
-
1
,
y
≥
1
,
0
,
0
≤
y
<
1
,
-
y
,
y
<
0
and, for each λ
>
0,
(75)
(
f
+
δ
C
+
λ
f
1
)
*
(
y
)
=
y
2
4
λ
+
λ
.
Thus,
(76)
epi
⁡
(
f
+
δ
A
)
*
=
{
(
x
,
y
)
∈
R
2
:
x
≥
1
,
y
≥
x
-
1
}
∪
(
[
0,1
)
×
R
+
)
∪
{
(
x
,
y
)
∈
R
2
:
x
<
0
,
y
≥
-
x
}
,
⋃
λ
≥
0
‍
epi
⁡
(
f
+
δ
C
+
λ
f
1
)
*
=
(
R
×
(
0
,
+
∞
)
)
∪
(
{
0
}
×
R
+
)
.
This implies that
(77)
epi
⁡
(
f
+
δ
A
)
*
≠
⋃
λ
≥
0
‍
epi
⁡
(
f
+
δ
C
+
λ
f
1
)
*
.
Hence, by [5, Theorem  5.2], the stable strong duality does not hold. Therefore, the stable strong Lagrange duality and (73) are not equivalent.
In the remainder of this section, we study the total Lagrange duality problem; that is, when does the strong duality hold between(
P
) and (
D
) (assuming that ∅
≠
S
(
P
)
:
=
{
y
∈
A
:
f
(
x
)
=
min
⁡
x
∈
A
f
(
x
)
})? Obviously, if the strong duality holds between (
P
) and (
D
), then so does the total duality. Hence, if one of conditions in Theorem 9 holds, then the total duality holds. Below we give some sufficient and necessary conditions to ensure that the total duality holds.Theorem 14.
The following assertions are equivalent.(i)
The total Lagrange duality holds between(
P
) and (
D
).
(ii)
For eachx
∈
dom
⁡
f
∩
A,
(78)
0
∈
∂
*
(
f
+
δ
A
)
(
x
)
⟺
0
∈
⋃
λ
∈
R
+
(
T
)
∑
t
∈
T
λ
t
f
t
(
x
)
=
0
∂
*
(
f
+
δ
C
+
∑
t
∈
T
‍
λ
t
f
t
)
(
x
)
.
(iii)
For eachx
∈
dom
⁡
f
∩
A,
(79)
∂
*
(
f
+
δ
A
)
(
x
)
=
⋃
λ
∈
R
+
(
T
)
∑
t
∈
T
λ
t
f
t
(
x
)
=
0
∂
*
(
f
+
δ
C
+
∑
t
∈
T
‍
λ
t
f
t
)
(
x
)
=
X
*
.
(iv)
The family{
δ
C
;
f
t
:
t
∈
T
} has the quasi-(
W
B
C
Q
).Proof.
It is evident that (ii)⇔(iv). Note that
(80)
0
∈
∂
*
(
f
+
δ
A
)
(
x
)
⟺
∂
*
(
f
+
δ
A
)
(
x
)
=
X
*
,
0
∈
⋃
λ
∈
R
+
(
T
)
∑
t
∈
T
λ
t
f
t
(
x
)
=
0
∂
*
(
f
+
δ
C
+
∑
t
∈
T
‍
λ
t
f
t
)
(
x
)
⟺
⋃
λ
∈
R
+
(
T
)
∑
t
∈
T
λ
t
f
t
(
x
)
=
0
∂
*
(
f
+
δ
C
+
∑
t
∈
T
‍
λ
t
f
t
)
(
x
)
=
X
*
.
Hence, (ii) ⇔(iii). Suppose that (iv) holds. Let f
(
x
0
)
=
min
⁡
x
∈
A
f
(
x
). Then by (19), 0
∈
∂
*
(
f
+
δ
A
)
(
x
0
). This implies that 0
∈
Im
⁡
∂
*
(
f
+
δ
A
). Hence, by Proposition 8, the quasi-(
WEHP
) holds and by Theorem 9, the strong Lagrange duality holds between (
P
) and (
D
). Therefore, (i) holds and the implication (iv) ⇒ (i) is proved. Below we only need to show that (i) ⇒ (iv). To do this, assume that (i) holds. Let x
0
∈
dom
⁡
f
∩
A. To show the quasi-(
WBCQ
), it suffices by Remark 7 to show that (39) holds with x
0 in place of x. To do this, let 0
∈
∂
*
(
f
+
δ
A
)
(
x
0
). Then by (19), f
(
x
0
)
=
min
⁡
x
∈
A
f
(
x
). Since the strong duality holds between (
P
f
) and (
D
), it follows that there exists λ
∈
R
+
(
T
) such that
(81)
f
(
x
0
)
=
inf
⁡
x
∈
C
{
f
(
x
)
+
∑
t
∈
T
‍
λ
t
f
t
(
x
)
}
≤
f
(
x
0
)
+
∑
t
∈
T
‍
λ
t
f
t
(
x
0
)
≤
f
(
x
0
)
,
where the last inequality holds because x
0
∈
A. Hence, ∑
t
∈
T
‍
λ
t
f
t
(
x
0
)
=
0 and it follows that
(82)
(
f
+
δ
C
+
∑
t
∈
T
‍
λ
t
f
t
)
(
x
0
)
≤
(
f
+
δ
C
+
∑
t
∈
T
‍
λ
t
f
t
)
(
x
)
fffffffffffffffffffffffffffffffffffffffffffffffff
for
each
x
∈
X
,
which by (19) implies that 0
∈
∂
*
(
f
+
δ
C
+
∑
t
∈
T
‍
λ
t
f
t
)
(
x
0
). Therefore, (39) holds and the proof is complete.Corollary 15.
Suppose that there existsx
0
∈
dom
⁡
f
∩
A such that ∂
*
f
(
x
0
)
∩
(
-
N
A
(
x
0
)
)
≠
∅. Then, for (
P
) and (
D
), the total Lagrange duality holds if and only if the strong Lagrange duality holds.Proof.
Letx
*
∈
∂
*
f
(
x
0
)
∩
(
-
N
A
(
x
0
)
)
≠
∅. Then, by definition,
(83)
∀
x
∈
X
,
〈
x
*
,
x
-
x
0
〉
≥
0
⟹
f
(
x
)
≥
f
(
x
0
)
,
〈
x
*
,
x
-
x
0
〉
≥
0
for
each
x
∈
A
.
Hence, x
0 is a minimizer of f on A. This implies that 0
∈
∂
*
(
f
+
δ
A
)
(
x
0
). Thus, by Proposition 8, the quasi-(
WEHP
) and the quasi-(
WBCQ
) are equivalent. Therefore, by Theorems 9 and 14, the result is seen to hold.



---

*Source: 453912-2014-05-22.xml*