Volume 2012, Issue 1 606457
Research Article
Open Access

Stable Zero Lagrange Duality for DC Conic Programming

D. H. Fang

Corresponding Author

D. H. Fang

College of Mathematics and Statistics, Jishou University, Jishou 416000, China jsu.edu.cn

Search for more papers by this author
First published: 29 November 2012
Academic Editor: Abdel-Maksoud A. Soliman

Abstract

We consider the problems of minimizing a DC function under a cone-convex constraint and a set constraint. By using the infimal convolution of the conjugate functions, we present a new constraint qualification which completely characterizes the Farkas-type lemma and the stable zero Lagrange duality gap property for DC conical programming problems in locally convex spaces.

1. Introduction

Let X and Y be real locally convex Hausdorff topological vector spaces and CX be a nonempty convex set. Let SY be a closed convex cone and S the positive dual cone of S. Let be a proper function and h : XY be an S-convex mapping with respect to the cone S. Consider the conic programming problem
()
Its Lagrange dual problem can be expressed as
()

It is well know that the optimal values of these problems, v(𝒫), and v(𝒟) respectively, satisfy the so-called weak duality, that is, v(𝒫) ≥ v(𝒟), but a duality gap may occur, that is, we may have v(𝒫) > v(𝒟). A challenge in convex analysis has been to give sufficient conditions which guarantee the strong duality, that is, v(𝒫) = v(𝒟) and the dual problem (𝒟) has at least an optimal solution. In the case when φ is a proper convex function, numerous conditions have been given in the literature ensuring the strong duality (see, e.g., [18] and the other references therein).

Recently, the zero duality, that is, only the situation when v(𝒫) = v(𝒟), has received much attention (e.g., see [913] and references therein). Obviously, the strong duality implies the zero duality. However, the converse implication does not always hold. As mentioned in [10], the question of finding condition, which ensures the zero duality, is not only important for understanding the fundamental feature of convex programming but also for the efficient development of numerical schemes. Some sufficient conditions and characterizations in terms of the optimal value function of (𝒫) for the zero duality have been given in [12], and some convex programming problems which enjoy zero duality have been studied in [13]. Especially, in the case when φ is lower semicontinuous (lsc in brief) convex, h is star lsc and C is closed; Jeyakumar and Li in [10] presented some constraint qualifications which completely characterize the zero duality for convex programming problems in Banach spaces; they established necessary and sufficient dual conditions for the stable zero duality in [11] under the assumptions that C = X and h is continuous.

Observe that most works dealing with problem (1.1) in the literature mentioned above were done under the assumptions that the involved functions are convex and lsc. In this paper, we consider the following DC conical programming:
()
and its dual problem
()
where are proper convex functions. As pointed out in [14], problems of DC programming are highly important from both viewpoints of optimization theory and applications, and they have been extensively studied in the literature (cf. [1421] and the references therein). Here and throughout the whole paper, following [22, page 39], we adopt the convention that (+)+(−) = (+)−(+) = +, 0 · (+) = + and 0 · (−) = 0. Then, for any two proper convex functions , we have that
()
hence,
()

The purpose of this paper is to study the stable zero duality. Our main contribution is to provide complete characterizations for the stable zero duality between (P) and (D) via the newly constraint qualifications. In general, we only assume that f, g are proper convex and h is S-convex (not necessarily lsc).

The paper is organized as follows. The next section contains some necessary notations and preliminary results. The Farkas-type lemma and the stable zero duality between (P) and (D) are considered in Section 3.

2. Notations and Preliminary Results

The notation used in the present paper is standard (cf. [22]). In particular, we assume throughout the whole paper that X and Y are real locally convex Hausdorff topological vector spaces, and let X* denote the dual space, endowed with the weak*-topology w*(X*, X). By 〈x*, x〉, we will denote the value of the functional x*X* at xX, that is, 〈x*, x〉 = x*(x). Let Z be a set in X. The closure of Z is denoted by cl Z. If WX*, then cl W denotes the weak*-closure of W. For the whole paper, we endow X* × with the product topology of w*(X*, X) and the usual Euclidean topology.

The indicator function δZ of the nonempty set Z is defined by
()
Let be a proper convex function. The effective domain, the conjugate function, and the epigraph of f are denoted by dom  f, f* and epif, respectively; they are defined by
()
It is well known and easy to verify that epif* is weak*-closed. The lsc hull of f, denoted by cl f, is defined by
()
Then (cf. [22, Theorems 2.3.1]),
()
By definition, the Young-Fenchel inequality below holds:
()
If g, h are proper, then
()
()
Moreover, if g is convex and lsc on dom h, then the same argument for the proof of [21, Lemma 2.3] shows that
()
Furthermore, we define the infimal convolution of g and h as the function gh : X ∪ {±} given by
()
If g and h are lsc and dom g∩dom h, then by [22], we have that
()
Moreover, we also have
()
Note that an element pX* can be naturally regarded as a function on X in such a way that
()
Thus, the following facts are clear for any a and any function :
()
()

