Evenly Convex Functions

Abstract

In this chapter we introduce evenly convex functions as those whose epigraphs are evenly convex sets, and develop a duality theory for nonlinear programming problems involving evenly convex functions, that is, evenly convex optimization problems. In Sect. 4.1 we present the main properties of this class of convex functions that contains the important subclass of lower semicontinuous convex functions, whose relevance in convex analysis comes from the fact that the Fenchel conjugacy is an involution on most of them. More precisely, any proper lower semicontinuous convex function coincides with its biconjugate. In Sects. 4.2 and 4.3 we introduce the evenly convex hull of a function and appropriate conjugation schemes for evenly convex functions, respectively. Finally, in Sect. 4.4, we use the perturbational approach for developing the so-called c-conjugate duality theory, providing closedness-type regularity conditions. These conditions will be expressed in terms of the even convexity of the involved functions, for both strong and stable strong duality for convex optimization problems.

In this chapter we introduce evenly convex functions as those whose epigraphs are evenly convex sets, and develop a duality theory for nonlinear programming problems involving evenly convex functions, that is, evenly convex optimization problems. In Sect. 4.1 we present the main properties of this class of convex functions that contains the important subclass of lower semicontinuous convex functions, whose relevance in convex analysis comes from the fact that the Fenchel conjugacy is an involution on most of them. More precisely, any proper lower semicontinuous convex function coincides with its biconjugate. In Sects. 4.2 and 4.3 we introduce the evenly convex hull of a function and appropriate conjugation schemes for evenly convex functions, respectively. Finally, in Sect. 4.4, we use the perturbational approach for developing the so-called c-conjugate duality theory, providing closedness-type regularity conditions. These conditions will be expressed in terms of the even convexity of the involved functions, for both strong and stable strong duality for convex optimization problems.

4.1 Evenly Convex Functions

In the same way that convex functions are defined by the convexity of their epigraphs, we will say that an extended real-valued function $f:\mathbb {R}^{n}\rightarrow \overline {\mathbb {R}}$ is evenly convex (in brief, e-convex) provided that its epigraph $\operatorname {epi}f$ is an e-convex set in $\mathbb {R}^{n+1}$. Obviously, any e-convex function is convex and, since any closed convex set is e-convex, lsc convex functions constitute a subclass of e-convex functions. In particular, any finite-valued convex function is e-convex.

The next two examples show that not every convex function is e-convex and not every e-convex function is a lower semicontinuous convex function, respectively.

Example 4.1 (Example 3.2 Revisited)

The epigraph of the function f defined in Example 3.2, which is represented in Fig. 4.1, is obviously a convex set, but it is not e-convex. In fact, considering $\overline {x}=(1,2)\in \mathbb {R}^{2}\backslash \left ( \operatorname {epi}f\right )$, we have that, for any hyperplane H containing $\overline {x}$, $H\cap \left ( \operatorname {epi}f\right ) \neq \emptyset$.

Fig. 4.1

$\operatorname {epi}f$ is not e-convex

Example 4.2

One can easily check that the epigraph, represented in Fig. 4.2, of the function $f:\mathbb {R}\rightarrow \overline {\mathbb {R}}$ defined by

$$\displaystyle \begin{aligned} f\left( x\right) =\left\{ \begin{array}{cl} x^{2}, & \text{if}\ x>-1, \\ +\infty , & \text{if}\ x\leq -1, \end{array} \right. \end{aligned}$$

Fig. 4.2

f is an e-convex function but it is not lower semicontinuous

is e-convex, but it is not closed. Then, f is an e-convex function which is not lower semicontinuous.

Recall that closedness of lower level sets characterizes the class of lower semicontinuous functions. While lower level sets are convex for convex functions, a function whose lower level sets are all convex needs not be convex (see, e.g., the function f in Example 3.7). Analogously, lower level sets of e-convex functions are all e-convex, that is, every e-convex function is e-quasiconvex as well. This fact follows from the identity

$$\displaystyle \begin{aligned}{}[f\leq r] \times \{r\} = (\operatorname{epi}f) \cap (\mathbb{R}^{n} \times \{r\}), \quad \forall r \in\mathbb{R},\end{aligned}$$

and the properties of e-convex sets studied in Chap. 1 (see Proposition 1.2(iii) and (v)).

Having these facts in mind, the following diagram shows the relations between different types of convex and quasiconvex functions.

It is well-known that the effective domain of a convex function is a convex set, since it is the projection on $\mathbb {R}^{n}$ of the epigraph. However, the projection of an e-convex set is not, in general, e-convex. Then, the effective domain of an e-convex function is convex but not necessarily e-convex, as the following example shows Example 4.3.

Example 4.3

Let $f:\mathbb {R}^{2}\rightarrow \overline {\mathbb {R}}$ be the function defined by

$$\displaystyle \begin{aligned} f\left( x\right) =\left\{ \begin{array}{ll} x_{1}\ln \frac{x_{1}}{x_{2}}, & \text{if}\ x\in E, \\ 0, & \text{if}\ x=0_{2}, \\ +\infty , & \text{otherwise,} \end{array} \right. \end{aligned}$$

where $E=\left \{ x\in \mathbb {R}^{2}:0<x_{1}\leq 1,\;0<x_{2}\leq x_{1}\right \}$, whose graph is represented in Fig. 4.3. Observe that $\operatorname {dom}f=E\cup \left \{ 0_{2}\right \}$ (represented in Fig. 4.4) is not e-convex, although, as we shall see, f is a lower semicontinuous convex function and, therefore, it is e-convex.

Consider the function $g:\mathbb {R}_{++}^{2}\rightarrow \mathbb {R}$ defined by $g\left ( x\right ) =x_{1}\ln \frac {x_{1}}{x_{2}}$, where $\mathbb {R }_{++}^{2}=(]0,+\infty \lbrack )^{2}$. Since g is a twice continuously differentiable real-valued function on the open convex set $\mathbb {R} _{++}^{2}$ and its Hessian matrix is positive semi-definite for every $x\in \mathbb {R}_{++}^{2}$, according to [148, Th. 4.5], we have that g is a convex function on $\mathbb {R}_{++}^{2}$. On the other hand, both functions f and g coincide on the convex subset E of $\mathbb {R} _{++}^{2}$ and, hence, f is convex on E. The convexity of f on $\operatorname { dom} f=E\cup \left \{ 0_{2}\right \}$ can be easily proved showing that $f\left ( \lambda x+\left ( 1-\lambda \right ) y\right ) \leq \lambda f\left ( x\right ) +\left ( 1-\lambda \right ) f\left ( y\right )$ for x ∈ E, y = 0₂ and 0 < λ < 1. So, f is a convex function.

Since every convex function is always lsc except perhaps at relative boundary points of its domain, we only have to prove that f is lsc on $\operatorname {rbd}\left ( \operatorname {dom}f\right )$.

Since g is a finite-valued convex function on $\mathbb {R} _{++}^{2}$, g is lsc at any $\overline {x}\in \mathbb {R}_{++}^{2}$, i.e., for all $\lambda <g\left ( \overline {x}\right )$, there exists a neighborhood of $\overline {x}$, $V_{\overline {x}}$, in $\mathbb {R}_{++}^{2}$ such that $\lambda <g\left ( x\right )$ for all $x\in V_{\overline {x}}$. Then, given $\overline {x}\in \operatorname {rbd}\left ( \operatorname {dom}f\right ) \cap E\subset \mathbb {R} _{++}^{2}$, we have that, for all $\lambda <f\left ( \overline {x}\right ) =g\left ( \overline {x}\right )$, there exists a neighborhood of $\overline {x}$ , $V_{\overline {x}}$, in $\mathbb {R}_{++}^{2}\subset \mathbb {R}^{2}$ such that $\lambda <g\left ( x\right ) =f\left ( x\right )$ for all $x\in V_{ \overline {x}}\cap E$. Obviously, if $x\in V_{\overline {x}}\cap ( \mathbb {R} ^{2}\backslash E) \subset \mathbb {R}^{2}\backslash \left ( \operatorname {dom}f\right )$, then $f\left ( x\right ) =+\infty >\lambda$, so that f is lsc at $\overline {x}$.

On the other hand, lower semicontinuity of f at 0₂ is a direct consequence of $f\left ( x\right ) \geq 0=f\left ( 0_{2}\right )$ for all $x\in \mathbb {R}^{2}$.

Finally, for $\overline {x}\in \left ] 0,1\right ] \times \left \{ 0\right \}$, we have $f\left ( \overline {x}\right ) =+\infty >\lambda$ for all $\lambda \in \mathbb {R}$. Moreover, since

$$\displaystyle \begin{aligned} \lim_{\substack{ x\rightarrow \overline{x} \\ x\in E}}f\left( x\right) =\lim _{\substack{ x\rightarrow \overline{x} \\ x\in E}}g\left( x\right) =+\infty , \end{aligned}$$

we have that, given any $\lambda \in \mathbb {R}$, there exists a neighborhood of $\overline {x}$, $V_{\overline {x}}$, in $\mathbb {R} ^{2}\backslash \left \{ 0_{2}\right \}$ such that $f\left ( x\right ) >\lambda$ , for all $x\in V_{\overline {x}}\cap E$, and $f\left ( x\right ) =+\infty >\lambda$, for all $x\in V_{\overline {x}}\cap (\mathbb {R}^{2}\backslash E)$. Then, f is also lsc on $\left ] 0,1\right ] \times \left \{ 0\right \}$.

The next result states conditions ensuring the even convexity of the effective domain of an e-convex function. Recall that a function is said to be improper if it is not proper (i.e., if it is identically + ∞ or takes the value −∞ at some point). Clearly, the improper e-convex functions identically either + ∞ or −∞ have e-convex effective domains. Precise references to all missing proofs in this chapter are appropriately given in Sect. 4.5.

Theorem 4.1 (On the Effective Domain of an e-Convex Function)

Let $f:\mathbb {R}^{n}\rightarrow \overline {\mathbb {R}}$.

• (i) If f is an improper function such that $f\left ( \overline {x} \right ) =-\infty$ for some $\overline {x}\in \mathbb {R}^{n}$, then f is e-convex if and only if $\operatorname {dom}f$ is e-convex and $f\left ( x\right ) =-\infty$ for all $x\in \operatorname {dom}f$.

• (ii) If f is a proper e-convex function bounded from above on $\operatorname {dom}f$, then $\operatorname {dom}f$ is e-convex.

So, the even convexity of the effective domain is a necessary condition for the even convexity of proper functions which are bounded from above. However, this is not a sufficient condition, as illustrates the function considered in Example 4.1, which is bounded on $\operatorname {dom}f=\left ] -1,1\right ]$ and $\operatorname {dom}f$ is e-convex, but f is not e-convex.

As stated in Diagram 4.1, the class of e-convex functions is intermediate between the class of lower semicontinuous convex functions and the class of convex functions (that are always lower semicontinuous except perhaps at relative boundary points of their domains). Next we provide a characterization of proper e-convex functions in terms of lower semicontinuity.

Diagram 4.1

Evenly convex and related functions

Fig. 4.3

The graph of f

Fig. 4.4

The domain of f is not e-convex

Theorem 4.2 (Characterization of e-Convex Functions I)

Let $f:\mathbb {R}^{n}\rightarrow \overline {\mathbb {R}}$ be a proper function. Then, f is e-convex if and only if f is convex and lower semicontinuous on $\operatorname {eco}\left ( \operatorname {dom}f\right )$.

Corollary 4.1

Let $f:\mathbb {R}^{n}\rightarrow \overline {\mathbb {R}}$ be an e-convex function whose effective domain is closed. Then, f is a lower semicontinuous convex function.

It is well-known that any convex function f is lsc/usc/continuous relative to $\operatorname {rint}\operatorname {dom}f$ (see [148, Th. 10.1]). Moreover, if f is a proper e-convex function, then f is lower semicontinuous on the greater set $\operatorname {eco}\operatorname {dom}f$. When we ask whether any proper convex function f can be assumed upper semicontinuous on $\operatorname {rbd}\left ( \operatorname {dom}f\right ) \cap \operatorname {dom}f$ relative to $\operatorname {dom}f$, the answer is negative in general (see [148, p. 83]). However, it is easy to prove that this property holds for univariate functions. Consequently, we consider the concept of upper semicontinuity along lines (as in [114] ).

Given a nonempty convex set $A\subset \mathbb {R}^{n}$, a function $f:\mathbb { \ R}^{n}\rightarrow \overline {\mathbb {R}}$ is said to be upper (resp. lower) semicontinuous along lines on $A\subset \mathbb {R}^{n}$ if, for every x, y ∈ A, the function $f_{x,y}:[0,1]\rightarrow \overline {\mathbb {R}}$, given by

$$\displaystyle \begin{aligned} f_{x,y}(t):=f(x+t(y-x)), \end{aligned}$$

is upper semicontinuous (resp. lower semicontinuous) at t relative to [0, 1], for any t ∈ [0, 1]. Moreover, f is said to be continuous along lines on A if f is upper and lower semicontinuous along lines on A.

For any proper convex function f, $\operatorname {dom}f$ is a nonempty convex set and, for every $x,y \in \operatorname {dom}f$, f _x,y is a univariate convex function and, therefore, it is upper semicontinuous relative to [0, 1]. As a consequence, any proper convex function is upper semicontinuous along lines on its domain. Furthermore, it is easy to prove that any proper convex function f that is lower semicontinuous on a nonempty convex set $A\subset \operatorname {dom}f$, is also lower semicontinuous along lines on A.

Proposition 4.1 (Necessary Conditions for Even Convexity)

If f is a proper e-convex function, then it is continuous along lines on its domain, and its image set $\operatorname {Im}f:=\left \{ f(x):x\in \operatorname {dom}f\right \}$ is convex.

It is well-known that convexity and lower semicontinuity are preserved by the most important functional operations. The following theorem shows that the same happens with even convexity.

Theorem 4.3 (Operations with e-Convex Functions)

Let $f,g,f_{i}:\mathbb {R}^{n}\rightarrow \overline {\mathbb {R}}$, i ∈ I.

• (i) If f is an e-convex function and α > 0, then αf is e-convex.

• (ii) If {f _i}_{i ∈ I} is a family of e-convex functions, then sup_{i ∈ I}f _i is an e-convex function.

• (iii) If f and g are two proper e-convex functions, then f + g is e-convex.

• (iv) If f and g are two e-convex functions and f is improper, then f + g is e-convex if and only if $\operatorname {dom}(f+g)$ is an e-convex set.

• (v) If f and g are two e-convex functions, where f is improper and g is proper with e-convex domain, then f + g is e-convex.

• (vi) If f and g are two e-convex functions, where f is improper and g is proper and bounded on its domain, then f + g is e-convex.

• (vii) If f and g are two improper e-convex functions, then f + g is e-convex.

In general, (iii) is not true whenever one of the functions is not proper.

Example 4.4

Let $f,g:\mathbb {R}^{2}\rightarrow \overline {\mathbb {R}}$, where f is the proper e-convex function defined in Example 4.3 and g is the improper e-convex function defined by

$$\displaystyle \begin{aligned} g(x)=\left\{ \begin{array}{ll} -\infty , & \text{if }x\in \lbrack 0,1]^{2}, \\ +\infty , & \text{otherwise.} \end{array} \right. \end{aligned}$$

Obviously, $\operatorname {dom}(f+g)=(\operatorname {dom}f)\cap (\operatorname {dom}g)=\operatorname {dom}f$, that is not an e-convex set, and, in particular,

