# Lagrange duality on DC evenly convex optimization problems via a generalized
conjugation scheme

Maria Dolores Fajardo Department of Mathematics, University of Alicante,
Alicante, Spain<EMAIL_ADDRESS>José Vidal Department of Physics and
Mathematics, University of Alcalá, Alcalá de Henares, Spain<EMAIL_ADDRESS>
###### Abstract

In this paper we study how Lagrange duality is connected to optimization
problems whose objective function is the difference of two convex functions,
briefly called DC problems. We present two Lagrange dual problems, each of
them obtained via a different approach. While one of the duals corresponds to
the standard formulation of the Lagrange dual problem, the other is written in
terms of conjugate functions. When one of the involved functions in the
objective is evenly convex, both problems are equivalent, but this relation is
no longer true in the general setting. For this reason, we study conditions
ensuring not only weak, but also zero duality and strong duality between the
primal and one of the dual problems written using conjugate functions. For the
other dual, and due to the fact that weak duality holds by construction, we
just develop conditions for zero duality gap and strong duality between the
primal DC problem and its (standard) Lagrange dual problem. Finally, we
characterize weak and strong duality together with zero duality gap between
the primal problem and its Fenchel-Lagrange dual following techniques used
throughout the manuscript.

MSC Subject Classification. 52A20, 26B25, 90C25, 49N15.

Keywords:  Generalized convex conjugation, evenly convex function, DC problem,
Fenchel duality, Lagrange duality, weak duality, strong duality, zero duality
gap

##  1 Introduction

Conjugate duality is a branch within the area of optimization that has
attained a lot of attention in mathematics. One of the reasons of its success
is that, given an optimization problem of interest, called primal problem, it
makes it possible to analyze an alternative problem, called dual, to solve the
pursued problem. To get a deep introduction about basic tools and a complete
theoretical perspective, we refer the reader, for instance, to the textbooks
[2, 5, 32, 39] among many others. As recent applications of duality theory, we
mention that this approach has been used in [24] in the context of inverse
problems, [4] in optimization problems posed on Riemannian manifolds, [28] in
the context of economics or [9] in the development of the well-known primal-
dual algorithm call Chambolle-Pock.

In this paper, we focus our attention both in a particular type of duality,
which is Lagrange duality, and in a distinctive type of optimization problems,
called DC problems. For a throughout introduction on them, we refer the reader
to [25, 34, 35, 37, 36]. These problems allow to mathematically model
optimization problems belonging to areas like, for instance, data
visualization [8], and they are also of interest from the algorithmic point of
view, as one can appreciate from [1] or [3]. Regarding Lagrange duality, it
has already been explored not only in the classical setting, using Fenchel
conjugate teory, by [26, 7, 6], but also using a more general conjugation
scheme, the $c$-conjugation, based on generalized convex conjugation in [17]
and [19], where the authors develop sufficient conditions ensuring strong
duality between a convex primal problem and its Lagrange dual. To get an
entire perspective using this generalized conjugation scheme into duality
theory, see [16]. To make profit of this conjugation scheme, the involved
functions must be evenly convex. Following [33], a function is evenly convex
if its epigraph is an evenly convex set, a set which can be expressed as the
intersection of an arbitrary family of open half-spaces. These sets were
introduced by Fenchel in [23] to extend polarity theory to non-closed and
convex sets.

In the novel work [14], two Fenchel dual problems for a DC optimization primal
one were built by means of $c$-conjugation, being both equivalent under even
convexity assumption of one of the functions in the primal problem.
Characterizations for weak, strong and stable strong duality were presented.
That work has motivated us to continue with the study of Lagrange duality,
making use of the Lagrange dual problem developed in [17] for a convex
optimization primal one and the way that, again under even convexity
assumptions, this dual problem can be reformulated in an equivalent form
expressed in terms of the $c$-conjugates of the involved functions in the
primal problem. This tecnique, applied to Fenchel conjugation, is used in
[22]. As it happened with Fenchel duality, weak duality is not guaranteed with
this reformulated dual problem if the even convexity assumption does not hold.
This issue serves as a starting point to develop conditions ensuring not only
weak and strong duality, but also zero duality gap as well for this primal-
dual pair.

On the other hand and, since in [17] there is no analysis about zero duality
gap between the primal problem and its standard Lagrange dual, this paper
recaps this situation providing necessary and sufficient conditions for both
strong duality and zero duality gap. As it will be shown, these conditions are
written using the epigraphs of the $c$-conjugate functions of the involved
functions in the primal problem, so they belong to the class of closedness-
type regularity conditions. Additionally, we also compare strong dualities of
both primal-dual pairs using the theoretical results presented throughout the
paper. Last but not least, we study conditions for weak, strong and zero
duality gap between the DC primal problem and its Fenchel-Lagrange dual. As it
happens in [14] for Fenchel and in the sequel for Lagrange duals, it is also
possible to derive an equivalent formulation of the Fenchel-Lagrange dual
problem presented in [20]. Under the same even convexity assumption, both dual
problems turn out to be equivalent and we characterize weak and strong
dualities together with zero duality gap between the new Fenchel-Lagrange dual
and the primal problem.

The structure of the paper is as follows. In Section 2 we state the necessary
results to keep the paper self-contained. Section 3 presents two Lagrange dual
problems that will be the focus of the work. As it will be shown, both are
equivalent under the even convexity of just one of the functions in the
objective. Section 4 contains conditions for weak and strong duality and zero
duality gap between the primal and the Lagrange dual problem which is
expressed in terms of conjugate functions. Section 5 characterizes both strong
duality and zero duality gap between the primal and its standard Lagrange dual
problem, and it also compares strong dualities of both primal-dual pairs
derived in Section 3. Section 6 is devoted to the analysis of an alternative
Fenchel-Lagrange dual problem which turns out to be equivalent to the
(standard) Fenchel-Lagrange dual under appropiate assumptions. Finally,
Section 7 emphasizes the achieved goals in the paper and concludes the
manuscript.

##  2 Preliminaries