We end this section with a lemma, which is known in [3, 22].

Lemma 2.1. Let be proper convex functions satisfying dom g∩dom h.

  • (i)

    If g, h are lsc, then

    ()

  • (ii)

    If either g or h is continuous at some point of dom g∩dom h, then

    ()

3. Characterizations for the Stable Zero Duality

Throughout this section, let X, Y be locally convex spaces and CX be a nonempty convex set. Let SY be a closed convex cone. Its dual cone S is defined by
()
Define an order on Y by saying that y ≤S  x if yx ∈ −S. We attach a greatest element with respect to ≤S and denote Y : = Y ∪ {+}. The following operations are defined on Y: for any yY, y + = + y = and t = for any t ≥ 0. Let be proper convex functions such that cl g and fg are proper, and h : XY be S-convex in the sense that for every u, v ∈ dom G and every t ∈ [0,1],
()
(see [6]). Let λS and let dom h : = {xX : h(x) ∈ Y} ≠ . As in [3], we define for each λS,
()
It is easy to see that h is S-convex if and only if is a convex function for each λS. Following [10], we define the function by
()
Let h−1(−S): = {x ∈ dom g : h(x)∈−S}. Recall from [19, 23] that G is said to be star lsc if λG is lsc on X for each λS and to be S-epi-closed if epiS (G) is closed, where
()
It is known (cf. [23]) that if G is star lsc, then it is S-epi-closed. Let A denote the solution set of the system {xC; h(x)∈−S}, that is,
()
To avoid trivially, we always assume that A.

The following lemma, which is taken from [10, Theorem 3.1], will be useful in our study.

Lemma 3.1. Suppose that h is a proper star lsc and S-convex mapping with h−1(S) ≠ . Then

  • (i)

    h is a proper convex function on X*.

  • (ii)

    epih is a convex cone.

  • (iii)

    and .

Let pX*. Consider the primal problem
()
and its dual problem of (Pp)
()
In the case when p = 0, problem (Pp) and its dual problem (Dp) are reduced to problem (P) and its dual problem (D) defined in (1.1) and (1.2), respectively. Let v(Pp) and v(Dp) denote the optimal values of (Pp) and (Dp), respectively. Let r, then by the definition of conjugate function, one has that
()
Moreover, in the case when g is lsc, then for each xX,
()
thus, it is easy to see that the following inequality holds:
()
that is, the stable weak Lagrange duality holds. However, (3.11) does not necessarily hold in general as showed in the following example.

Example 3.2. Let X = Y = C : = and S = [0, +). Define by f = h : = δ(−,0], p = 0 and for each x,

()
(note that g is not lsc at x = 0). Then A = (−, 0] and v(P) = −2. Note that for each S = [0, +),
()
Then v(D) = 0 > v(P). This means that (3.11) does not hold.

Below we give a sufficient condition to ensure that (3.11) holds.

Lemma 3.3. Suppose that the following condition holds:

()
Then (3.11) holds.

Proof. Let pX*. Then for each u* ∈ dom g* and λS, one has by (2.5) that for each xX,

()
where the last inequality holds because δC + λgδA for each λS. Note that the above inequalities hold for each u* ∈ dom g*. Then for each xX,
()
where the last equality holds by (3.10). Hence,
()
which implies that (p, −v(Dp)) ∈ epi (f − cl g + δA) * and (p, −v(Dp)) ∈ epi (fg + δA) * by (3.14). Hence, by (3.9), one has v(Pp) ≥ v(Dp). Therefore, (3.11) holds by the arbitrary of pX*. The proof is complete.

Remark 3.4. Condition (3.14) was introduced in [21] and was called (LSC) there. Obviously, if g is lsc on A, then (3.14) holds. But the converse is not true in general as showed by [21, Example 4.1].

This section is devoted to the study of the zero dualities between (P) and (D), which is defined as follows.

Definition 3.5. We say that

  • (a)

    the zero duality holds between (P) and (D) if v(P) = v(D);

  • (b)

    the stable zero duality holds between (P) and (D) if for each pX*, the zero duality holds between (Pp) and (Dp).

Definition 3.6. We say the family {f, g, δC, h} satisfies the constraint qualification (CQ) if

()

The following proposition provides an equivalent condition for (CQ) to hold.

Proposition 3.7 3.7. Suppose that (3.14) holds (e.g., g is lsc) and that

()
Then the family {f, g, δC, h} satisfies (CQ) if and only if
()