$$\displaystyle \begin{aligned} (f+g)(x)=\left\{ \begin{array}{ll} -\infty , & \text{if }x\in \operatorname{dom}f, \\ +\infty , & \text{otherwise,} \end{array} \right. \end{aligned}$$

so, by Theorem 4.1, f + g is not an e-convex function.

4.2 Evenly Convex Hull

Given a function f, its evenly convex hull, abbreviated as e-convex hull and denoted by $\operatorname {eco}f$, is defined to be the largest e-convex function minorizing f. Obviously, thanks to Theorem 4.3(ii), $\operatorname {eco}f$ coincides with the pointwise supremum of all the e-convex functions minorizing f. Moreover, a function f is said to be evenly convex at a point $\overline {x}$ provided that $f(\overline {x})=(\operatorname {eco}f)(\overline {x})$.

With each subset $A\subset \mathbb {R}^{n+1}$, we associate the so-call lower-bound function $\varphi _{A}:\mathbb {R}^{n}\rightarrow \overline {\mathbb {R}}$ (cf. [90]) defined by

$$\displaystyle \begin{aligned} \varphi _{A}(x):=\inf \{t\in \mathbb{R}:(x,t)\in A\}. \end{aligned}$$

If A = ∅ then φ _A(x) = +∞ for all $x\in \mathbb {R} ^{n}$. A set $A\subset \mathbb {R}^{n+1}$ is said to be ascending if either A = ∅ or there exists $(\overline {x},\overline {t})\in A$ such that $(\overline {x},t)\in A$ for all $t\geq \overline {t}$. Thanks to Proposition 1.1(v), which can be equivalently written as follows: “if there exist $x\in C\subset \mathbb {R}^{n}$ and y ≠ 0_n such that {x + λy : λ ≥ 0}⊂ C, then $d\in 0^{+}(\operatorname {eco}C)$”, one easily gets that for a nonempty e-convex set $A\subset \mathbb {R}^{n+1}$, A is ascending if and only if (0_n, 1) ∈ 0⁺A. This fact allows to get the following results, where the strict epigraph of a function f is denoted by

$$\displaystyle \begin{aligned} \operatorname{epi}_{s}f:=\left\{ (x,\lambda )\in \mathbb{R}^{n+1}:x\in \operatorname{dom} f,\;f(x)<\lambda \right\} . \end{aligned}$$

Theorem 4.4 (Sufficient Conditions for Even Convexity)

Let $A\subset \mathbb {R}^{n+1}$ be an e-convex set and $f:\mathbb {R}^{n}\rightarrow \overline {\mathbb {R}}$ . Then

• (i) If A is ascending, then φ _A is an e-convex function.

• (ii) If A is such that $\operatorname {epi}_{s}f\subset A\subset \operatorname {epi} f$ , then f is an e-convex function. In particular, any function whose strict epigraph is e-convex, is e-convex as well.

Concerning statement $\left ( i\right )$ in the above theorem, it is worth saying that the assumption that A is ascending is not superfluous in order to guarantee the even convexity of φ _A (see the e-convex set in [101, Ex. 3.1]). This makes a difference with a well-known result ensuring that if $A\subset \mathbb {R}^{n}\times \mathbb {R}$ is a closed convex set, then φ _A is a lower semicontinuous convex function (see [148, Th. 5.3]), no matter A is ascending or not.

Regarding statement (ii), whose proof derives from $\left ( i\right ) ,$ not every e-convex function has an e-convex strict epigraph, as we can see in the following example.

Example 4.5

Let $f:\mathbb {R}\rightarrow \overline {\mathbb {R}}$ be the function defined by

$$\displaystyle \begin{aligned} f(x)=\left\{ \begin{array}{ll} -\sqrt{1-x^{2}}, & \text{if}-1\leq x\leq 1, \\ +\infty , & \text{otherwise.} \end{array} \right. \end{aligned}$$

In Fig. 4.5a, we can see that the epigraph of f is e-convex (so f is an e-convex function), whereas Fig. 4.5b shows that its strict epigraph is not.

Fig. 4.5

(a) The epigraph of f; (b) The strict epigraph of f

Theorem 4.5

Let $A\subset \mathbb {R}^{n+1}$ and $f:\mathbb {R}^{n}\rightarrow \overline { \mathbb {R}}$.

• (i) If $\operatorname {eco}A$ is ascending, then

  $$\displaystyle \begin{aligned} \operatorname{eco}\varphi _{A}=\varphi _{\operatorname{eco}A}. \end{aligned}$$

• (ii) If A is such that $\operatorname {epi}_{s}f\subset A\subset \operatorname {epi} f$, then

  $$\displaystyle \begin{aligned} \operatorname{eco}f=\varphi _{\operatorname{eco}A}. \end{aligned}$$

  Consequently,

  $$\displaystyle \begin{aligned} (\operatorname{eco}f)(x)=\operatorname{inf}\left\{ a\in \mathbb{R}:(x,a)\in \operatorname{eco}\operatorname{ epi}f\right\} ,\mathit{}\forall x\in \mathbb{R}^{n}. {} \end{aligned}$$

Next we summarize some basic properties regarding the domain and the epigraph of the e-convex hull.

Theorem 4.6 (Properties of the e-Convex Hull)

Let $f:\mathbb {R}^{n}\rightarrow \overline {\mathbb {R}}$ be a convex function. Then:

• (i) $\operatorname {cl}f\leq \operatorname {eco}f\leq f$.

• (ii) $\operatorname {epi}_{s}(\operatorname {eco}f)\subset \operatorname {eco}\operatorname {epi} f\subset \operatorname {epi}(\operatorname {eco}f)$.

• (iii) $\operatorname {dom}f\subset \operatorname {dom}(\operatorname {eco}f)\subset \operatorname {dom} \left ( \operatorname {cl}f\right ) \subset \operatorname {cl}\operatorname {dom}f$.

• (iv) $\operatorname {dom}(\operatorname {eco}f)\subset \operatorname {eco}\operatorname {dom}f\subset \operatorname {cl}\operatorname {dom}f$.

• (v) $\operatorname {rint}\operatorname {dom}(\operatorname {eco}f)=\operatorname {rint}\operatorname {dom}f$.

The inequalities in statement $\left ( i\right )$ and the inclusions in statements $\left (\textit {ii}\right )$, $\left (\textit {iii}\right )$ and $\left (\textit {iv}\right )$ can be strict, as the following example shows.

Example 4.6 (Example 3.2 Revisited)

Consider the function $f:\mathbb {R}\rightarrow \overline {\mathbb {R}}$ defined in Example 3.2. Taking into account the epigraph of f, represented in Fig. 4.1, it is easy to conclude that

$$\displaystyle \begin{aligned} \left( \operatorname{eco}f\right) \left( x\right) =\left\{ \begin{array}{ll} x^{2}, & \text{if}\ -1<x\leq 1, \\ +\infty , & \text{otherwise,} \end{array} \right. \end{aligned}$$

and

$$\displaystyle \begin{aligned} \left( \operatorname{cl}f\right) \left( x\right) =\left\{ \begin{array}{ll} x^{2}, & \text{if}\ -1\leq x\leq 1, \\ +\infty , & \text{otherwise.} \end{array} \right. \end{aligned}$$

Thus, $\operatorname {cl}f \lneqq \operatorname {eco}f \lneqq f$ and

$$\displaystyle \begin{aligned} \operatorname{dom}f=\operatorname{dom}\left( \operatorname{eco}f\right) =\operatorname{eco}\left( \operatorname{dom} f\right) =\left] -1,1\right] \varsubsetneq \left[ -1,1\right] =\operatorname{dom} \left( \operatorname{cl}f\right) =\operatorname{cl}\operatorname{dom}f. \end{aligned}$$

On the other hand, in Fig. 4.6, we can see that

$$\displaystyle \begin{aligned} \operatorname{epi}_{s}(\operatorname{eco}f)\varsubsetneq \operatorname{eco}\operatorname{epi}f\varsubsetneq \operatorname{epi}(\operatorname{eco}f). \end{aligned}$$

Fig. 4.6

The inclusions in Theorem 4.6(ii) are strict

The following result characterizes the even convexity of a function at a point. Corresponding characterizations have been given in Chap. 3 for even quasiconvexity of a function at a point by using lower level sets instead of epigraphs.

Theorem 4.7 (Characterization of the Even Convexity at a Point)

Let $f:\mathbb {R}^{n}\rightarrow \overline {\mathbb {R}}$ and $\overline {x}\in \mathbb {R}^{n}$ . Then:

• (i) f is e-convex at $\overline {x}$ if and only if $(\overline {x} ,a)\notin \operatorname {eco}\operatorname {epi}f$ for every $a<f(\overline {x})$.

• (ii) f is e-convex at $\overline {x}$ if and only if, for any $a<f( \overline {x})$, there exists $q\in \mathbb {R}^{n+1}$ such that $\left \langle q,(x,\lambda )-(\overline {x},a)\right \rangle >0$, for all $(x,\lambda )\in \operatorname {epi}f$.

• (iii) f is e-convex if and only if it is e-convex at every $\overline {x}\in \mathbb {R}^{n}$.

The even convexity of a function can also be characterized in most cases through the set $\mathscr {E}_{f}$ of all the e-affine minorants of f, that is,

$$\displaystyle \begin{aligned} \mathscr{E}_{f}:=\left\{ a:\mathbb{R}^{n}\rightarrow \overline{\mathbb{R}}:a\text{ is e-affine and }a\leq f\right\} . \end{aligned}$$

Here, a function $a:\mathbb {R}^{n}\rightarrow \overline {\mathbb {R}}$ is said to be e-affine if there exist $c,z\in \mathbb {R} ^{n}$ and $\alpha ,t\in \mathbb {R}$ such that, for all $x\in \mathbb {R}^{n}$ ,

$$\displaystyle \begin{aligned} a(x)=\left\{ \begin{array}{ll} \left\langle x,c\right\rangle -\alpha , & \text{if }\left\langle x,z\right\rangle <t, \\ +\infty , & \text{if }\left\langle x,z\right\rangle \geq t, \end{array} \right. \end{aligned}$$

i.e., a is the restriction of an ordinary affine function to some open half-space, and it is identically + ∞ on its complement. For instance, the function $a:\mathbb {R}\rightarrow \overline {\mathbb {R}}$ defined by

$$\displaystyle \begin{aligned} a(x)=\left\{ \begin{array}{ll} \frac{3x-6}{5}, & \text{if }x>\frac{-6}{5}, \\ +\infty , & \text{if }x\leq \frac{-6}{5}, \end{array} \right. \end{aligned}$$

is an e-affine minorant of the function $f:\mathbb {R}\rightarrow \overline { \mathbb {R}}$ in Example 4.5, that is, $a\in \mathscr {E}_{f}$ (see Fig. 4.7).

Fig. 4.7

An e-affine minorant of f

Theorem 4.8 (Characterization of e-Convex Functions II)

Let f be a proper function. Then, f is e-convex if and only if

$$\displaystyle \begin{aligned} f=\sup \mathscr{E}_{f}. {} \end{aligned} $$

(4.1)

The representation of e-convex functions as suprema of their e-affine minorants in (4.1) also applies to improper e-convex functions identically either −∞ or + ∞, by considering $\mathscr {E}_{f}$ the empty set and the set of all e-affine functions, respectively. However, such a representation does not apply to those improper e-convex functions f such that $f(\overline {x})=-\infty$ for some and $\overline {x}\in \mathbb {R} ^{n}$ and $\operatorname {dom}f\neq \mathbb {R}^{n}$, as in this case $\mathscr E_f = \emptyset$.

Corollary 4.2

Let $f:\mathbb {R}^{n}\rightarrow \overline {\mathbb {R}}$.

• (i) If f has a proper e-convex minorant, then

  $$\displaystyle \begin{aligned} \operatorname{eco}f=\sup \mathscr{E}_{f}. \end{aligned}$$

• (ii) If f is a proper e-convex function, then

  $$\displaystyle \begin{aligned} \operatorname{eco}\operatorname{dom}f=\bigcap_{a\in \mathscr{E}_{f}}\operatorname{dom}a. \end{aligned}$$

4.3 Conjugacy and Subdifferentiability

In this section we shall adopt the generalized conjugation theory of Moreau described in Sect. 3.3 in order to provide up to three different conjugation schemes which are appropriate for e-convex functions, in the sense that a (proper) function is e-convex if and only if it coincides with its biconjugate. For this purpose, we shall recall that every lsc convex function f admitting a continuous affine minorant coincides with its Fenchel biconjugate f ^∗∗ (see, e.g., [41, Prop. 3.1]).

4.3.1 First Conjugacy Scheme

Let us consider the space $W:=\mathbb {R}^{n}\times \mathbb {R}^{n}\times \mathbb {R}$ and the coupling function $c:\mathbb {R}^{n}\times W\rightarrow \mathbb {R}\cup \left \{ +\infty \right \}$ defined by

$$\displaystyle \begin{aligned} c(x,(x^{\ast },u^{\ast },\alpha )):=\left\{ \begin{array}{ll} \left\langle x^{\ast },x\right\rangle , & \text{if }\left\langle u^{\ast },x\right\rangle <\alpha , \\ +\infty , & \text{if }\left\langle u^{\ast },x\right\rangle \geq \alpha . \end{array} \right. {} \end{aligned} $$

(4.2)

Then, the c-conjugate of a function $f: \mathbb {R}^{n}\rightarrow \overline {\mathbb {R}}$ is the function $f^{c}:W\rightarrow \overline {\mathbb {R}}$ given, for every (x ^∗, u ^∗, α) ∈ W, by

$$\displaystyle \begin{aligned} \begin{array}{rcl} f^{c}(x^{\ast },u^{\ast },\alpha ) &\displaystyle =&\displaystyle \sup_{x\in \mathbb{R}^{n}}\left\{ c(x,(x^{\ast },u^{\ast },\alpha ))-f(x)\right\} \\ &\displaystyle =&\displaystyle \left\{ \begin{array}{ll} f^{\ast }(x^{\ast }), &\displaystyle \text{if }\operatorname{dom}f\subset \lbrack u^{\ast }<\alpha ], \\ +\infty , &\displaystyle \text{otherwise}. \end{array} \right. \end{array} \end{aligned} $$

From this expression, one easily gets that

$$\displaystyle \begin{aligned} \operatorname{dom}f^{c}=\operatorname{dom}f^{\ast }\times \left\{ (u^{\ast },\alpha )\in \mathbb{R}^{n}\times \mathbb{R}:\operatorname{dom}f\subset \lbrack u^{\ast }<\alpha ]\right\} . \end{aligned}$$

Similarly, the c ^′-conjugate of a function $g:W\rightarrow \overline {\mathbb {R}}$ is the function $g^{c^{\prime }}:\mathbb {R} ^{n}\rightarrow \overline {\mathbb {R}}$ given, for every $x\in \mathbb {R}^{n}$ , by

$$\displaystyle \begin{aligned} \begin{array}{rcl} g^{c^{\prime }}(x) &\displaystyle =&\displaystyle \sup_{(x^{\ast },u^{\ast },\alpha )\in W}\left\{ c(x,(x^{\ast },u^{\ast },\alpha ))-g(x^{\ast },u^{\ast },\alpha )\right\} \\ &\displaystyle =&\displaystyle \left\{ \begin{array}{ll} g^{\ast }(x,0_{n},0), &\displaystyle \text{if }\operatorname{dom}g\subset \lbrack (0_{n},x,-1)<0], \\ +\infty , &\displaystyle \text{otherwise.} \end{array} \right. \end{array} \end{aligned} $$

For this particular coupling function in (4.2), that is, for this particular conjugation scheme, we have that the class of c-elementary functions is precisely the family of e-affine functions, and then, by Theorem 4.8, the class of Γ _c-convex functions coincides with the class of e-convex functions from $\mathbb {R}^{n}$ to $\mathbb {R} \cup \left \{ +\infty \right \}$ along with the function identically −∞. We will say that a function $g:W\rightarrow \overline {\mathbb {R}}$ is e ^′-convex if it is $\varGamma _{c^{\prime }}$-convex, and the e^′-convex hull of $g:W\rightarrow \overline {\mathbb {R}}$ will be denoted by $\operatorname {e}^{\prime }\operatorname {co}g$.

The most remarkable properties of this c-conjugation scheme are summarized in the following theorem.

Theorem 4.9 (Properties of c-Conjugation)

Let $f:\mathbb {R}^{n}\rightarrow {\overline {\mathbb {R}}}$ , $g:W\rightarrow {\overline {\mathbb {R}}}$ and $c:\mathbb {R}^{n}\times W\rightarrow \mathbb {R}\cup \left \{ +\infty \right \}$ be as in (4.2). Then,

• (i) f ^c is e ^′-convex, and $g^{c^{\prime }}$ is e-convex.

• (ii) $f^{cc^{\prime }}=\left \{ \begin {array}{ll} f^{\ast \ast }+\delta _{\operatorname {eco}\operatorname {dom}f}, & \mathit{\text{if }}\operatorname {dom} f^{\ast }\neq \emptyset , \\ -\infty , & \mathit{\text{otherwise.}} \end {array} \right .$

• (iii) If f is minorized by a proper e-convex function, then $\operatorname {eco}f =f^{cc^{\prime }}$.

• (iv) If f does not take the value −∞, then f is e-convex if and only if $f=f^{cc^{\prime }}$.

• (v) $\operatorname {e}^{\prime }\operatorname {co}g=g^{c^{\prime }c}$.

• (vi) g is e ^′-convex if and only if $g=g^{c^{\prime }c}$ .

Consequently, $f:\mathbb {R}^{n}\rightarrow \mathbb {R}\cup \left \{ +\infty \right \}$ is e-convex at $x\in \mathbb {R}^{n}$ if and only if $f(x)=f^{cc^{\prime }}(x)$, and $g:W\rightarrow \overline {\mathbb {R}}$ is e^′-convex at (x ^∗, u ^∗, α) ∈ W if and only if $g(x^{\ast },u^{\ast },\alpha )=g^{c^{\prime }c}(x^{\ast },u^{\ast },\alpha )$ .

Statement (iv) also holds whenever f is the function identically −∞, but it fails if f is an arbitrary function such that $\emptyset \neq \operatorname {dom}f\neq \mathbb {R}^{n}$ and $f(\overline {x})=-\infty$ for some $\overline {x}\in \mathbb {R}^{n}$, as in that case $f^{cc'}$ is identically −∞. Furthermore, if $f:\mathbb {R}^{n}\rightarrow \mathbb {R}\cup \left \{ +\infty \right \}$ does not admit any proper e-convex minorant, then the relation $\operatorname {eco}f = f^{cc^{\prime }}$ may be false, as it is shown by the following example, which involves the so-called valley function υ _C of a set $C\subset \mathbb {R}^{n},$ defined as $\upsilon _{C}\left ( x\right ) :=-\infty$ if x ∈ C and $\upsilon _{C}\left ( x\right ) :=+\infty$ if x∉C.

Example 4.7

Consider the function f defined on the real line given by

$$\displaystyle \begin{aligned}f(x) = \left\{ \begin{array}{ll} 0, & \text{ if }x=0, \\ -\frac{1}{\left\vert x\right\vert }, & \text{ if }0<\left\vert x\right\vert <1, \\ +\infty, & \text{ if }\left\vert x\right\vert \geq 1. \end{array} \right.\end{aligned}$$

Its effective domain is $\left ] -1,1\right [$, which is an e-convex set. We have f ^∗≡ +∞ and, by Theorem 4.9(ii), $f^{cc^{\prime }}\equiv -\infty$. However, it is easy to see that $\operatorname {eco}f=v_{\left ] -1,1\right [ }$. Hence, in this case the identity $\operatorname {eco}f = f^{cc'}$ fails because of the fact that f does not have a proper e-convex minorant.

Next example illustrates how this conjugation scheme works with a well-known function.

Example 4.8

By applying the conjugation scheme developed in this subsection to the indicator function δ _C of $C\subset \mathbb {R}^{n}$, for every (x ^∗, u ^∗, α) ∈ W one has

$$\displaystyle \begin{aligned} \delta _{C}^{c}(x^{\ast },u^{\ast },\alpha )=\left\{ \begin{array}{ll} \sigma _{C}(x^{\ast }), & \text{if }C\subset \lbrack u^{\ast }<\alpha ], \\ +\infty , & \text{otherwise}. \end{array} \right. \end{aligned}$$

The function $\delta _{C}^{c}:W\rightarrow \overline {\mathbb {R}}$ can be regarded as a kind of support function of C. The second conjugate is

$$\displaystyle \begin{aligned} \delta _{C}^{cc^{\prime }}(x)=\left\{ \begin{array}{ll} \delta _{\operatorname{cl}\operatorname{co}C}(x), & \text{if }x\in \operatorname{eco}C, \\ +\infty , & \text{if }x\notin \operatorname{eco}C. \end{array} \right. \end{aligned}$$

Consequently, $\operatorname {eco}\delta _{C}=\delta _{C}^{cc^{\prime }}=\delta _{ \operatorname {eco}C}$.

4.3.2 Second Conjugacy Scheme

Next we apply the e-quasiconvex conjugation scheme developed in Sect. 3.3 in order to get another conjugation scheme for e-convex functions. More precisely, we will consider a slightly modification of the coupling function in (3.7), in order to get a conjugation scheme for e-convex functions in $\mathbb {R}^{n}$ by means of the conjugation scheme for e-quasiconvex functions in $\mathbb {R}^{n+1}$. Thus, consider the coupling function $c:\mathbb {R} ^{n+1}\times ( \mathbb {R}^{n+1}\times \mathbb {R}) \rightarrow \overline {\mathbb {R}}$ defined by

$$\displaystyle \begin{aligned} c\left( \left( x,t\right) ,\left( x^{\ast },t^{\ast },\alpha \right) \right) :=\left\{ \begin{array}{ll} 0, & \text{if }\left\langle x^{\ast },x\right\rangle +tt^{\ast }\geq \alpha , \\ -\infty , & \text{if }\left\langle x^{\ast },x\right\rangle +tt^{\ast }<\alpha . \end{array} \right. {} \end{aligned} $$

(4.3)

With each function $f:\mathbb {R}^{n}\rightarrow \overline {\mathbb {R}}$, we associate the function $\widetilde {f}:\mathbb {R}^{n+1}\rightarrow \overline { \mathbb {R}}$ defined, for every $(x,t)\in \mathbb {R}^{n}\times \mathbb {R}$, by

$$\displaystyle \begin{aligned} \widetilde{f}\left( x,t\right) :=f\left( x\right) +t. \end{aligned}$$

Observe that $\operatorname {dom}\widetilde {f}=\operatorname {dom}f\times \mathbb {R}$. If we assume that $\operatorname {dom}f\neq \emptyset$ and consider the coupling function c in (4.3), then the c-conjugate of $\widetilde {f}$ is

$$\displaystyle \begin{aligned} \widetilde{f}^{c}\left( x^{\ast },t^{\ast },r\right) =\left\{ \begin{array}{ll} f^{\ast }\left( \frac{x^{\ast }}{t^{\ast }}\right) -\frac{r}{t^{\ast }}, & \text{if }t^{\ast }>0, \\ +\infty , & \text{if }t^{\ast }<0, \\ +\infty , & \text{if }t^{\ast }=0\text{ and }\operatorname{dom}f\not\subset \left[ x^{\ast }<r\right] , \\ -\infty , & \text{if }t^{\ast }=0\text{ and }\operatorname{dom}f\subset \left[ x^{\ast }<r\right] , \end{array} \right. \end{aligned}$$

for every $\left ( x^{\ast },t^{\ast },r\right ) \in \mathbb {R}^{n}\times \mathbb {R}\times \mathbb {R}$. From Sect. 3.3, $\widetilde {f} ^{cc^{\prime }}$, the biconjugate of $\widetilde {f}$, coincides with the e-quasiconvex hull of $\widetilde {f}$. This fact, together with the following equivalences,

$$\displaystyle \begin{aligned} f\text{ is e-convex }\Longleftrightarrow \widetilde{f}\text{ is e-convex } \Longleftrightarrow \widetilde{f}\text{ is e-quasiconvex }, {} \end{aligned} $$

(4.4)

allow to obtain expressions for the e-convex hulls of $\widetilde {f}$ and f .

Theorem 4.10 (Properties of c-Conjugation)

Let $c:\mathbb {R}^{n+1}\times ( \mathbb {R}^{n+1}\times \mathbb {R} ) \rightarrow \overline {\mathbb {R}}$ be as in (4.3). For any $f:\mathbb {R}^{n}\rightarrow \overline {\mathbb {R}}$ and any $\left ( x,t\right ) \in \mathbb {R}^{n}\times \mathbb {R}$, the following statements hold:

• (i) $(\operatorname {eco}\widetilde {f})\left ( x,t\right ) =\left ( \operatorname {eco} f\right ) \left ( x\right ) +t.$

• (ii) $\widetilde {f}^{cc^{\prime }}\left ( x,t\right ) =f^{\ast \ast }\left ( x\right ) +\delta _{\operatorname {eco}\operatorname {dom}f}\left ( x\right ) +t.$

• (iii) $(\operatorname {eco}\widetilde {f})\left ( x,t\right ) =f^{\ast \ast }\left ( x\right ) +\delta _{\operatorname {eco}\operatorname {dom}f}\left ( x\right ) +t.$

• (iv) $\operatorname {eco}f=f^{\ast \ast }+\delta _{\operatorname {eco}\operatorname {dom}f}$.

The conjugation method described in this subsection does not apply directly on a given function f on $\mathbb {R}^{n}$, but on a certain extension $\widetilde {f}$ defined on $\mathbb {R}^{n+1}$. The results obtained in Theorem 4.10 follow from the relationship between f and $\widetilde {f}$ in (4.4), and the conjugation method for e-quasiconvex functions. Among the given results, we observe that the identity $\operatorname {eco}f=f^{\ast \ast }+\delta _{\operatorname {eco}\operatorname {dom}f}$ is guaranteed for any extended real-valued function f. However, with the method described in Sect. 4.3.1, such equality can be just asserted for functions having an e-convex minorant (besides the function identically −∞).

4.3.3 Third Conjugacy Scheme

Now, consider the coupling function $c:\mathbb {R}^{n}\times \left ( \mathbb {R}^{n}\times \mathbb {R}\times \left \{ 0,1\right \} \right ) \rightarrow \overline {\mathbb {R}}$, defined by

$$\displaystyle \begin{aligned} c\left( x,\left( x^{\ast },r,i\right) \right) :=\left\{ \begin{array}{ll} \left\langle x,x^{\ast }\right\rangle , & \text{if }i=0, \\ \upsilon _{\lbrack x^{\ast }<r]}\left( x\right) , & \text{if }i=1. \end{array} \right. {} \end{aligned} $$

(4.5)

In this case, the c-conjugate of $f:\mathbb {R}^{n}\rightarrow \overline { \mathbb {R}}$ is the function $f^{c}:\mathbb {R}^{n}\times \mathbb {R}\times \left \{ 0,1\right \} \rightarrow \overline {\mathbb {R}}$ given, for every $(x^{\ast },r)\in \mathbb {R}^{n}\times \mathbb {R}$ by

$$\displaystyle \begin{aligned} f^{c}\left( x^{\ast },r,i\right) =\left\{ \begin{array}{ll} f^{\ast }\left( x^{\ast }\right) , & \text{ if }i=0, \\ \upsilon _{\{\left( x^{\ast },r\right) \in \mathbb{R}^{n}\times \mathbb{R} \,:\,\operatorname{dom}f\subset \lbrack x^{\ast }<r]\}}, & \text{ if }i=1. \end{array} \right. \end{aligned}$$

Observe that the c-elementary functions are, on the one hand, the continuous affine functions on $\mathbb {R}^{n}$, and, on the other hand, the valley functions of the open halfspaces of $\mathbb {R}^{n}$, plus the constant functions + ∞ and −∞.

The main properties of this conjugation scheme are as follows.

Theorem 4.11 (Properties of c-Conjugation)

Let $c:\mathbb {R}^{n}\times \left ( \mathbb {R}^{n}\times \mathbb {R}\times \left \{ 0,1\right \} \right ) \rightarrow \overline {\mathbb {R} }$ be as in (4.5). For any function $f:\mathbb {R}^{n}\rightarrow \overline {\mathbb {R}}$, the following statements hold:

• (i) $f^{cc^{\prime }} = \operatorname {eco}f$.

• (ii) f is e-convex if and only if $f^{cc^{\prime }}=f$.

• (iii) $f^{cc^{\prime }} = \max \{ f^{\ast \ast },\upsilon _{\operatorname {eco} \operatorname {dom}f} \} = f^{\ast \ast }+\delta _{\operatorname {eco}\operatorname {dom}f}$.

• (iv) $\operatorname {eco}f$ coincides with the supremum of all the continuous affine functions and all the open halfspaces valley functions that are minorants of f.

From the above theorem we get that $\operatorname {eco}f=f^{\ast \ast } + \delta _{\operatorname {eco}\operatorname {dom}f}$ for any extended real-valued function f. This identity was also obtained in Sect. 4.3.2 by using a different approach. It required a transformation of the function f, which is not needed here. Furthermore, we observe that the identity $\operatorname {eco}f = f^{cc^{\prime }}$ holds for any function f, while in Sect. 4.3.1 such equality was just asserted for functions having an e-convex minorant (besides the function identically −∞). Finally, Theorem 4.11 points out that $\operatorname {eco}f = \max \{ f^{\ast \ast },\upsilon _{\operatorname {eco}\operatorname {dom}f} \}$, which is another representation of the e-convex hull of f (and of its biconjugate $f^{cc^{\prime }}$) that was not obtained with the two approaches in Sects. 4.3.1 and 4.3.2. Such representation is related with the following geometric interpretation: the e-convex hull of a function f is the supremum of all the continuous affine minorants and all the open halfspaces valley functions that are minorants of f.

4.3.4 Subdifferentials

As pointed out in Sect. 3.3, each coupling functional c defining a conjugacy has an associated c-subdifferential ∂ _c. Thus, if we consider the first coupling function c in this section, the one in (4.2), the following result provides the link between the c-subdifferential ∂ _c and the Moreau–Rockafellar subdifferential ∂. We would like to clarify that this subsection is not related to Clark subdifferentials at all.

Proposition 4.2

Let $f:\mathbb {R}^{n}\rightarrow \overline {\mathbb {R}}$ and $\overline {x} \in f^{-1}(\mathbb {R})$ . Then,

$$\displaystyle \begin{aligned} \partial_{c}f(\overline{x}) = \partial f(\overline{x}) \times \{(u^*,\alpha)\in\mathbb{R}^{n} \times \mathbb{R} : \operatorname{dom}f \subset [u^* < \alpha] \}. \end{aligned}$$

Example 4.9

Consider the function f in Example 4.5 and $\overline {x}=0$. Then,

$$\displaystyle \begin{aligned} \partial _{c}f(0)=\{0\}\times \{(a,b)\in \mathbb{R}^{2}:ax<b\ \text{is a consequence of }\{-x\leq 1,x\leq 1\}\}. \end{aligned}$$

More precisely, the latter set is characterized in Theorem 2.3 as

$$\displaystyle \begin{aligned} \begin{array}{rcl} &\displaystyle &\displaystyle \{0\}\times \operatorname{proj}\nolimits_{3}^{\left\{ 1,2\right\} }\left( \operatorname{ cone}\left\{ \begin{pmatrix} -1 \\ 1 \\ 0 \end{pmatrix} , \begin{pmatrix} 1 \\ 1 \\ 0 \end{pmatrix} , \begin{pmatrix} 0 \\ 1 \\ -1 \end{pmatrix} , \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix} \right\} \cap \left( \mathbb{R}^{2}\times \left( -\mathbb{R}_{++}\right) \right) \right) \\ &\displaystyle =&\displaystyle \{0\}\times \operatorname{int}\operatorname{epi}\left\vert \cdot \right\vert , \end{array} \end{aligned} $$

where $\left \vert \cdot \right \vert :\mathbb {R}\rightarrow \mathbb {R}$ is the absolute value function (see Fig. 4.8).

Fig. 4.8

The c-subdifferential of f at 0

As a consequence of Proposition 4.2, f is c-subdifferentiable at $\overline {x}$ if and only if it is subdifferentiable at this point. This motivates our focus on the (Moreau-Rockafellar) subdifferential in the next results. Firstly, we provide a characterization of the ε -subdifferentiability of a function at a given point in terms of the even convexity of its strict epigraph.

Proposition 4.3 (Non-emptiness of the ε-Subdifferential)

Let ε ≥ 0, $f:\mathbb {R}^{n}\rightarrow \overline {\mathbb {R}}$ and $\overline {x}\in f^{-1}(\mathbb {R})$. Then, the following statements are equivalent:

• (i) $\partial _{\varepsilon }f(\overline {x}) \neq \emptyset$.

• (ii) $(\{\overline {x}\}\times \mathbb {R}) \cap \operatorname {eco}(\operatorname {epi} _{s} f) \subset (\{\overline {x}\}\times \mathbb {R}) \cap \operatorname {epi} _{s}(f-\varepsilon )$.

• (iii) $(\overline {x},f(\overline {x})-\varepsilon ) \notin \operatorname {eco}( \operatorname {epi}_{s} f)$.

The following notion is inspired by the concept of closedness regarding to a set (see [20, p. 56]): given two sets A and B, one says that A is e-convex regarding to B provided that $B\cap \operatorname {eco}A=B\cap A$.

Corollary 4.3

Let $f:\mathbb {R}^{n}\rightarrow \overline {\mathbb {R}}$ and $\overline {x}\in f^{-1}(\mathbb {R})$ . Then, the following statements are equivalent:

• (i) $\partial f(\overline {x}) \neq \emptyset$.

• (ii) $\operatorname {epi}_{s} f$ is e-convex regarding to $\{\overline {x} \}\times \mathbb {R}$.

• (iii) $\left ( \overline {x},f(\overline {x})\right ) \notin \operatorname {eco} \left ( \operatorname {epi}_{s}f\right )$.

Regarding the function in Example 4.5 and $\overline {x}=-1,$ we have

$$\displaystyle \begin{aligned} \left( \left\{ -1\right\} \times \mathbb{R}\right) \cap \operatorname{epi }_{s}f=\left\{ -1\right\} \times \mathbb{R}_{++},\end{aligned}$$

while $\left ( \left \{ -1\right \} \times \mathbb {R}\right ) \cap \operatorname {eco}\operatorname {epi} _{s}f=\left \{ -1\right \} \times \mathbb {R}_{+}$ (see, Fig. 4.9). Since (ii) fails, (i) and (iii) also fail. In the case $\overline {x}=0$, (i), (ii) and (iii) hold.

Fig. 4.9

(a) $\left ( \left \{ -1 \right \} \times \mathbb {R} \right ) \cap \operatorname {epi}_{s}f= \left \{ -1 \right \} \times \mathbb {R}_{++}$; (b) $\left ( \left \{ -1 \right \} \times \mathbb {R} \right ) \cap \operatorname {eco} \left ( \operatorname {epi}_{s}f \right ) = \left \{ -1 \right \} \times \mathbb {R}_{+}$

In particular, if the strict epigraph of a function f is e-convex, then f is subdifferentiable on $f^{-1}(\mathbb {R})$.

Proposition 4.4 (Necessary Condition for Subdifferentiability)

Assume that $f:\mathbb {R}^{n}\rightarrow \overline {\mathbb {R}}$ is subdifferentiable on $f^{-1}(\mathbb {R})$ and either f is e-convex or $\operatorname {dom}f$ is e-convex. Then, $\operatorname {epi}_{s}f$ is e-convex.

We conclude this section by providing two additional characterizations of the even convexity at a given point (cf. Ths. 4.5 and 4.7).

Theorem 4.12 (Characterization of the Even Convexity at a Point)

Consider $f:\mathbb {R}^{n}\rightarrow \overline {\mathbb {R}}$, $\overline {x}\in f^{-1}(\mathbb {R})$ and $A\subset \mathbb {R}^{n}\times \mathbb {R}$ such that $\operatorname {epi}_{s}f\subset A\subset \operatorname {epi}f$. Then, the following statements are equivalent:

• (i) $f(\overline {x}) = (\operatorname {eco} f)(\overline {x})$.

• (ii) For all ε > 0, $\partial _{\varepsilon } f(\overline {x} ) \neq \emptyset$.

• (iii) For all ε > 0, $(\overline {x},f(\overline {x} )-\varepsilon ) \notin \operatorname {eco} A$.

There exits also an ε-subdifferentiability notion associated with the c-conjugation pattern described in Sect. 4.3.1. For $f:\mathbb {R}^{n}\rightarrow \overline {\mathbb {R}}$ and ε ≥ 0, it is said that $\left ( x^{\ast },u^{\ast },\alpha \right ) \in W$ is an ε − c-subgradient of f at $x_{0}\in f^{-1}(\mathbb {R})$, if $\left \langle u^{\ast },x_{0}\right \rangle <\alpha$ and

$$\displaystyle \begin{aligned} f( x) -f( x_{0}) \geq c\left( x,\left( x^{\ast },u^{\ast },\alpha \right) \right) -c\left( x_{0},\left( x^{\ast },u^{\ast },\alpha \right) \right) -\varepsilon , \end{aligned}$$

for all $x\in \mathbb {R}^{n}$. The set of all the ε − c-subgradients of f at x ₀ is denoted by ∂ _c,εf(x ₀), and it is called the ε − c-subdifferential of f at x ₀. Clearly, for ε = 0 we obtain the c-subdifferential of f at x ₀.

The most important properties of ε − c-subdifferentiability, whose counterparts for ε-subdifferentiability and Fenchel conjugation are very well known, are summarized in the following theorem. Previously, we introduce a set of e-affine functions associated to a pair of functions $f,g:\mathbb {R}^{n}\rightarrow \overline {\mathbb {R}}$, due to the lack of additivity property in the set of e-affine functions. This new set, denoted by $\widetilde {\mathscr E}_{f+g}$ is defined in the following way: a ∈ $\widetilde {\mathscr E}_{f+g}$ if and only if there exist $a_{1}\in \mathscr E_{f}$, $a_{2}\in \mathscr E_{g}$ such that, if

$$\displaystyle \begin{aligned} a_{1}\left( x\right) =\left\{ \begin{array}{ll} \left\langle x,y_{1}\right\rangle -\beta _{1}, & \text{if }\left\langle x,z_{1}\right\rangle <\alpha _{1}, \\ +\infty, & \text{otherwise,} \end{array} \right. \text{ and }\ a_{2}\left( x\right) =\left\{ \begin{array}{ll} \left\langle x,y_{2}\right\rangle -\beta _{2}, & \text{if }\left\langle x,z_{2}\right\rangle <\alpha _{2}, \\ +\infty, & \text{otherwise,} \end{array} \right. \end{aligned}$$

then

$$\displaystyle \begin{aligned} a\left( x\right) =\left\{ \begin{array}{l} \left\langle x,y_{1}+y_{2}\right\rangle -\left( \beta _{1}+\beta _{2}\right), \\ +\infty , \end{array} \begin{array}{l} \text{if }\left\langle x,z_{1}+z_{2}\right\rangle <\alpha _{1}+\alpha _{2}, \\ \text{otherwise.} \end{array} \right. \end{aligned} $$

(4.6)

Clearly $\widetilde {\mathscr E}_{f+g}\subset \mathscr E_{f+g}$.

Theorem 4.13 (Properties of c-Subdifferentiability)

Let $f,g:\mathbb {R}^{n}\rightarrow \overline {\mathbb {R}}$ be proper functions, such that $\operatorname {dom}f \cap \operatorname {dom}g \neq \emptyset$ . Then,

• (i) For $x_{0}\in \operatorname {dom}f$,

  $$\displaystyle \begin{aligned} \operatorname{epi}f^{c} = \bigcup\limits_{\varepsilon \geq 0}\left\{ \left( x^{\ast },u^{\ast },\alpha ,\left\langle x^{\ast },x_{0}\right\rangle +\varepsilon -f\left( x_{0}\right) \right) : \left( x^{\ast },u^{\ast },\alpha \right) \in \partial_{c,\varepsilon }f\left( x_{0}\right) \right\} . \end{aligned}$$

• (ii) If $f+g = \sup \{ a : a\in \widetilde {\mathscr E}_{f+g}\}$, $\operatorname {epi}f^{c}+\operatorname {epi}g^{c}$ is e ^′-convex if and only if

  $$\displaystyle \begin{aligned} \partial _{c,\varepsilon }\left( f+g\right) \left( x\right) =\bigcup\limits_{\varepsilon _{1}+\varepsilon _{2}=\varepsilon }\partial _{c,\varepsilon _{1}}f\left( x\right) +\partial _{c,\varepsilon _{2}}g\left( x\right) . \end{aligned}$$

  for all ε ≥ 0 and $x\in \operatorname {dom}f\cap \operatorname {dom}g.$

• (iii) If $f+g = \sup \{ a : a\in \widetilde {\mathscr E}_{f+g}\}$ and $\operatorname {epi}f^{c}+\operatorname {epi}g^{c}$ is e ^′ -convex, then

  $$\displaystyle \begin{aligned} \partial _{c}\left( f+g\right) \left( x\right) =\partial _{c}f\left( x\right) +\partial _{c}g\left( x\right) . \end{aligned}$$

  for all $x\in \operatorname {dom}f\cap \operatorname {dom}g.$

4.4 Duality in Evenly Convex Optimization

4.4.1 General Regularity Conditions

An important part of mathematical programming from both theoretical and computational points of view is duality theory. We consider an arbitrary unconstrained optimization problem

$$\displaystyle \begin{aligned} (GP) \quad \operatorname*{\mathrm{Min}}\limits_{x\in \mathbb{R}^{n}} \,F(x), {} \end{aligned} $$

(4.7)

where $F:\mathbb {R}^{n}\rightarrow \overline {\mathbb {R}}$ is a proper function, and we apply the perturbational approach to duality as in Sect. 3.4. By taking a perturbation function $\varPhi :\mathbb {R} ^{n}\times \mathbb {R}^{m}\rightarrow \overline {\mathbb {R}}$ such that Φ(x, 0_m) = F(x) for all $x\in \mathbb {R}^{n}$, $\mathbb {R}^{m}$ being the space of perturbation variables, the so-called conjugate dual problem of (GP) can be formulated as follows:

$$\displaystyle \begin{aligned} (GD) \quad \operatorname*{\mathrm{Max}}\limits_{y^{\ast}\in \mathbb{R}^{m}} \, -\varPhi^{\ast}(0_{n},y^{\ast}), \end{aligned}$$

where $\varPhi ^{\ast }:\mathbb {R}^{n}\times \mathbb {R}^{m}\rightarrow \overline {\mathbb {R}}$ is the Fenchel conjugate of Φ, that is,

$$\displaystyle \begin{aligned} \varPhi ^{\ast }\left( x^{\ast },y^{\ast }\right) =\sup_{\left( x,y\right) \in \mathbb{R}^{n}\times \mathbb{R}^{m}}\left\{ \left\langle x,x^{\ast }\right\rangle +\left\langle y,y^{\ast }\right\rangle -\varPhi \left( x,y\right) \right\} . \end{aligned}$$

Problem (GD) can also be expressed by means of the infimum value function $p:\mathbb {R}^{m}\rightarrow \overline {\mathbb {R}},$

$$\displaystyle \begin{aligned} p\left( y\right) :=\inf_{x\in \mathbb{R}^{n}}\varPhi \left( x,y\right) . {} \end{aligned} $$

(4.8)

In fact, since $p\left ( 0_{m}\right ) =\inf _{x\in \mathbb {R}^{n}}F\left ( x\right )$, and $p^{\ast }\left ( y^{\ast }\right ) =\varPhi ^{\ast }(0_{n},y^{\ast }),$ one has

$$\displaystyle \begin{aligned} (GD) \quad \operatorname*{\mathrm{Max}}\limits_{y^{\ast}\in \mathbb{R}^{m}} \, p^{\ast }\left(y^{\ast }\right) . \end{aligned}$$

From the so-called Fenchel–Young inequality

$$\displaystyle \begin{aligned} p^{\ast }\left( y^{\ast }\right) +p\left( y\right) \geq \left\langle y,y^{\ast }\right\rangle ,\forall y,y^{\ast }\in \mathbb{R}^{m}, \end{aligned}$$

it follows that $-p^{\ast }\left ( y^{\ast }\right ) \leq p\left ( 0_{m}\right )$ and, denoting by v(GP) and v(GD) the optimal values of the primal and the dual problems, respectively, we have v(GD) ≤ v(GP), situation known as weak duality. The difference between the optimal values of the primal and the dual problems is called duality gap, and it is said that there exists strong duality when there is no duality gap and the dual problem is solvable. Sufficient conditions for strong duality are called regularity conditions, and they are classified, mainly, in two different groups: interiority-type and closedness-type conditions, being the last ones used recently as a viable alternative to their interiority-type counterparts. This well-known framework will be named the classical setting throughout this section. In this classical framework, strong duality is characterized through the subdifferential of the infimum value function at 0_m; [191, Th. 2.6.1] states that, if the perturbation function is convex, $\partial p\left ( 0_{m}\right ) \neq \emptyset$ if and only if strong duality holds.

However, from the point of view of applicability, it is also necessary to find out conditions guaranteeing strong duality even when F is perturbed with linear functions, situation called stable strong duality.

Since e-convex functions can be viewed as a generalization of convex lower semicontinuous functions and, moreover, c-conjugation (with c the coupling function in (4.2)) is suitable for this kind of functions, it is natural trying the extension of well-known results for convex duality in the classical setting to that more general framework. In this moment we introduce the notion of e^′-convexity, which appeared firstly in [46], for the calculus of the counterpart of the classical Moreau–Rockafellar formula (see, e.g., [24]). The idea consisted in creating a kind of hull for the convex set $\operatorname {epi}f^{c}+\operatorname {epi}g^{c},$ for $f,g:\mathbb {R}^{n}\rightarrow \overline {\mathbb {R}},$ trying to link it with $\operatorname {epi}\left ( f+g\right ) ^{c}$. For this problem, lower semicontinuous and evenly convex hulls do not properly work. Recall that $\operatorname {epi}f^{c}+\operatorname {epi} g^{c}$ and $\operatorname {epi}\left ( f+g\right ) ^{c}$ are both contained in $W\times \mathbb {R}$, where $W=\mathbb {R}^{n}\times \mathbb {R}^{n}\times \mathbb {R}$.

A subset $D\subset W\times \mathbb {R}$ is said to be e ^′-convex if there exists an e^′-convex function $h:W\rightarrow \overline {\mathbb {R}}$ such that $D=\operatorname {epi}h$. Clearly, the intersection of an arbitrary family of e^′-convex sets is an e^′-convex set, and the e ^′-convex hull of a set $D\subset W\times \mathbb {R}$ is defined as the smallest e^′-convex set containing D, which will be denoted by $\operatorname {e}^{\prime }\operatorname {co}D$. Actually, it is the epigraph of the e^′-convex hull of the function $f_{D}:\mathbb {R}^{n}\rightarrow \overline {\mathbb {R}}$ defined by $f_{D}(x^{\ast },u^{\ast },\alpha ):=\inf \left \{ a\in \mathbb {R}:(x^{\ast },u^{\ast },\alpha ,a)\in D\right \} .$

Considering now the general dual problem (4.7) with $F: \mathbb {R}^{n}\rightarrow \overline {\mathbb {R}}$ a proper function, let us take a perturbation function $\varPhi :\mathbb {R}^{n}\times \mathbb {R} ^{m}\rightarrow \overline {\mathbb {R}}$. Denoting by $Z=\mathbb {R}^{n}\times \mathbb {R}^{m}$, the c-conjugate of the perturbation function Φ, $\varPhi ^{c}:Z\times Z\times \mathbb {R}\rightarrow \overline {\mathbb {R}}$, is

$$\displaystyle \begin{aligned} \varPhi ^{c}\left( \left( x^{\ast },y^{\ast }\right) ,\left( u^{\ast },v^{\ast }\right) ,\alpha \right) =\sup_{\left( x,y\right) \in Z}\left\{ \overline{c} \left( \left( x,y\right) ,\left( \left( x^{\ast },y^{\ast }\right) ,\left( u^{\ast },v^{\ast }\right) ,\alpha \right) \right) -\varPhi \left( x,y\right) \right\} , \end{aligned}$$

where $\overline {c}:Z\times Z\times Z\times \mathbb {R}\rightarrow \overline { \mathbb {R}}$ is the coupling function

$$\displaystyle \begin{aligned} \overline{c}\left( \left( x,y\right) ,\left( \left( x^{\ast },y^{\ast }\right) ,\left( u^{\ast },v^{\ast }\right) ,\alpha \right) \right) =\left\{ \begin{array}{ll} \left\langle x,x^{\ast }\right\rangle +\left\langle y,y^{\ast }\right\rangle , & \text{if }\left\langle x,u^{\ast }\right\rangle +\left\langle y,v^{\ast }\right\rangle <\alpha , \\ +\infty , & \text{otherwise.} \end{array} \right. \end{aligned}$$

In [46], the general problem (GP) is associated with the dual problem

$$\displaystyle \begin{aligned} \begin{array}{lcl} (GD_{c}) \quad & \operatorname*{\mathrm{Max}}\limits_{y^{\ast },v^{\ast }\in \mathbb{R}^{m},\alpha \in \mathbb{R}} & -\varPhi ^{c}\left( \left( 0_{n},y^{\ast }\right) ,\left( 0_{n},v^{\ast }\right) ,\alpha \right) \\ & \text{s.t.} & \alpha >0, \end{array} {} \end{aligned} $$

(4.9)

verifying weak duality, v(GD _c) ≤ v(GP). Since

$$\displaystyle \begin{aligned} \varPhi ^{c}\left( \left( 0_{n},y^{\ast }\right) ,\left( 0_{n},v^{\ast }\right) ,\alpha \right) =p^{c}\left( y^{\ast },v^{\ast },\alpha \right) ,\forall y^{\ast },v^{\ast }\in \mathbb{R}^{m},\forall \alpha >0, \end{aligned}$$

(GD _c) can also be expressed by means of the infimum value function p in (4.8), as follows:

$$\displaystyle \begin{aligned} \begin{array}{lcl} (GD_{c}) \quad & \operatorname*{\mathrm{Max}}\limits_{y^{\ast },v^{\ast }\in \mathbb{R}^{m},\alpha\in\mathbb{R}} & -p^{c}\left( y^{\ast },v^{\ast },\alpha \right) \\ & \text{s.t.} & \alpha >0. \end{array} \end{aligned}$$

We focus firstly in obtaining interior point regularity conditions for strong duality between (GP) and (GD _c). It is evident that strong duality holds if v(GP) = −∞, hence we deal with the case $v(GP)\in \mathbb {R}$. In first place, we will characterize strong duality in terms of the c-subdifferential associated to the coupling c in (4.2) as considered in Sect. 4.3.

Proposition 4.5 (General Characterization of Strong Duality)

Let us assume that $v(GP)\in \mathbb {R}$. Then the duality pair (GP) − (GD _c) verifies strong duality if and only if $\partial _{c}p\left ( 0_{m}\right ) \neq \emptyset$. In this case, $\partial _{c}p\left ( 0_{m}\right )$ is the solution set of (GD _c).

We introduce an interior point condition expressed in terms of the relative interior of a set, and a closedness-type one, expressed in terms of closures of epigraphs, as usual in this kind of conditions.

Denoting by $\operatorname {proj}\left ( \operatorname {dom}\varPhi \right )$ the projection of $\operatorname {dom}\varPhi$ onto $\mathbb {R}^{m}$, let us also observe that $\operatorname {epi}\varPhi ^{c}\subset Z\times Z\times \mathbb {R\times R}$, $Z= \mathbb {R}^{n}\times \mathbb {R}^{m}$, so denoting by $W=\mathbb {R}^{n}\times \mathbb {R}^{n}\times \mathbb {R}$, we refer to the projection of $\operatorname {epi }\varPhi ^{c}$ onto $W\mathbb {\times R}$ by $\operatorname {proj}\left ( \operatorname {epi} \varPhi ^{c}\right ).$ These two projections could be written more precisely as $\operatorname {proj}_{n+m}^{\left \{ n+1,\ldots ,n+m\right \} }$ and $\operatorname {proj} _{2n+2m+1}^{\left \{ 1,\ldots ,n,m+1,\ldots ,m+n,2n+2m+1\right \} },$ respectively, but this notation would provide cumbersome formulae.

Theorem 4.14 (General Regularity Conditions)

Let us consider the general primal problem (GP) and its dual (GD _c), and assume that Φ is e-convex. The following conditions ensure $\partial _{c}p\left ( 0_{m}\right ) \neq \emptyset$ and, therefore, strong duality between (GP) and (GD _c):

• (C1) $0_{m}\in \operatorname {rint} \operatorname {proj}\left ( \operatorname {dom}\varPhi \right ) .$

• (C2) $\operatorname {proj}\left ( \operatorname {epi}\varPhi ^{c}\right )$ is e ^′-convex or, equivalently,

  $$\displaystyle \begin{aligned} \operatorname{proj}\left( \operatorname{epi}\varPhi ^{c}\right) =\operatorname{epi}\varPhi ^{c}\left( \cdot ,0_{m}\right) . \end{aligned}$$

  Moreover, this equality can be reformulated as the fulfilment of the following condition

  $$\displaystyle \begin{aligned} \varPhi ^{c}\left( \cdot ,0_{m}\right) =\min_{y^{\ast },v^{\ast }\in \mathbb{R} ^{m}}\varPhi ^{c}\left( \left( \cdot ,y^{\ast }\right) ,\left( \cdot ,v^{\ast }\right) ,\cdot \right) , \end{aligned}$$

  where $\varPhi \left ( \cdot ,0_{m}\right ) :\mathbb {R}^{n}\rightarrow \overline { \mathbb {R}},$ $\varPhi ^{c}\left ( \cdot ,0_{m}\right ) :W\rightarrow \overline { \mathbb {R}},$ $\varPhi ^{c}\left ( \left ( \cdot ,y^{\ast }\right ) ,\left ( \cdot ,v^{\ast }\right ) ,\cdot \right ) :W\rightarrow \overline {\mathbb {R}}$ and $W= \mathbb {R}^{n}\times \mathbb {R}^{n}\times \mathbb {R}.$

Remark 4.1

As it is shown in [47], conditions $\left ( C1\right )$ and $\left ( C2\right )$ are also sufficient for stable strong duality. The perturbed problems with linear functionals and the corresponding duals are

$$\displaystyle \begin{aligned} \begin{array}{rcl} (GP_{x^{\ast }}) \quad &\displaystyle \operatorname*{\mathrm{Min}}\limits_{x\in \mathbb{R}^{n}} &\displaystyle \varPhi (x,0_{m})+\left\langle x,x^{\ast }\right\rangle , \\ (GD_{c,x^{\ast }}) \quad &\displaystyle \operatorname*{\mathrm{Max}}\limits_{y^{\ast },v^{\ast }\in \mathbb{R}^{m},\alpha\in\mathbb{R}} &\displaystyle -\varPhi ^{c}\left( \left( -x^{\ast },y^{\ast }\right) ,\left( 0_{n},v^{\ast }\right) ,\alpha \right) \\ &\displaystyle \text{s.t.} &\displaystyle \alpha >0, \end{array} \end{aligned} $$

for an arbitrary $x^{\ast }\in \mathbb {R}^{n}.$

4.4.2 Regularity Conditions for Fenchel Duality

In this subsection, we consider a particular primal problem together with a particular perturbation function, whose c-conjugate allows us to obtain a Fenchel-type dual problem. We analyze regularity conditions for this pair of problems and do a comparison among them. Let us consider the following optimization problem

$$\displaystyle \begin{aligned} \begin{array}{lcl} (P_{1}) \quad & \operatorname*{\mathrm{Min}}\limits_{x\in \mathbb{R}^{n}} & f(x)+g(x), \end{array} \end{aligned}$$

where $f,g:\mathbb {R}^{n}\rightarrow \overline {\mathbb {R}}$ are proper functions, with $\operatorname {dom}f\cap \operatorname {dom}g\neq \emptyset$. The problem (P ₁) is a particular case of (GP) with F = f + g.

We will consider the perturbation function $\varPhi _{F}:\mathbb {R} ^{n}\times \mathbb {R}^{n}\rightarrow \overline {\mathbb {R}}$ given by

$$\displaystyle \begin{aligned} \varPhi _{F}\left( x,u\right) :=f\left( x+u\right) +g\left( x\right) . {} \end{aligned} $$

(4.10)

Calculating the c-conjugate of Φ _F as in (4.9) we obtain the Fenchel dual problem of (P ₁):

$$\displaystyle \begin{aligned} \begin{array}{lcl} (D_{F}) \quad & \operatorname*{\mathrm{Max}}\limits_{x^{\ast },u^{\ast }\in \mathbb{R}^{n},\alpha_1,\alpha_2\in\mathbb{R}} & \left\{ -f^{c}\left( x^{\ast },u^{\ast },\alpha _{1}\right) -g^{c}\left( -x^{\ast },-u^{\ast },\alpha _{2}\right) \right\} \\ & \text{s.t.} & \alpha _{1}+\alpha _{2}>0. \end{array} {} \end{aligned} $$

(4.11)

We state the next theorem which gathers all the studied regularity conditions for Fenchel duality, being $\left ( C1_{F}\right )$ and $\left ( C2_{F}\right )$ the particularized versions of the general conditions $\left ( C1\right )$ and $\left ( C2\right )$ in Theorem 4.14, respectively. Let us recall that for proper convex functions $f,g:\mathbb {R}^{n}\rightarrow \overline {\mathbb {R}}$, the infimal convolution of f with g, denoted by $f\square g:\mathbb {R}^{n}\rightarrow \overline {\mathbb {R}}$, is defined by

$$\displaystyle \begin{aligned} \left( f\square g\right) \left( x\right) :=\inf_{x_{1}+x_{2}=x}\left\{ f\left( x_{1}\right) +g\left( x_{2}\right) \right\} , \end{aligned}$$

and it is said to be exact at $x\in \mathbb {R} ^{n}$ if $\left ( f\square g\right ) \left ( x\right ) =f\left ( a\right ) +g\left ( x-a\right )$ for some $a\in \mathbb {R}^{n}$. Moreover, the infimal convolution is called exact when it is exact at any $x\in \mathbb {R}^{n}$.

Observe that, in this case, $Z=\mathbb {R}^{n}\times \mathbb {R}^{n}$, and $W= \mathbb {R}^{n}\times \mathbb {R}^{n}\times \mathbb {R}$, and when we refer to the projection of $\operatorname {epi}\varPhi _{F}^{c}$ onto $W\mathbb {\times R}$, $\operatorname {proj}\left ( \operatorname {epi}\varPhi _{F}^{c}\right ) ,$ we mean

$$\displaystyle \begin{aligned} \operatorname{proj}\left( \operatorname{epi}\varPhi _{F}^{c}\right) = \left\{ \left( x^{\ast },u^{\ast },\alpha ,\beta \right) \in W\mathbb{\times R}:\left( x^{\ast },y^{\ast },u^{\ast },v^{\ast },\alpha ,\beta \right) \in \operatorname{ epi}\varPhi _{F}^{c}, y^{\ast },v^{\ast }\in \mathbb{R}^{n}\right\} . \end{aligned}$$

Theorem 4.15 (Fenchel Regularity Conditions)

Let us consider the primal problem (P ₁), where $f,g: \mathbb {R}^{n}\rightarrow \overline {\mathbb {R}}$ are proper e-convex functions, and its Fenchel dual (D _F). The following conditions ensure strong duality between both problems:

• (C1F) $0_{n}\in \operatorname {rint}\left ( \operatorname {dom}f- \operatorname {dom}g\right ) .$

• (C2F) $\operatorname {proj}\left ( \operatorname {epi}\varPhi _{F}^{c}\right )$ is e ^′-convex, or, equivalently,

  $$\displaystyle \begin{aligned} \varPhi _{F}^{c}\left( \cdot ,0_{m}\right) =\min_{y^{\ast },v^{\ast }\in \mathbb{R}^{n}}\varPhi _{F}^{c}\left( \left( \cdot ,y^{\ast }\right) ,\left( \cdot ,v^{\ast }\right) ,\cdot \right) . \end{aligned}$$

• (C3F) $f+g=\sup \widetilde {\mathscr {E}}_{f,g}$ and $\operatorname {epi}f^{c}+\operatorname {epi}g^{c}$ is e ^′-convex.

Moreover, strong duality is characterized by the following condition:

• (C4F) There exists α > 0 such that $\left ( f+g\right ) ^{c}\left ( 0_{n},0_{n},\alpha \right ) \geq \left ( f^{c}\square g^{c}\right ) \left ( 0_{n},0_{n},\alpha \right )$ and the infimal convolution is exact at $\left ( 0_{n},0_{n},\alpha \right ) ,$ which is equivalent to saying that

  $$\displaystyle \begin{aligned} \operatorname{epi}\left( f+g\right) ^{c}\cap \left\{ \left( 0_{n},0_{n},\alpha \right) \times \mathbb{R}\right\} \subseteq \left( \operatorname{epi}f^{c}+ \operatorname{epi}g^{c}\right) \cap \left\{ \left( 0_{n},0_{n},\alpha \right) \times \mathbb{R}\right\} . \end{aligned}$$

Comparing regularity conditions $\left ( C1_{F}\right ) ,$ $\left ( C2_{F}\right )$ and $\left ( C3_{F}\right ) ,$ the unique relationship among them is that $\left ( C3_{F}\right )$ implies $\left ( C2_{F}\right )$, as it is pointed out ahead in Proposition 4.6. The following example shows that $\left ( C3_{F}\right )$ does not imply $\left ( C1_{F}\right ) .$

Example 4.10

Let us take n = 1, $f=\delta _{\left [ 0,+\infty \right [ }$ and $g=\delta _{\left ] -\infty ,0\right ] }$. Since

$$\displaystyle \begin{aligned} \operatorname{dom}f - \operatorname{dom}g = [0,+\infty[, \end{aligned}$$

$0\in \operatorname {int}(\operatorname {dom}f - \operatorname {dom}g)$ and (C1_F) does not hold. We now check condition $\left (C3_{F}\right )$.

We have $f+g=\delta _{\left \{ 0\right \} }$ and let $h=\sup \widetilde { \mathscr {E}}_{f,g}$. Now, an e-affine function $a_{1}\in \mathscr {E}_{f}$ if and only if

$$\displaystyle \begin{aligned} a_{1}\left( x\right) =\left\{ \begin{array}{ll} \alpha _{1}x-\beta _{1}, & \text{if }\gamma _{1}x<\delta _{1}, \\ +\infty , & \text{otherwise,} \end{array} \right. \end{aligned}$$

with α ₁ ≤ 0, β ₁ ≥ 0, γ ₁ ≤ 0 and δ ₁ > 0. On the other hand, $a_{2}\in \mathscr {E}_{g}$ if and only if

$$\displaystyle \begin{aligned} a_{2}\left( x\right) =\left\{ \begin{array}{ll} \alpha _{2}x-\beta _{2}, & \text{if }\gamma _{2}x<\delta _{2}, \\ +\infty , & \text{otherwise,} \end{array} \right. \end{aligned}$$

with α ₂ ≥ 0, β ₂ ≥ 0, γ ₂ ≥ 0 and δ ₂ > 0. Then, $a\in \widetilde {\mathscr {E}}_{f,g}$ if and only if

$$\displaystyle \begin{aligned} a\left( x\right) =\left\{ \begin{array}{ll} \alpha x-\beta , & \text{if }\gamma x<\delta , \\ +\infty , & \text{otherwise,} \end{array} \right. \end{aligned}$$

with $\alpha ,\gamma \in \mathbb {R}$, β ≥ 0 and δ > 0.

We obtain $h=\sup \widetilde {\mathscr {E}}_{f,g}=\delta _{\left \{ 0\right \} }=f+g.$ The following step is to calculate $\operatorname {epi}f^{c}+\operatorname {epi} g^{c}$. We have $\left ( \alpha ,\beta ,\gamma ,\delta \right ) \in \operatorname {epi}f^{c}$ if and only if, for all x ≥ 0, αx ≤ δ and βx < γ, hence $\operatorname {epi}f^{c}=\mathbb {R}_{-}\times \mathbb {R}_{-}\times \mathbb {R}_{++}\times \mathbb {R}_{+}.$ Similarly, $\left ( \alpha ,\beta ,\gamma ,\delta \right ) \in \operatorname {epi} g^{c}$ if and only if, for all x ≤ 0, αx ≤ δ and βx < γ, hence $\operatorname {epi}\delta _{A}^{c}=\mathbb {R} _{+}\times \mathbb {R}_{+}\times \mathbb {R}_{++}\times \mathbb {R}_{+}.$ We obtain

$$\displaystyle \begin{aligned} \operatorname{epi}f^{c}+\operatorname{epi}g^{c}=\mathbb{R}\times \mathbb{R}\times \mathbb{R}_{++}\times \mathbb{R}_{+}. \end{aligned}$$

This set is e^′-convex, because it is the epigraph of the c^′-elementary function $c^{\prime }\left ( \cdot ,0\right ) ,$ which allows us to conclude that conditions in $\left ( C3_{F}\right )$ fulfills.

Proposition 4.6 (Relations Between Fenchel Regularity Conditions)

$\left ( C3_{F}\right )$ implies $\left ( C 2_{F}\right )$. Moreover, if $f+g=\sup \widetilde {\mathscr {E}}_{f,g}$, $\left ( C2_{F}\right )$ implies $\left (\mathrm {C3}_{F}\right )$ if and only if

$$\displaystyle \begin{aligned} f^{c}\square g^{c}=\min_{y^{\ast },v^{\ast }\in \mathbb{R}^{n}}\varPhi ^{c}\left( \left( \cdot ,y^{\ast }\right) ,\left( \cdot ,v^{\ast }\right) ,\cdot \right) . \end{aligned}$$

The following example shows that in general $\left ( C2_{F}\right )$ does not imply $\left ( C3_{F}\right ) .$

Example 4.11

Let us take n = 1, $g=\delta _{\left [ 0,+\infty \right [ }$ and $f=\delta _{\left ] 0,+\infty \right [ }.$

It is easy to see that $f+g=\sup \widetilde {\mathscr {E}}_{f,g}$. The most important fact to prove is that

$$\displaystyle \begin{aligned} \left( f^{c}\square g^{c}\right) \left( x^{\ast },u^{\ast },\alpha \right) >\inf_{y^{\ast },v^{\ast }\in \mathbb{R}}\varPhi ^{c}\left( \left( x^{\ast },y^{\ast }\right) ,\left( u^{\ast },v^{\ast }\right) ,\alpha \right) \end{aligned}$$

at some point $\left ( x^{\ast },u^{\ast },\alpha \right ) \in \mathbb {R}^{3},$ implying, by Proposition 4.6, that $\left ( C3_{F}\right )$ does not hold. So, we must give $\left ( u^{\ast },\alpha \right ) \in \mathbb {R}^{2}$ such that, if we have

$$\displaystyle \begin{aligned} \left( v^{\ast }-u^{\ast }\right) x+u^{\ast }u<\alpha ,\forall x\in \operatorname{ dom}g,\forall u\in \operatorname{dom}f, {} \end{aligned} $$

(4.12)

for some $v^{\ast }\in \mathbb {R},$ then

$$\displaystyle \begin{aligned} \left( u^{\ast }-w^{\ast }\right) x<\alpha _{1}\text{ and }w^{\ast }u<\alpha _{2} {} \end{aligned} $$

(4.13)

whatever $w^{\ast }\in \mathbb {R}$ implies α ₁ + α ₂ > α, meaning that $\left (f^{c}\square g^{c}\right ) \left ( x^{\ast },u^{\ast },\alpha \right ) =+\infty .$ Take $\left ( u^{\ast },\alpha \right ) =\left ( -1,0\right ) .$ For any − 1 ≤ v ^∗ < 0, (4.12) holds. However for any $w^{\ast }\in \mathbb {R}$ verifying (4.13) it must be α ₁ + α ₂ > 0, since α ₁ > 0 and α ₂ ≥ 0 necessarily.

On the other hand, if x ^∗≤ 0,

$$\displaystyle \begin{aligned} \inf_{y^{\ast },v^{\ast }\in \mathbb{R}}\varPhi ^{c}\left( \left( x^{\ast },y^{\ast }\right) ,\left( -1,v^{\ast }\right) ,0\right) =\inf_{y^{\ast }\in \mathbb{R}}\left\{ \sup_{x\geq 0}\left( x^{\ast }-y^{\ast }\right) x+\sup_{z>0}y^{\ast }z\right\} =0. \end{aligned}$$

Now we are going to check that

$$\displaystyle \begin{aligned} \sup_{x\in \mathbb{R}}\left\{ c\left( x,\left( x^{\ast },u^{\ast },\alpha \right) \right) -\varPhi \left( x,0\right) \right\} =\min_{y^{\ast },v^{\ast }\in \mathbb{R}}\varPhi ^{c}\left( \left( x^{\ast },y^{\ast }\right) ,\left( u^{\ast },v^{\ast }\right) ,\alpha \right) , {} \end{aligned} $$

(4.14)

for all $\left ( x^{\ast },u^{\ast },\alpha \right ) \in \mathbb {R}^{3},$ which means that $\left ( C2_{F}\right )$ holds.

In the case $\sup _{x\in \mathbb {R}}\left \{ c\left ( x,\left ( x^{\ast },u^{\ast },\alpha \right ) \right ) -\varPhi \left ( x,0\right ) \right \} =+\infty ,$ (4.14) holds trivially. Hence, let us assume that $\sup _{x\in \mathbb {R}}\left \{ c\left ( x,\left ( x^{\ast },u^{\ast },\alpha \right ) \right ) -\varPhi \left ( x,0\right ) \right \} <+\infty .$ It is equivalent to saying that $\left ( x^{\ast },u^{\ast },\alpha \right ) \in \mathbb {R}_{-}\times \left ( \mathbb {R} _{-}\times \mathbb {R}_{+}\backslash \left \{ 0_{2}\right \} \right )$ and then

$$\displaystyle \begin{aligned} \sup_{x\in \mathbb{R}}\left\{ c\left( x,\left( x^{\ast },u^{\ast },\alpha \right) \right) -\varPhi \left( x,0\right) \right\} =0. \end{aligned}$$

We now compute $\varPhi ^{c}\left ( \left ( x^{\ast },y^{\ast }\right ) ,\left ( u^{\ast },v^{\ast }\right ) ,\alpha \right )$, for any points $\left ( x^{\ast },u^{\ast },\alpha \right ) \in \mathbb {R}_{-}\times \left ( \mathbb {R}_{-}\times \mathbb {R}_{+}\backslash \left \{ 0_{2}\right \} \right )$ and $y^{\ast },v^{\ast }\in \mathbb {R}:$

$$\displaystyle \begin{aligned} \begin{array}{rcl} &\displaystyle &\displaystyle \varPhi ^{c}\left( \left( x^{\ast },y^{\ast }\right) ,\left( u^{\ast },v^{\ast }\right) ,\alpha \right) \\ &\displaystyle =&\displaystyle \sup_{x,z\in \mathbb{R}}\left\{ \overline{c}\left( \left( x,y\right) ,\left( x^{\ast }-y^{\ast },y^{\ast }\right) ,\left( u^{\ast }-v^{\ast },v^{\ast }\right) ,\alpha \right) -f\left( y\right) -g\left( x\right) \right\} \\ &\displaystyle =&\displaystyle \sup_{x\geq 0,y>0}\left\{ \overline{c}\left( \left( x,y\right) ,\left( x^{\ast }-y^{\ast },y^{\ast }\right) ,\left( u^{\ast }-v^{\ast },v^{\ast }\right) ,\alpha \right) \right\} . \end{array} \end{aligned} $$

Since we are interested in those suprema which are finite, if u ^∗ < 0 and α ≥ 0, take any $v^{\ast }\in \left [ u^{\ast },0\right [$ and, if u ^∗ = 0 and α > 0, take v ^∗ = 0. Then

$$\displaystyle \begin{aligned} \begin{array}{rcl} &\displaystyle &\displaystyle \inf_{y^{\ast },v^{\ast }\in \mathbb{R}}\sup_{x\geq 0,y>0}\left\{ \overline{c}\left( \left( x,y\right) ,\left( x^{\ast }-y^{\ast },y^{\ast }\right) ,\left( u^{\ast }-v^{\ast },v^{\ast }\right) ,\alpha \right) \right\} \\ &\displaystyle =&\displaystyle \inf_{y^{\ast }\leq x^{\ast }}\sup_{x\geq 0,y>0}\left\{ \left( x^{\ast }-y^{\ast }\right) x+y^{\ast }z\right\} =0, \end{array} \end{aligned} $$

and this infimum is a minimum.

We finish the comparison with an example showing that $\left ( C 1_{F}\right )$ does not imply $\left ( C2_{F}\right )$.

Example 4.12

Let us take n = 1, $g=\delta _{\left [ 0,+\infty \right [ }$ and $f=\delta _{ \left ] 1,+\infty \right [ }$. At the point $\left ( x^{\ast },-1,-1\right ) \in \mathbb {R}^{3}$, x ^∗≤ 0, we obtain

$$\displaystyle \begin{aligned} \sup_{x\in \mathbb{R}}\left\{ c\left( x,\left( -1,-1,-1\right) \right) -\varPhi \left( x,0\right) \right\} =\sup_{x>1}\left\{ c\left( x,\left( x^{\ast },-1,-1\right) \right) \right\} =x^{\ast }. \end{aligned}$$

On the other hand,

$$\displaystyle \begin{aligned} \begin{array}{rcl} &\displaystyle &\displaystyle \inf_{y^{\ast },v^{\ast }\in \mathbb{R}}\varPhi ^{c}\left( \left( x^{\ast },y^{\ast }\right) ,\left( -1,v^{\ast }\right) ,-1\right) \\ &\displaystyle =&\displaystyle \inf_{y^{\ast },v^{\ast }\in \mathbb{R}}\sup_{z>1,x\geq 0}\left\{ \overline{c}\left( \left( x,y\right) ,\left( x^{\ast }-y^{\ast },y^{\ast }\right) ,\left( -1-v^{\ast },v^{\ast }\right) ,-1\right) \right\} . \end{array} \end{aligned} $$

Let us observe that a necessary condition (depending on $v^{\ast }\in \mathbb {R}$) for these suprema to be finite is that, for all x ≥ 0 and y > 1,

$$\displaystyle \begin{aligned} \left( -1-v^{\ast }\right) x+v^{\ast }y<-1. \end{aligned}$$

In particular for x = 0 and y > 1, it must be v ^∗ < −1, but this implies that $\left ( -1-v^{\ast }\right ) >0$ and hence $\left ( -1-v^{\ast }\right ) x$ cannot be bounded from above, since x ≥ 0. We conclude that

$$\displaystyle \begin{aligned} \overline{c}\left( \left( x,y\right) ,\left( x^{\ast }-y^{\ast },y^{\ast }\right) ,\left( -1-v^{\ast },v^{\ast }\right) ,-1\right) =+\infty , \end{aligned}$$

for all $y^{\ast },v^{\ast }\in \mathbb {R}$ and

$$\displaystyle \begin{aligned} \min_{y^{\ast },v^{\ast }\in \mathbb{R}}\varPhi ^{c}\left( \left( x^{\ast },y^{\ast }\right) ,\left( -1,v^{\ast }\right) ,-1\right) =+\infty . \end{aligned}$$

Hence $\left ( C2_{F}\right )$ does not hold despite $\left ( C1_{F}\right )$ being fulfilled, because of the fact that $\operatorname {dom}f-\operatorname {dom}g=~\mathbb {R}$.

Remark 4.2

As it is shown in [47], $\left ( C3_{F}\right )$ is a sufficient condition for stable strong Fenchel duality, i.e., for strong duality between the pair of problems

$$\displaystyle \begin{aligned} \begin{array}{rcl} (P_{1,x^{\ast }}) \quad &\displaystyle \operatorname*{\mathrm{Min}}\limits_{x\in \mathbb{R}^{n}} &\displaystyle f\left( x\right) +g(x)+\left\langle x,x^{\ast }\right\rangle \\ {} (D_{F,x^{\ast }}) \quad &\displaystyle \operatorname*{\mathrm{Max}}\limits_{y^{\ast },u^{\ast }\in \mathbb{R}^{n},\alpha_1,\alpha_2\in\mathbb{R}} &\displaystyle \left\{ -f^{c}\left( y^{\ast }-x^{\ast },u^{\ast },\alpha _{1}\right) -g^{c}\left( -y^{\ast },-u^{\ast },\alpha _{2}\right) \right\} \\ &\displaystyle \text{s.t.} &\displaystyle \alpha _{1}+\alpha _{2}>0, \end{array} \end{aligned} $$

for all $x^{\ast }\in \mathbb {R}^{n}.$

4.4.3 Regularity Conditions for Lagrange Duality

In this subsection, we consider the following primal problem

$$\displaystyle \begin{aligned} \begin{array}{lcl} (P_{2}) \quad & \operatorname*{\mathrm{Min}}\limits_{x\in\mathbb{R}^{n}} & f(x) \\ & \text{s.t.} & g_{i}\left( x\right) \leq 0,i=1,\ldots ,m, \end{array} {} \end{aligned} $$

(4.15)

where $f,g_{i}:\mathbb {R}^{n}\rightarrow \overline {\mathbb {R}}$, for all i = 1, …, m, are proper functions. Let us suppose that the feasible set $A=\left \{ x\in \mathbb {R}^{n}:g_{i}\left ( x\right ) \leq 0,i=1,\ldots ,m\right \}$ is nonempty. The problem (P ₂) is a particular case of (GP) with F = f + δ _A. We also consider the following perturbation function $\varPhi _{L}:\mathbb {R}^{n}\times \mathbb {R}^{m}\rightarrow \overline { \mathbb {R}}$,

$$\displaystyle \begin{aligned} \varPhi _{L}\left( x,b\right) =\left\{ \begin{array}{ll} f\left( x\right) , & \text{if }g_{i}\left( x\right) \leq b_{i},i=1,\ldots ,m, \\ +\infty , & \text{otherwise.} \end{array} \right. {} \end{aligned} $$

(4.16)

In this case, the perturbation variable is $b\in \mathbb {R}^{m}.$ We can describe A as the set $\{ x\in \mathbb {R}^{n} : g\left ( x\right ) \in -\mathbb {R}_{+}^{m} \}$, where $g\left ( x\right ) =\left ( g_{1}\left ( x\right ) ,\ldots ,g_{m}\left ( x\right ) \right ) ,$ for all $x\in \mathbb {R}^{n},$ and the perturbation function Φ _L reads

$$\displaystyle \begin{aligned} \varPhi _{L}\left( x,b\right) =\left\{ \begin{array}{ll} f\left( x\right) , & \text{if }g\left( x\right) -b\in -\mathbb{R}_{+}^{m}, \\ +\infty , & \text{otherwise.} \end{array} \right. \end{aligned}$$

Calculating the c-conjugate of Φ _L makes it possible to associate to (P ₂) a dual problem verifying weak duality. In [45] it was obtained the following Lagrange dual problem

$$\displaystyle \begin{aligned} (D_{L}) \quad \operatorname*{\mathrm{Max}}\limits_{\lambda \in \mathbb{R}_{+}^{m}} \ \inf_{x\in \mathbb{R}^{n}}\left\{ f\left( x\right) +\left\langle \lambda ,g\left( x\right) \right\rangle \right\} {} \end{aligned} $$

(4.17)

which is the classical Lagrange dual problem actually.

This subsection is devoted to study strong duality between $\left ( P_{2}\right )$ and (D _L). Trivially, if v(P ₂) = −∞ strong duality holds. The function $\left \langle \lambda ,g\left ( \cdot \right ) \right \rangle :\mathbb {R}^{n}\rightarrow \overline {\mathbb {R}}$ defined as $\left \langle \lambda ,g\left ( \cdot \right ) \right \rangle \left ( x\right ) :=\left \langle \lambda ,g\left ( x\right ) \right \rangle$, for any $\lambda \in \mathbb {R}_{+}^{m},$ will be denoted by λg.

We will say that (P ₂) verifies the e-convex cone constraint qualification $\left ( ECCQ\right )$ if the cone $\bigcup \limits _{\lambda \in \mathbb {R}_{+}^{m}} \operatorname {epi}\left ( \lambda g\right ) ^{c}$ is an e^′-convex set. It can be viewed as the counterpart of the Farkas-Minkowski CQ in [69], and can be reformulated in the following way, if the e^′-convex hull of $\bigcup \limits _{\lambda \in \mathbb {R}_{+}^{m}}\operatorname {epi}\left ( \lambda g\right ) ^{c}$ is computed:

$$\displaystyle \begin{aligned} \begin{array}{cc} \left( ECCQ\right) & \bigcup\limits_{\lambda \in \mathbb{R}_{+}^{m}}\operatorname{epi }\left( \lambda g\right) ^{c}=\operatorname{epi}\delta _{A}^{c}. \end{array} {} \end{aligned} $$

(4.18)

The next theorem shows the main regularity conditions for Lagrange duality. Again, as in Fenchel case, conditions $\left ( C1_{L}\right )$ and $\left ( C2_{L}\right )$ are the particularized versions of the general conditions $\left ( C1\right )$ and $\left ( C2\right )$ in Theorem 4.14, respectively.

In this context, $\operatorname {epi}\varPhi _{L}^{c}\subset Z\times Z\times \mathbb { R\times R}$, $Z=\mathbb {R}^{n}\times \mathbb {R}^{m}$, $W=\mathbb {R} ^{n}\times \mathbb {R}^{n}\times \mathbb {R}$, and when we refer to the projection of $\operatorname {epi}\varPhi _{L}^{c}$ onto $W\mathbb {\times R}$, $\operatorname {proj}\left ( \operatorname {epi}\varPhi _{L}^{c}\right ) ,$ we mean

$$\displaystyle \begin{aligned} \operatorname{proj}\left( \operatorname{epi}\varPhi _{L}^{c}\right) = \left\{ \left( x^{\ast },u^{\ast },\alpha ,\beta \right) \in W\mathbb{\times R} : \left( x^{\ast },\lambda ,u^{\ast },\delta ,\alpha ,\beta \right) \in \operatorname{epi} \varPhi_{L}^{c}, \lambda ,\delta \in \mathbb{R}^{m}\right\} . \end{aligned}$$

Theorem 4.16 (Lagrange Regularity Conditions)

Let us consider the primal problem (P ₂), where $f,g_{t}: \mathbb {R}^{n}\rightarrow \overline {\mathbb {R}}$ are proper e-convex functions, and its Lagrange dual (D _L). If $f+\delta _{A}=\sup \widetilde {\mathscr {E}}_{f,\delta _{A}}$ and $\operatorname {epi}f^{c}+\operatorname {epi} \delta _{A}^{c}$ is e ^′-convex, any of the following conditions ensures strong duality between (P ₂) − (D _L).

• (C1L) $0_{m}\in \operatorname {rint}\left ( g\left ( \operatorname { dom}f\right ) +\mathbb {R}_{+}^{m}\right ) .$

• (C2L) $\operatorname {proj}\left ( \operatorname {epi}\varPhi _{L}^{c}\right )$ is e ^′-convex, or, equivalently,

  $$\displaystyle \begin{aligned} \varPhi _{L}\left( \cdot ,0_{m}\right) ^{c}=\min_{\lambda ,\beta \in \mathbb{R} ^{m}}\varPhi _{L}^{c}\left( \cdot ,\left( \lambda ,\beta \right) \right) . \end{aligned}$$

• (C3L) (P ₂) verifies $\left ( ECCQ\right )$.

• (C4L) For all $\left ( x^{\ast },y^{\ast },\alpha \right ) \in W$ such that $A\subset \left \{ x\in \mathbb {R}^{n}:\left \langle x,y^{\ast }\right \rangle <\alpha \right \}$ it holds

  $$\displaystyle \begin{aligned} \inf_{x\in A}c\left( x,\left( x^{\ast },y^{\ast },\alpha \right) \right) =\max_{\mathbb{R}_{+}^{m}}\left\{ \inf_{x\in \mathbb{R}^{n}}\left\{ c\left( x,\left( x^{\ast },y^{\ast },\alpha \right) \right) +\lambda g\left( x\right) \right\} \right\} . {} \end{aligned} $$

  (4.19)

  and there exists a solution $\overline {\lambda }$ of $\left ( \mathit{\mbox{4.19}} \right )$ which, in addition, verifies

  $$\displaystyle \begin{aligned} \inf_{x\in A}c\left( x,\left( x^{\ast },y^{\ast },\alpha \right) \right) =\inf_{x\in \operatorname{dom}\overline{\lambda }g}\left\{ -c\left( x,\left( -x^{\ast },y^{\ast },\alpha \right) \right) +\overline{\lambda }g\left( x\right) \right\} . \end{aligned}$$

Actually, $\left ( C3_{L}\right )$ and (C4_L) are equivalent.

Next we compare the regularity conditions $\left ( C1_{L}\right ) ,$ $\left ( C2_{L}\right )$ and $\left ( C3_{L}\right ) .$ As we shall see, the unique relationship between them is that $\left ( C3_{L}\right )$ implies $\left ( C2_{L}\right ) .$

Proposition 4.7 (Relation Between Lagrange Regularity Conditions)

Regularity condition $\left ( C3_{L}\right )$ implies $\left ( C2_{L}\right )$.

The following example shows that $\left ( C2_{L}\right )$ does not imply $\left ( C3_{L}\right ) .$

Example 4.13

Let us take n = 1, $f=\delta _{\left [ 0,+\infty \right [ },$ m =  1 and $g_{1}\left ( x\right ) =x.$ We have $A=\left ] -\infty ,0\right ] .$

It was shown, in Example 4.10, that $f+\delta _{A}=\sup \widetilde {\mathscr {E}}_{f,\delta _{A}}$ and

$$\displaystyle \begin{aligned} \operatorname{epi}f^{c}+\operatorname{epi}\delta _{A}^{c}=\mathbb{R}\times \mathbb{R}\times \mathbb{R}_{++}\times \mathbb{R}_{+}, \end{aligned}$$

which is e^′-convex. We shall see that (ECCQ) does not hold, i.e.,

$$\displaystyle \begin{aligned} \bigcup\limits_{\lambda \geq 0}\operatorname{epi}\left( \lambda g\right) ^{c}\subsetneqq \operatorname{epi}\delta _{A}^{c}. \end{aligned}$$

Since $\operatorname {epi}\delta _{A}^{c}=\mathbb {R}_{+}\times \mathbb {R}_{+}\times \mathbb {R}_{++}\times \mathbb {R}_{+}$ (see again Example 4.10), a point $( \alpha ,\beta ,\gamma ,\delta ) \in \operatorname {epi}\delta _{A}^{c}$ verifies α ≥ 0, β ≥ 0, γ > 0 and δ ≥ 0. This point will be in $\operatorname {epi}\left ( \lambda g\right ) ^{c}$ for some λ ≥ 0 if $c\left ( x,\left ( \alpha ,\beta ,\gamma \right ) \right ) -\lambda x\leq \delta ,$ for all $x\in \operatorname {dom}\left ( \lambda g\right ) =\mathbb {R}$, which implies that βx < γ, for all $x\in \mathbb {R}$, and this is impossible if β ≠ 0. Hence $\left ( C 3_{L}\right )$ does not fulfill.

We now prove that $\left ( C2_{L}\right )$ holds. The set $\operatorname { proj}\left ( \operatorname {epi}\varPhi _{L}^{c}\right )$ is e^′-convex if and only if

$$\displaystyle \begin{aligned} \operatorname{epi}\varPhi _{L}\left( \cdot ,0\right) ^{c}\subset \operatorname{proj}\left( \operatorname{epi}\varPhi _{L}^{c}\right) , \end{aligned}$$

according to the equivalent formulation of $\left ( C2_{L}\right )$. Since $\left ( \operatorname {dom}f\right ) \cap A\neq \emptyset$, $f+\delta _{A}=h_{f,\delta _{A}}$ and $\operatorname {epi}f^{c}+\operatorname {epi}\delta _{A}^{c}$ is e^′-convex, applying Theorem 4.16, we have

$$\displaystyle \begin{aligned}\operatorname{epi}\varPhi _{L}\left( \cdot ,0\right) ^{c}=\operatorname{epi}\left( f+\delta _{A}\right) ^{c}= \operatorname{epi}f^{c}+\operatorname{epi}\delta _{A}^{c},\end{aligned}$$

hence we will see that

$$\displaystyle \begin{aligned} \mathbb{R}\times \mathbb{R}\times \mathbb{R}_{++}\times \mathbb{R}_{+}=\operatorname{ epi}f^{c}+\operatorname{epi}\delta _{A}^{c}\subset \operatorname{proj}\left( \operatorname{epi} \varPhi _{L}^{c}\right) . \end{aligned}$$

Take a point $\left ( \alpha ,\beta ,\gamma ,\delta \right ) \in \operatorname {epi} f^{c}+\operatorname {epi}\delta _{A}^{c}.$ Hence $\alpha \in \mathbb {R},$ $\beta \in \mathbb {R},$ γ > 0 and δ ≥ 0. This point will be in $\operatorname {proj}\left ( \operatorname {epi}\varPhi _{L}^{c}\right )$ if and only if there exist $\lambda _{1},\lambda _{2}\in \mathbb {R}$ such that $\varPhi _{L}^{c}\left ( \left ( \alpha ,\lambda _{1}\right ) ,\left ( \beta ,\lambda _{2}\right ) ,\gamma \right ) \leq \delta ,$ meaning that, for all $\left ( x,b\right ) \in \operatorname {dom}\varPhi _{L},$

$$\displaystyle \begin{aligned}c_{1}\left( \left( x,b\right) ,\left( \alpha ,\lambda _{1}\right) ,\left( \beta ,\lambda _{2}\right) ,\gamma \right) \leq \delta ;\end{aligned}$$

equivalently,

$$\displaystyle \begin{aligned} \beta x+\lambda _{2}b<\gamma \text{ and }\alpha x+\lambda _{1}b\leq \delta . {} \end{aligned} $$

(4.20)

Since $\operatorname {dom}\varPhi _{L}=\left \{ \left ( x,b\right ) \in \mathbb {R}\times \mathbb {R}:0\leq x\leq b\right \} ,$ taking in particular x = 0 and b ≥ 0, from (4.20) we deduce that λ ₁, λ ₂ ≤ 0. Now, for x > 0 and b ≥ x,

$$\displaystyle \begin{aligned} \beta x+\lambda _{2}b\leq x\left( \beta +\lambda _{2}\right) . \end{aligned}$$

Taking λ ₂ ≤ 0 satisfying $\left ( \beta +\lambda _{2}\right ) \leq 0,$ we have βx + λ ₂b < γ, If we now take the second inequality in (4.20), we also deduce that the choice of λ ₁ only depends of the chosen α, which is fixed, and again clearly λ ₁ ≤ 0 can be found. We conclude that $\left ( \alpha ,\beta ,\gamma ,\delta \right ) \in \operatorname {proj}\left ( \operatorname {epi}\varPhi _{L}^{c}\right ) .$

We continue with an example showing that $\left ( \text{C3}_{L}\right )$ does not imply $\left ( C1_{L}\right ) .$

Example 4.14

Consider n = 1, $f=\delta _{\left [ 0,+\infty \right [ },$ m = 2 and $g_{i}\left ( x\right ) =\left ( i-1\right ) x+\delta _{\left ] -\infty ,i-1\right ] }\left ( x\right ) ,$ i = 1, 2. We have Then, as in the previous example, $f+\delta _{A}=h_{f,\delta _{A}}$ and $\operatorname {epi}f^{c}+\operatorname {epi}\delta _{A}^{c}$ is e^′ -convex. For the fulfilment of $\left ( C3_{L}\right )$ we only need to show that $\left ( ECCQ\right )$ holds, i.e.,

$$\displaystyle \begin{aligned} \operatorname{epi}\delta _{A}^{c}=\mathbb{R}_{+}\times \mathbb{R}_{+}\times \mathbb{R }_{++}\times \mathbb{R}_{+}\subset \bigcup\limits_{\lambda \in \mathbb{R} _{+}^{2}}\operatorname{epi}\left( \lambda g\right) ^{c}. \end{aligned}$$

Take any point $\left ( \alpha ,\beta ,\gamma ,\delta \right ) \in \operatorname {epi} \delta _{A}^{c},$ with α ≥ 0, β ≥ 0, γ > 0 and δ ≥ 0. Then $\left ( \alpha ,\beta ,\gamma ,\delta \right ) \in \operatorname { epi}\left ( \lambda g\right ) ^{c}$ for some $\lambda \in \mathbb {R}_{+}^{2}$ if $c\left ( x,\left ( \alpha ,\beta ,\gamma \right ) \right ) -\lambda g\left ( x\right ) \leq \delta ,$ for all $x\in \mathbb {R},$ i.e.,

$$\displaystyle \begin{aligned} \operatorname{dom}\left( \lambda g\right) \subset \left\{ x\in \mathbb{R:}\beta x<\gamma \right\} \text{ and }\alpha x-\lambda g\left( x\right) \leq \delta , \forall x\in \operatorname{dom}\left( \lambda g\right) . \end{aligned}$$

We distinguish two cases.

Case 1::

If β = 0, it is enough to take $\lambda =\left ( \lambda _{1},\lambda _{2}\right ) =\left ( 0,\alpha \right )$. Then $\operatorname {dom}\left ( \lambda g\right ) =\operatorname {dom}g_{2}=\left ] -\infty ,1\right ] \subset \left \{ x\in \mathbb {R:}\beta x<\gamma \right \} =\mathbb {R}.$ Moreover, $\alpha x-\lambda g\left ( x\right ) =\left ( \alpha -\alpha \right ) x=0\leq \delta ,$ for all x ≤ 1, since δ ≥ 0.

Case 2::

If β > 0, take $\lambda =\left ( \lambda _{1},\lambda _{2}\right ) =\left ( 1,0\right ) .$ Then $\operatorname {dom}\left ( \lambda g\right ) = \operatorname {dom}g_{1}=\left ] -\infty ,0\right ] \subset \left \{ x\in \mathbb {R} \left \vert \beta x<\gamma \right . \right \} .$ Moreover, $\alpha x-\lambda g\left ( x\right ) =\alpha x\leq \delta ,$ for all $x\in \operatorname {dom}\left ( \lambda g\right ) ,$ since α ≥ 0 and δ ≥ 0.

Then, we conclude that $\operatorname {epi}\delta _{A}^{c}\subset \bigcup \limits _{\lambda \in \mathbb {R}_{+}^{2}}\operatorname {epi}\left ( \lambda g\right ) ^{c}.$

It remains to prove that $0 \notin \mbox{rint} \left ( g(\operatorname {dom} f) + +\mathbb {R}_{+}^{2}\right )$, meaning that (C1_L) does not hold. Since $\operatorname {dom}f=\left [ 0,+\infty \right [ ,$ x = 0 is the only point verifying $g\left ( 0\right ) \in$ $\mathbb {R}^{2}$. Hence

$$\displaystyle \begin{aligned} g\left( \operatorname{dom}f\right) +\mathbb{R}_{+}^{2}=\mathbb{R}_{+}^{2}, \end{aligned}$$

and (C1_L) does not fulfill.

We finish with an example showing that $\left ( C1_{L}\right )$ does not imply $\left ( C2_{L}\right ) .$

Example 4.15

Let us take n = 2, m = 2, $g_{1}\left ( x\right ) =x_{1}+x_{2}$ and $g_{2}\left ( x\right ) =x_{1}-x_{2},$ and consider the function $f:\mathbb {R}^{2}\rightarrow \overline {\mathbb {R}}$ such that

$$\displaystyle \begin{aligned} f\left( x_{1},x_{2}\right) =\left\{ \begin{array}{ll} \frac{x_{2}^{2}}{x_{1}}, & \text{if }x_{1}>0, \\ 0, & \text{if }x_{1}=x_{2}=0, \\ +\infty , & \text{otherwise.} \end{array} \right. \end{aligned}$$

It was shown, in Example 4.3, that f is a proper e-convex function. We have

$$\displaystyle \begin{aligned} A=\left\{ \left( x_{1},x_{2}\right) \in \mathbb{R}^{2}:x_{1}\leq 0,x_{1}\leq x_{2}\right\} . \end{aligned}$$

It is clear that $\left ( C1_{L}\right )$ holds, since $\operatorname {dom} f=\left ( \left ] 0,+\infty \right [ \times \mathbb {R}\right ) \cup \left \{ 0_{2}\right \}$], and we obtain in this case that $g\left ( \operatorname {dom}f\right ) +\mathbb {R}_{+}^{2}=\mathbb {R }^{2}$.

Now, we use the equivalent condition to $\left ( C2_{L}\right )$, and we will see that there exists at least a point $\left ( x^{\ast },y^{\ast },\alpha \right ) \in W$ such that

$$\displaystyle \begin{aligned} \varPhi _{L}\left( \cdot ,0\right) ^{c}\left( x^{\ast },y^{\ast },\alpha \right) <\min_{\lambda ,\beta \in \mathbb{R}^{2}}\varPhi _{L}^{c}\left( \left( x^{\ast },\lambda \right) ,\left( y^{\ast },\beta \right) ,\alpha \right) . \end{aligned}$$

Let $y^{\ast }=\left ( 0,1\right )$, any $x^{\ast }\in \mathbb {R}^{2}$ and α = 1. Then,

$$\displaystyle \begin{aligned} \begin{array}{rcl} \varPhi _{L}\left( \cdot ,0\right) ^{c}\left( x^{\ast },y^{\ast },\alpha \right) &\displaystyle =&\displaystyle \sup_{x\in A\cap \operatorname{dom}f}\left\{ c\left( x,\left( x^{\ast },y^{\ast },\alpha \right) \right) -\varPhi _{L}\left( x,0\right) \right\} \\ &\displaystyle =&\displaystyle \sup_{x=0_{2}}\left\{ \left\langle x,x^{\ast }\right\rangle \right\} =0. \end{array} \end{aligned} $$

Now, take any $\lambda ,\beta \in \mathbb {R}^{2}.$ Then,

$$\displaystyle \begin{aligned} \varPhi _{L}^{c}\left( \left( x^{\ast },\lambda \right) ,\left( y^{\ast },\beta \right) ,\alpha \right) =\sup_{\substack{ x\in \operatorname{dom}f \\ g\left( x\right) -b\in -\mathbb{R}_{+}^{2}}}\left\{ c_{1}\left( \left( x,b\right) ,\left( x^{\ast },\lambda \right) ,\left( y^{\ast },\beta \right) ,\alpha \right) -f\left( x\right) \right\} . \end{aligned}$$

It is clear that $c_{1}\left ( \left ( x,b\right ) ,\left ( x^{\ast },\lambda \right ) ,\left ( y^{\ast },\beta \right ) ,\alpha \right ) <+\infty$ only if

$$\displaystyle \begin{aligned} \left\langle x,y^{\ast }\right\rangle +\left\langle \beta ,b\right\rangle <\alpha , {} \end{aligned} $$

(4.21)

for all $\left ( x,b\right )$ such that $x\in \operatorname {dom}f$ and $g\left ( x\right ) -b\in -\mathbb {R}_{+}^{2}.$ Since the sequence $\left \{ \left ( x_{k}^{0},b_{k}^{0}\right ) \right \} ,$ where $x_{k}^{0}=\left ( 1,k\right )$ and $b_{k}^{0}=\left ( 1+k,1-k\right )$ for $k\in \mathbb {N}$ is contained in the set $D:=\left \{ \left ( x,b\right ) :x\in \operatorname {dom}f,\,g\left ( x\right ) -b\in -\mathbb {R}_{+}^{2}\right \} ,$ the fulfilment of (4.21) implies that, denoting $\beta =\left ( \beta _{1},\beta _{2}\right ) ,$

$$\displaystyle \begin{aligned} 1+\beta _{1}-\beta _{2}\leq 0. \end{aligned}$$

On the other hand, taking the sequence $\left \{ \left ( x_{k}^{1},b_{k}^{1}\right ) \right \} ,$ where $x_{k}^{1}=\left ( 1,-k\right )$ and $b_{k}^{1}=\left ( 1-k,1+k\right )$ for $k\in \mathbb {N}$, also contained in D, (4.21) forces

$$\displaystyle \begin{aligned} 1+\beta _{1}-\beta _{2}\geq 0, \end{aligned}$$

and we conclude that 1 + β ₁ − β ₂ = 0. Finally, considering the sequence $\left \{ \left ( x_{k}^{2},b_{k}^{2}\right ) \right \} ,$ where $x_{k}^{2}=\left ( \frac {1}{k},k\right )$ and $b_{k}^{2}=\left ( \frac {1}{k}+k, \frac {1}{k}-k\right )$ for $k\in \mathbb {N}$, again contained in D, we obtain, if (4.21) holds and taking into account that 1 + β ₁ = β ₂,

$$\displaystyle \begin{aligned} k+\frac{2}{k}\beta _{1}<1, \end{aligned}$$

for $k\in \mathbb {N}$, which is impossible. Hence $c_{1}\left ( \left ( x,b\right ) ,\left ( x^{\ast },\lambda \right ) ,\left ( y^{\ast },\beta \right ) ,\alpha \right ) =+\infty ,$ for all $\lambda ,\beta \in \mathbb {R}^{2}$, and

$$\displaystyle \begin{aligned} \min_{\lambda ,\beta \in \mathbb{R}^{2}}\varPhi _{L}^{c}\left( \left( x^{\ast },\lambda \right) ,\left( y^{\ast },\beta \right) ,\alpha \right) =+\infty . \end{aligned}$$

Remark 4.3

(C3_L) is a sufficient condition for stable strong duality for (P ₂) − (D _L). Here the extended primal and dual problems are

$$\displaystyle \begin{aligned} \begin{array}{rcl} (P_{2,x^{\ast }}) \quad &\displaystyle \operatorname*{\mathrm{Min}}\limits_{x\in\mathbb{R}^{n}} &\displaystyle f\left( x\right) +\left\langle x,x^{\ast }\right\rangle \\ &\displaystyle \text{s.t.} &\displaystyle g_{i}\left( x\right) \leq 0,i=1,\ldots ,m, \\ {} (D_{L,x^{\ast }}) \quad &\displaystyle \operatorname*{\mathrm{Max}}\limits_{\lambda \in \mathbb{R}_{+}^{m}} &\displaystyle \left\{ \inf_{x\in \mathbb{R}^{n}}\left\{ f\left( x\right) +\left\langle x,x^{\ast }\right\rangle +\lambda g\left( x\right) \right\} \right\} , \end{array} \end{aligned} $$

for all $x^{\ast }\in \mathbb {R}^{n}$, as it is shown in [47, Prop. 5.1]. Moreover, in that work, it was introduced another sufficient condition which has its counterpart in the classical setting, where f and g _i, for all i = 1, …, m, are proper convex and lsc functions. As it is proved in [22], stable strong Lagrange duality in the classical setting is equivalent to the closedness of the set

$$\displaystyle \begin{aligned} \bigcup\limits_{\lambda \in \mathbb{R}_{+}^{m}}\operatorname{epi}\left( f+\lambda g\right) ^{\ast }. \end{aligned}$$

Then, Proposition 5.3 and Corollary 5.4 in [47] show that condition

$$\displaystyle \begin{aligned} (C_{{L}}^{\prime }) \quad \bigcup\limits_{\lambda \in \mathbb{R} _{+}^{m}}\mathrm{epi}\left( f+\lambda g\right) ^{c}\text{ is an }\mathrm{e}\mathrm{{}^{\prime }}\text{-convex set} \end{aligned}$$

is sufficient for stable strong Lagrange duality, however not necessary, as we can see in the following example, since $\left ( C 3_{L}\right )$ does not imply $\left ( C_{{L}}^{\prime }\right ) .$

Example 4.16

Let us take n = 1, $f=\delta _{\left [ 0,+\infty \right [ },$ m = 2 and $g_{i}\left ( x\right ) =$ $\left ( i-1\right ) x+\delta _{\left ] -\infty ,i-1 \right ] }\left ( x\right ) ,$ i = 1, 2. We have $A=\left ] -\infty ,0\right ] .$ From Example 4.14, it is shown that $\left ( C3_{L}\right )$ holds, so $f+\delta _{A}=\sup \widetilde {\mathscr {E}}_{f,\delta _{A}}$ and the sets $\operatorname {epi}f^{c}+\operatorname {epi}\delta _{A}^{c}$ and $\bigcup _{\lambda \in \mathbb {R}_{+}^{2}}\operatorname {epi}(\lambda g)^{c}$ are e^′-convex in $\mathbb {R}^{4}$. Furthermore,

$$\displaystyle \begin{aligned} \operatorname{epi}f^{c}+\operatorname{epi}\delta _{A}^{c}=\mathbb{R}\times \mathbb{R} \times \mathbb{R}_{++}\times \mathbb{R}_{+}. \end{aligned}$$

We are going to see that

being, in this case,

$$\displaystyle \begin{aligned} \operatorname{e}^{\prime }\operatorname{co}\left( \bigcup\limits_{\lambda \in \mathbb{R} _{+}^{2}}\operatorname{epi}\left( f+\lambda g\right) ^{c}\right) =\operatorname{epi} \left( f+\delta _{A}\right) ^{c}=\operatorname{epi}f^{c}+\operatorname{epi}\delta _{A}^{c}. \end{aligned}$$

Let us take any $\lambda \in \mathbb {R}_{+}^{2}$. Then $\left ( y^{\ast },z^{\ast },\alpha ,\beta \right ) \in \operatorname {epi}\left ( f+\lambda g\right ) ^{c}$ if and only if

$$\displaystyle \begin{aligned} c\left( x,\left( y^{\ast },z^{\ast },\alpha \right) \right) -f\left( x\right) -\lambda g\left( x\right) \leq \beta ,\forall x\in \mathbb{R}. \end{aligned}$$

This is equivalent to the fulfilment of

$$\displaystyle \begin{aligned} \left\langle x,y^{\ast }\right\rangle -\lambda _{1}\left( \delta _{\left] -\infty ,0\right] }\left( x\right) \right) -\lambda _{2}\left( x+\delta _{-\infty ,1}\left( x\right) \right) \leq \beta \text{ and }\left\langle x,z^{\ast }\right\rangle <\alpha ,\forall x\geq 0. \end{aligned}$$

It implies, in particular, that z ^∗≤ 0, and it happens for any $\lambda \in \mathbb {R}_{+}^{2}.$ Then

4.4.4 Regularity Conditions for Fenchel–Lagrange Duality

The primal optimization problem treated in this subsection will be again (4.15)

$$\displaystyle \begin{aligned} \begin{array}{lcl} (P_{2}) \quad & \operatorname*{\mathrm{Min}}\limits_{x\in\mathbb{R}^{n}} & f(x) \\ & \text{s.t.} & g_{i}\left( x\right) \leq 0,i=1,\ldots ,m, \end{array} \end{aligned}$$

where $f,g_{i}:\mathbb {R}^{n}\rightarrow \overline {\mathbb {R}}$ , i = 1, …, m, are proper functions and the feasible set $A=\left \{ x\in \mathbb {R}^{n}:g_{i}\left ( x\right ) \leq 0,i=1,\ldots ,m\right \}$ is nonempty. In [48], using the c-conjugation scheme and the perturbation function $\varPhi _{FL}:\mathbb {R}^{n}\times \left ( \mathbb {R} ^{n}\times \mathbb {R}^{m}\right ) \rightarrow \overline {\mathbb {R}}$ defined as

$$\displaystyle \begin{aligned} \varPhi _{FL}(x,\left( u,b\right) ):=\left\{ \begin{array}{ll} f(x+u), & g_{i}\left( x\right) \leq 0,i=1,\ldots ,m, \\ +\infty , & \text{otherwise,} \end{array} \right. {} \end{aligned} $$

(4.22)

the Fenchel–Lagrange dual problem for (P ₂) was obtained:

$$\displaystyle \begin{aligned} \begin{array}{lcl} (D_{FL}) \quad & \operatorname*{\mathrm{Max}}\limits_{\lambda \in \mathbb{R}_{+}^{m}, y^{\ast}, v^{\ast} \in \mathbb{R}^{n},\alpha_1,\alpha_2\in\mathbb{R}} & \left\{ -f^{c}(x^{\ast },u^{\ast },\alpha _{1})-(\lambda g)^{c}(-x^{\ast },-u^{\ast },\alpha _{2})\right\} \\ & \text{s.t.} & \alpha_{1}+\alpha_{2}>0, \end{array} {} \end{aligned} $$

(4.23)

where $\lambda g=\left \langle \lambda ,g\left ( \cdot \right ) \right \rangle : \mathbb {R}^{n}\rightarrow \overline {\mathbb {R}}$ is defined as $\left \langle \lambda ,g\left ( \cdot \right ) \right \rangle \left ( x\right ) :=\left \langle \lambda ,g\left ( x\right ) \right \rangle$, for any $\lambda \in \mathbb {R} _{+}^{m}$. Observe that the perturbation function (4.22) is a combination of the perturbation functions (4.10) and (4.16) to build the Fenchel and the Lagrange dual problems, respectively. It is natural, then, to try to connect the regularity conditions for both dualities presented in the previous subsections in order to obtain regularity conditions for Fenchel–Lagrange duality.

We state, in the next theorem, all the studied regularity conditions for Fenchel–Lagrange duality, where $\left ( C1_{FL}\right )$ and $\left ( C2_{FL}\right )$ are the particularized versions of the general regularity conditions $\left ( C1\right )$ and $\left ( C 2\right )$ in Theorem 4.14, respectively. Moreover, two of them are characterizations. In this result, we use the set $\operatorname {gph}\left ( -g\right ) =\left \{ \left ( x,-g\left ( x\right ) \right ) \right \} \subset \mathbb {R}^{n}\times \mathbb {R} ^{m}.$ For the definition of $\widetilde {\mathscr {E}}_{f,g}$ in $\left ( C3_{F}\right )$, we recall (4.6).

In this setting, $\operatorname {epi}\varPhi _{FL}^{c}\subset Z\times Z\times \mathbb { R\times R}$ and the spaces $Z=\mathbb {R}^{n}\times \mathbb {R}^{n}\times \mathbb {R}^{m}$ , $W=\mathbb {R}^{n}\times \mathbb {R}^{n}\times \mathbb {R}$, and when we refer to the projection of $\operatorname {epi}\varPhi _{FL}^{c}$ onto $W\mathbb { \times R}$, $\operatorname {proj}\left ( \operatorname {epi}\varPhi _{FL}^{c}\right ) ,$ we mean

$$\displaystyle \begin{aligned} \operatorname{proj}\left( \operatorname{epi}\varPhi _{FL}^{c}\right) =\left\{ \begin{array}{rl} \left( x^{\ast },u^{\ast },\alpha ,\beta \right) \in W\mathbb{\times R} : & \left( x^{\ast },y^{\ast },\lambda ,u^{\ast },v^{\ast },\delta ,\alpha ,\beta \right) \in \operatorname{epi}\varPhi _{L}^{c}, \\ & \lambda ,\delta \in \mathbb{R}^{m}, y^{\ast},v^{\ast }\in \mathbb{R}^{n} \end{array} \right\} . \end{aligned}$$

Theorem 4.17 (Fenchel–Lagrange Regularity Conditions)

Let us consider the primal problem (P ₂), where f, g _i $(i=1,\ldots ,m):\mathbb {R}^{n}\rightarrow \overline {\mathbb {R}}$ are proper e-convex functions, and its Fenchel–Lagrange dual (D _FL). Any of the following conditions ensure strong duality between both problems:

• (C1FL) $0_{n+m}\in \operatorname {rint}\left ( \left ( \operatorname {dom}f\times \mathbb {R}_{+}^{m}\right ) -\operatorname {gph}\left ( -g\right ) \right ) .$

• (C2FL) $\operatorname {proj}\left ( \operatorname {epi}\varPhi _{FL}^{c}\right ) =\operatorname {epi}(f+\delta _{A})^{c}$, or, equivalently,

  $$\displaystyle \begin{aligned} \varPhi _{FL}^{c}(\cdot ,0_{n},0_{m})=\min_{\substack{ y^{\ast },v^{\ast }\in \mathbb{R}^{n} \\ \lambda ,\beta \in \mathbb{R}^{m}}}\varPhi _{FL}((\cdot ,y^{\ast },\lambda ),(\cdot ,v^{\ast },\beta ),\cdot ). \end{aligned}$$

• (C3FL) $f+\lambda g=\sup \widetilde {\mathscr {E}} _{f,\lambda g}$ for all $\lambda \in \mathbb {R}_{+}^{m}$ and the set

  $$\displaystyle \begin{aligned} \operatorname{epi}f^{c}+\bigcup_{\lambda \in \mathbb{R}_{+}^{m}}\operatorname{epi} (\lambda g)^{c} \end{aligned}$$

  is e ^′-convex, which is equivalent to saying that $\operatorname {epi} f^{c}+\bigcup _{\lambda \in \mathbb {R}_{+}^{m}}\operatorname {epi}(\lambda g)^{c}= \operatorname {epi}(f+\delta _{A})^{c}.$

Moreover, strong duality is characterized by the followings conditions:

• (C4FL) For some $\overline {\alpha }>0,$ it holds

  $$\displaystyle \begin{aligned} \operatorname{epi}(f+\delta _{A})^{c}\bigcap \left\{ (0_{n},0_{n},\overline{ \alpha })\times \mathbb{R}\right\} \subseteq \left( \operatorname{epi} f^{c}+\bigcup_{\lambda \in \mathbb{R}_{+}^{m}}\operatorname{epi}(\lambda g)^{c}\right) \bigcap \left\{ (0_{n},0_{n},\overline{\alpha })\times \mathbb{ R}\right\} , \end{aligned}$$

  where $\left \{ (0_{n},0_{n},\overline {\alpha })\times \mathbb {R}\right \} :=\left \{ (0_{n},0_{n},\overline {\alpha },\beta )\,:\,\beta \in \mathbb {R} \right \}$.

• (C5FL) For some $\overline {\lambda }\in \mathbb {R} _{+}^{m}$ and $\overline {\alpha }>0$ , it holds

  $$\displaystyle \begin{aligned} (f^{c}\square (\overline{\lambda }g)^{c})(0_{n},0_{n},\overline{\alpha } )\leq (f+\delta _{A})^{c}(0_{n},0_{n},\overline{\alpha }) \end{aligned}$$

  and $f^{c}\square (\overline {\lambda }g)^{c}$ is exact at $(0_{n},0_{n}, \overline {\alpha }).$

We study the relationships between the regularity conditions $\left ( C 2_{FL}\right )$ and $\left ( C3_{FL}\right )$. The only relation between them is stated in the next result.

Proposition 4.8 (Relation Between Fenchel–Lagrange Regularity Conditions)

If the functions f, g _i, i = 1, …, m, are e-convex and $f+\lambda g=\sup \widetilde {\mathscr {E}}_{f,\lambda g}$ for all $\lambda \in \mathbb {R}_{+}^{m}$, then (C3_FL) implies (C2_FL).

The following example shows that the converse of the above proposition does not hold in general. From this example and Theorem 4.17 we deduce that (C3_FL) is not necessary for strong Fenchel–Lagrange duality because otherwise, (C2_FL) would imply (C3_FL).

Example 4.17

Let n = 1, f = δ _]0,+∞[, m = 1 and g(x) = −x + δ _]−1,+∞[(x). Since f and g are e-convex functions, first of all we will check that $f+\lambda g=\sup \widetilde {\mathscr {E}} _{f,\lambda g}$ for any λ ≥ 0. In that case, we have (f + λg)(x) = −λx + δ _]0,+∞[(x). Identifying any e-affine function

$$\displaystyle \begin{aligned} a\left( x\right) =\left\{ \begin{array}{ll} \alpha x-\beta , & \text{ if }\gamma x<\delta , \\ +\infty , & \text{ otherwise}, \end{array} \right. \end{aligned}$$

with $a = (\alpha ,\beta ,\gamma ,\delta )\in \mathbb {R}^{4},$ we see that $\mathscr {E}_{f} = \mathbb {R}_{-}\times \mathbb {R} _{+}\times (\mathbb {R}_{-}\times \mathbb {R}_{+}\backslash \left \{ 0_{2}\right \} )$ and, since λg(x) = −λx + δ _]−1,+∞[(x), we have $\mathscr {E}_{\lambda g} = \left \{ -\lambda \right \} \times \mathbb {R}_{+}\times \left \{ 0\right \} \times \mathbb {R}_{++}$. Then,

$$\displaystyle \begin{aligned} \widetilde{\mathscr{E}}_{f,\lambda g}=]-\infty ,-\lambda ]\times \mathbb{R} _{+}\times (\mathbb{R}_{-}\times \mathbb{R}_{+}\backslash \left\{ 0_{2}\right\} ), \end{aligned}$$

and $\sup \widetilde {\mathscr {E}}_{f,\lambda g}=f+\lambda g$.

In order to show that (C2_FL) holds, and taking into account that $\operatorname {epi}(f+\delta _{A})^{c}=\operatorname {epi}f^{c}=\mathbb {R}_{-}\times ( \mathbb {R}_{-}\times \mathbb {R}_{+}\backslash \left \{ 0_{2}\right \} )\times \mathbb {R}_{+}$, it will be enough to show that

$$\displaystyle \begin{aligned} \mathbb{R}_{-}\times (\mathbb{R}_{-}\times \mathbb{R}_{+}\backslash \left\{ 0_{2}\right\} )\times \mathbb{R}_{+}\subseteq \operatorname{proj}\left( \operatorname{ epi}\varPhi _{FL}^{c}\right) . \end{aligned}$$

Let us fix $(\alpha ,\beta ,\gamma ,\delta )\in \mathbb {R}_{-}\times ( \mathbb {R}_{-}\times \mathbb {R}_{+}\backslash \left \{ 0_{2}\right \} )\times \mathbb {R}_{+}$ arbitrarily. The key is to find $\kappa ,\nu \in \mathbb {R}$ and $\lambda ,\mu \in \mathbb {R}$ such that, for all $(x,u,b)\in \operatorname {dom }\varPhi _{FL}$

$$\displaystyle \begin{aligned} \beta x+\nu u+\mu b<\gamma \ \text{and }\ \alpha x+\kappa u+\lambda b\leq \delta . {} \end{aligned} $$

(4.24)

Now, $\operatorname {dom}\varPhi _{FL}=\left \{ (x,u,b)\,:\,x+u>0,\,x>-1,\,b\geq -x\right \}$, and if we consider any sequence $\{u_{k}\}\subseteq \mathbb {R} _{++}$ converging to zero, and any b ≥ 0, $\left \{ (0,u_{k},b)\right \} \subseteq \operatorname {dom}\varPhi _{FL}$. Then, from (4.24), taking limits when k tends to + ∞, it follows that, necessarily, λ, μ ≥ 0. For every $(x,u,b)\in \operatorname {dom}\varPhi _{FL}$, if $\nu \in \mathbb {R}$ and μ ≥ 0 , βx + νu + μb ≤ (β − μ)x + νu. In the case β = 0 (let us observe that γ > 0), take μ = 0 (ν = 0), and if β < 0, take μ ≥ 0 such that β − μ < 0, and name ν = β − μ. We would have, in both cases, βx + νu + μb < γ. Proceeding in the same way with the second inequality in (4.24), we can also find κ and λ verifying it. Hence, $(\alpha ,\beta ,\gamma ,\delta )\in \operatorname {proj} \left ( \operatorname {epi}\varPhi _{FL}^{c}\right )$ and (C2_FL) is fulfilled. Finally, let us check that (C3_FL) does not hold, i.e., $\operatorname {epi}f^{c}+\bigcup _{\lambda \geq 0}\operatorname {epi}(\lambda g)^{c}\subsetneq \operatorname {epi}(f+\delta _{A})^{c}.$ Let λ ≥ 0 be arbitrary. Then, $\operatorname {epi}(\lambda g)^{c}=\left \{ (\alpha ,\beta ,\gamma ,\delta ):\alpha \leq \lambda ,\beta \leq 0,\gamma >-\beta ,\delta \geq \lambda -\alpha \right \}$ and $\cup _{\lambda \geq 0}\operatorname {epi} (\lambda g)^{c}=\mathbb {R}_{-}\times \mathbb {R}_{-}\times \mathbb {R} _{++}\times \mathbb {R}_{+}$, so that (C3_FL) is not fulfilled.

To close this subsection, let us show that (C2_FL) is not necessary for strong Fenchel–Lagrange duality either.

Example 4.18 (Example 4.15 Revisited)

Let n = 2, m = 2, $g_{1}\left ( x\right ) =x_{1}+x_{2},$ $g_{2}\left ( x\right ) =x_{1}-x_{2},$ and $f:\mathbb {R}^{2}\rightarrow \overline {\mathbb {R}}$ such that

$$\displaystyle \begin{aligned} f\left( x_{1},x_{2}\right) =\left\{ \begin{array}{ll} \frac{x_{2}^{2}}{x_{1}}, & \text{if }x_{1}>0, \\ 0, & \text{if }x_{1}=x_{2}=0, \\ +\infty , & \text{otherwise.} \end{array} \right. \end{aligned}$$

The feasible set is $A=\left \{ (x_{1},x_{2})\in \mathbb {R}^{2}\,:\,x_{1}\leq 0,\,x_{1}\leq x_{2}\right \}$ and we obtain v(P ₂) = 0. On the other hand, taking λ = 0 and $\overline {\alpha }_{1},\overline {\alpha }_{2}>0$, one has

$$\displaystyle \begin{aligned} v(D_{FL})\geq -f^{c}(0,0,\overline{\alpha }_{1})-(0g)^{c}(0,0,\overline{ \alpha }_{2})=\inf_{x\in \mathbb{R}^{2}}\left\{ f(x)\right\} =0. \end{aligned}$$

Hence, we have shown that v(D _FL) ≥ v(P ₂). Due to the weak duality, it follows that strong Fenchel–Lagrange duality holds. Now, let us see that (C2_FL) is not fulfilled. We will use its equivalent formulation which is stated in Theorem 4.17 and we will see that there exists, at least a point $(\overline {x}^{\ast },\overline {u}^{\ast },\overline { \alpha })$, such that

$$\displaystyle \begin{aligned} \varPhi _{FL}(\cdot ,0,0)^{c}(\overline{x}^{\ast },\overline{u}^{\ast }, \overline{\alpha })<\min_{\substack{ y^{\ast },v^{\ast }\in \mathbb{R} \\ \lambda ,\beta \in \mathbb{R}^{2}}}\varPhi _{FL}((\overline{x}^{\ast },y^{\ast },\lambda ),(\overline{u}^{\ast },v^{\ast },\beta ),\overline{\alpha }). \end{aligned}$$

Let any $\overline {x}^{\ast }\in \mathbb {R}^{2}$, $\overline {u}^{\ast }=(0,1)$ and $\overline {\alpha }=1$. Then, it is not difficult to see that

$$\displaystyle \begin{aligned} \varPhi _{FL}(\cdot ,0,0)^{c}(\overline{x}^{\ast },\overline{u}^{\ast }, \overline{\alpha })=\sup_{x=0_{2}}\left\{ \left\langle x,\overline{x}^{\ast }\right\rangle \right\} =0, \end{aligned}$$

and following an analogous argument to the one of Example 4.15, it follows

$$\displaystyle \begin{aligned} \min_{\substack{ y^{\ast },v^{\ast }\in \mathbb{R} \\ \lambda ,\beta \in \mathbb{R}^{2}}}\varPhi _{FL}^{c}((\overline{x}^{\ast },y^{\ast },\lambda ),( \overline{u}^{\ast },v^{\ast },\beta ),\overline{\alpha })=+\infty . \end{aligned}$$

Remark 4.4

It is easy to check that if $f+\lambda g=\sup \widetilde {\mathscr {E}} _{f,\lambda g}$ for all $\lambda \in \mathbb {R}_{+}^{m}$, (C3_FL) assures stable strong duality between (P ₂) − (D _FL). Here the extended primal and dual problems are

$$\displaystyle \begin{aligned} \begin{array}{rcl} (P_{2,x^{\ast }}) \quad &\displaystyle \operatorname*{\mathrm{Min}}\limits_{x\in\mathbb{R}^{n}} &\displaystyle f\left( x\right) +\left\langle x,x^{\ast }\right\rangle \\ &\displaystyle \text{s.t.} &\displaystyle g_{i}\left( x\right) \leq 0,i=1,\ldots ,m, \\ {} (D_{FL}) \quad &\displaystyle \operatorname*{\mathrm{Max}}\limits_{\lambda \in \mathbb{R}_{+}^{m},y^{\ast },v^{\ast }\in \mathbb{R}^{n},\alpha_1,\alpha_2\in\mathbb{R}} &\displaystyle \left\{ -\left( f+\left\langle \cdot ,x^{\ast }\right\rangle \right) ^{c}(y^{\ast },u^{\ast },\alpha _{1})-(\lambda g)^{c}(-y^{\ast },-u^{\ast },\alpha _{2})\right\} \\ &\displaystyle \text{s.t.} &\displaystyle \alpha _{1}+\alpha _{2}>0, \end{array} \end{aligned} $$

for all $x^{\ast }\in \mathbb {R}^{n}$.

4.4.5 A Comparison Between Optimal Values and Optimal Solutions

We devote this subsection to make a comparison of the optimal values of Fenchel, Lagrange and Fenchel–Lagrange dual problems for the primal problem (P ₂) in (4.15). We point out that in the case of the Fenchel dual, since the objective function in (P ₂) is F = f + δ _A, being the feasible set $A=\left \{ x\in \mathbb {R}^{n}:g_{i}\left ( x\right ) \leq 0,i=1,\ldots ,m\right \} ,$ we obtain

$$\displaystyle \begin{aligned} \begin{array}{lcl} (D_{F}) \quad & \operatorname*{\mathrm{Min}}\limits_{x^{\ast},u^{\ast} \in \mathbb{R}^{n},\alpha_1,\alpha_2\in\mathbb{R}} & \left\{ -f^{c}\left( x^{\ast },u^{\ast },\alpha _{1}\right) -\delta _{A}^{c}\left( -x^{\ast },-u^{\ast },\alpha _{2}\right) \right\} \\ & \text{s.t.} & \alpha _{1}+\alpha _{2}>0. \end{array} {} \end{aligned} $$

(4.25)

Recall that $f,g_{i}:\mathbb {R}^{n}\rightarrow \overline {\mathbb {R}}$ for all i = 1, …, m are proper functions. We assume also that the feasible set is nonempty. We will provide sufficient conditions under which the optimal value of Fenchel–Lagrange dual problem is equal, on the one hand, to the one of Fenchel dual problem and, on the other hand, to the optimal value of Lagrange dual problem. Finally, we study the relations between the optimal solutions of these three dual problems and their solvability.

First of all, we will establish the main inequalities that their optimal values satisfy as well as some examples where the inequalities are strictly fulfilled. Recall that the space $W=\mathbb {R}^{n}\times \mathbb {R} ^{n}\times \mathbb {R}.$

Theorem 4.18 (Optimal Values Relationships)

Let (D _F), (D _L) and (D _FL) be the dual problems defined in (4.25), (4.17) and (4.23), respectively. The following statements hold:

• (i) v(D _L) ≥ v(D _FL).

• (ii) v(D _F) ≥ v(D _FL).

• (iii) If $f,g_{i}:\mathbb {R}^{n}\rightarrow \overline {\mathbb {R}}$ are convex, for all i = 1, …, m, then v(D _L) = v(D _FL).

• (iv) If there exist $\overline {\alpha }>0$ and $(\left ( \overline {y} ^{\ast },\overline {v}^{\ast },\overline {\alpha }_{1}\right ) ,\overline { \alpha }_{2},\overline {\lambda })\in W\times \mathbb {R}\times \mathbb {R} _{+}^{m}$ such that $\overline {\alpha }_{1}+\overline {\alpha }_{2}=\overline { \alpha }$ and

  $$\displaystyle \begin{aligned} f^{c}(\overline{y}^{\ast },\overline{v}^{\ast },\overline{\alpha }_{1})+( \overline{\lambda }g)^{c}(-\overline{y}^{\ast },-\overline{v}^{\ast }, \overline{\alpha }_{2}) \leq \inf_{\lambda \in \mathbb{R}_{+}^{m}}\left\{ (f+\lambda g)^{c}(0_{n},0_{n},\overline{\alpha })\right\} , \end{aligned}$$

  then v(D _L) = v(D _FL).

• (v) If (ECCQ) (4.18) holds, and g _i, for all i = 1, …, m, are e-convex functions, then v(D _F) = v(D _FL).

• (vi) If there exist $\overline {\lambda }\in \mathbb {R}_{+}^{(T)}$ and $\overline {\alpha }>0$ such that $(f+\delta _{A})^{c}(0_{n},0_{n}, \overline {\alpha })=(f^{c}\square (\overline {\lambda }g)^{c})(0_{n},0_{n}, \overline {\alpha })$ and the infimal convolution is exact at $(0_{n},0_{n}, \overline {\alpha })$, then

  $$\displaystyle \begin{aligned} v(P_{2})=v(D_{L})=v(D_{F})=v(D_{FL}). \end{aligned}$$

Remark 4.5

In statement (iii), the convexity assumption on the involved functions in the primal problem cannot be removed.

Example 4.19

Let us take n = 1, f(x) = −x ², m = 1 and $g_{1}\left ( x\right ) =x^{2}.$ Clearly $A=\left \{ 0\right \}$ and

$$\displaystyle \begin{aligned} v(D_{L})=\sup_{\lambda \geq 0}\left\{ \inf_{x\in \mathbb{R}}\left\{ -x^{2}+\lambda x^{2}\right\} \right\} =0. \end{aligned}$$

On the other hand,

$$\displaystyle \begin{aligned} \begin{array}{rcl} &\displaystyle &\displaystyle v(D_{FL})=\sup_{\substack{ y^{\ast },v^{\ast }\in \mathbb{R}, \\ \alpha _{1}+\alpha _{2}>0, \\ \lambda \geq 0}}\left\{ -\sup_{x\in \mathbb{R} }\left\{ c\left( x,\left( y^{\ast },v^{\ast },\alpha _{1}\right) \right) +x^{2}\right\}\right.\\ &\displaystyle &\displaystyle \left.\qquad \qquad \quad -\sup_{x\in \mathbb{R}}\left\{ c\left( x,\left( -y^{\ast },-v^{\ast },\alpha _{2}\right) \right) -\lambda x^{2}\right\} \right\} . \end{array} \end{aligned} $$

It is clear that we can restrict ourselves to v ^∗ = 0 and α ₁, α ₂ > 0, and we get

$$\displaystyle \begin{aligned} (D_{FL})=\sup_{\substack{ y^{\ast },\in \mathbb{R}, \\ \lambda \geq 0}} \left\{ \inf_{x\in \mathbb{R}}\left\{ -xy^{\ast }-x^{2}\right\} +\inf_{x\in \mathbb{R}}\left\{ xy^{\ast }+\lambda x^{2}\right\} \right\} =-\infty . \end{aligned}$$

In the following example it is shown that condition (ECCQ) is necessary in Theorem 4.18(v), even when the involved functions in (P ₂) are e-convex.

Example 4.20

Let us take n = 2, m = 2, $g_{1}\left ( x\right ) =-x_{2},$ $g_{2}\left ( x\right ) =x_{1}-x_{2}$ and

$$\displaystyle \begin{aligned} f(x)=\left\{ \begin{array}{ll} x_{2} & \text{if }x_{1}\leq 0,\,x_{2}\in \mathbb{R}, \\[0.15cm] +\infty & \text{otherwise.} \end{array} \right. \end{aligned}$$

Firstly, let us see that f is e-convex. Naming $H=\left \{ (x_{1},x_{2},x_{3})\in \mathbb {R}^{3}:x_{3}\geq \,x_{2}\,\right \} ,$ it is easy to calculate $\operatorname {epi}f=H\cap (\operatorname {dom}f\times \mathbb {R})$. This set is clearly convex and closed, so f is e-convex. The feasible set A is

$$\displaystyle \begin{aligned} A=\left\{ (x_{1},x_{2})\in \mathbb{R}^{2}\,:\,x_{2}\geq 0,\,x_{2}\geq x_{1}\right\} . \end{aligned}$$

Hence, since $A\cap \operatorname {dom}f=\left \{ (x_{1},x_{2})\in \mathbb {R} ^{2}\,:\,x_{1}\leq 0,x_{2}\geq 0\right \}$, a simple calculation shows that v(P ₂) = 0. Now, we calculate the optimal value of the Lagrange dual problem

$$\displaystyle \begin{aligned} v(D_{L})=\sup_{\lambda _{1},\lambda _{2}\geq 0}\inf_{x\in \operatorname{dom} f}\left\{ \lambda _{1}x_{1}+\left( 1-\lambda _{1}-\lambda _{2}\right) x_{2}\right\} =-\infty . \end{aligned}$$

Since the involved functions are convex, from Theorem 4.18, we get that v(D _FL) = v(D _L) = −∞. If we compute the optimal value of the Fenchel dual problem, we have

$$\displaystyle \begin{aligned} v(D_{F})=\sup_{\substack{ y^{\ast },v^{\ast }\in \mathbb{R}^{2}, \\ \alpha _{1}+\alpha _{2}>0}}\left\{ -f^{c}(y^{\ast },v^{\ast },\alpha _{1})-(\delta _{A})^{c}(-y^{\ast },-v^{\ast },\alpha _{2})\right\} . \end{aligned}$$

It is not difficult to see that, at least, one of these c-conjugate functions equals + ∞ whenever v ^∗≠ 0₂. Analyzing the trivial case where v ^∗ = 0₂ and α ₁, α ₂ > 0, we get that f ^c(y ^∗, v ^∗, α ₁) and (δ _A)^c(−y ^∗, −v ^∗, α ₂) are finite, and

$$\displaystyle \begin{aligned} \begin{array}{rcl} v(D_{F}) &\displaystyle =&\displaystyle \sup_{\substack{ y^{\ast }\in \mathbb{R}^{2}}}\left\{ -\sup_{x\in \operatorname{dom}f}\left\{ x_{1}y_{1}^{\ast }+x_{2}y_{2}^{\ast }-x_{2}\right\} -\sup_{x\in A}\left\{ -x_{1}y_{1}^{\ast }-x_{2}y_{2}^{\ast }\right\} \right\} \\[0.15cm] &\displaystyle \geq &\displaystyle -\sup_{x\in \operatorname{dom}f}\left\{ x_{1}\cdot 0+x_{2}\cdot 1-x_{2}\right\} +\inf_{x\in A}\left\{ x_{1}\cdot 0+x_{2}\cdot 1\right\} =\inf_{x\in A}x_{2}=0. \end{array} \end{aligned} $$

We have just shown that v(D _F) ≥ 0 and, by the weak duality, v(D _F) ≤ 0, so v(D _F) = 0. To conclude this example, it remains to see that

$$\displaystyle \begin{aligned} \operatorname{epi}\delta _{A}^{c}\nsubseteq \bigcup_{\lambda \in \mathbb{R} _{+}^{2}}\operatorname{epi}(\lambda g)^{c}. {} \end{aligned} $$

(4.26)

Clearly, $((0,-1),(0,-1),1,0)\in \operatorname {epi}\delta _{A}^{c}$. However, this element does not belong to any $\operatorname {epi}(\overline {\lambda }g)^{c}$ with $\overline {\lambda }\in \mathbb {R}_{+}^{2}$ since this fact would imply the fulfilment of

$$\displaystyle \begin{aligned} c((x_{1},x_{2}),((0,-1),(0,-1),1))-(\overline{\lambda }g)(x_{1},x_{2})\leq 0, \end{aligned}$$

for all $(x_{1},x_{2})\in \operatorname {dom}\overline {\lambda }g=\mathbb {R}^{2}$, or, equivalently, $\left \langle (x_{1},x_{2}),(0,-1)\right \rangle <1,$ for all $(x_{1},x_{2})\in \operatorname {dom}(\lambda g)=\mathbb {R}^{2}$, which is not true. Therefore, (4.26) holds.

Remark 4.6

If the involved functions are proper and convex, applying Theorem 4.18, it always holds

$$\displaystyle \begin{aligned} v(D_{L})=v(D_{FL})\leq v(D_{F}), \end{aligned}$$

but without any assumption over the primal problem, v(D _L) and v(D _F) cannot be related.

It is worth studying conditions under which the solvability of one of these dual problems implies the solvability of the others.

Theorem 4.19 (Optimal Solutions Relationships)

Let (D _F), (D _L) and (D _FL) be the dual problems defined in (4.25), (4.17) and (4.23), respectively. The following statements hold:

• (i) If v(P) = v(D _FL) and $(y_{0}^{\ast },v_{0}^{\ast },\overline { \alpha }_{1},\overline {\alpha }_{2},\overline {\lambda })\in W\times \mathbb {R }\times \mathbb {R}_{+}^{m}$ is an optimal solution of (D _FL) with α ₁ + α ₂ > 0, then $\overline {\lambda }$ is optimal to (D _L), $(y_{0}^{\ast },v_{0}^{\ast },\overline {\alpha }_{1},\overline { \alpha }_{2})$ is optimal to (D _F), and

  $$\displaystyle \begin{aligned} v(P)=v(D_{L})=v(D_{F})=v(D_{FL}). \end{aligned}$$

  Then if there exists strong Fenchel–Lagrange duality, there also exist Fenchel and Lagrange strong dualities.

• (ii) If v(D _L) = v(D _F) = v(D _FL) and either (D _L) or (D _F) is not solvable, then (D _FL) is not solvable.

We finish by showing that the converse statement of Theorem 4.19(i) does not hold in general.

Example 4.21

Let us take n = 1, f = δ _[0,+∞[, m = 1 and g ₁(x) = x. Then, A =] −∞, 0] and trivially v(P) = 0. On the other hand,

$$\displaystyle \begin{aligned} v(D_{L})=\sup_{\lambda \geq 0}\left\{ \inf_{x\geq 0}\left\{ \lambda g(x)\right\} \right\} =0, \end{aligned}$$

so every λ ≥ 0 is an optimal solution of (D _L). Since f ^c(y ^∗, v ^∗, α ₁) < +∞ if and only if $(y^{\ast },v^{\ast },\alpha _{1})\in \mathbb {R}_{-}\times \mathbb {R}_{-}\times \mathbb {R}_{++}$ and its value is 0, and $\delta _{A}^{c}(-y^{\ast },-v^{\ast },\alpha _{2})<+\infty$ if and only if $(y^{\ast },v^{\ast },\alpha _{2})\in \mathbb {R}_{-}\times \mathbb {R}_{-}\times \mathbb {R}_{++}$ being its value, again, 0, it follows that v(D _F) = 0 and the solution set of (D _F) is $\mathbb {R}_{-}\times \mathbb {R}_{-}\times \mathbb { R}_{++}\times \mathbb {R}_{++}$.

Now, taking in particular $\overline {y}^{\ast }=\overline {v}^{\ast }=0$, $\overline {\alpha }_{1},\overline {\alpha }_{2}>0$ and $\overline {\lambda }=1$, which are optimal solutions of (D _F) and (D _L), respectively, we get that $f^{c}(0,0,\overline {\alpha }_{1})=0$, but

$$\displaystyle \begin{aligned} (\overline{\lambda }g)^{c}(0,0,\overline{\alpha }_{2})=\sup_{x\in \mathbb{R} }\left\{ -x\right\} =+\infty . \end{aligned}$$

Then, $(0,0,\overline {\alpha }_{1},\overline {\alpha }_{2},\overline {\lambda } )$ is not optimal to (D _FL) since, according to Theorem 4.18, v(D _FL) = v(D _L) = 0.

4.5 Bibliographic Notes

Convex and lower semicontinuous functions represent a crucial ingredient in variational analysis (see, e.g., [41]), subdifferential calculus [90, 147], conjugate duality theory and optimization [20, 149]. The Fenchel-Moreau Theorem, or the biconjugation Theorem, gives necessary and sufficient conditions for a real extended valued function to be equal to its biconjugate. This happens, in particular, if the function is proper, convex and lower semicontinuous (see [191, Th. 2.3.3]). This theorem represents a fundamental tool when we deal with duality in convex optimization, where a convex optimization problem is embedded in a family of perturbed problems, and by using Fenchel conjugation, a dual problem is associated with the primal one.

In the literature we can find good references concerning the perturbational approach to conjugate duality theory. It has been well-described in the monographs from Rockafellar [149] in the finite-dimensional context, from Ekeland and Temam [41] in Banach spaces, and from Zălinescu [191] in locally convex spaces. There exist two main classes of regularity conditions, named generalized interior-point and closedness-type conditions. In [21] it is provided an overview on some classical interior-point regularity conditions as well as several new ones, which are indeed generalized interior-point ones. In [24,25,26,27, 94, 95] the reader can find closedness-type regularity conditions for particular cases of primal and dual problems, see for instance [20] as a presentation of the state of art in this field. The mechanisms behind the closedness-type regularity conditions can be seen in [81]. Also in the general case, sufficient interior-point-type conditions for stable strong duality can be found in [191], while it is characterized by a much more general closedness-type condition in [27].

Evenly convex functions, introduced in [151], extend in a natural way the concept of evenly convex set to functions, and also allow a generalization of the convex and lower semicontinuous functions class. Although Fenchel conjugation theory is not suitable for evenly convex functions, in the sense that different evenly convex functions may have the same lower semicontinuous hull and hence identical second conjugates, we have described in this chapter different conjugation schemes fulfilling that, in the case of an evenly convex function, the second conjugate is identical to the original function. Thus, invoking to the c-conjugation scheme in particular, a perturbational duality theory for evenly convex optimization problems has been developed by Fajardo and her co-authors [45,46,47,48,49], while regularity conditions for strong duality based on even convexity are given in [43, 45, 46, 48, 49, 181].

This chapter is based on [43, 45, 48, 49, 126, 151, 181, 184]. Evenly convex functions definition, properties and examples in Sect. 4.1 can be found almost entirely in [151]: statements (i) and (ii) of Theorem 4.1 are [151, Th. 2.6] and [151, Prop. 2.7], respectively, Theorem 4.2 and Corollary 4.1 correspond to [151, Th. 2.9] and [151, Cor. 2.10], respectively. For Proposition 4.1 see [151, Prop. 2.12], while operations with evenly convex functions in Theorem 4.3 are stated in [151, Sec. 3].

Results in Sect. 4.2 on the e-convex hull of a given function can be found in [126, 151, 181]. The representation for the e-convex hull of a function f in (4.5) was proved for the first time in [151, Prop. 3.10] and it still remains true if the set $\operatorname {epi}f$ is replaced by $\operatorname {epi}_{s}f$, or even by any set A such that $\operatorname {epi}_{s}f\subset A\subset \operatorname {epi}f$. More precisely, Theorem 4.4 is [181, Prop. 2.3 and Cor. 2.4], Theorem 4.5 is [181, Prop. 2.6 and Cor. 2.7], Theorems 4.6 and 4.7 are taken from [151], Theorem 4.8 is [126, Th. 16], and finally, Corollary 4.2 encompasses [126, Cors. 18 and 19].

Section 4.3 is devoted to three possible conjugation schemes for evenly convex functions, depending on the chosen coupling functions, and the notion of subdifferentibility associated to one of these schemes. It is based on [46, 126, 184]. On the one hand, regarding the conjugation patterns, the first approach is taken from [46, 126], whereas the details to the second and the third approaches can be found in [184]. On the other hand, c-subdifferentiability is described in [126]. Regarding the precise references for the given results in this section, Theorem 4.9 is [46, Prop. 2], Theorem 4.10 encompasses [184, Props. 4.2, 5.2 and Cor. 5.1] while the key tool (4.4) is proved in [184, Prop. 4.1], and Theorem 4.11 is [184, Th. 6.1 and Cor. 6.1]. In addition to that, Proposition 4.2 is [126, Prop. 45], Proposition 4.3 is [181, Th. 3.1], Corollary 4.3 is [181, Cor. 3.2], Proposition 4.4 is [181, Prop. 3.4], and finally, Theorem 4.12 is [181, Th. 4.1]. Readers who are familiar with the classical concept of subdifferentiability and its relationship with Fenchel conjugation will find that the three statements given in Theorem 4.13 are generalizations of well-known formulas (see, e.g., [20]). Statement (i) in that theorem is [46, Lem. 9], while (ii) is [46, Th. 11] and (iii) is [46, Cor. 12].

Section 4.4 is divided into five subsections, corresponding to the following objectives. Section 4.4.1 is devoted to regularity conditions for general optimization problems and duals obtained via perturbational approach and by means of c-conjugation, and is based mostly on [43], where the general optimization problem framework does not have any restrictions about dimensionality, and the involved spaces are Hausdorff locally convex. Actually the Fenchel dual problem and the regularity conditions were obtained in the particular case of g being an indicator function of any subset, but all the results can be generalized easily to any function g. It is necessary to point out that the regularity condition (C1) in Theorem 4.5 is expressed in terms of the relative algebraic interior of certain projection of $\operatorname {dom}\varPhi$. Theorem 4.5 is proved in [43, Prop. 4.3]. This result can be derived as a particular case in [124, Prop. 6.4, Th. 6.7 and Cor. 6.2], because the dual problem with u ₀ = 0 suggested by Martínez-Legaz is equivalent to $\left ( GD_{c}\right )$, as it is shown in [46]. The general regularity conditions in Theorem 4.14 are stated in [43, Prop. 4.5] and [43, Props. 5.4 and 5.5], respectively.

The topic in Sect. 4.4.2 is Fenchel duality, obtaining regularity conditions and comparing them. Most results there can be found in [43, Section 6]. Condition $\left ( C3_{F}\right )$ in Theorem 4.15 is studied in detail in [46, Section 5], and strong duality characterization $\left ( C4_{F}\right )$ is discussed in [47, Lem. 4.3]. This characterization was motivated by [109], where, in the classical setting, strong Fenchel duality is equivalent to the following inequality, which is called (FRC)_A,

$$\displaystyle \begin{aligned} \left( f+g\circ A\right) ^{\ast }\left( 0\right) \geq \left( f^{\ast }\square A^{\ast }g^{\ast }\right) \left( 0\right) , \end{aligned}$$

together with the exactness of the infimal convolution at the point 0. In that paper, X and Y  are assumed to be Hausdorff locally convex spaces, A : X → Y  is a linear operator and $f:X\rightarrow \overline {\mathbb {R}}$ and $g:Y\rightarrow \overline {\mathbb {R}}$ are proper convex functions such that $A(\operatorname {dom}f)\cap \operatorname {dom}g\neq \emptyset$. Finally, the relationships between regularity conditions in Proposition 4.6 are established in [43, Props. 6.3 and 6.5].

Section 4.4.3 develops an analogous study for Lagrange duality, with a similar structure than in the previous subsection. It is based mostly on [45], where the primal problem is stated in an infinite-dimensional framework and the number of constraints is arbitrary. The calculus of the e^′-convex hull of $\bigcup _{\lambda \in \mathbb {R}_{+}^{m}}\left ( \lambda g\right ) ^{c}$ is computed in [45, Prop. 4.1], which allows formula (4.18). The general regularity condition (C1_L) in Lagrange duality Theorem 4.16 is provided in [45, Prop. 5.1], while $\left ( C3_{L}\right ) ,$ $\left ( C4_{L}\right )$ and their equivalence can be found in [45, Prop. 4.2 and Th. 4.1]. The comparison between regularity conditions in Proposition 4.7 is stated in [45, Prop. 5.2].

Regarding Fenchel–Lagrange duality, Sect. 4.4.4 follows the same scheme as Sects. 4.4.2 and 4.4.3. All the results can be found in [49], in a more general framework with infinite dimensional spaces and an arbitrary number of constraints in the primal problem. The regularity condition $\left ( C3_{FL}\right )$ from Theorem 4.17 is proved in [49, Prop. 3.4], and it was motivated by the regularity condition (ECCQ) in (4.18). Actually, it is a direct generalization of a regularity condition from the closed convex case; see $\left ( CQ^{FL}\right )$ in [22]. On the other hand, strong duality characterizations $\left ( C4_{FL}\right )$ and $\left ( C 5_{FL}\right )$ can be found in [49, Prop. 3.1], and the comparison between regularity conditions in Proposition 4.8 is provided in [49, Prop. 4.1]. It is worth to remark that in the infinite dimensional case, (i) in Proposition 4.8 is not enough for the equality between optimal values v(D _L) and v(D _FL). We also need that $\operatorname {int}(\operatorname {epi}f) \neq \emptyset$, as it is pointed out in [49, Rem. 4.2 and Ex. 4.3].

The last subsection within Sect. 4.4 extends what Boţ and Wanka obtained in [23], where they compared the three dual problems on finite-dimensional spaces having a finite number of constraints and dealing with the classical Fenchel conjugation scheme. In our setting we also deal with a finite number of inequalities, but work with the c-conjugation pattern. The relations between optimal values in Theorem 4.18 can be found, in a more general setting, with an arbitrary number of constraints and within Hausdorff locally convex spaces, in the following references from [48]: (i), (iii) and (iv) in Proposition 4.1, (ii) in Proposition 4.5, (v) in Proposition 4.6 and (vi) in Proposition 5.1. Finally, Theorem 4.19 is stated in Theorems 5.3 and 5.5.

For readers who could be interested in evenly convex optimization, a very recent work [44] deals with converse and total duality, situations where, in the first case, there is no duality gap and the primal problem is solvable, and, in the second case, strong and converse duality hold together. Total duality is characterized by means of the saddle-point theory approach. Furthermore, one can find there formulae for the c-subdifferential and biconjugate of the objective function in a general optimization problem.