Abstract
In this paper, we provide Lagrange-type duality theorems for mathematical programming problems with DC objective and constraint functions. The class of problems to which Lagrange-type duality theorems can be applied is broader than the class in the previous research. The main idea is to consider equivalent inequality systems given by the maximization of the original functions. In order to compare the present results with the previously reported results, we describe the difference between their constraint qualifications, which are technical assumptions for the duality.
Similar content being viewed by others
1 Introduction
Lagrange duality is very effective in solving convex programming problems with inequality constraints. Constraint qualifications, which are technical assumptions for Lagrange duality, play an essential role in proving its duality theorems. For convex functions \(f_{i}: \mathbb{R}^{n}\to \mathbb{R}\), \(i=1,\ldots ,m\), the inequality system \(\{f_{i}\le 0, i=1,\ldots ,m\}\) is said to have the Farkas-Minkowski property (FM, for short) if \(\operatorname {cone}\operatorname {co}\bigcup^{m}_{i=1}\operatorname {epi}f^{*} _{i}+\{0\}\times [0,+\infty )\) is closed. FM is well known as a necessary and sufficient constraint qualification for Lagrange duality; see [1]. Also it is easy to check that the system \(\{f_{i}\le 0, i=1,\ldots ,m\}\) has FM if and only if the system \(\{\max_{i=1,\ldots ,m}f_{i}\le 0\}\) has FM.
A function is said to be DC if it can be expressed as the difference of two convex functions. In this paper, we consider the following mathematical programming problem with DC objective and constraint functions:
where \(f_{i},g_{i}:\mathbb{R}^{n}\to \mathbb{R}\) are convex functions for each \(i=0,1,\ldots ,m\). For the inequality system \(\{f_{i}-g_{i} \le 0, i=1,\ldots ,m\}\), its constraint qualifications for Lagrange-type duality have been observed in [2, 3]. To our surprise, we can observe that such constraint qualifications of two DC inequality systems \(\{f_{i}-g_{i}\le 0, i=1,\ldots ,m\}\) and \(\{F-G\le 0\}\), where \(F=\max_{i=1,\ldots ,m}\{f_{i}+\sum_{j\ne i}g _{j}\}\) and \(G=\sum^{m}_{j=1}g_{j}\), have a difference in spite of the two systems being equivalent.
The purpose of this paper is to provide other Lagrange-type duality theorems for DC programming problems with equivalent DC inequalities. The class of problems to which Lagrange-type duality theorems can be applied is broader than the class in previous research. The main idea, motivated by the above observation, is to consider equivalent inequality systems given by the maximization of the original functions. In order to compare the present results with the previously reported results, we describe the difference between their constraint qualifications. The outline of the paper is as follows: In Section 2, we introduce definitions and preliminary results which will be used in this paper. In Section 3, we provide a Lagrange-type duality theorem for equivalent inequality system \(\{F-G\le 0\}\). We provide an application of this theorem and we describe the difference between the present and previous constraint qualifications. Also, we provide a unified Lagrange-type duality theorem which contains the present theorem and the previous results in [3]. In Section 4, we summarize our results. Finally, we give proofs of lemmas which will be used in the proof of the main result in the Appendix.
2 Notations and preliminaries
In this section, we describe our notations and present preliminary results. The inner product of two vectors x and y in the n-dimensional real Euclidean space \(\mathbb{R}^{n}\) will be denoted by \(\langle x,y \rangle \). For a set \(A\subseteq \mathbb{R}^{n}\), we shall denote the closure, convex hull, conical hull of A by clA, coA, and coneA, respectively. For a convex set \(C\subseteq \mathbb{R}^{n}\) and \(\alpha , \beta \in [0,+\infty )\), \((\alpha +\beta )C=\alpha C+ \beta C\), where \(\alpha A=\{\alpha x\mid x\in A\}\) and \(A+B=\{x+y\mid x\in A, y\in B\}\) for any \(\alpha \in \mathbb{R}\) and \(A, B\subseteq \mathbb{R}^{n}\). For an extended real-valued function \(f:\mathbb{R} ^{n}\to \mathbb{R}\cup \{+\infty \}\), the domain, the epigraph, and the conjugate function of f are defined by
The indicator function of \(A\subseteq \mathbb{R}^{n}\) is denoted by \(\delta_{A}\). For each \(x\in \operatorname{dom} f\), the subdifferential of the function f at x is the set
If \(x\in \operatorname{dom} f\), then \(f(x)+f^{*}(y)\ge \langle y,x \rangle \) (the Young-Fenchel inequality) holds for each \(y\in \mathbb{R}^{n}\) and
For two extended real-valued functions \(f, g:\mathbb{R}^{n}\to \mathbb{R}\cup \{+\infty \}\), the infimal convolution of f and g is defined by
For extended real-valued convex functions \(f_{i}:\mathbb{R}^{n}\to \mathbb{R}\cup \{+\infty \}\), \(i=1,\ldots ,m\), if \(\bigcap^{m} _{i=1}\operatorname {int}\operatorname{dom} f_{i}\ne \emptyset \), then
for all \(x\in \bigcap^{m}_{i=1}\operatorname{dom} f_{i}\) and for each \(y\in \partial (f_{1}+\cdots +f_{m})(x)\), there exists \(y_{i}\in \partial f_{i}(x)\) (\(i=1,\ldots ,m\)) such that
Hence
the infimal convolution is attained for all y; see [4]. It is easy to show that (3) implies that
When all \(f_{i}\) are real-valued convex functions,
holds; see Theorem 2.4.7 in [5]. The following theorem will be used in the proof of the main theorem.
Theorem 1
Sion, [6]
Let X be a convex set, Y be a compact convex set, \(f:X\times Y\to \mathbb{R}\), where \(f(x,\cdot )\) is usc concave on Y for each \(x\in X\) and \(f(\cdot ,y)\) is lsc convex on X for each \(y\in Y\). Then
3 Main results
We observe the following DC programming problem with inequality constraints:
where \(f_{i},g_{i}:\mathbb{R}^{n}\to \mathbb{R}\) are convex functions for each \(i=0,1,\ldots ,m\). First, we give a real-valued version of a previous Lagrange-type duality result for (P) in [3] as follows, where \(\operatorname{Val}(\mathrm{P})\) is the infimum value of (P):
Theorem 2
Harada, Kuroiwa, [3]
Let \(f_{i},g_{i}:\mathbb{R} ^{n}\to \mathbb{R}\) be convex functions for each \(i=0,1,\ldots ,m\), \(S=\{x\in \mathbb{R}^{n}\mid f_{i}(x)-g_{i}(x)\le 0, \forall i=1, \ldots ,m\}\), \(\bigcup_{x\in S}\partial g_{0}(x)\subseteq D _{0}\subseteq \mathbb{R}^{n}\) and \(\bigcup_{x\in S} ( \prod^{m}_{i=1}\partial g_{i}(x) ) \subseteq D \subseteq \mathbb{R}^{nm}\). If \(S((y_{i})_{i=1}^{m})=\{x\in \mathbb{R}^{n}\mid f _{i}(x)- \langle x,y_{i} \rangle +g^{*}_{i}(y_{i})\le 0, \forall i=1,\ldots ,m\}\) is not empty and
for each \((y_{i})_{i=1}^{m}\in D\cap \prod^{m}_{i=1} \operatorname{dom} g^{*}_{i}\), then
We remark that, in the real-valued case, this theorem contains the previous theorems in [3]. Clearly, problem (P) is equivalent to the following problem (P′):
and problem (P′) is also a DC programming problem because
and F and G are convex functions. To our surprise, we can observe that constraint qualifications of two DC inequality systems \(\{f_{i}-g_{i}\le 0, i=1,\ldots ,m\}\) and \(\{F-G\le 0\}\) have a difference in spite of the two systems being equivalent. This can be seen at the end of Section 3. Motivated by the observation, we give the first duality result.
Theorem 3
Let \(f_{i},g_{i}:\mathbb{R}^{n}\to \mathbb{R}\) be convex functions for each \(i=0,1,\ldots ,m\), \(S=\{x\in \mathbb{R}^{n}\mid f_{i}(x)-g_{i}(x) \le 0, \forall i=1,\ldots ,m\}\), \(\bigcup_{x\in S}\partial g _{0}(x)\subseteq D_{0}\) and \(D=\bigcup_{x\in S}\sum^{m} _{i=1}\partial g_{i}(x)\). If
for each \((y_{i})_{i=1}^{m}\in \bigcup_{x\in S}\prod^{m}_{i=1}\partial g_{i}(x)\), then the following Lagrange-type duality holds:
Also we give a unified result of Theorem 2 and Theorem 3, as follows.
Theorem 4
Let \(f_{i},g_{i}:\mathbb{R}^{n}\to \mathbb{R}\) be convex functions for each \(i=0,1,\ldots ,m\), \(S=\{x\in \mathbb{R}^{n}\mid f_{i}(x)-g_{i}(x) \le 0, \forall i=1,\ldots ,m\}\), \(I\subseteq \{1,\ldots ,m\}\), \(\bigcup_{x\in S}\partial g_{0}(x)\subseteq D_{0}\) and \(D=\bigcup_{x\in S} ( \prod_{i\notin I}\partial g _{i}(x)\times \sum_{i\in I}\partial g_{i}(x) ) \). If
is closed for each \((y_{i})_{i=1}^{m}\in \bigcup_{x\in S} \prod^{m}_{i=1}\partial g_{i}(x)\), then
Remark 1
If \(I=\emptyset \), then Theorem 4 becomes Theorem 2, and if \(I=\{1,\ldots ,m\}\), then Theorem 4 becomes Theorem 3. Also, the assumptions of Theorem 2 and Theorem 3 have a difference. This can be seen at the end of Section 3. Therefore Theorem 4 is a generalization of Theorem 2 and Theorem 3.
In order to prove Theorem 4, we provide Lemma 1 and Lemma 2.
Lemma 1
For any \(m\in \mathbb{N}\) and for any convex sets \(C_{i}\subseteq \mathbb{R}^{n}\) (\(i=1,\ldots ,m\)),
Lemma 2
For any \(m\in \mathbb{N}\) and for any convex sets \(A_{i}, B_{i} \subseteq \mathbb{R}^{n}\) (\(i=1,\ldots ,m\)),
The proofs of Lemma 1 and Lemma 2 will be given in the Appendix.
Proof of Theorem 4
Let \(F=\max_{i\in I}\{f_{i}+ \sum_{\substack{j\ne i \\ j\in I}}g_{j}\}\) and \(G=\sum_{i\in I}g_{i}\). We can see the problem (P) is converted to the following equivalent problem (P″) from (8):
From (1),
For each \(((y_{i})_{i\notin I},\hat{y})\in D\cap (\prod_{i\notin I} \operatorname{dom} g^{*}_{i}\times \operatorname{dom} G^{*})\), there exists \(\hat{x}\in S\) such that \(y_{i}\in \partial g_{i}(\hat{x})\) for each \(i\notin I\) and \(\hat{y}\in \partial \sum_{i\in I}g_{i}(\hat{x})\), that is,
From (3), there exists \(y_{i}\) (\(i\in I\)) such that \((\sum_{i\in I}g_{i})^{*}(\hat{y})=\sum_{i\in I}g^{*}_{i}(y _{i})\) and \(\sum_{i\in I}y_{i}=\hat{y}\). Then
and since \(g_{i}(\hat{x})+g^{*}_{i}(y_{i})\ge \langle \hat{x},y _{i} \rangle \) for each \(i\in I\), we have
for each \(i\in I\). Therefore
From \(\hat{y}\in \partial \sum_{i\in I}g_{i}(\hat{x})\) and \(\hat{x} \in S\),
From \(y_{i}\in \partial g_{i}(\hat{x})\) for each \(i\notin I\) and \(\hat{x}\in S\), \(f_{i}(\hat{x})- \langle \hat{x},y_{i} \rangle +g ^{*}_{i}(y_{i})=f_{i}(\hat{x})-g_{i}(\hat{x})\le 0\). Therefore x̂ is an element of \(\{x\in \mathbb{R}^{n}\mid f_{i}(x)- \langle x,y _{i} \rangle +g^{*}_{i}(y_{i})\le 0, \forall i\notin I, F(x)- \langle x,\hat{y} \rangle +G^{*}(\hat{y})\le 0\}\) and this set is non-empty. For each \(i\in I\), let \(F_{i}=f_{i}+ \sum_{\substack{j\ne i \\ j\in I}}g_{j}\). Now we have
Therefore
and hence
because \(\operatorname {co}(A\cup \operatorname {co}B)=\operatorname {co}(A\cup B)\) for any \(A, B\subseteq \mathbb{R}^{n}\). From (10), this set is closed. By using Theorem 2,
holds. For any \((y_{0},((y_{i})_{i\notin I},\hat{y}))\in D_{0}\times D\),
The fourth equality of the previous equalities follows from Theorem 1. Hence we have
This completes the proof. □
Now we can apply Theorem 3 to DC programming problems.
Example 1
Consider the following DC programming problem:
where \(f_{0}(x_{1},x_{2})=x_{1}^{2}-x_{2}\), \(g_{0}(x_{1},x_{2})=0\), \(f_{1}(x_{1},x_{2})=x_{2}\), \(g_{1}(x_{1},x_{2})=\vert x_{1}\vert \), \(f_{2}(x _{1},x_{2})=-x_{2}\), and \(g_{2}(x_{1},x_{2})=\vert x_{1}\vert \). This mathematical programming problem is neither convex nor differentiable, therefore the previous theorems concerned with convex or differentiable programming problems cannot be applied directly. Let \(D_{0}=\bigcup_{x\in S} \partial g_{0}(x)=\{(0,0)\}\) and \(D=\bigcup_{x\in S}(\partial g_{1}(x)+ \partial g_{2}(x))=[-2,2]\times \{0\}\). We can check that the assumption of Theorem 3 holds. Therefore,
and we can see that
then we have
This example shows that Theorem 3 contributes to solving DC programming problems.
Next, we provide an observation that Theorem 3 has no relevance to Theorem 2. At first, we give a DC inequality system for which holds the assumption of Theorem 3 but not the assumption of Theorem 2 in the following example.
Example 2
Define \(f_{1},f_{2},g_{1},g_{2}:\mathbb{R}\to \mathbb{R}\) as
where \([\cdot ]\) is the greatest integer function. We have \(g_{2}(x)=kx-k ^{2}\) if \(x\in [2k-1,2k+1)\) where \(k\in \mathbb{Z}\), \(g_{2}\) is also a convex function. Also we can see that
Put \(F=\max \{f_{1}+g_{2},f_{2}+g_{1}\}\) and \(G=g_{1}+g_{2}\). For each \(\hat{y}\in D=\bigcup_{x\in S}(\partial g_{1}(x)+\partial g_{2}(x))\), there exists \(\hat{x}\in S\), \(y_{1}\in \partial g_{1}(\hat{x})\), \(y _{2}\in \partial g_{2}(\hat{x})\) such that \(\hat{y}=y_{1}+y_{2}\) and \(G^{*}(\hat{y})=g^{*}_{1}(y_{1})+g^{*}_{2}(y_{2})\) from (3). Since \(\operatorname {epi}F^{*}=\operatorname {co}((\operatorname {epi}f^{*}_{1}+\operatorname {epi}g^{*}_{2})\cup (\operatorname {epi}f^{*}_{2}+\operatorname {epi}g^{*}_{1}))\),
The latter set is always closed. In general,
where \(a, b\in \mathbb{R}\), \(\alpha =\min \{ \frac{n^{2}-b}{n-a}\mid n\in \mathbb{Z}, n>a \} \), \(\beta = \max \{ \frac{n^{2}-b}{n-a}\mid n\in \mathbb{Z}, n>a \} \), and \(h(x)= \Bigl\{ \small{\begin{array}{l@{\quad}l} \alpha x & \mbox{if } x\ge 0, \\ \beta x & \mbox{otherwise.} \end{array} } \) From this, \(\operatorname {cone}\operatorname {co}(\{(n,n^{2})\mid n\in \mathbb{Z}\}-(a,b))\) is always closed. Therefore for \(\{F-G\le 0\}\) holds condition (6). Also \(S(\hat{y})\ne \emptyset \) because \(F(\hat{x})- \langle \hat{x}, \hat{y} \rangle +G^{*}(\hat{y})\le 0\). Therefore for \(\{F-G \le 0\}\) holds the assumption of Theorem 3. However,
is not closed, that is, \(\{f_{1}-g_{1}\le 0, f_{2}-g_{2}\le 0\}\) does not hold (6).
Next, we give a DC inequality system for which holds the assumption of Theorem 2 but not the assumption of Theorem 3 in the following example.
Example 3
Define \(f_{1},f_{2},g_{1},g_{2}:\mathbb{R}\to \mathbb{R}\) as
We can see that
and then
for each \((y_{1},y_{2})\in \bigcup_{x\in S}(\partial g_{1}(x)\times \partial g_{2}(x))\). The latter set is always closed in a similar way to Example 2. Also, for each \((y_{1},y_{2})\in \bigcup_{x\in S}(\partial g_{1}(x)\times \partial g_{2}(x))\), there exists \(z\in \mathbb{R}\) such that \(y_{1}=\frac{1}{2}z\), \(y_{2}=z\), then
Then \(S(y_{1},y_{2})\) is non-empty. Therefore \(\{f_{1}-g_{1}\le 0, f _{2}-g_{2}\le 0\}\) holds by the assumption of Theorem 2. However,
is not a closed set, that is, (9) does not hold.
4 Conclusions
In this paper, we studied Lagrange-type duality for DC programming problems with DC inequality constraints. It is well known that the maximum of DC functions is also a DC function. Based on this idea, we presented Theorem 3, which is a Lagrange-type duality theorem for the maximum DC inequality constraint of the original DC inequality constraints. Theorem 3 has no relevance to Theorem 2, which is a previous Lagrange-type duality for DC programming problems proved in [3]. More precisely, Theorem 3 does not imply Theorem 2 and Theorem 2 does not imply Theorem 3. Also we proved Theorem 4, which is a unified Lagrange-type duality result of Theorem 2 and Theorem 3. Consequently, the class of DC programming problems to which Lagrange-type duality theorems can be applied was broader than the class in previous research.
References
Goberna, MA, Jeyakumar, V, López, MA: Necessary and sufficient constraint qualifications for solvability of systems of infinite convex inequalities. Nonlinear Anal. 68, 1184-1194 (2008)
Martínez-Legaz, JE, Volle, M: Duality in DC programming: the case of several DC constraints. J. Math. Anal. Appl. 237, 657-671 (1999)
Harada, R, Kuroiwa, D: Lagrange-type duality in DC programming. J. Math. Anal. Appl. 418, 415-424 (2014)
Rockafellar, RT: Convex Analysis. Princeton Paperbacks, Princeton (1996)
Hiriart-Urruty, J, Baptiste, J, Lemarechal, C: Convex Analysis and Minimization Algorithms II. Advanced Theory and Bundle Methods. Grundlehren der Mathematischen Wissenschaften. Springer, Berlin (1993)
Sion, M: On general minimax theorems. Pac. J. Math. 8, 171-176 (1958)
Acknowledgements
The authors are grateful to the anonymous referees of valuable comments and suggestions which improved the quality of the paper. This work has been partially supported by JSPS KAKENHI Grant Number 16K05274.
Author information
Authors and Affiliations
Corresponding author
Additional information
Competing interests
The authors declare to have no competing interests.
Authors’ contributions
RH conceived of the study and drafted, completed, and approved the final manuscript. DK conceived of the study and drafted, read, and approved the final manuscript.
Appendix
Appendix
In this section, we give proofs of Lemma 1 and Lemma 2.
Proof of Lemma 1
Clearly, (11) holds when \(m=1, 2\). Assume that (11) holds for some \(m\in \mathbb{N}\). Let \(C_{i}\subseteq \mathbb{R}^{n}\) be convex sets for all \(i=1,\ldots ,m+1\). Then
Therefore (11) holds for \(m+1\). From mathematical induction, the proof is completed. □
Proof of Lemma 2
We may assume that all \(A_{i}\) and \(B_{i}\) are not empty. We show this lemma by using mathematical induction. It is clear that (12) holds when \(m=1\). In the case of \(m=2\), (12) holds from Lemma 1 by putting \(C_{1}=A _{1}+B_{2}\) and \(C_{2}=A_{2}+B_{1}\). Assume that (12) holds for some \(m\in \mathbb{N}\). Let \(A_{i}, B_{i}\subseteq \mathbb{R} ^{n}\) be convex sets for all \(i=1,\ldots ,m+1\). Then
For all \(i=2,\ldots ,m+1\), since \(B_{i}\) are convex sets, \(1-\lambda _{i}=(1-\lambda_{1}-\lambda_{i})+\lambda_{1}\), and \(1-\lambda_{1}- \lambda_{i}\ge 0\), we have
and then
Hence,
From the assumption,
By using Lemma 1,
Consequently, (12) holds for \(m+1\). □
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
About this article
Cite this article
Harada, R., Kuroiwa, D. Lagrange-type duality in DC programming problems with equivalent DC inequalities. J Inequal Appl 2016, 276 (2016). https://doi.org/10.1186/s13660-016-1219-5
Received:
Accepted:
Published:
DOI: https://doi.org/10.1186/s13660-016-1219-5