Proof. To show the equivalence of (CQ) and (3.20), we only need to show that

()
To do this, by (3.19) and the fact (2.11), it is easy to see that the following inclusion holds:
()
Note that A is closed and so δA is lsc. Then by Lemma 3.1(c), one has that
()
where the last inclusion holds by Lemma 2.1(i). Therefore,
()
where the first equality holds by (2.8) and the last equality holds by (3.14). Hence, (3.21) holds and the proof is complete.

Below we give another sufficient conditions ensuring (CQ). For the study of the Lagrange duality and the Fenchel-Lagrange duality, the authors in [3] introduced the following condition:
()
This condition was also introduced independently but with different terminologies “C1(f, A)" and “(CC)" in [24], under the assumptions
()
and [19, 20] (under the assumptions (3.26) together with the star lsc of h), respectively.

Proposition 3.8. Suppose that (3.14) and (3.19) hold. Then

()

Proof. Suppose that C1(f, A) holds. Note by the definition h that (λh) *h for each λS. Then and

()
Hence, by (2.11), one has that
()
This together with the C1(f, A) implies that
()
Thus, by (2.8) and (3.14), we can obtain that
()
Hence, by Proposition 3.7, (CQ) holds and the proof is complete.

The converse of Proposition 3.8 does not necessarily hold, even in the case when g = 0, as showed in the following example.

Example 3.9. Let X = Y = C : = and S = [0, +). Let be defined by f : = δ[0,+), g : = 0 and h(x) = x2 for each x. Then epif* = (−, 0]×[0, +) and A : = {xC : h(x)∈−S} = {0}. Hence, epi (f + δA) * = × [0, +). Moreover, it is easy to see that for each x*,

()
Then, h = 0. This implies that epih = × [0, +). Hence,
()
This means that (CQ) holds (noting that dom g* = {0}). However, note that
()
Then
()
and so the C1(f, A) does not hold.

Proposition 3.10. Let g = 0. Suppose that (3.19) holds. Then the family {f, g, δC, h} satisfies (CQ) if and only if is weak*-closed.

Proof. Since f is lsc and A is closed, it follows from Lemma 2.1(i) that

()
while the last equality holds by Lemma 3.1(c). Note by (2.11) that
()
Hence, by (3.36), one has that
()
This together with (3.23) implies that
()
Thus, the result is seen to hold.

The following theorem provides a Farkas-type lemma for the DC optimization problem (3.7) in terms of the condition (CQ).

Theorem 3.11. Let pX* and r. Suppose that the family {f, g, δC, h} satisfies (CQ). Consider the following statements.

  • (i)

    For each xA, f(x) − g(x)−〈p, x〉≥−r.

  • (ii)

    .

  • (iii)

    For each ϵ > 0 and for each u* ∈ dom g*, there exists λS such that

    ()

Then (i)⇒ (ii)⇒ (iii). Furthermore, if (3.14) holds, then (i)⇔(ii)⇔(iii).

Proof. Consider (i)⇒(ii). Suppose that (i) holds. Then for each xA, f(x) + δA(x) ≥ g(x)+〈p, x〉−r. Thus, by (2.7) and the assumed (CQ),

()
while by (2.14), one has that
()
Hence, (ii) holds.

Consider (ii)⇒(iii). Suppose that (ii) holds. Let u* ∈ dom g* be arbitrary. Then,

()
that is,
()
This means that for each ϵ > 0, there exist such that
()
Moreover, by the definition of the function h, there exists λS such that
()
Hence,
()
Therefore, by the Young-Fenchel inequality (2.5), one sees that for each xX,
()
Note that the above inequalities and the equality hold for each xX, it follows that
()
Hence, (ii) holds.

Furthermore, suppose that (3.14) holds. Then the weak duality holds between (Pp) and (Dp), that is, v(Dp) ≤ v(Pp). Below we show that (iii)⇒(i). To do this, assume that (iii) holds. Then by the definition of v(Dp), one has that v(Dp)≥−rϵ and v(Dp)≥−r by the arbitrary of ϵ. Thus, by the weak duality holds between (Pp) and (Dp), one has that v(Pp)≥−r. Hence, (i) holds and the proof is complete.

Let cont h denote the set of all points at which h is continuous, that is,
()
The following theorem shows that the condition (CQ) is equivalent to the stable zero duality.

Theorem 3.12. Suppose that (3.14) holds. Consider the following statements.

  • (i)

    The family {f, g, δC, h} satisfies (CQ).

  • (ii)

    The stable zero duality holds between (P) and (D).

Then (i)⇒ (ii). Furthermore, (i)⇔ (ii) if (3.19) holds and one of the following conditions holds:
  • (a)

    cont fA and cont hA;

  • (b)

    cont hA∩int C.