This section contains the necessary results and concepts that will be used in
the sequel. Let $X$ be a non-trivial separated locally convex space, lcs in
short, whose topology is the one induced by its continuous dual space $X^{*}$,
i.e., $\sigma(X,X^{*})$. We represent by $\left\langle x,x^{*}\right\rangle$
the action of $x^{*}$ at $x$. For a set $D$ in $X$, we denote by
$\operatorname{conv}(D)$ and $\operatorname{cl}(D)$ its convex hull and
closure, respectively. Throughout we will use the notation
$\overline{\mathbb{R}}:=\mathbb{R}\cup\left\\{\pm\infty\right\\}$,
$\mathbb{R}_{+}=[0,+\infty[$ and $\mathbb{R}_{++}=]0,+\infty[$.

As indicated in Section 1, evenly convex sets, briefly e-convex, were
introduced in [23], studied in terms of their sections and projections in [27]
and characterized in [10] as follows. Actually this characterization is the
way that e-convex sets are defined in [10], more tratable than the original
one.

######  Definition 2.1 (Def. 1, [10]).

A set $C\subseteq X$ is e-convex if for every point $x_{0}\notin C$, there
exists $x^{*}\in X^{*}$ such that $\left\langle x-x_{0},x^{*}\right\rangle<0$,
for all $x\in C$.

If $D$ is a set in $X$, its convex hull, denoted by $\operatorname{econv}D$,
is the smallest e-convex set that contains $D$. If $D$ is, moreover, convex,
then

$D\subseteq\operatorname{econv}D\subseteq\operatorname{cl}D.$

The e-convex hull operator is closed under arbitrary intersections and due to
Hahn-Banach theorem, every closed or open convex set is e-convex too, being
the converse statement false in general; see [14, Ex. 2.2].

Given a function $f:X\to\overline{\mathbb{R}}$, we keep the standard notation
for its domain and epigraph, that is,

$\displaystyle\operatorname{dom}f$ $\displaystyle:=\left\\{x\in
X~{}:~{}f(x)<+\infty\right\\},$ $\displaystyle\operatorname{epi}f$
$\displaystyle:=\left\\{(x,\alpha)\in
X\times\mathbb{R}~{}:~{}f(x)\leq\alpha\right\\},$

and it is proper if $f(x)>-\infty$, for all $x\in X$, and its domain is non-
empty. Its lower semicontinuous convex hull, denoted by $\operatorname{cl}f$,
is the function verifying
$\operatorname{epi}\operatorname{cl}f=\operatorname{cl}(\operatorname{epi}f)$,
and $f$ is called lower semicontinuous, lsc, in breaf, if
$f=\operatorname{cl}f$. In a bit different way, the e-convex hull of a proper
function $f$, briefly denoted by $\operatorname{econv}f$, is its largest
e-convex minorant. Let us observed that it cannot be defined as that function
verifying
$\operatorname{epi}\operatorname{econv}f=\operatorname{econv}(\operatorname{epi}f)$.

######  Example 2.2.

Let us consider the function $f:\mathbb{R}\rightarrow\overline{\mathbb{R}}$

$f(x)=\left\\{\begin{aligned} x,~{}&~{}\text{if }x>0,\\\ 1,~{}&~{}\text{if
}x=0,\\\ +\infty,~{}&~{}\text{otherwise.}\end{aligned}\right.$

Then $\operatorname{econv}(\operatorname{epi}f)=\left\\{(x,x):x\geq
0\right\\}\setminus\left\\{(0,0)\right\\}$, and there is no function whose
epigraph is this e-convex set; see Figure 1.

$econv(epif)$ Figure 1: Set from Example 2.2

The class of lsc functions is a strictly contained subclass in the class of
e-convex functions, see [20, Ex. 2.1], which is an expected resulted, knowing
the relationship between closed convex sets and e-convex sets.

In the rest of this preliminary section, we state the conjugation scheme that
we will use throughout the paper, which is called the $c$-conjugation scheme;
see [29]. It is based on the generalized convex conjugation theory presented
by Moreau in [31] and it uses a particular pair of coupling functions. Let
$f:X\to\overline{\mathbb{R}}$ be a proper function and set $W:=X^{*}\times
X^{*}\times\mathbb{R}$. The coupling function used in _$c$ -conjugacy_ is
$c:X\times W\to\overline{\mathbb{R}}$

$c(x,(x^{*},y^{*},\alpha))=\left\\{\begin{aligned} \left\langle
x,x^{*}\right\rangle,&~{}~{}~{}\text{if }\left\langle
x,y^{*}\right\rangle<\alpha\\\
+\infty,&~{}~{}~{}\text{otherwise.}\end{aligned}\right.$

The _$c$ -conjugate_ of a function $f:X\to\overline{\mathbb{R}}$ is defined as

$f^{c}(x^{*},y^{*},\alpha):=\sup_{X}\left\\{c(x,(x^{*},y^{*},\alpha))-f(x)\right\\}.$

Observe that $c$-conjugation provides different results than standard Fenchel
conjugation, see [19, Ex. 2.5]. In fact,

$f^{c}(x^{*},y^{*},\alpha)=\left\\{\begin{aligned}
f^{*}(x^{*}),&~{}~{}~{}\text{if }\operatorname{dom}f\subseteq
H_{y^{*},\alpha}^{-},\\\
+\infty,&~{}~{}~{}\text{otherwise,}\end{aligned}\right.$

where $f^{*}:X^{*}\to\overline{\mathbb{R}}$ is the Fenchel conjugate of $f$
and $H_{y^{*},\alpha}^{-}$ is the open half-space in $X$ defined as

$H_{y^{*},\alpha}^{-}:=\\{x\in X:\left\langle x,y^{*}\right\rangle<\alpha\\}.$

This conjugation scheme is complemented by the use of the coupling function
$c^{\prime}:W\times X\to\overline{\mathbb{R}}$ defined as

$c^{\prime}((x^{*},y^{*},\alpha),x):=c(x,(x^{*},y^{*},\alpha)),$

which allows the following definition of the _$c^{\prime}$ -conjugate_ of a
proper function $h:W\to\overline{\mathbb{R}}$ as

$h^{c^{\prime}}(x):=\sup_{W}\left\\{c^{\prime}((x^{*},y^{*},\alpha),x)-h(x^{*},y^{*},\alpha)\right\\}.$

This conjugation pattern gives priority to $-\infty$, i.e., the sign
convention is

$(+\infty)+(-\infty)=(-\infty)+(+\infty)=(+\infty)-(+\infty)=(-\infty)-(-\infty)=-\infty.$

Based on the generalized convex duality theory, see [31], functions
$c(\cdot,(x^{*},y^{*},\alpha))-\beta:X\rightarrow\overline{\mathbb{R}}$, with
$(x^{*},y^{*},\alpha)\in W$ and $\beta\in\mathbb{R}$, are called _c-
elementary_ , and functions
$c^{\prime}(\cdot,x)-\beta:W\rightarrow\overline{\mathbb{R}}$, with $x\in X$
and $\beta\in\mathbb{R}$, are called _c_ ′-_elementary_. In [29], it is shown
that any proper e-convex function $f:X\rightarrow\overline{\mathbb{R}}$ is the
pointwise supremum of a set of $c$-elementary functions. Extending this
concept, [18] introduced the _$\operatorname{\text{e}^{\prime}}$ -convex
functions_ as convex functions $g:W\rightarrow\overline{\mathbb{R}}$ which can
be expressed as the pointwise supremum of a set of $c^{\prime}$-elementary
functions. The _$\operatorname{\text{e}^{\prime}}$ -convex hull_ of any
function $g:W\rightarrow\overline{\mathbb{R}}$,
$\operatorname{{e}^{\prime}conv}g$, is the largest
$\operatorname{\text{e}^{\prime}}$-convex minorant function of $g$. The
following theorem from [28] is the counterpart of Fenchel-Moreau theorem for
e-convex and $\operatorname{\text{e}^{\prime}}$-convex functions.

######  Theorem 2.3 (Prop. 6.1, 6.2, Cor. 6.1, [28]).

Let $f:X\rightarrow\overline{\mathbb{R}}$ and
$g:W\rightarrow\overline{\mathbb{R}}$. Then

  * (i)

$f^{c}$ is e′-convex; $g^{c^{\prime}}$ is e-convex.

  * (ii)

If $f$ has a proper e-convex minorant, then
$\operatorname{econv}f=f^{cc^{\prime}}$;
$\operatorname{{e}^{\prime}conv}g=g^{c^{\prime}c}$.

  * (iii)

If $f$ does not take on the value $-\infty$, then $f$ is e-convex if and only
if $f=f^{cc^{\prime}};g$ is e′-convex if and only if $g=g^{c^{\prime}c}$.

  * (iv)

$f^{cc^{\prime}}\leq f;$ $g^{c^{\prime}c}\leq g$.

According to $(iii)$, it makes sense to say that, if $f$ does not take on the
value $-\infty$, then $f$ is e-convex at a point $x_{0}\in X$ if and only if
$f(x_{0})=f^{cc^{\prime}}(x_{0})$ and $g$ is e′-convex at a point
$(x_{0}^{*},y_{0}^{*},\alpha_{0})\in W$ if and only if
$g(x_{0}^{*},y_{0}^{*},\alpha_{0})=g^{c^{\prime}c}(x_{0}^{*},y_{0}^{*},\alpha_{0})$.

We finish with the following definition of a kind of sets that complements the
family of e-convex sets. Their main properties were developed in [12] and they
were used in [15, 17, 21, 19] in the study of regularity conditions for
different pairs of primal-dual problems.

######  Definition 2.4 (Def.2, [18]).

A set $D\subset W\times\mathbb{R}$ is
$\operatorname{\text{e}^{\prime}}$-convex if there exists an
$\operatorname{\text{e}^{\prime}}$-convex function $k:W\to\mathbb{R}$ such
that $D=\operatorname{epi}k$. The $\operatorname{\text{e}^{\prime}}$-convex
hull of an arbitrary set $D\subset W\times\mathbb{R}$ is defined as the
smallest $\operatorname{\text{e}^{\prime}}$-convex set containing $D$, and it
will be denoted by $\operatorname{{e}^{\prime}conv}D$.

##  3 Dual problems

Consider the following optimization problem

$\inf_{A}\left\\{f(x)-g(x)\right\\}$ ($P$)

where

$A=\left\\{x\in X\,:\,h_{t}(x)\leq 0,~{}t\in T\right\\}$ (1)

and $f,g,h_{t}:X\to\overline{\mathbb{R}}$ are proper convex functions, for all
$t\in T$, being $T$ an arbitrary index set. Using the perturbational approach,
in [14] a Fenchel dual problem for $(P)$ is presented. Additionally, and using
a convexification technique, another dual problem is obtained, being both
problems equivalent whenever the function $g$ in ($P$) is e-convex. Also
characterizations of weak duality, zero duality gap and strong duality are
given, as well as a relationship between strong duality for both pairs of
primal-dual problems.

Inspired by that work, firstly, in this section, we will introduce two
Lagrange dual problems that are also equivalent in case the function $g$ in
($P$) is e-convex. We assume that $f(x)-g(x)=+\infty$ in case
$x\not\in\operatorname{dom}f$, which implies that $f-g$ will be a proper
function if $\operatorname{dom}f\subseteq\operatorname{dom}g$, and,
consequently, for all $(u^{*},v^{*},\gamma)\in\operatorname{dom}g^{c}$,
$\operatorname{dom}f\subseteq H_{v^{*},\gamma}^{-}$.

According to [17], a dual problem for ($P$) can be built using the
perturbational approach (see, for instance, [11]), by means of the
$c$-conjugate of the perturbation function

$\sup_{\mathbb{R}^{(T)}_{+}}\inf_{X}\left\\{f(x)-g(x)+\lambda h(x)\right\\},$
($D_{L}$)

verifying weak duality, i.e., $v(P)\geq v\eqref{eq:Dual_problem_1}$. Here
$\mathbb{R}^{(T)}$ denotes the space of generalized finite sequences, i.e., a
sequence $\lambda=(\lambda_{t})_{t\in T}$ belongs to $\mathbb{R}^{(T)}$ if
only finitely many $\lambda_{t}$ are different from zero, and
${\mathbb{R}^{(T)}_{+}}$ represents its nonnegative polar cone. It is worth
emphasizing that such a dual problem was obtained in [17] without restrictions
on the involved functions, just proper extended real valued functions. The
same weak duality result was shown in [30, Lem. 2.2] using the Fenchel
conjugate pattern.

In case the function $g$ is e-convex, being moreover proper, we can use the
equality $g=g^{cc^{\prime}}$, by Theorem 2.3 $(iii)$, to deduce

$\displaystyle\inf_{X}$ $\displaystyle\left\\{f(x)-g(x)+\lambda h(x)\right\\}$
$\displaystyle=$
$\displaystyle\inf_{X}\left\\{f(x)-\sup_{W}\left\\{c(x,(u^{*},v^{*},\gamma))-g^{c}(u^{*},v^{*},\gamma)\right\\}+\lambda
h(x)\right\\}$ $\displaystyle=$
$\displaystyle\inf_{W}\left\\{g^{c}(u^{*},v^{*},\gamma)-\sup_{X}\left\\{c(x,(u^{*},v^{*},\gamma))-(f(x)+\lambda
h(x))\right\\}\right\\}$ $\displaystyle=$
$\displaystyle\inf_{W}\left\\{g^{c}(u^{*},v^{*},\gamma)-(f+\lambda
h)^{c}(u^{*},v^{*},\gamma)\right\\}.$

It leads to reformulate the dual problem ($D_{L}$) as

$\sup_{\mathbb{R}^{(T)}_{+}}\inf_{W}\left\\{g^{c}(u^{*},v^{*},\gamma)-(f+\lambda
h)^{c}(u^{*},v^{*},\gamma)\right\\}.$ ($\overline{D}_{L}$)

Nevertheless, without assuming the e-convexity of $g$, the dual problems
($D_{L}$) and ($\overline{D}_{L}$) may not be equivalent and, even more, weak
duality might not hold for the dual pair ($P$)$-$($\overline{D}_{L}$) as we
can see in the following example.

######  Example 3.1.

Let $T$ be a singleton and $f,g,h:X\to\overline{\mathbb{R}}$ defined by

$f(x)=\left\\{\begin{aligned} x,~{}&~{}\text{if }x\geq 0,\\\
+\infty,~{}&~{}\text{otherwise;}\end{aligned}\right.\hskip
9.95863ptg(x)=\left\\{\begin{aligned} x,~{}&~{}\text{if }x>0,\\\
1,~{}&~{}\text{if }x=0,\\\
+\infty,~{}&~{}\text{otherwise;}\end{aligned}\right.\hskip
9.95863pth(x)=\left\\{\begin{aligned} -x,~{}&~{}\text{if }x\geq 0,\\\
+\infty,~{}&~{}\text{otherwise.}\end{aligned}\right.$

Since $A=\left\\{x\in\mathbb{R}:h(x)\leq 0\right\\}=\left[0,+\infty\right]$,
we obtain, for all $x\geq 0$

$f(x)-g(x)=\left\\{\begin{aligned} 0,~{}&~{}\text{if }x>0,\\\
-1,~{}&~{}\text{if }x=0,\\\
+\infty,~{}&~{}\text{otherwise,}\end{aligned}\right.$

and $v\eqref{eq:Primal_problem}=\inf\left\\{f(x)-g(x):x\geq 0\right\\}=-1$.
On the other hand, we have, for $(u^{*},v^{*},\alpha)\in\mathbb{R}^{3}$,

$\displaystyle g^{c}(u^{*},v^{*},\alpha)$
$\displaystyle=\sup_{\mathbb{R}}\left\\{c(x,(u^{*},v^{*},\alpha))-g(x)\right\\}$
$\displaystyle=\left\\{\begin{aligned} \sup\left\\{\sup_{x\geq
0}\left\\{x(u^{*}-1)\right\\},-1\right\\},~{}&~{}\text{if }v^{*}\leq
0,\alpha>0\\\ +\infty,~{}&~{}\text{otherwise,}\end{aligned}\right.$
$\displaystyle=\left\\{\begin{aligned} 0,~{}&~{}\text{if }u^{*}\leq
1,v^{*}\leq 0,\alpha>0\\\
+\infty,~{}&~{}\text{otherwise.}\end{aligned}\right.$

Moreover,
$\operatorname{dom}g^{c}=\left\\{(u^{*},v^{*},\alpha)\in\mathbb{R}^{3}:u^{*}\leq
1,v^{*}\leq 0,\alpha>0\right\\}$. Now, for all
$(u^{*},v^{*},\alpha)\in\operatorname{dom}g^{c}$ and $\lambda\geq 0$,

$\displaystyle(f+\lambda h)^{c}(u^{*},v^{*},\alpha)$
$\displaystyle=\sup_{\mathbb{R}}\left\\{c(x,(u^{*},v^{*},\alpha))-(f+\lambda
h)(x)\right\\}$ $\displaystyle=\sup_{x\geq
0}\left\\{x(u^{*}-1+\lambda)\right\\}=\left\\{\begin{aligned}
0,~{}&~{}\text{if }u^{*}\leq 1-\lambda\\\
+\infty,~{}&~{}\text{otherwise.}\end{aligned}\right.$

Finally, we have, for all $(u^{*},v^{*},\alpha)\in\operatorname{dom}g^{c}$ and
$\lambda\geq 0$,

$g^{c}(u^{*},v^{*},\alpha)-(f+\lambda
h)^{c}(u^{*},v^{*},\alpha)=\left\\{\begin{aligned} 0,~{}&~{}\text{if
}u^{*}\leq 1-\lambda\\\
-\infty,~{}&~{}\text{otherwise,}\end{aligned}\right.\\\ $

and, for all $\lambda>0$,

$\inf_{\operatorname{dom}g^{c}}\left\\{g^{c}(u^{*},v^{*},\alpha)-(f+\lambda
h)^{c}(u^{*},v^{*},\alpha)\right\\}=-\infty,$

but, for $\lambda=0$,

$\inf_{\operatorname{dom}g^{c}}\left\\{g^{c}(u^{*},v^{*},\alpha)-f^{c}(u^{*},v^{*},\alpha)\right\\}=0,$

hence $v\eqref{eq:Dual_problem_2}=0$ and weak duality does not hold for
($P$)$-$($\overline{D}_{L}$). In addition, it is not difficult to compute the
optimal value of ($D_{L}$), since

$f(x)-g(x)+\lambda h(x)=\left\\{\begin{aligned} -\lambda x,~{}&~{}\text{if
}x>0\\\ -1,~{}&~{}\text{if }x=0\\\
+\infty,~{}&~{}\text{otherwise,}\end{aligned}\right.\\\ $

and, for $\lambda\geq 0$,

$\inf_{x\geq 0}\left\\{f(x)-g(x)+\lambda h(x)\right\\}=\left\\{\begin{aligned}
-\infty,~{}&~{}\text{if }\lambda>0\\\ -1,~{}&~{}\text{if }\lambda=0,\\\
\end{aligned}\right.\\\ $

then

$v\eqref{eq:Dual_problem_1}=\sup_{\lambda\geq 0}~{}\inf_{x\geq
0}\left\\{f(x)-g(x)+\lambda h(x)\right\\}=-1$

and, finally,

$v\eqref{eq:Dual_problem_1}=v\eqref{eq:Primal_problem}<v\eqref{eq:Dual_problem_2}.$

$\square$

As we can observe in the previous example, not only weak duality between $(P)$
and $\eqref{eq:Dual_problem_1}$ is guaranteed, but also there is no duality
gap, condition that may not happen, in general. Moreover, in duality theory,
there exists an interest for finding conditions which assure strong duality,
i.e., when there is no duality gap and the dual problem is solvable.

Therefore, the rest of the paper is devoted to the derivation of conditions
ensuring weak duality, in case $g$ is not e-convex, for
($P$)$-$($\overline{D}_{L}$), and conditions for zero duality gap and strong
duality for both pairs ($P$)$-$($\overline{D}_{L}$) and ($P$)$-$($D_{L}$). We
will also compare both strong dualities making use of the theoretical results
we derive in Section 4.

##  4 Duality results for ($P$)$-$($\overline{D}_{L}$)

As we have seen in Section 3, if $g$ is an e-convex function, there exists
weak duality between ($P$) and ($\overline{D}_{L}$). If we eliminate the even
convexity assumption on $g$, we can also guarantee weak duality under the
hypothesis of the following proposition.

######  Proposition 4.1.

Let us suppose that $g$ in the primal problem $(P)$ has a proper e-convex
minorant. If ($P$) is solvable and there exists a solution where $g$ is
e-convex, then weak duality holds for ($P$)$-$($\overline{D}_{L}$).

###### Proof.

We build the problem

$\inf_{A}\left\\{f(x)-\operatorname{econv}g(x)\right\\}.$ ($P_{e}$)

According to [17] again, we can derive a dual problem for $(P_{e})$, verifying
weak duality

$\sup_{\mathbb{R}^{(T)}_{+}}\inf_{X}\left\\{f(x)-\operatorname{econv}g(x)+\lambda
h(x)\right\\}.$ ($D_{e,L}$)

In this case, $\operatorname{econv}g$ is e-convex, and following the steps
done for the construction of $\eqref{eq:Dual_problem_2}$ for $(P)$, we obtain
an equivalent problem to $(D_{e,L})$

$\sup_{\mathbb{R}^{(T)}_{+}}\inf_{W}\left\\{(\operatorname{econv}g)^{c}(u^{*},v^{*},\gamma)-(f+\lambda
h)^{c}(u^{*},v^{*},\gamma)\right\\}.$

However, it is easy to see, by means of Theorem 2.3 $(ii)$, that
$(\operatorname{econv}g)^{c}=(g^{cc^{\prime}})^{c}=g^{c}$, so
$\eqref{eq:Dual_problem_2}$ and $(D_{e,L})$ are equivalent, thus
$v\eqref{eq:Dual_problem_2}\leq v(P_{e})$. Naming $x_{0}$ to a solution of
$(P)$ where $g$ is e-convex, $g(x_{0})=\operatorname{econv}g(x_{0})$, and we
obtain

$\displaystyle v(P)$
$\displaystyle=f(x_{0})-g(x_{0})+\delta_{A}(x_{0})=f(x_{0})-\operatorname{econv}g(x_{0})+\delta_{A}(x_{0})$
$\displaystyle\geq v(P_{e})\geq v\eqref{eq:Dual_problem_2}.$

∎

######  Corollary 4.2.

If $(P)$ is solvable and $x_{0}$ is a solution verifying
$\partial_{c}g(x_{0})\neq\emptyset$, then weak duality holds for
($P$)$-$($\overline{D}_{L}$).

###### Proof.

This result is an immediate consequence of [13, Th. 3 (ii)]. ∎

In order to derive additional conditions ensuring weak and strong dualities,
and zero duality gap for this dual pair, we define the following sets, being
$A$ the set given in (1)

$\displaystyle K$
$\displaystyle:=\bigcup_{\mathbb{R}^{(T)}_{+}}\bigcap_{\operatorname{dom}g^{c}}\left\\{\operatorname{epi}(f+\lambda
h)^{c}-(u^{*},v^{*},\gamma,g^{c}(u^{*},v^{*},\gamma))\right\\},$ (2)
$\displaystyle\Lambda$
$\displaystyle:=\bigcap_{\operatorname{dom}g^{c}}\left\\{\operatorname{epi}(f+\delta_{A})^{c}-(u^{*},0,0,g^{c}(u^{*},v^{*},\gamma))\right\\}.$
(3)

Regarding these sets, we state the following lemma.

######  Lemma 4.3.

Let $K$ and $\Lambda$ the sets defined in (2) and (3), respectively. It holds

  * i)

$\Lambda=\operatorname{epi}(f-\operatorname{econv}g+\delta_{A})^{c}$.

  * ii)

$K\supseteq\bigcup_{\mathbb{R}^{(T)}_{+}}\operatorname{epi}(f-\operatorname{econv}g+\lambda
h)^{c}$.

###### Proof.

i) The proof is stated in [14, Prop. 5.5].
ii) For any $\lambda\in\mathbb{R}^{(T)}_{+}$, it is not difficult to see that

$f-\operatorname{econv}g+\lambda
h=\inf_{\operatorname{dom}g^{c}}\left\\{-c(\cdot,(u^{*},v^{*},\gamma))+g^{c}(u^{*},v^{*},\gamma)+f+\lambda
h\right\\}.$

Applying $c$-conjugation standard properties, we obtain

$\displaystyle(f-$ $\displaystyle\operatorname{econv}g+\lambda
h)^{c}(x^{*},y^{*},\alpha)=\sup_{X}\left\\{c(x,(x^{*},y^{*},\alpha))-(f-\operatorname{econv}g+\lambda
h)(x)\right\\}$
$\displaystyle=\sup_{X,~{}\operatorname{dom}g^{c}}\left\\{c(x,(x^{*},y^{*},\alpha))+c(x,(u^{*},v^{*},\gamma))-(f+\lambda
h)(x)-g^{c}(u^{*},v^{*},\gamma)\right\\}$
$\displaystyle\geq\sup_{X,~{}\operatorname{dom}g^{c}}\left\\{c(x,(x^{*}+u^{*},y^{*}+v^{*},\alpha+\gamma))-(f+\lambda
h)(x)-g^{c}(u^{*},v^{*},\gamma)\right\\}$ $\displaystyle\geq(f+\lambda
h)^{c}(x^{*}+u^{*},y^{*}+v^{*},\alpha+\gamma)-g^{c}(u^{*},v^{*},\gamma),$

for all $(u^{*},v^{*},\gamma)\in\operatorname{dom}g^{c}$. Then, if
$(x^{*},y^{*},\alpha,\beta)\in\operatorname{epi}(f-\operatorname{econv}g+\lambda
h)^{c}$,

$(x^{*}+u^{*},y^{*}+v^{*},\alpha+\gamma,\beta+g^{c}(u^{*},v^{*},\gamma))\in\operatorname{epi}(f+\lambda
h)^{c}$

for all $(u^{*},v^{*},\gamma)\in\operatorname{dom}g^{c}$. Since $\lambda$ was
any sequence from $\mathbb{R}^{(T)}_{+}$, we get the inclusion given in $ii)$.
∎

Now, we continue presenting a useful lemma from [14] and adapting [14, Lem.
4.1 (ii)] to the set $K$ defined in (2).

######  Lemma 4.4.

[14, Lem. 4.1 (i)] Let $\beta\in\mathbb{R}$ and $A$ the set defined in (1).
Then, there exists $\delta>0$ such that
$(0,0,\delta,\beta)\in\operatorname{epi}(f-g+\delta_{A})^{c}$ if and only if
$v\eqref{eq:Primal_problem}\geq-\beta$.

######  Remark 1.

Taking into account that
$(f-g+\delta_{A})^{c}(0,0,\delta)=\sup_{X}\left\\{-(f-g+\delta_{A})(x)\right\\}$,
for any $\delta>0$, it is evident that
$(0,0,\delta,\beta)\in\operatorname{epi}(f-g+\delta_{A})^{c}$, for a certain
$\delta>0$, if and only if
$(0,0,\delta,\beta)\in\operatorname{epi}(f-g+\delta_{A})^{c}$, for all
$\delta>0$.

######  Lemma 4.5.

Let $K$ be the set defined in (2) and $\beta\in\mathbb{R}$. Then,
$(0,0,0,\beta)\in K$ if and only if there exists
$\lambda\in\mathbb{R}^{(T)}_{+}$ such that for all
$(u^{*},v^{*},\gamma)\in\operatorname{dom}g^{c}$, it holds

$g^{c}(u^{*},v^{*},\alpha)-(f+\lambda h)^{c}(u^{*},v^{*},\gamma)\geq-\beta.$
(4)

###### Proof.

A point $(0,0,0,\beta)\in K$ if and only if there exists
$\lambda\in\mathbb{R}^{(T)}_{+}$ such that, for all
$(u^{*},v^{*},\gamma)\in\operatorname{dom}g^{c}$,

$(0,0,0,\beta)+(u^{*},v^{*},\gamma,g^{c}(u^{*},v^{*},\gamma))\in\operatorname{epi}(f+\lambda
h)^{c},$

which is equivalent to the inequality

$\left(f+\lambda
h\right)^{c}(u^{*},v^{*},\gamma)\leq\beta+g^{c}(u^{*},v^{*},\gamma)$

and (4) fulfills. ∎

Duality results for the primal-dual pair ($P$)$-$($\overline{D}_{L}$) are
based on the set

$K^{\prime}:=\left\\{(0,0,\delta,\beta)\,:\,(0,0,0,\beta)\in K\,\text{ and
}\,\delta>0\right\\}$ (5)

and the auxiliary set

$B:=\left\\{(0,0)\times\mathbb{R}_{++}\times\mathbb{R}\right\\}\subseteq
W\times\mathbb{R}.$ (6)

Together with the sets $K^{\prime}$ and $B$, the following lemmas will be
necessary in the sequel.

######  Lemma 4.6.

If $v(P)\in\mathbb{R}$, it holds

$\operatorname{epi}(f-g+\delta_{A})^{c}\cap
B=\left\\{(0,0,\delta,\beta)\,:\delta>0,\beta\geq-v\eqref{eq:Primal_problem}\right\\}=\bigcap_{X}\operatorname{epi}c^{\prime}(\cdot,x)-v\eqref{eq:Primal_problem}.$

Consequently, $\operatorname{epi}(f-g+\delta_{A})^{c}\cap B$ is an
$\operatorname{\text{e}^{\prime}}$-convex set.

###### Proof.

The first equality derives directly from Lemma 4.4. Now a point
$(x^{*},y^{*},\delta,\beta)$ belongs to the set
$\bigcap_{X}\operatorname{epi}c^{\prime}(\cdot,x)-v\eqref{eq:Primal_problem}$
if and only if, for all $x\in X$,

$c^{\prime}((x^{*},y^{*},\delta),x)-v(P)\leq\beta.$

Equivalently, for all $x\in X$,

$\left\langle x,y^{*}\right\rangle<\delta\text{ and }\left\langle
x,x^{*}\right\rangle-v(P)\leq\beta.$

This means that, necessarily, $x^{*}=y^{*}=0$, $\delta>0$ and
$-v(P)\leq\beta.$ So, $\operatorname{epi}(f-g+\delta_{A})^{c}\cap B$ is the
epigraph of the $\operatorname{\text{e}^{\prime}}$-convex function
$\sup_{X}\left\\{c^{\prime}(\cdot,x)-v\eqref{eq:Primal_problem}\right\\}$ and,
hence, it is $\operatorname{\text{e}^{\prime}}$-convex. ∎

######  Lemma 4.7.

Let us asumme that $v\eqref{eq:Dual_problem_2}\in\mathbb{R}$. Then

$\left\\{(0,0,\delta,\beta)\,:\delta>0,\beta>-v\eqref{eq:Dual_problem_2}\right\\}\subseteq
K^{\prime}\subseteq\left\\{(0,0,\delta,\beta)\,:\delta>0,\beta\geq-v\eqref{eq:Dual_problem_2}\right\\}.$
(7)

In particular, if $\eqref{eq:Dual_problem_2}$ is solvable, it holds

$K^{\prime}=\left\\{(0,0,\delta,\beta)\,:\delta>0,\beta\geq-v\eqref{eq:Dual_problem_2}\right\\}$
(8)

and, consequently, $K^{\prime}$ is $\operatorname{\text{e}^{\prime}}$-convex.

###### Proof.

Take a point $(0,0,\delta,\beta)$ in $W\times\mathbb{R}$ with $\delta>0$ and
$\beta>-v\eqref{eq:Dual_problem_2}$. Since
$v\eqref{eq:Dual_problem_2}>-\beta$, there would exist
$\lambda\in\mathbb{R}^{(T)}_{+}$ such that, for all
$(u^{*},v^{*},\gamma)\in\operatorname{dom}g^{c}$,

$g^{c}(u^{*},v^{*},\gamma)-(f+\lambda h)^{c}(u^{*},v^{*},\gamma)\geq-\beta,$

and, according to Lemma 4.5, $(0,0,0,\beta)\in K$ and therefore
$(0,0,\delta,\beta)\in K^{\prime}.$ The second inclusion in (7) also comes
directly from Lemma 4.5.
Now, let us suppose that $v\eqref{eq:Dual_problem_2}$ is attainable at
$\bar{\lambda}$. If $\beta\geq-v\eqref{eq:Dual_problem_2}$, we have

$g^{c}(u^{*},v^{*},\gamma)-(f+\bar{\lambda}h)^{c}(u^{*},v^{*},\gamma)\geq-\beta$

for all $(u^{*},v^{*},\gamma)\in\operatorname{dom}g^{c}$ and, according to
Lemma 4.5, $(0,0,0,\beta)\in K$ hence, for all $\delta>0$,
$(0,0,\delta,\beta)\in K^{\prime}$ and (8) holds. It is easy to see, as in the
proof of the previous lemma, that,

$\left\\{(0,0,\delta,\beta)\,:\delta>0,\beta\geq-v\eqref{eq:Dual_problem_2}\right\\}=\bigcap_{X}\operatorname{epi}c^{\prime}(\cdot,x)-v\eqref{eq:Dual_problem_2}.$

∎

######  Proposition 4.8.

Let $A$, $K^{\prime}$ and $B$ be the sets defined in (1), (5) and (6),
respectively. Then weak duality holds for ($P$)$-$($\overline{D}_{L}$) if and
only if

$K^{\prime}\subseteq\operatorname{epi}(f-g+\delta_{A})^{c}\cap B.$ (9)

###### Proof.

Let us assume that $v\eqref{eq:Primal_problem}\geq
v\eqref{eq:Dual_problem_2}.$ If $v\eqref{eq:Primal_problem}=-\infty$, then by
Lemma 4.4, $\operatorname{epi}(f-g+\delta_{A})^{c}\cap B=\emptyset$. On the
other hand, because $v\eqref{eq:Dual_problem_2}=-\infty$ too, by Lemma 4.5,
$K^{\prime}=\emptyset$.
Now, suppose that $v\eqref{eq:Primal_problem}\in\mathbb{R}$. Weak duality
implies that also $v\eqref{eq:Dual_problem_2}\in\mathbb{R}$ and the inclusion
(9) is a direct consequence from Lemmas 4.7 and 4.6.
Now we assume that (9) holds. If
$v\eqref{eq:Primal_problem}<v\eqref{eq:Dual_problem_2}$, we can take
$\beta\in\mathbb{R}$ in such a way that

$v\eqref{eq:Primal_problem}<-\beta<v\eqref{eq:Dual_problem_2}.$ (10)

Since $\beta>-v\eqref{eq:Dual_problem_2}$, by Lemma 4.7, for all $\delta>0$,
$(0,0,\delta,\beta)\in K^{\prime}$ and therefore, by (9),
$(0,0,\delta,\beta)\in\operatorname{epi}(f-g+\delta_{A})^{c}\cap B$, which is
not possible, in virtue of Lemma 4.6. ∎

######  Proposition 4.9.

Let $A$, $K^{\prime}$ and $B$ be the sets defined in (1), (5) and (6),
respectively. Then there exists zero duality gap for
($P$)$-$($\overline{D}_{L}$) if and only if

$\operatorname{{e}^{\prime}conv}K^{\prime}=\operatorname{epi}(f-g+\delta_{A})^{c}\cap
B.$ (11)

###### Proof.

Suppose that
$v\eqref{eq:Primal_problem}=v\eqref{eq:Dual_problem_2}\in\mathbb{R}$
(otherwise, $\operatorname{epi}(f-g+\delta_{A})^{c}\cap
B=K^{\prime}=\emptyset$ and $\emptyset$ is
$\operatorname{\text{e}^{\prime}}$-convex, since it is the epigraph of the
$\operatorname{\text{e}^{\prime}}$-convex function
$S=\sup_{X\times\mathbb{R}}c^{\prime}(\cdot,x)-\alpha)$.
In first place, we will see that

$\operatorname{{e}^{\prime}conv}\left\\{(0,0,\delta,\beta)\,:\delta>0,\beta>-v\eqref{eq:Primal_problem}\right\\}=\left\\{(0,0,\delta,\beta)\,:\delta>0,\beta\geq-v\eqref{eq:Primal_problem}\right\\}.$
(12)

Since, according to Lemma 4.6, the set
$\left\\{(0,0,\delta,\beta)\,:\delta>0,\beta\geq-v\eqref{eq:Primal_problem}\right\\}$
is $\operatorname{\text{e}^{\prime}}$-convex, it is clear that

$\operatorname{{e}^{\prime}conv}\left\\{(0,0,\delta,\beta)\,:\delta>0,\beta>-v\eqref{eq:Primal_problem}\right\\}\subseteq\left\\{(0,0,\delta,\beta)\,:\delta>0,\beta\geq-v\eqref{eq:Primal_problem}\right\\}.$

Let us denote by $H:W\rightarrow\mathbb{R}$ the
$\operatorname{\text{e}^{\prime}}$-convex function whose epigraph is
$\operatorname{{e}^{\prime}conv}\left\\{(0,0,\delta,\beta)\,:\delta>0,\beta>-v\eqref{eq:Primal_problem}\right\\}$.
Let us assume that

$H=\sup_{D}c^{\prime}(\cdot,x)-\alpha,$

where $D\subseteq X\times\mathbb{R}$. Then, for all $\delta>0$ and
$\beta>-v\eqref{eq:Primal_problem}$, for all $(x,\alpha)\in D$, we have

$c^{\prime}((0,0,\delta),x)-\alpha\leq\beta,$

or, equivalently,

$-\alpha\leq\beta,$ (13)

for all $\beta>-v\eqref{eq:Primal_problem}$, which means that $\alpha\geq
v\eqref{eq:Primal_problem}$, and $D$ is any nonempty subset of
$X\times\left[v(P),+\infty\right[.$ Let us show that

$\left\\{(0,0,\delta,\beta)\,:\delta>0,\beta\geq-v\eqref{eq:Primal_problem}\right\\}\subseteq\operatorname{{e}^{\prime}conv}\left\\{(0,0,\delta,\beta)\,:\delta>0,\beta>-v\eqref{eq:Primal_problem}\right\\}.$

For all $(x,\alpha)\in D$, if $\delta>0$ and $\beta\geq-v(P)$,

$c^{\prime}((0,0,\delta),x)-\alpha=-\alpha\leq-v(P)\leq\beta$

and hence $(0,0,\delta,\beta)\in\operatorname{epi}c^{\prime}(\cdot,x)-\alpha$,
therefore

$\left\\{(0,0,\delta,\beta)\,:\delta>0,\beta\geq-v\eqref{eq:Primal_problem}\right\\}\subseteq\bigcap_{D}\operatorname{epi}c^{\prime}(\cdot,x)-\alpha=\operatorname{epi}H$

and (12) fulfills.
Now, let us prove equality (11) under the hypothesis of zero duality gap.
According to Lemma 4.7, we will have

$\left\\{(0,0,\delta,\beta)\,:\delta>0,\beta>-v\eqref{eq:Primal_problem}\right\\}\subseteq
K^{\prime}\subseteq\left\\{(0,0,\delta,\beta)\,:\delta>0,\beta\geq-v\eqref{eq:Primal_problem}\right\\}.$

In virtue of Lemma 4.6 and the definition of e′-convex hull, we will have

$\operatorname{{e}^{\prime}conv}\left\\{(0,0,\delta,\beta)\,:\delta>0,\beta>-v\eqref{eq:Primal_problem}\right\\}\subseteq\operatorname{{e}^{\prime}conv}K^{\prime}\subseteq\operatorname{epi}(f-g+\delta_{A})^{c}\cap
B.$

According to equality (12), we obtain (11).
Now, let us suppose that (11) is true. Applying Proposition 4.8, we have
$v\eqref{eq:Primal_problem}\geq v\eqref{eq:Dual_problem_2}$. If
$v(P)=-\infty$, necessarily $v\eqref{eq:Dual_problem_2}=-\infty$, then suppose
that $v\eqref{eq:Primal_problem}\in\mathbb{R}$. Therefore
$v\eqref{eq:Dual_problem_2}\in\mathbb{R}$ too. Now, by Lemma 4.6 and (11), we
have

$\operatorname{{e}^{\prime}conv}K^{\prime}=\left\\{(0,0,\delta,\beta)\,:\delta>0,\beta\geq-v\eqref{eq:Primal_problem}\right\\},$

and by Lemma 4.7, taking e’convex hull, we obtain

$\operatorname{{e}^{\prime}conv}K^{\prime}\subseteq\left\\{(0,0,\delta,\beta):\delta>0,\,\beta\geq-v\eqref{eq:Dual_problem_2}\right\\},$

hence

$\left\\{(0,0,\delta,\beta):\delta>0,\,\beta\geq-v\eqref{eq:Primal_problem}\right\\}\subseteq\left\\{(0,0,\delta,\beta):\delta>0,\,\beta\geq-v\eqref{eq:Dual_problem_2}\right\\}$
(14)

and $v(P)\leq v\eqref{eq:Dual_problem_2}$. ∎

######  Proposition 4.10.

Let $A$, $K^{\prime}$ and $B$ be the sets defined in (1), (5) and (6),
respectively. Then strong duality holds for ($P$)$-$($\overline{D}_{L}$) if
and only if

$K^{\prime}=\operatorname{epi}(f-g+\delta_{A})^{c}\cap B.$ (15)

###### Proof.

Let us assume that there exists strong duality between $(P)$ and
($\overline{D}_{L}$) and both optimal values are finite (the infinite case is
discussed in Proposition 4.9). Acoording to Lemma 4.7, $K^{\prime}$ is
$\operatorname{\text{e}^{\prime}}$-convex, and from Proposition 4.9, we obtain
(15).
Let us check the converse implication. If
$K^{\prime}=\operatorname{epi}(f-g+\delta_{A})^{c}\cap B$, it implies in
particular that $K^{\prime}$ is an e′-convex set, then by Proposition 4.9,
$v\eqref{eq:Dual_problem_2}=v(P)$. In case $v(P)=-\infty$, strong duality
holds trivially, so let us assume that $v(P)=-\beta\in\mathbb{R}$.
By Lemma 4.4, $(0,0,\delta,\beta)\in\operatorname{epi}(f-g+\delta_{A})^{c}\cap
B$, for any $\delta>0$, and due to the equality in the hypothesis,
$(0,0,0,\beta)\in K$. Then according to Lemma 4.5, there exists
$\lambda_{0}\in\mathbb{R}^{(T)}_{+}$ such that for all
$(u^{*},v^{*},\gamma)\in\operatorname{dom}g^{c}$,

$v\eqref{eq:Dual_problem_2}\geq
g^{c}(u^{*},v^{*},\gamma)-(f+\lambda_{0}h)^{c}(u^{*},v^{*},\gamma)\geq-\beta=v\eqref{eq:Dual_problem_2},$

i.e., $\overline{D}_{L}$ is solvable and there exists strong duality for the
dual pair $(P)-$($\overline{D}_{L}$). ∎

##  5 Zero duality Gap and Strong duality for ($P$)$-$($D_{L}$)

Characterizations for zero duality gap and strong duality for
($P$)$-$($D_{L}$) can be obtained by means of the sets

$\displaystyle\Omega$
$\displaystyle:=\bigcup_{\mathbb{R}^{(T)}_{+}}\bigcap_{\operatorname{dom}g}\left[(g-f-\lambda
h)(x),+\infty\right[\subseteq\mathbb{R},$ $\displaystyle\Omega^{\prime}$
$\displaystyle:=\left\\{(0,0,\delta,\beta)\,:\,\delta>0,\beta\in\Omega\right\\}\subseteq
W\times\mathbb{R},$ (16)

with similar results to those in Section 4 for ($P$)$-$($\overline{D}_{L}$).
The following proposition has analogous proofs than Propositions 4.9 and 4.10.
The proof of $i)$ comes directly from the fulfilment of weak duality for
$(P)-(D_{L})$.

######  Proposition 5.1.

Let $A$, $\Omega^{\prime}$ and $B$ be the sets defined in (1), (16) and (6),
respectively. The following statements hold

  * i)

$\Omega^{\prime}\subseteq\operatorname{epi}(f+g-\delta_{A})^{c}\cap B$.

  * ii)

There exists zero duality gap for $(P)-(D_{L})$ if and only if

$\operatorname{{e}^{\prime}conv}\Omega^{\prime}=\operatorname{epi}(f-g+\delta_{A})^{c}\cap
B.$

  * iii)

There exists strong duality for $(P)-(D_{L})$ if and only if

$\Omega^{\prime}=\operatorname{epi}(f-g+\delta_{A})^{c}\cap B.$

###  5.1 Relation between strong dualities for (P)$-$($D_{L}$) and
(P)$-$($\overline{D}_{L}$)

This subsection aims to obtain conditions under which both strong dualities
are equivalent. The following theorem can be viewed as Lagrange counterpart of
Theorem 5.6 from [14].

######  Theorem 5.2.

Let $B$, $\Omega^{\prime}$, $K^{\prime}$ and $\Lambda$ the sets defined in
(6), (16), (5) and (3), respectively, and assume that

$\operatorname{epi}(f-g+\delta_{A})^{c}\cap B=\Lambda\cap B$ (17)

with $g$ having a proper e-convex minorant. Then the following statements are
equivalent

  * i)

There exists strong duality for $(P)-(D_{L})$;

  * ii)

There exists strong duality for $(P)-\left(\overline{D}_{L}\right)$ and
$\Omega^{\prime}=K^{\prime}$.

###### Proof.

The implication $ii)\Rightarrow i)$ is a direct consequence from Propositions
4.10 and 5.1. In this implication, condition (17) is not necessary.
$i)\Rightarrow ii)$ First of all, recall the dual problems ($P_{e}$) and
($D_{e,L}$) defined in the proof of Proposition 4.1

$\inf_{A}\left\\{f(x)-\operatorname{econv}g(x)\right\\}$ ($P_{e}$)
$\sup_{\mathbb{R}^{(T)}_{+}}\inf_{X}\left\\{f(x)-\operatorname{econv}g(x)+\lambda
h(x)\right\\}.$ ($D_{e,L}$)

In that proposition it was shown that $v(P_{e})\geq v(\overline{D}_{L})$.
Now, we will prove that $v(P)=v(P_{e})$. Since $\operatorname{econv}g\leq g$,
then $v(P_{e})\geq v(P)$. In case $v(P_{e})>v(P)$, it is enough to consider
any $\beta\in\mathbb{R}$ such that

$v(P)<-\beta\leq v(P_{e}).$

Applying Lemma 4.4 to $(P_{e})$, we obtain that
$(0,0,\delta,\beta)\in\operatorname{epi}(f-\operatorname{econv}g+\delta_{A})^{c}$,
for certain $\delta>0$, and by Lemma 4.3 $i)$, $(0,0,\delta,\beta)\in\Lambda$.
In virtue of equality (17),
$(0,0,\delta,\beta)\in\operatorname{epi}(f-g+\delta_{A})^{c}$, so again,
applying Lemma 4.4 to $(P)$, $v(P)\geq-\beta$, which is a contradiction. Then,
$v(P)=v(P_{e})$. This means that weak duality holds for
$(P)-(\overline{D}_{L})$. Equivalently, according to Propositions 4.8 and 5.1,

$K^{\prime}\subseteq\operatorname{epi}(f-g+\delta_{A})^{c}\cap
B=\Omega^{\prime}.$

Finally, we will see that $\Omega^{\prime}\subseteq K^{\prime}$. Take any
point $(0,0,\delta,\beta)\in\Omega^{\prime}$. We shall prove that
$(0,0,0,\beta)\in K$. By definition of the set $\Omega^{\prime}$ in (16),
there exists $\lambda\in\mathbb{R}^{(T)}_{+}$ such that for all
$x\in\operatorname{dom}g$,

$-g(x)+\beta\geq-(f+\lambda h)(x).$

Hence, for all $(u^{*},v^{*},\gamma)\in W$,

$g^{c}(u^{*},v^{*},\gamma)+\beta\geq(f+\lambda h)^{c}(u^{*},v^{*},\gamma),$

and
$(u^{*},v^{*},\gamma,g^{c}(u^{*},v^{*},\gamma)+\beta)\in\operatorname{epi}(f+\lambda
h)^{c}$, in particular for all
$(u^{*},v^{*},\gamma)\in\operatorname{dom}g^{c}$, concluding that
$(0,0,0,\beta)\in K$. Hence,
$K^{\prime}=\operatorname{epi}(f-g+\delta_{A})^{c}\cap B=\Omega^{\prime}$ and,
moreover, according to Proposition 4.10, there exists strong duality for
$(P)-\left(\overline{D}_{L}\right)$. ∎

##  6 Fenchel-Lagrange duality

Having studied characterizations for Fenchel and Lagrange weak and strong
dualities, and also zero duality gap for DC primal optimization problems, one
cannot forget the natural combination between Fenchel and Lagrange dual
problems. This mixed model, which is called Fenchel-Lagrange dual problem, was
introduced by Bot and Wanka for a convex optimization primal problem in [38]
by means of Fenchel conjugation scheme and making use of the pertubational
approach. In [20] it was built an alternative Fenchel-Lagrange dual using the
$c$-conjugation pattern, fulfilling weak duality by construction, which reads,
in the DC optimization context, like this

$\sup_{\begin{subarray}{c}\lambda\in\mathbb{R}^{(T)}_{+},\\\ x^{*},y^{*}\in
X^{*},\\\
\alpha_{1}+\alpha_{2}>0\end{subarray}}\left\\{-(f-g)^{c}(-x^{*},-y^{*},\alpha_{1})-(\lambda
h)^{c}(x^{*},y^{*},\alpha_{2})\right\\}.$ ($D_{FL}$)

Applying [14, Sec.3] to the previous Fenchel-Lagrange dual problem, we can
consider the following reformulation of ($D_{FL}$),

$\sup_{\mathbb{R}^{(T)}_{+},Z}\left\\{-(f-g)^{c}(-x^{*},-y^{*},\alpha)-(\lambda
h)^{c}(x^{*},y^{*},\alpha)\right\\},$ ($D_{FL}$)

where $Z:=X^{*}\times X^{*}\times\mathbb{R}_{++}$. Moreover, as it happened
for Fenchel and Lagrange dual problems, it is also possible to derive an
alternative formulation for ($D_{FL}$), provided that the function $g$ is
e-convex. Proceeding along the lines of [14, Sec.3] and replacing the function
$g$ by $g^{cc^{\prime}}$ in $(f-g)^{c}$, we get

$(f-g)^{c}(-x^{*},-y^{*},\alpha)=\sup_{\operatorname{dom}g^{c}}\left\\{f^{c}(u^{*}-x^{*},-y^{*},\alpha)-g^{c}(u^{*},v^{*},\gamma)\right\\}.$
(18)

Applying (18) in ($D_{FL}$) we obtain an equivalent refomulation, in case $g$
is e-convex,

$\sup_{\begin{subarray}{c}\mathbb{R}^{(T)}_{+},Z\end{subarray}}\biggl{\\{}\inf_{\operatorname{dom}{g^{c}}}\left\\{g^{c}(u^{*},v^{*},\gamma)-f^{c}(u^{*}-x^{*},-y^{*},\alpha)\right\\}-(\lambda
h)^{c}(x^{*},y^{*},\alpha)\biggr{\\}}.$ ($\overline{D}_{FL}$)

Considering ($\overline{D}_{FL}$) as a new Fenchel-Lagrange dual problem for
($P$) with $g$ just a convex, but not necessarily e-convex function, even weak
duality might fail, as one can see in the following example.

######  Example 6.1.

Let $T$ be a singleton and $f,g,h:X\to\overline{\mathbb{R}}$ defined as in
Example 3.1

$f(x)=\left\\{\begin{aligned} x,~{}&~{}\text{if }x\geq 0,\\\
+\infty,~{}&~{}\text{otherwise;}\end{aligned}\right.\hskip
9.95863ptg(x)=\left\\{\begin{aligned} x,~{}&~{}\text{if }x>0,\\\
1,~{}&~{}\text{if }x=0,\\\
+\infty,~{}&~{}\text{otherwise;}\end{aligned}\right.\hskip
9.95863pth(x)=\left\\{\begin{aligned} -x,~{}&~{}\text{if }x\geq 0,\\\
+\infty,~{}&~{}\text{otherwise.}\end{aligned}\right.$

We obtained $A=\left[0,+\infty\right]$ and $v\eqref{eq:Primal_problem}=-1$.
Moreover,
$\operatorname{dom}g^{c}=\left\\{(u^{*},v^{*},\alpha)\in\mathbb{R}^{3}:u^{*}\leq
1,v^{*}\leq 0,\alpha>0\right\\}$ and, for all
$(u^{*},v^{*},\alpha)\in\operatorname{dom}g^{c}$,

$g^{c}(u^{*},v^{*},\gamma)=\left\\{\begin{aligned} 0,~{}&~{}\text{if
}u^{*}\leq 1,v^{*}\leq 0,\gamma>0\\\
+\infty,~{}&~{}\text{otherwise.}\end{aligned}\right.$

On the other hand, for $(x^{*},y^{*},\alpha)\in\mathbb{R}^{3}$ and
$u^{*}\in\mathbb{R}$ such that
$(u^{*},v^{*},\gamma)\in\operatorname{dom}g^{c}$, we have

$\displaystyle f^{c}(u^{*}-x^{*},-y^{*},\alpha)$
$\displaystyle=\sup_{\mathbb{R}}\left\\{c(x,(u^{*}-x^{*},-y^{*},\alpha))-f(x)\right\\}$
$\displaystyle=\left\\{\begin{aligned} \sup_{x\geq
0}\left\\{x(u^{*}-x^{*}-1)\right\\},~{}&~{}\text{if }y^{*}\geq 0,\alpha>0\\\
+\infty,~{}&~{}\text{otherwise,}\end{aligned}\right.$
$\displaystyle=\left\\{\begin{aligned} 0,~{}&~{}\text{if }u^{*}-x^{*}\leq
1,y^{*}\geq 0,\alpha>0\\\
+\infty,~{}&~{}\text{otherwise.}\end{aligned}\right.$ $\displaystyle(\lambda
h)^{c}(x^{*},y^{*},\alpha)$
$\displaystyle=\sup_{\mathbb{R}}\left\\{c(x,(x^{*},y^{*},\alpha))-\lambda
h(x)\right\\}$ $\displaystyle=\left\\{\begin{aligned} \sup_{x\geq
0}\left\\{x(x^{*}+\lambda)\right\\},~{}&~{}\text{if }y^{*}\leq 0,\alpha>0\\\
+\infty,~{}&~{}\text{otherwise,}\end{aligned}\right.$
$\displaystyle=\left\\{\begin{aligned} 0,~{}&~{}\text{if
}x^{*}\leq-\lambda,y^{*}\leq 0,\alpha>0\\\
+\infty,~{}&~{}\text{otherwise.}\end{aligned}\right.$

We conclude that, for all $(u^{*},v^{*},\gamma)\in\operatorname{dom}g^{c}$,
the function

$g^{c}(u^{*},v^{*},\gamma)-f^{c}(u^{*}-x^{*},-y^{*},\alpha)-(\lambda
h)^{c}(x^{*},y^{*},\alpha)$

is finite (not $-\infty$) if and only if $y^{*}=0,\alpha>0,x^{*}\leq-\lambda$
and $x^{*}\geq u^{*}-1$, in such a case, its value is zero. Then, if
$(x^{*},y^{*},\alpha)\in\mathbb{R}^{3}$ and $\lambda\geq 0$

$\displaystyle\inf_{\operatorname{dom}{g^{c}}}\left\\{g^{c}(u^{*},v^{*},\gamma)-f^{c}(u^{*}-x^{*},-y^{*},\alpha)\right\\}-(\lambda
h)^{c}(x^{*},y^{*},\alpha)$ $\displaystyle=\left\\{\begin{aligned}
0,~{}&~{}\text{if }y^{*}=0,\alpha>0,x^{*}\leq-\lambda,x^{*}\geq u^{*}-1,\\\
-\infty,~{}&~{}\text{otherwise,}\end{aligned}\right.$

and

$v\eqref{eq:Dual_problem_2}=\sup_{\begin{subarray}{c}\mathbb{R}_{+},Z\end{subarray}}\biggl{\\{}\inf_{\operatorname{dom}{g^{c}}}\left\\{g^{c}(u^{*},v^{*},\gamma)-f^{c}(u^{*}-x^{*},-y^{*},\alpha)\right\\}-(\lambda
h)^{c}(x^{*},y^{*},\alpha)\biggr{\\}}=0.$

$\square$

From this example it is clear that conditions ensuring both weak and strong
dualities for the dual pair ($\overline{D}_{FL}$)-($P$) are needed, as it used
to happen for Fenchel and Lagrange dualities in Section 4 and [14]. Let us
define the set

$\displaystyle
K^{\prime\prime}:=\bigcup_{\mathbb{R}^{(T)}_{+}}~{}\bigcup_{\operatorname{dom}\lambda
h}~{}\bigcap_{\operatorname{dom}g^{c}}\biggl{\\{}$
$\displaystyle\operatorname{epi}\bigl{(}f-c(\cdot,(y^{*},v^{*},\alpha))\bigr{)}^{c}$
(19) $\displaystyle-\Bigl{(}x^{*},0,0,g^{c}(x^{*},u^{*},\gamma)-(\lambda
h)^{c}(-y^{*},-v^{*},\alpha)\Bigr{)}\biggr{\\}},$

which will shortly allow us to derive analogous duality results not only for
weak but also for strong duality between ($\overline{D}_{FL}$)$-$($P$). As
expected, this set turns out to be a combination of [14, Eq. (2)] and (2). In
addition, it is straightforward to derive the corresponding Fenchel-Lagrange
version of Lemma 4.5 from this manuscript or [14, Lem. 4.1 ii)]. To avoid
unnecessary repetitions, we conclude this section presenting next result where
we characterize zero duality gap together with weak and strong dualities for
($P$)$-$($\overline{D}_{FL}$). We omit the proof since its arguments resemble
the ones used in Section 4 from this manuscript and in [14, Sect. 4].

######  Theorem 6.2.

Let $A$, $K^{\prime\prime}$ and $B$ the sets defined in (1), (19) and (6),
respectively. The following statements hold

  * i)

Weak duality holds for ($P$)$-$($\overline{D}_{FL}$) if and only if

$K^{\prime\prime}\cap B\subseteq\operatorname{epi}(f-g+\delta_{A})^{c}\cap B.$

  * ii)

There exists zero duality gap for ($P$)$-$($\overline{D}_{FL}$) if and only if

$\operatorname{{e}^{\prime}conv}(K^{\prime\prime})\cap
B=\operatorname{epi}(f-g+\delta_{A})^{c}\cap B.$

  * iii)

Strong duality holds for ($P$)$-$($\overline{D}_{FL}$) if and only if

$K^{\prime\prime}\cap B=\operatorname{epi}(f-g+\delta_{A})^{c}\cap B.$

##  7 Conclusions

In this paper we present two dual problems for a general DC primal problem
with an arbitrary number of inequality convex constraints. Under the even
convexity of just one of the functions in the objective, both dual problems
turn out to be equivalent. While for one of them weak duality trivially holds,
for the other we need extra conditions to ensure it when one of the involved
functions is just convex but not necessarily e-convex. We develop
characterizations not only for weak duality, but also for zero duality gap and
strong duality for both dual pairs and we study the relation between both
strong dualities. Finally, we adapt our results from this work and from [14]
to, after a derivation of an alternative Fenchel-Lagrange dual problem to the
one stated in [20], study not only weak but also zero duality gap and strong
duality between this new Fenchel-Lagrange dual problem and the primal DC
problem ($P$).

## Disclosure statement

The authors declare that they have no conflict of interest.

## Funding

Research partially supported by MICIIN of Spain, Grant AICO/2021/165.

## References

  * [1] F.J. Aragón-Artacho, R. Campoy, and P.T. Vuong.  The boosted DC algorithm for linearly constrained DC programming.  Set-Valued and Variational Analysis, 30:1265–1289, 2022.
  * [2] H.H. Bauschke and P.L. Combettes.  Convex Analysis and Monotone Operator Theory in Hilbert Spaces.  Springer New York, NY, 2011.
  * [3] R Bergmann, O.P. Ferreira, E.M. Santos, and J.C.O Souza.  The difference of convex algorithm on hadamard manifolds.  Journal of Optimization Theory and Applications, 2024.
  * [4] R. Bergmann, R. Herzog, M. Silva-Louzeiro, D. Tenbrinck, and J. Vidal-Nunez.  Fenchel duality theory and a primal-dual algorithm on Riemannian manifolds.  Foundations of Computational Mathematics, 21:1465–1504, 2021.
  * [5] R.I. Boţ.  Conjugate Duality in Convex Optimization, volume 637.  Lecture Notes in Economics and Mathematical Systems, Springer-Verlag, Berlin Heidelberg, 2010.
  * [6] R.I. Boţ, S.M. Grad, and G. Wanka.  On strong and total lagrange duality for convex optimization problems.  Journal of Mathematical Analysis and Applications, 337(2):1315–1325, 2008.
  * [7] R.I. Boţ and G. Wanka.  An alternative formulation for a new closed cone constraint qualification.  Nonlinear Analysis, 64:1367–1381, 2006.
  * [8] E. Carrizosa, V. Guerrero, and D. Romero-Morales.  Visualizing data as objects by DC (difference of convex) optimization.  Mathematical Programming Ser. B, 169:119–140, 2018.
  * [9] A. Chambolle and T. Pock.  A first-order primal-dual algorithm for convex problems with applications to imaging.  Journal of Mathematical Imaging and Vision, 40(1):120–145, 2011\.
  * [10] A. Daniilidis and J.E. Martínez-Legaz.  Characterizations of evenly convex sets and evenly quasiconvex functions.  Journal of Mathematical Analysis and Applications, 273:58–66, 2002\.
  * [11] I. Ekeland and R. Temam.  Convex Analysis and Variational Problems.  North-Holland Publishing Company, Amsterdam, 1976.
  * [12] M. D. Fajardo and J. Vidal.  E′-convex sets and functions: Properties and characterizations.  Vietnam Journal of Mathematics, 48(3):407–423, 2020.
  * [13] M. D. Fajardo and J. Vidal.  On subdifferentials via a generalized conjugation scheme: an application to DC problems and optimality conditions.  Set-Valued and Variational Analysis, 30:1313–1331, 2022 (available on line).
  * [14] M. D. Fajardo and J. Vidal.  On Fenchel c-conjugate dual problems for DC optimization: characterizing weak, strong and stable strong duality.  Optimization, 2023 (available on line).
  * [15] M.D. Fajardo.  Regularity conditions for strong duality in evenly convex optimization problems. An application to Fenchel duality.  Journal of Convex Analysis, 22(3):711–731, 2015.
  * [16] M.D. Fajardo, M.A. Goberna, M.M.L. Rodríguez, and J. Vicente-Pérez.  Even Convexity and Optimization.  Springer, Cham, 2020.
  * [17] M.D. Fajardo, M.M.L. Rodríguez, and J. Vidal.  Lagrange duality for evenly convex optimization problems.  Journal of Optimization Theory and Applications, 168(1):109–128, 2016.
  * [18] M.D. Fajardo, J. Vicente-Pérez, and M.M.L. Rodríguez.  Infimal convolution, $c$-subdifferentiability and Fenchel duality in evenly convex optimization.  TOP, 20(2):375–396, 2012.
  * [19] M.D. Fajardo and J. Vidal.  Stable strong Fenchel and Lagrange duality for evenly convex optimization problems.  Optimization, 65(9):1675–1691, 2016.
  * [20] M.D. Fajardo and J. Vidal.  A comparison of alternative $c$-conjugate dual problems in infinite convex optimization.  Optimization, 66(5):705–722, 2017.
  * [21] M.D. Fajardo and J. Vidal.  Necessary and sufficient conditions for strong Fenchel-Lagrange duality via a coupling conjugation scheme.  Journal of Optimization Theory and Applications, 176(1):57–73, 2018\.
  * [22] D.H. Fang, G.M. Lee, C. Li, and J.C. Yao.  Extended Farkas’s lemmas and strong Lagrange dualities for DC infinite programming.  J. of Nonlinear and Convex Analysis, 14(4):747–767, 2013.
  * [23] W. Fenchel.  A remark on convex sets and polarity.  Comm. Sèm. Math. Univ. Lund (Medd. Lunds Algebra Univ. Math. Sem.), (Tome Supplémentaire):82–89, 1952.
  * [24] M. Herrmann, R. Herzog, H. Kröner, S. Schmidt, and J. Vidal.  Analysis and an interior-point approach for TV image reconstruction problems on smooth surfaces.  SIAM Journal on Imaging Sciences, 11(2):889–922, 2018.
  * [25] R. Horst and N.V. Thoai.  DC programming: overview.  Journal of Optimization Theory and Applications, 103(1):1–43, 1999\.
  * [26] V. Jeyakumar, N. Dihn, and G.M. Lee.  A new closed constraint qualification for convex optimization.  Appl. Math. Report AMR 04/8, 2004.  University of New South Wales.
  * [27] V. Klee, E. Maluta, and C. Zanco.  Basic properties of evenly convex sets.  Journal of Convex Analysis, 14(1):137–148, 2006.
  * [28] J.E. Martínez-Legaz.  Generalized convex duality and its economic applications.  In Handbook of generalized convexity and generalized monotonicity, volume 76 of Nonconvex Optim. Appl., pages 237–292. Springer.
  * [29] J.E. Martínez-Legaz and J. Vicente-Pérez.  The e-support function of an e-convex set and conjugacy for e-convex functions.  Journal of Mathematical Analysis and Applications, 376:602–612, 2011.
  * [30] J.E. Martínez-Legaz and M. Volle.  Duality in D.C. programming: the case of several D.C. constraints.  Journal of Mathematical Analysis and Applications, 237:657–671, 1999.
  * [31] J.J. Moreau.  Inf-convolution, sous-additivité, convexité des fonctions numériques.  Journal de Mathématiques Pures et Appliquées, 49:109–154, 1970\.
  * [32] R.T. Rockafellar.  Convex Analysis.  Princeton University Press, Princeton, 1970.
  * [33] M.M.L. Rodríguez and J. Vicente-Pérez.  On evenly convex functions.  Journal of Convex Analysis, 18:721–736, 2011.
  * [34] P.H. Tao and L.T.H. An.  Convex analysis approach to DC programming: theory, algorithms and applications.  Acta Mathematica Vietnamica, 22(1):289–355, 1997.
  * [35] H.A.L. Thi and T.P. Dinh.  DC programming and DCA: thirty years of developments.  Mathematical Programming Ser. B, 169:5–68, 2018.
  * [36] H.A.L. Thi and T.P. Dinh.  Open issues and recent advances in DC programming and DCA.  Journal of Global Optimization, 2023.
  * [37] Oliveira W.  The ABC of DC programming.  Set-Valued and Variational Analysis, 28:679–706, 2020.
  * [38] G. Wanka and R.I. Boţ.  On the relations between different dual problems in convex mathematical programming.  Springer-Verlag, Heidelberg, Germany, 2002.  P. Chamoni, R. Leisten, A. Martin, J. Minnemann and H. Stadtler.
  * [39] C. Zălinescu.  Convex Analysis in General Vector Spaces.  World Scientific, New Jersey, 2002.