Stable Zero Lagrange Duality for DC Conic Programming
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
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., [1–8] and the other references therein).
Recently, the zero duality, that is, only the situation when v(𝒫) = v(𝒟), has received much attention (e.g., see [9–13] 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.
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 x ∈ X, that is, 〈x*, x〉 = x*(x). Let Z be a set in X. The closure of Z is denoted by cl Z. If W⊆X*, 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.
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
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)
epi h⋄ is a convex cone.
- (iii)
and .
Example 3.2. Let X = Y = C : = ℝ and S = [0, +∞). Define by f = h : = δ(−∞,0], p = 0 and for each x ∈ ℝ,
Below we give a sufficient condition to ensure that (3.11) holds.
Proof. Let p ∈ X*. Then for each u* ∈ dom g* and λ ∈ S⊕, one has by (2.5) that for each x ∈ X,
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 p ∈ X*, 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
Proof. To show the equivalence of (CQ) and (3.20), we only need to show that
Proof. Suppose that C1(f, A) holds. Note by the definition h⋄ that (λh) * ≥ h⋄ for each λ ∈ S⊕. Then and
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 epi f* = (−∞, 0]×[0, +∞) and A : = {x ∈ C : h(x)∈−S} = {0}. Hence, epi (f + δA) * = ℝ × [0, +∞). Moreover, it is easy to see that for each x* ∈ ℝ,
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
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 p ∈ X* and r ∈ ℝ. Suppose that the family {f, g, δC, h} satisfies (CQ). Consider the following statements.
- (i)
For each x ∈ A, f(x) − g(x)−〈p, x〉≥−r.
- (ii)
.
- (iii)
For each ϵ > 0 and for each u* ∈ dom g*, there exists λ ∈ S⊕ such that
()
Proof. Consider (i)⇒(ii). Suppose that (i) holds. Then for each x ∈ A, f(x) + δA(x) ≥ g(x)+〈p, x〉−r. Thus, by (2.7) and the assumed (CQ),
Consider (ii)⇒(iii). Suppose that (ii) holds. Let u* ∈ dom g* be arbitrary. Then,
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.
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).
- (a)
cont f∩A ≠ ∅ and cont h∩A ≠ ∅;
- (b)
cont h∩A∩int C ≠ ∅.
Proof. Consider (i)⇒ (ii). Suppose that (i) holds. Let p ∈ X*. 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
Corollary 3.13. Suppose that
- (i)
The family {f, g, h} satisfies (CQ), that is,
() - (ii)
For each p ∈ X*,
()
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 h∩A ≠ ∅. Then the following statements are equivalent.
- (i)
The condition (CQ1) holds.
- (ii)
If the proper lsc convex function φ is such that
()
- (iii)
If the proper lsc convex function φ is continuous at some point in A, then (3.65) holds.
- (iv)
If p ∈ X*, 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
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
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.
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).