Proof. Consider (i)⇒ (ii). Suppose that (i) holds. Let pX*. If v(Pp) = −, then the stable zero duality holds between (P) and (D) trivially. Below we assume that −r : = v(Pp) ∈ . Then by the implication (i)⇒(ii) of Theorem 3.11, one has that v(Dp)≥−r. Hence, v(Dp) ≥ v(Pp) and, by Lemma 3.3, v(Pp) = v(Dp). Thus, (ii) holds.

Furthermore, suppose that (3.19) holds and one of the conditions (a) and (b) holds. Then, by Lemma 2.1(b), one has that

()
To show (i), by Proposition 3.7, it suffices to show that (3.20) holds. To do this, let (p, r) ∈ epi (fg + δA) *. Then, by (3.9), v(Pp)≥−r and hence v(Dp)≥−r by the stable zero duality between (P) and (D). Let ϵ > 0 and u* ∈ dom g*, then there exists such that
()
This implies that . Hence,
()
and by the arbitrary of ϵ, one has that
()
where the equality holds by (3.51). This together with (3.29) and (2.11) implies that
()
that is,
()
Hence, by the arbitrary of u*, we have that
()
Therefore, (3.20) holds and the proof is complete.

Recall that in the case when C = X and g = 0, under the assumptions that f is lsc and h is continuous, the authors establish in [11, Theorem 3.1] the equivalence between the stable zero duality and the following regularity condition:
In this case, by Proposition 3.10, the following equivalence holds:
()
Hence, the following corollary, which follows from Theorem 3.12, improves the result in [11, Theorem 3.1].

Corollary 3.13. Suppose that

()
Consider the following statements.
  • (i)

    The family {f, g, h} satisfies (CQ), that is,

    ()

  • (ii)

    For each pX*,

    ()

Then (i)⇒(ii). Furthermore, if (3.19) holds and cont gA, then (i)⇔(ii).

In the case when g = 0, the authors introduce in [10] the following condition:
to study the zero duality between (P) and (D). Under the assumptions that (3.19) holds and int (dom f)∩A, the authors in [10] establish the zero duality using the regularity condition (CQ1). In this case, by Lemma 2.1(b) and Lemma 3.1, we have that
()
This together with Proposition 3.7 implies that
()
By Theorem 3.12, we get the following corollary straightforwardly, which improves the corresponding result in [10, Theorem 4.1], since we do not need to assume that (3.19) holds and int (dom f)∩A.

Corollary 3.14. Suppose that the family {f, g, δC, h} satisfies (CQ). Then the zero duality holds between (P) and (D).

By Theorem 3.12, we have the following result, where the equivalences of (i), (iii), and (iv) are given in [10, Theorem 4.1].

Corollary 3.15. Suppose that C is closed, h is star lsc and that cont hA. Then the following statements are equivalent.

  • (i)

    The condition (CQ1) holds.

  • (ii)

    If the proper lsc convex function φ is such that

    ()

then
()
  • (iii)

     If the proper lsc convex function φ is continuous at some point in A, then (3.65) holds.

  • (iv)

     If pX*, then

    ()

Proof. Consider (i)⇒(ii). Suppose that (i) holds and let φ be such that (3.64) is satisfied. Then, it follows from Lemma 3.1(c) that

()
where the second equality holds by the condition (CQ1) and the last inclusion holds by (2.11). Hence, by Proposition 3.7(a) (note that g = 0), the (CQ) holds. Applying Corollary 3.14 to φ in place of f, we complete the proof of the implication (i)⇒(ii).

Consider (ii)⇒(iii). Note that (3.64) is satisfied if φ is continuous at some point in A (see Lemma 2.1(ii)). Thus, it is immediate that (ii)⇒(iii).

Consider (iii)⇒(iv). It is trivial.

Consider (iv)⇒(i). Suppose that (iv) holds. Then applying Theorem 3.12 to f = 0, one has that

()
Hence, by Lemma 3.1(c), we obtain that
()
that is, the (CQ1) holds.

Using the same argument, one can obtain a sufficient and necessary condition to ensure the zero duality between the primal problem and the Fenchel-Lagrange duality.

Theorem 3.16. Suppose that (3.14) holds. Consider the following statements.

  • (i)

    The family {f, g, δC, h} satisfies the following condition:

    ()

  • (ii)

    For pX*, the following equality holds:

    ()

Then (i)⇒ (ii). Furthermore, if (3.19) holds and either cont gC or dom g∩int C, then (i)⇔(ii).

Acknowledgments

The author is grateful to the anonymous reviewer for valuable suggestions and remarks helping to improve the quality of the paper. This author was supported in part by the National Natural Science Foundation of China (grant 11101186).

      The full text of this article hosted at iucr.org is unavailable due to technical difficulties.