Duality theory for optimistic bilevel optimization

Houria En-Naciri111Laboratoire LASMA, Department of Mathematics, Sidi Mohammed
Ben Abdellah University, Morocco (email<EMAIL_ADDRESS>Lahoussine Lafhim222Laboratoire LASMA, Department of Mathematics, Sidi
Mohammed Ben Abdellah University, Morocco (email:
<EMAIL_ADDRESS>Alain Zemkoho333School of Mathematical
Sciences, University of Southampton, UK (email: a.b.zemkoho@soton.ac.uk). This
author’s work is supported by the EPSRC grant EP/V049038/1 and the Alan Turing
Institute under the EPSRC grant EP/N510129/1

Abstract: In this paper, we exploit the so-called value function reformulation
of the bilevel optimization problem to develop duality results for the
problem. Our approach builds on Fenchel-Lagrange-type duality to establish
suitable results for the bilevel optimization problem. First, we overview some
standard duality results to show that they are not applicable to our problem.
Secondly, via the concept of partial calmness, we establish weak and strong
duality results. In particular, Lagrange, Fenchel-Lagrange, and Toland-
Fenchel-Lagrange duality concepts are investigated for this type of problems
under some suitable conditions. Thirdly, based on the use of some
regularization of our bilevel program, we establish sufficient conditions
ensuring strong duality results under a generalized Slater-type condition
without convexity assumptions and without the partial calmness condition.
Finally, without the Slater condition, a strong duality result is constructed
for the bilevel optimization problem with geometric constraint.

Keywords: optimistic bilevel optimization, lower level value function
reformulation, duality theory
Mathematics Subject Classification 2020: 90C46, 90C26, 90C31

##  1 Introduction

In this paper, we are concerned with the following standard optimistic bilevel
programming problem

${\displaystyle\min_{x,y}}\ F(x,y)\;\;\mbox{s.t.}\;\;G_{i}\left(x,y\right)\leq
0,\;\;i\in I_{k},\;\;y\in\mathcal{S}(x),$ (P)

where, for each $x\in\mathbb{R}^{n}$, $\mathcal{S}(x)$ represents the optimal
solution set of the lower level problem

${\displaystyle\min_{y}}\ f(x,y)\;\;\mbox{ s.t. }\;\;y\in K\left(x\right),$
(L[$x$])

$F:\mathbb{R}^{n}\times\mathbb{R}^{m}\rightarrow\mathbb{R}\cup\\{+\infty\\}$
and
$f:\mathbb{R}^{n}\times\mathbb{R}^{m}\rightarrow\mathbb{R}\cup\\{+\infty\\}$
are the upper and lower level objective functions, while
$G_{i}:\mathbb{R}^{n}\times\mathbb{R}^{m}\rightarrow\mathbb{R}\cup\\{+\infty\\}$
for $i\in I_{k}:=\\{1,\ldots,k\\}$ ($k\in\mathbb{N}\setminus\\{0\\}$) denotes
the upper level constraint functions. Throughout the paper, we confine
ourselves to the case where the lower level feasible set is defined, for all
$x\in\mathbb{R}^{n}$, by

$K(x):=\left\\{y\in\mathbb{R}^{m}\mid g_{j}(x,y)\leq 0,\;\;j\in
I_{p}:=\\{1,\cdots,p\\}\right\\}$

with
$g_{j}:\mathbb{R}^{n}\times\mathbb{R}^{m}\rightarrow\mathbb{R}\cup\\{+\infty\\}$
for $j=1,\ldots,p$ ($p\in\mathbb{N}\setminus\\{0\\}$). The objective functions
$F$ and $f$, as well as the constraint functions $G_{i}$ for $i=1,\ldots,k$
and $g_{j}$ for $j=1,\ldots,p$, are assumed to be proper convex functions. In
the sequel, from [24], we adopt the following standard operations involving
$+\infty$ and $-\infty$:

$\begin{array}[]{rll}\left(+\infty\right)-\left(+\infty\right)=\left(-\infty\right)-\left(-\infty\right)=\left(+\infty\right)+\left(-\infty\right)=\left(-\infty\right)+\left(+\infty\right)&=&+\infty,\\\
0\cdot\left(+\infty\right)&=&+\infty,\\\
0\cdot\left(-\infty\right)&=&0.\end{array}$

Our main goal in this paper is to study the duality theory for the bilevel
optimization problem (P), which corresponds to the optimistic version of the
problem; more details on bilevel optimization and related properties can be
found in [11, 13], where surveys on different classes on the problem,
including the pessimistic version, are also given.

The literature on duality theory for general optimization problems is very
rich. For example, strong duality for nearly convex optimization problems is
established by BoŢ and Wanka [7], where three kinds of conjugate dual problems
are devoted to the primal optimization problem; i.e., the Lagrange, Fenchel,
and Fenchel-Lagrange dual problems. Also, Martínez-Legaz and Volle [18]
introduced in particular a duality scheme for the problem of minimizing the
difference of two extended real-valued convex functions (i.e., d.c. functions
for short) under finitely many d.c. constraints in terms of the Legendre-
Fenchel conjugates of the involved convex functions. Another related
interesting problem in conjugate duality theory developed by Rockafellar (see
[19] and [14]) is the well-known perturbational approach, consisting in the
use of a perturbation function as the keystone to obtain a dual problem for a
general primal one by means of the Fenchel conjugation. Both problems satisfy
weak duality (in the sense that the optimal value of the dual problem is less
than or equal to the optimal value of the primal one), as a direct consequence
of the Fenchel–Young inequality, whereas conditions ensuring strong duality
(no duality gap and dual problem solvable) can be found in these references
and many other ones in the literature.

However, only a small number of papers have been dedicated to duality theory
for bilevel optimization problems. In [2], Aboussoror and Adly adapted the
Fenchel–Lagrange duality, which has been first introduced by Boţ and Wanka in
[8] and tailored to convex programming problems, showing that a strong duality
result holds between a bilevel nonlinear optimization problem with extremal-
value function and its Fenchel-Lagrange dual under appropriate assumptions.
Afterwards, a duality approach for the strong bilevel programming problem (P)
via a regularization and the Fenchel-Lagrange duality was presented by
Aboussoror, Adly and Saissi in [3]. More precisely, using
$\varepsilon-$approximate solutions of the lower level problem, they consider
a regularized problem (Pϵ) of (P). Via this regularization and the operation
of scalarization they present in [1], a duality approach using conjugacy for a
semivectorial bilevel programming problem with the upper and lower levels
being vectorial and scalar respectively, are proposed.

In this paper, we overview the literature to construct appropriate duality
results for bilevel optimization problems, including Fenchel, Lagrange-
Fenchel, and Toland-Lagrange-based techniques. Clearly, the aim of this paper
is two-fold. We explore standard duality results from the literature and show
their limitations, in terms of their applicability to the bilevel optimization
problem. Secondly, we explore a number of approaches to develop tractable
approaches to obtain duality results for the bilevel optimization problem. In
the latter case, we first use an exact penalization of problem (P) based on
the well-know concept of partial calmness (see [23]) to completely
characterize Fenchel-Lagrange-type results. The key to this exact penalization
is that the resulting problem can be viewed as a minimization problem of a
d.c. objective function under convex constraints. Note that the technique used
to get such a transformation is inspired by the work of [6, 18], and conjugacy
is the main tool involved in this technique. The results are obtained under
the Slater constraint qualification and further regularity conditions and some
closedness conditions. Additionally, based on the use of a regularization of
problem (P), we establish sufficient conditions ensuring strong duality
results under a generalized Slater-type condition without convexity
assumptions and without the partial calmness condition. Finally, without any
Slater-type condition, strong duality results are investigated for the bilevel
optimization problem with geometric constraint.

In next section, we first recall some definitions of convex analysis tools
needed in this work. The preliminaries are mainly concerned with relevant
properties of the subdifferential, also of the epigraph and some conjugate
properties of convex functions. In Section $3$, we collect some existing
results while showing their limitations for our program. In Section $4$, we
investigate duality theory for problem (P) using the partial calmness under
some appropriate conditions. Subsequently, we completely characterize the
strong duality for problem (P) in the presence of partial calmness. In Section
$5$ however, in the absence of partial calmness, but under a generalized
Slater constraint qualification, we provide a strong duality for the nonconvex
bilevel optimization problem (P). Then, the special case where the bilevel
problem is geometrically constrained is also studied. Finally, we conclude our
work in Section $6$.

##  2 Preliminaries

Here, we recall some fundamental definitions and results essentially related
to convex mappings. To proceed, let $D$ be a subset of $\mathbb{R}^{n}$. The
sets $intD$, $clD$ and $coD$, stand for the topological interior, the closure
and the convex hull of $D$, respectively. Moreover, the convex cone
(containing the origin of $\mathbb{R}^{n}$) generated by $D$ is denoted by
$coneD$, and its closure is $\overline{cone}D$, the positive polar cone of $D$
is given by

$D^{\circ}=\left\\{x^{*}\in\mathbb{R}^{n}:\left\langle
x^{*},x\right\rangle\geqslant 0,\ \forall x\in D\right\\},$

while the indicator function
$\delta_{D}:\mathbb{R}^{n}\rightarrow\mathbb{R}\cup\\{+\infty\\}$ of $D$ is
defined by

$\delta_{D}(x)=\left\\{\begin{array}[]{ll}0,&\text{ if }x\in D,\\\
+\infty,&\text{ if }x\notin D.\end{array}\right.$

Additionally, the support function
$\sigma_{D}:\mathbb{R}^{n}\rightarrow\bar{\mathbb{R}}=\mathbb{R}\cup\\{-\infty\\}\cup\\{+\infty\\}$
of $D$ is

$\sigma_{D}\left(x^{*}\right)=\sup_{x\in D}\left\langle x^{*},x\right\rangle.$

For the optimization problem (P) we denote by
${\mathcal{V}}\left(\ref{calm0}\right)$ its optimal objective value and this
notation is extended to the optimization problems that we use in this paper.

For a given extend real valued function
$f:\mathbb{R}^{n}\rightarrow\bar{\mathbb{R}}$, the epigraph, the lower
semicontinuous hull, and the effective domain of $f$ are respectively defined
by

$\begin{array}[]{rll}\operatorname{epi}f&=&\left\\{(x,r)\in\mathbb{R}^{n}\times\mathbb{R}\mid
f(x)\leqslant r\right\\},\\\\[3.44444pt]
\operatorname{epi}(\operatorname{cl}f)&=&\operatorname{cl}(\operatorname{epi}f),\\\\[3.44444pt]
\operatorname{dom}f&=&\left\\{x\in\mathbb{R}^{n}\mid
f(x)<+\infty\right\\}.\end{array}$

We say that $f$ is proper if $f(x)>-\infty$ for all $x\in\mathbb{R}^{n}$, and
$\operatorname{dom}f\neq\emptyset$.

######  Definition 2.1.

Let $f:\mathbb{R}^{n}\rightarrow\bar{\mathbb{R}}$ be a function, and $D$ a
nonempty subset of $\mathbb{R}^{n}$. The conjugate function of $f$ relative to
the set $D$ is denoted by $f_{D}^{*}$ and defined on $\mathbb{R}^{n}$ by

$f_{D}^{*}(p)=\sup_{x\in D}\left\\{\langle p,x\rangle-f(x)\right\\},$

where $\langle.,.\rangle$, denotes the inner product of two vectors in
$\mathbb{R}^{n}$, i.e., for given $x=\left(x_{1},\ldots,x_{n}\right)^{T}$ and
$y=\left(y_{1},\ldots,y_{n}\right)^{T}$, we have $\langle
x,y\rangle=\displaystyle\sum_{i=1}^{n}x_{i}y_{i}.$ When $D=\mathbb{R}^{n},$ we
get the usual Legendre-Fenchel conjugate function of $f$ denoted by $f^{*}$.

Let $D\subset\mathbb{R}^{n}$ and $\bar{x}\in clD$. The contingent cone to $D$
at $\bar{x}$ is the set

$T\left(\bar{x},D\right)=\left\\{y\in\mathbb{R}^{n}\mid\exists t_{k}\downarrow
0,\exists y_{k}\rightarrow y,\bar{x}+t_{k}y_{k}\in D\ \forall
k\in\mathbb{N}\right\\}.$

######  Definition 2.2.

Let $f:\mathbb{R}^{n}\rightarrow\mathbb{R}\cup\\{+\infty\\}$ be a proper
convex function and $\bar{x}\in\operatorname{dom}f$. The subdifferential in
the sense of convex analysis of $f$ at $\bar{x}$ denoted by $\partial
f(\bar{x})$ is the set

$\partial f(\bar{x})=\left\\{x^{*}\in\mathbb{R}^{n}\mid f(x)\geq
f(\bar{x})+\left\langle x^{*},x-\bar{x}\right\rangle\ \forall
x\in\mathbb{R}^{n}\right\\}.$

An element $x^{*}\in\partial f(\bar{x})$ is called a subgradient of $f$ at
$\bar{x}$.

######  Remark 2.3.

Let $f:\mathbb{R}^{n}\rightarrow\mathbb{R}\cup\\{+\infty\\}$. Then, the
following assertions hold:

  * (i)

$x^{*}\in\partial f(\bar{x})\ \text{if and only if}\ \left\langle
x^{*},\bar{x}\right\rangle=f(\bar{x})+f^{*}\left(x^{*}\right)$;

  * (ii)

$f(x)+f^{*}\left(x^{*}\right)\geq\left\langle x^{*},x\right\rangle\ \ \
\forall x,x^{*}\in\mathbb{R}^{n}$ (the Young-Fenchel inequality);

  * (iii)

If $\operatorname{cl}f$ is proper and convex, then it holds that
$f^{**}=\operatorname{cl}f$.

######  Proposition 2.4.

Let $f_{1},\ldots,f_{k}:\mathbb{R}^{n}\rightarrow\mathbb{R}\cup\\{+\infty\\}$
be proper convex functions. If the set
$\displaystyle\bigcap_{i=1}^{k}\operatorname{ri}\left(\operatorname{dom}\left(f_{i}\right)\right)$
is nonempty, then

$\left(\sum_{i=1}^{k}f_{i}\right)^{*}(p)=\left(f_{1}^{*}\square\ldots\square
f_{k}^{*}\right)(p),$

where for a nonempty subset $B$ of $\mathbb{R}^{n}$, $\text{ri}B$ denotes the
relative interior of $B$, i.e., the interior of $B$ relative to the smallest
affine set containing $B$, and

$\left(f_{1}^{*}\square\ldots\square
f_{k}^{*}\right)(p):=\inf\left\\{\sum_{i=1}^{k}f_{i}^{*}\left(p_{i}\right):p=\sum_{i=1}^{k}p_{i}\right\\}$

is the infimal convolution of $f_{1}^{*},\ldots,f_{k}^{*}$, and for each
$p\in\mathbb{R}^{n}$ the infimum is attained.

######  Proposition 2.5.

Let $I$ be an index set, and let $\left\\{f_{i}:i\in I\right\\}$ be a family
of proper convex functions, where
$f_{i}:\mathbb{R}^{n}\rightarrow\mathbb{R}\cup\\{+\infty\\}$. Then the
following statements hold:

  * (i)

$\operatorname{epi}\left(\underset{i\in
I}{\sup}f_{i}\right)=\displaystyle\underset{i\in
I}{\bigcap}\operatorname{epi}f_{i}$;

  * (ii)

$\left(\underset{i\in I}{\inf}f_{i}\right)^{*}=\underset{i\in
I}{\sup}f_{i}^{*}$ and hence, $\operatorname{epi}\left(\underset{i\in
I}{\inf}f_{i}\right)^{*}=\displaystyle\underset{i\in
I}{\bigcap}\operatorname{epi}f_{i}^{*}$;

  * (iii)

If the set $I$ is finite and
$\displaystyle\bigcap_{i=1}^{k}\operatorname{ri}\left(\operatorname{dom}\left(f_{i}\right)\right)$
is nonempty, then

$\operatorname{epi}\left(\left(\sum_{i=1}^{k}f_{i}\right)^{*}\right)=\sum_{i=1}^{k}\operatorname{epi}\left(f_{i}^{*}\right).$

Finally, any point $p\in\mathbb{R}^{n}$ can be considered as a function on
$\mathbb{R}^{n}$ in such a way that $p(x):=\langle p,x\rangle$, for any
$x\in\mathbb{R}^{n}.$ Thus, for any $\alpha\in\mathbb{R}$ and any function
$h:\mathbb{R}^{n}\rightarrow\bar{R}$,

$\left(h+p+\alpha\right)^{\ast}\left(x^{\ast}\right)=h^{\ast}\left(x^{\ast}-p\right)-\alpha,\
\ \text{for all}\ x^{\ast}\in\mathbb{R}^{n}$

and

$\operatorname{epi}(h+p+\alpha)^{*}=\operatorname{epi}h^{*}+(p,-\alpha).$

For convenience, let $\theta\in\mathbb{R}^{m}$ and
$M:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$, the composition mapping
$\theta\circ K$ will be denoted by $\theta M$.

##  3 Limitations of some existing theory

Consider the following lower level value reformulation of the bilevel
optimization problem (P) under consideration:

$\left\\{\begin{array}[]{ll}{\displaystyle\min_{x,y}}\ F(x,y)\\\
G_{i}(x,y)\leq 0&\forall i\in I_{k}=\\{1,\dots,k\\},\\\ g_{j}(x,y)\leq
0&\forall j\in I_{p}=\\{1,\dots,p\\},\\\ f(x,y)-\varphi(x)\leq
0,\end{array}\right.$ (LLVF)

where $\varphi$ denotes the optimal value function of the lower level problem
(L[$x$]):

$\varphi(x):=\underset{y}{\min}~{}\left\\{f(x,y)|\;\;y\in K(x)\right\\}.$

###  3.1 Convex optimization with only inequality constraints

In this subsection, we review some duality results for the mathematical
programming problem

$\min\\{\phi\left(x\right)|\;\psi\left(x\right)\leq 0\\}$ (Pin)

with $\phi:\mathbb{R}^{n}\rightarrow\mathbb{R}$ and
$\psi=\left(\psi_{1},\cdots,\psi_{p}\right)^{T}:\mathbb{R}^{n}\rightarrow\mathbb{R}^{r}$,
where $\psi\left(x\right)\leq 0$ means that $\psi_{i}\left(x\right)\leq 0$ for
all $i\in I_{r}=\\{1,\cdots,r\\}$. To define the dual problem of (Pin), Bot et
al. [8] considered a perturbation by using the following perturbation
function:

$\Phi\left(x,\alpha,\beta\right)=\left\\{\begin{array}[]{lcl}\phi\left(x+\alpha\right)&&\text{if}\
\psi\left(x\right)\leq\beta,\\\ +\infty&&\text{otherwise}.\end{array}\right.$

Afterwards, they calculate the conjugate of $\Phi$ and obtained the following
Fenchel-Lagrange dual problem

${\displaystyle\sup_{\alpha^{\ast}\in\mathbb{R}^{n},\
\beta^{\ast}\in\mathbb{R}_{+}^{r}}}\
\bigg{\\{}-\phi^{\ast}\left(\alpha^{\ast}\right)+{\displaystyle\inf_{x\in\mathbb{R}^{n}}}\
\left[\langle\alpha^{\ast},x\rangle+\langle\beta^{\ast},\psi\left(x\right)\rangle\right]\bigg{\\}}.$
(Din)

In general, to deal with strong duality which charaterizes (Pin), we need to
use a Slater-type constraint qualification.

######  Definition 3.1.

We say that the genaralized Slater constraint qualification holds for the
familly $\left(\psi_{i}\right)_{i\in I_{r}}$ if there exist an element
$\bar{x}\in\mathbb{R}^{n}$ such that $\psi_{i}\left(\bar{x}\right)<0$ for
$i\in N$ and $\psi_{i}\left(\bar{x}\right)\leq 0$ for $i\in L$, where $N$ and
$L$ are respectively given as

$\begin{array}[]{ll}N=\\{i\in I_{r}\ |&\text{such that}\ \psi_{i}\ \text{is
not an affine function}\\},\\\ L=\\{i\in I_{r}\ |&\text{such that}\ \psi_{i}\
\text{is an affine function}\\}.\end{array}$

######  Theorem 3.2 ([8]).

Let $\phi$ and $\psi_{i}$, with $i\in I_{r}$ be convex functions. Assume that
the genaralized Slater constraint qualification holds for the familly
$\left(\psi_{i}\right)_{i\in I_{r}}$. If ${\mathcal{V}}\eqref{w-o-ineq}$ is
finite, then strong duality holds and ${\mathcal{V}}\eqref{w-o-
ineq}={\mathcal{V}}\eqref{w-o-ineq-dual}$.

Note that in [8] the Slater constraint qualification is used as a sufficient
condition to establish strong Fenchel-Lagrange duality. Unfortunately, due to
the presence of $f(x,y)-\varphi(x)$ as a constraint, problem (LLVF)does not
satisfy the Slater constraint qualification. Moreover, problem (LLVF)is not
convex, even if the data are convex. Hence, Theorem 3.2 is not applicable for
problem (LLVF). However, there is a chance that some of these requirements can
hold for the simple bilevel optimization problem (see, e.g., [21]), where the
lower level problem is an unperturbed optimization problem.

###  3.2 Convex optimization with inequality and equality constraints

Next, we add some equality constraints to problem (Pin) to get the following
primal optimization problem with equality constraints

$\min\\{\phi\left(x\right)\ |\ \psi\left(x\right)\leq 0,\ \
\omega\left(x\right)=0\\},$ (Peq)

where $\omega:\mathbb{R}^{n}\rightarrow\mathbb{R}^{q}$ is an affine-linear
mapping and $\phi:\mathbb{R}^{n}\rightarrow\mathbb{R}$ and
$\psi:\mathbb{R}^{n}\rightarrow\mathbb{R}^{r}$ are two functions such that the
function
$\left(\phi,\psi\right):\mathbb{R}^{n}\rightarrow\mathbb{R}\times\mathbb{R}^{r}$
defined by
$\left(\phi,\psi\right)\left(x\right)=\left(\phi\left(x\right),\psi\left(x\right)\right)$
is convex-like with respect to the cone
$\mathbb{R}_{+}\times\mathbb{R}_{+}^{r}$; that is, the set
$\left(\phi,\psi\right)\left(\mathbb{R}^{n}\right)+\left(\mathbb{R}_{+}\times\mathbb{R}_{+}^{r}\right)$
is convex. The Lagrange dual (Deq) of (Peq) is defined as

${\displaystyle\sup_{\beta^{\ast}\in\mathbb{R}_{+}^{r},\
\gamma^{\ast}\in\mathbb{R}^{q}}}\ {\displaystyle\inf_{x\in\mathbb{R}^{n}}}\
\bigg{\\{}\phi\left(x\right)+\langle\beta^{\ast},\psi\left(x\right)\rangle+\langle\gamma^{\ast},\omega\left(x\right)\rangle\bigg{\\}}.$
(Deq)

In [4], Bot et al. provide a strong duality theorem for (Peq) and its Lagrange
dual problem by using some regularity conditions expressed by means of the
contingent cone. More precisely, they work under the assumption that $\bar{x}$
is an optimal solution of the primal problem (Peq). To clarify their concept,
let us introduce the following sets:

$\begin{array}[]{lcl}\Sigma&=&\\{x\in\mathbb{R}^{n}\ |\ \psi\left(x\right)\leq
0,\ \ \omega\left(x\right)=0\\},\\\
{\mathcal{E}}&=&\left(\phi\left(\bar{x}\right)-\phi\left(x\right)-\sigma,-\psi\left(x\right)-z,-\omega\left(x\right)\right)\
|\ x\in\mathbb{R}^{n},\sigma\geq 0,\ z\in\mathbb{R}_{+}^{r}\\}.\end{array}$

We arrive now to the strong duality theorem stated in the latter reference.

######  Theorem 3.3.

If $\bar{x}$ is an optimal solution for (Peq), the following assertions are
equivalent

  1. 1.

The equality
$T_{\mathcal{E}}\left(0,0_{\mathbb{R}^{r}},0_{\mathbb{R}^{q}}\right)\bigcap\left(\mathbb{R}_{+}^{\ast}\times
0_{\mathbb{R}^{r}}\times 0_{\mathbb{R}^{q}}\right)=\emptyset$ holds;

  2. 2.

${\mathcal{V}}\eqref{w-o-eq}={\mathcal{V}}\eqref{w-o-eq-dual}$ and there
exists a point
$(\bar{\beta},\bar{\gamma})\in\mathbb{R}_{+}^{r}\times\mathbb{R}^{q}$ that
solves problem (Deq).

In this case, we have $\langle\bar{\beta},\psi\left(\bar{x}\right)\rangle=0$.

We now analyze the applicability of this theorem to our bilevel program (P).
To proceed, we consider the classical optimistic bilevel programming problem
with linear lower level problem

$\left\\{\begin{array}[]{ll}{\displaystyle\min_{x,y}}\ F(x,y)\\\
G_{i}(x,y)\leq 0\quad\forall i\in I_{k}=\\{1,\dots,k\\},\\\ y\in
S\left(x\right)=\arg\underset{y}{\min}~{}\left\\{C^{T}y\,|\;\;Ax+By\leq
d\right\\},\end{array}\right.$ (3.1)

where $d\in\mathbb{R}^{r}$, $C\in\mathbb{R}^{m}$,
$A\in\mathbb{R}^{r}\times\mathbb{R}^{n}$ and
$B\in\mathbb{R}^{r}\times\mathbb{R}^{m}$. Its lower level value function
reformulation can be written as

${\displaystyle\min_{x,y}}\ F(x,y)\ :\ G_{i}(x,y)\leq 0\quad\forall i\in
I_{k}=\\{1,\dots,k\\},\ Ax+By\leq d,\ C^{T}y-\varphi\left(x\right)=0,$

where the lower-level value function $\varphi$ is given by

$\varphi\left(x\right)={\displaystyle\min_{y}}\ \\{C^{T}y\,|\;\;Ax+By\leq
d\\}.$

In general, even if the lower level problem is fully affine linear (i.e., in
$(x,y)$), as it is the case here, the optimal value function $\varphi$ is not
linear. This function is typically only be piecewise linear. Consequently,
Theorem 3.3 will rarely be applicable to a problem of the form (3.1).

###  3.3 Nonconvex optimization with inequality and equality constraints

Now, we do not assume that (Peq) has a solution, also no convexity assumption
is imposed. Let us consider the Lagrangian

$L\left(\varsigma,\beta,\gamma,x\right)=\varsigma\phi\left(x\right)+\langle\beta,\psi\left(x\right)\rangle+\langle\gamma,\omega\left(x\right)\rangle.$

It can be seen that for all $\varsigma\in\mathbb{R}_{+}$,
$\beta\in\mathbb{R}_{+}^{r}$ and $\gamma\in\mathbb{R}^{q}$, it holds that

${\displaystyle\inf_{x\in\mathbb{R}^{n}}}\
L\left(\varsigma,\beta,\gamma,x\right)\leq\varsigma{\mathcal{V}}\left(P_{eq}\right),\
\ \ \forall\varsigma\geq 0.$

Consequently, weak duality is satisfied in this case.

In [15], a strong Lagrange duality theorem for the nonconvex optimization
problem (Peq) and its dual is established under a suitable generalized Slater
assumption. Based on this reference, it is said that the generalized Slater
condition holds if

$\overline{cone}\
\bigg{(}\left(\psi,\omega\right)\left(\mathbb{R}^{n}\right)+\mathbb{R}^{r}_{+}\times\\{0_{\mathbb{R}^{q}}\\}\bigg{)}=\mathbb{R}^{r}\times\mathbb{R}^{q}.$
(3.2)

To proceed we need the following construction

$\Psi\left(\mathbb{R}^{n}\right)=\bigg{\\{}\left(\phi\left(x\right),\psi\left(x\right),\omega\left(x\right)\right)\in\mathbb{R}\times\mathbb{R}^{r}\times\mathbb{R}^{q}\
|\ x\in\mathbb{R}^{n}\bigg{\\}}.$

By assuming that a genaralized Slater condition holds together with an
additional condition, the authors prove the following strong duality result.

######  Theorem 3.4.

Consider problems (Peq) and (Deq) and suppose that

  * •

${\mathcal{V}}\eqref{w-o-eq}$ is finite,

  * •

$int\bigg{(}\text{co}\left(\Psi\left(\mathbb{R}^{n}\right)\right)+\left(\mathbb{R}_{+}\times\mathbb{R}_{+}^{r}\times\mathbb{R}^{q}\right)\bigg{)}\neq\emptyset$,

  * •

the generalized Slater condition $\left(\ref{cq-w-p-casnorm}\right)$ holds.

Furthermore, let one of the following assumption hold:

$A\left(1\right)$

$\text{cone}\
\bigg{(}int\bigg{[}\text{co}\left(\Psi\left(\mathbb{R}^{n}\right)\right)-{\mathcal{V}}\eqref{w-o-
eq}\left(1,0_{\mathbb{R}_{+}\times\mathbb{R}_{+}^{r}\times\mathbb{R}^{q}}\right)+\left(\mathbb{R}_{+}\times\mathbb{R}_{+}^{r}\times\mathbb{R}^{q}\right)\bigg{]}\bigg{)}$
is pointed,

$A\left(2\right)$

$\left(0,0\right)\notin
int\bigg{[}\text{co}\left(\Psi\left(\mathbb{R}^{n}\right)\right)-{\mathcal{V}}\eqref{w-o-
eq}\left(1,0_{\mathbb{R}_{+}\times\mathbb{R}_{+}^{r}\times\mathbb{R}^{q}}\right)+\left(\mathbb{R}_{+}\times\mathbb{R}_{+}^{r}\times\mathbb{R}^{q}\right)\bigg{]}$.

Then, $\mathcal{V}\eqref{w-o-eq}=\mathcal{V}\eqref{w-o-eq-dual}$ and there
exists
$\left(\bar{\beta},\bar{\gamma}\right)\in\mathbb{R}^{r}_{+}\times\mathbb{R}^{q}$
such that

${\mathcal{V}}\eqref{w-o-eq}={\displaystyle\inf_{x\in\mathbb{R}^{n}}}\
L\left(1,\bar{\beta},\bar{\gamma},x\right).$

Next, we do not assume that (P) has a solution, also no convexity assumption
is imposed. Let us consider the Lagrangian

$L\left(\varsigma,\alpha,\beta,\gamma,x,y\right)=\varsigma
F(x,y)+\gamma(f(x,y)-\varphi(x)))+\sum_{i=1}^{k}\alpha_{i}G_{i}(x,y)+\sum_{j=1}^{p}\beta_{j}g_{j}(x,y).$

It can be seen that for all $\gamma\in\mathbb{R}$,
$\alpha\in\mathbb{R}_{+}^{k}$ and $\beta\in\mathbb{R}_{+}^{p}$

${\displaystyle\inf_{\left(x,y\right)\in\mathbb{R}^{n}\times\mathbb{R}^{m}}}\
L\left(\varsigma,\alpha,\beta,\gamma,x,y\right)\leq\varsigma{\mathcal{V}}\left({\mathcal{P}}\right),\
\ \ \forall\varsigma\geq 0.$

Consequently, the weak duality holds. To provide the strong duality, we need
that the following Slater-type condition holds

$\overline{cone}\
\bigg{(}\left(f-\varphi,G,g\right)\left(\mathbb{R}^{n}\times\mathbb{R}^{m}\right)+\\{0_{\mathbb{R}}\\}\times\mathbb{R}_{+}^{k+p}\bigg{)}=\mathbb{R}\times\mathbb{R}^{k+p}.$
(3.3)

Unfortunately, this is not the case, as any vector
$\left(a,0_{\mathbb{R}^{k}},0_{\mathbb{R}^{p}}\right)$ with $a<0$ does not
belong to the set in the left-hand-side of equation $\left(\ref{cq-w-p-
cLLVF}\right)$. Hence, Theorem 3.4 in not applicable for (P) problem.

##  4 Duality under partial calmness

To deal with the fact that most standard constraint qualifications do not hold
for problem (P), we are going to use the partial calmness concept in this
section. To proceed, we use the reformulation (LLVF). Here, when
$\mathcal{S}\left(x\right)=\emptyset$ for some $x\in\mathbb{R}^{n}$, we use
the convention $\inf\emptyset=\infty$.

In general, the value function $\varphi$ is not lower semicontinuous, even
when the involved functions satisfy this property. To ensure the validity of
the lower semicontinuity of $\varphi$, we will impose some additional
conditions on the set-valued map $K$; see [17, Lemma 3.2] for relevant
details. To proceed here, we consider the perturbed version of problem (LLVF)
linearly parameterized by $t\in\mathbb{R}$:

$\left\\{\begin{array}[]{l}{\displaystyle\min_{x,y}}\ \ F\left(x,y\right)\\\
f\left(x,y\right)-\varphi\left(x\right)+t=0,\\\ G_{i}\left(x,y\right)\leq 0\ \
\text{for all}\ i\in I_{k}=\\{1,\cdots,k\\},\\\ g_{j}\left(x,y\right)\leq 0\ \
\text{for all}\ j\in I_{p}=\\{1,\cdots,p\\}.\end{array}\right.$ (P[$t$])

######  Definition 4.1.

[23] we say that the unperturbed problem (LLVF) is partially calm at its
feasible solution $\left(\bar{x},\bar{y}\right)$ if there is a constant
$\lambda>0$ and a neighborhood $U$ of the triple
$\left(\bar{x},\bar{y},0\right)\in{\mathbb{R}}^{n}\times{\mathbb{R}}^{m}\times\mathbb{R}$
such that

$F\left(x,y\right)-F\left(\bar{x},\bar{y}\right)+\lambda\mid t\mid\geq 0\ \ \
\text{for all}\ \ \left(x,y,t\right)\in U\ \ \text{feasible to}\
\eqref{calm1}.$ (4.1)

In the next lemma, we show that the partial calmness to the bilevel program
(LLVF) allows us an exact penalization of these problem. In fact, the upper-
level objective in our problem may be neither Lipschitz nor continuous,
conditions that are usually imposed in existing results; see, e.g., [23].
However, we formulate another proof here when the upper-level objective
function is only lower semi-continuous.

######  Lemma 4.2.

Let $\left(\bar{x},\bar{y}\right)$ be a partially calm local optimal solution
to the bilevel program (LLVF), and let the upper-level objective function $F$
be lower semi-continuous at this point. Then $\left(\bar{x},\bar{y}\right)$ is
a local optimal solution to the penalized problem

$\left\\{\begin{array}[]{l}{\displaystyle\min_{x,y}}\ \
\lambda^{-1}F\left(x,y\right)+f\left(x,y\right)-\varphi\left(x\right)\\\
G_{i}\left(x,y\right)\leq 0\ \ \text{for all}\ i\in I_{k}=\\{1,\cdots,k\\},\\\
g_{j}\left(x,y\right)\leq 0\ \ \text{for all}\ j\in
I_{p}=\\{1,\cdots,p\\},\end{array}\right.$ (Pλ)

where $\lambda>0$ is the constant from the partial calmness condition
$\left(\ref{calm1100}\right)$.

###### Proof.

Suppose that $\left(\bar{x},\bar{y}\right)$ is a partially calm local optimal
solution to the bilevel program (LLVF) whereas $\left(\bar{x},\bar{y}\right)$
is not a local solution of (Pλ). First, we can find a parameter $\lambda>0$
and a neighborhood $U$ of the triple
$\left(\bar{x},\bar{y},0\right)\in{\mathbb{R}}^{n}\times{\mathbb{R}}^{m}\times\mathbb{R}$
such that

$F\left(x,y\right)-F\left(\bar{x},\bar{y}\right)+\lambda\mid t\mid\geq 0\ \ \
\text{for all}\ \ \left(x,y,t\right)\in U\ \ \text{feasible to}\eqref{calm1}.$
(4.2)

Secondly, there is a sequence
$\left(x_{k},y_{k}\right)\in\mathbb{R}^{n}\times\mathbb{R}^{m}$ feasible to
(Pλ) and satisfying
$\left(x_{k},y_{k}\right)\rightarrow\left(\bar{x},\bar{y}\right)$ such that

$F\left(x_{k},y_{k}\right)+\lambda\left(f\left(x_{k},y_{k}\right)-\varphi\left(x_{k}\right)\right)<F\left(\bar{x},\bar{y}\right)$
(4.3)

for all $k\in\mathbb{N}$. It follows from the lower semi-continuity of $F$ at
$\left(\bar{x},\bar{y}\right)$ that there is $\delta>0$ and $\eta>0$ such that
$V=\left[\left(\bar{x},\bar{y}\right)+\eta\mathbb{B}_{\mathbb{R}^{n}\times\mathbb{R}^{m}}\right]\times\left(-\delta,\delta\right)\subset
U$ and that the inequality

$-\lambda\delta\leq F\left(x,y\right)-F\left(\bar{x},\bar{y}\right)$ (4.4)

holds true for all
$\left(x,y\right)\in\left(\bar{x},\bar{y}\right)+\eta\mathbb{B}_{\mathbb{R}^{n}\times\mathbb{R}^{m}}$.
Setting $t_{k}=f\left(x_{k},y_{k}\right)-\varphi\left(x_{k}\right)$, two cases
have to be considered.
Case I. Let $\left(\left(x_{k},y_{k}\right),t_{k}\right)\in V$; then combining
$\left(\ref{sci1}\right)$ and $\left(\ref{sci2}\right)$, it follows that

$0\leq
F\left(x_{k},y_{k}\right)-F\left(\bar{x},\bar{y}\right)+\lambda\left(f\left(x_{k},y_{k}\right)-\varphi\left(x_{k}\right)\right)<0.$

However, this is a contradiction.
Case II. Assume that $\left(\left(x_{k},y_{k}\right),t_{k}\right)\notin V$. On
the one side, since for $k$ large enough
$\left(x_{k},y_{k}\right)\in\left(\bar{x},\bar{y}\right)+\eta\mathbb{B}_{\mathbb{R}^{n}\times\mathbb{R}^{m}}$,
one has $t_{k}\notin\left(-\delta,\delta\right)$. On the other side, by
definition of optimal value function, we have $t_{k}\geq 0$. Consequently,
$t_{k}\geq\delta$. Hence, by $\left(\ref{sci3}\right)$,

$-\lambda\left(f\left(x_{k},y_{k}\right)-\varphi\left(x_{k}\right)\right)\leq
F\left(x,y\right)-F\left(\bar{x},\bar{y}\right).$ (4.5)

Combining the latter with $\left(\ref{sci2}\right)$, one obtains

$0\leq
F\left(x_{k},y_{k}\right)-F\left(\bar{x},\bar{y}\right)+\lambda\left(f\left(x_{k},y_{k}\right)-\varphi\left(x_{k}\right)\right)<0.$

However, this inequality is a contradiction. Since both cases lead to a
contradiction, we conclude that $\left(\bar{x},\bar{y}\right)$ is a local
optimal solution to the penalized problem (Pλ). ∎

If further assumptions are made about the marginal map $\varphi$ and the lower
level objective function, the converse result may be obtained.

######  Lemma 4.3.

Let $\left(\bar{x},\bar{y}\right)$ with
$\bar{y}\in{\mathcal{S}}\left(\bar{x}\right)$ be a local optimal solution of
the penalized problem (Pλ) for some $\lambda>0$. Assume that $f$ and $\varphi$
are locally Lipschitz near $\left(\bar{x},\bar{y}\right)$ with Lipschitz
modulus $k_{f}$ and $k_{\varphi}$, respectively. Then,
$\left(\bar{x},\bar{y}\right)$ is a partially calm local optimal solution to
the bilevel optimization problem (LLVF).

###### Proof.

Suppose that there exists $\lambda>0$ such that $\left(\bar{x},\bar{y}\right)$
solves (Pλ) locally. Then, there exists $\delta>0$ such that we have the
inequality

$\lambda^{-1}F\left(\bar{x},\bar{y}\right)\leq\lambda^{-1}F\left(x,y\right)+f\left(x,y\right)-\varphi\left(x\right).$
(4.6)

for all
$\left(x,y\right)\in\left(\bar{x},\bar{y}\right)+\delta\mathbb{B}_{\mathbb{R}^{n}\times\mathbb{R}^{m}}$
feasible for problem (Pλ). Let us set
$\eta=\left\\{\frac{\delta}{2k_{f}};\frac{\delta}{2k_{\varphi}};\frac{\delta}{2}\right\\}$.
Then, for any point
$\left(x,y\right)\in\left(\bar{x},\bar{y}\right)+\eta\mathbb{B}_{\mathbb{R}^{n}\times\mathbb{R}^{m}}$
feasible for problem (Pλ), one has

$\begin{array}[]{lcl}\mid f\left(x,y\right)-\varphi\left(x\right)\mid&=&\mid
f\left(x,y\right)-f\left(\bar{x},\bar{y}\right)+\varphi\left(\bar{x}\right)-\varphi\left(x\right)\mid\\\
&\leq&k_{f}\parallel\left(x,y\right)-\left(\bar{x},\bar{y}\right)\parallel+k_{\varphi}\parallel
x-\bar{x}\parallel\\\ &\leq&\delta.\end{array}$

Thus, setting $t=\varphi\left(x\right)-f\left(x,y\right)$, the local
optimality $\left(\ref{sci4}\right)$ leads to

$F\left(x,y\right)-F\left(\bar{x},\bar{y}\right)+\lambda\mid t\mid\geq 0.$

The latter inequality is valid for all
$\left(x,y\right)\in\bigg{(}\left(\bar{x},\bar{y}\right)+\eta\mathbb{B}\bigg{)}\times\left(-\delta;\delta\right)$
feasible to (P[$t$]). Consequently, $\left(\bar{x},\bar{y}\right)$ is a
partially calm local optimal solution to the bilevel program (LLVF). ∎

###  4.1 Duality under the Slater condition

In this subsection, we aim to describe the dual problem of the auxiliary
problem (Pλ) and characterize the corresponding assumption. To proceed, let
the feasible set of problem (Pλ) be denoted by

$\mathcal{S}=\Big{\\{}(x,y)\in\mathbb{R}^{n}\times\mathbb{R}^{m}:G_{i}(x,y)\leqslant
0,\ i\in I_{k},\ \ g_{j}(x,y)\leqslant 0,\ j\in I_{p}\Big{\\}},$ (4.7)

and consider the following dual of problem (Pλ):

$\begin{array}[]{l}\underset{x^{*}\in\operatorname{dom}\varphi^{*}}{\inf}\underset{\underset{\alpha\in\mathbb{R}_{+}^{k},\beta\in\mathbb{R}_{+}^{p},}{\left(z^{*},q^{\ast}\right)\in\mathbb{R}^{n}\times\mathbb{R}^{m}}}{\sup}\bigg{\\{}\varphi^{*}\left(x^{*}\right)-(\lambda^{-1}F+f)^{*}\left(z^{\ast},q^{\ast}\right)\\\
\qquad\qquad\qquad\qquad\qquad\qquad-\left.\left(\displaystyle\sum_{i=1}^{k}\
\alpha_{i}G_{i}+{\displaystyle\sum_{j=1}^{p}}\
\beta_{j}g_{j}\right)^{\ast}\left(x^{\ast}-z^{*},-q^{\ast}\right)\right\\}.\end{array}$
(Dλ)

Next, we will characterize the weak and strong duality between (Pλ) and (Dλ).
To proceed, and from here on, we denote by
$G=\left(G_{1},\cdots,G_{k}\right)^{T}$ and
$g=\left(g_{1},\cdots,g_{p}\right)^{T}$ the vectors of upper and lower
constraint functions, respectively.

######  Theorem 4.4.

Consider problem (Pλ) for some $\lambda>0$ and let
$F,f,g_{1},\ldots,g_{p},G_{1},\ldots,G_{k}$ be extended real-valued convex
functions on $\mathbb{R}^{n}\times\mathbb{R}^{m}$. Assume that $\varphi$ is
lower semicontinuous. Then, the weak duality between (Pλ) and (Dλ) holds. Thus
is, ${\mathcal{V}}\eqref{calm3}\geq{\mathcal{V}}\eqref{weak-problem-stand}$.

###### Proof.

Since $\varphi$ is lower semicontinuous, then the equality
$\varphi^{**}(x)=\varphi(x)$ holds. Following the standard convexification
technique, and using the Fenchel equality for $\varphi(\cdot)$, stated in
$(\ref{eq.dual})$, the problem (Pλ) takes the following form

$\underset{x^{*}\in\operatorname{dom}\varphi^{*}}{\inf}\ \
\underset{\underset{G\left(x,y\right)\leq 0,\ g\left(x,y\right)\leq
0}{(x,y)\in\mathbb{R}^{n}\times\mathbb{R}^{m}}}{\inf}\bigg{\\{}\lambda^{-1}F(x,y)+f(x,y)+\varphi^{*}\left(x^{*}\right)-\left\langle
x^{*},x\right\rangle\bigg{\\}}.$ (Pλ)

For any $x^{*}\in\operatorname{dom}\varphi^{*}$ consider

$\underset{\underset{G\left(x,y\right)\leq 0,\ g\left(x,y\right)\leq
0}{(x,y)\in\mathbb{R}^{n}\times\mathbb{R}^{m}}}{\inf}\bigg{\\{}\lambda^{-1}F(x,y)+f(x,y)+\varphi^{*}\left(x^{*}\right)-\left\langle
x^{*},x\right\rangle\bigg{\\}},$ (P${}^{\lambda}\left(x^{\ast}\right)$)

and set
$\phi\left(x,y\right)=\lambda^{-1}F(x,y)+f(x,y)+\varphi^{*}\left(x^{*}\right)-\left\langle
x^{*},x\right\rangle$. Since, (P${}^{\lambda}\left(x^{\ast}\right)$) is a
convex optimisation problem, its Fenchel-Lagrange duality reformulation is

$\begin{array}[]{ll}\underset{\underset{\left(s^{*},q^{\ast}\right)\in\mathbb{R}^{n}\times\mathbb{R}^{m}}{\alpha\in\mathbb{R}_{+}^{k},\beta\in\mathbb{R}_{+}^{p}}}{\sup}&\bigg{\\{}-\phi^{\ast}\left(s^{*},q^{\ast}\right)-\left(\displaystyle\sum_{i=1}^{k}\
\alpha_{i}G_{i}+{\displaystyle\sum_{j=1}^{p}}\
\beta_{j}g_{j}\right)^{\ast}\left(-s^{*},-q^{*}\right)\bigg{\\}}.\end{array}$
(D${}^{\lambda}\left(x^{\ast}\right)$)

On the other hand, by an easy calculation, using the equality stated in
$\left(\ref{eqr}\right)$ together with the definition of conjugate function,
we get

$\phi^{\ast}\left(s^{*},q^{\ast}\right)=\left(\lambda^{-1}F+f\right)^{\ast}\left(s^{*}+x^{\ast},q^{\ast}\right)-\varphi^{\ast}\left(x^{\ast}\right).$
(4.8)

Inserting $\left(\ref{w-calm-3}\right)$ in
(D${}^{\lambda}\left(x^{\ast}\right)$), we obtain

$\begin{array}[]{l}\underset{\underset{\alpha\in\mathbb{R}_{+}^{k},\beta\in\mathbb{R}_{+}^{p},}{\left(s^{*},q^{\ast}\right)\in\mathbb{R}^{n}\times\mathbb{R}^{m}}}{\sup}\left\\{\varphi^{*}\left(x^{*}\right)-(\lambda^{-1}F+f)^{*}\left(s^{*}+x^{\ast},q^{\ast}\right)\right.\\\
\qquad\quad\qquad\qquad\qquad\quad-\left.\left(\displaystyle\sum_{i=1}^{k}\
\alpha_{i}G_{i}+{\displaystyle\sum_{j=1}^{p}}\
\beta_{j}g_{j}\right)^{\ast}\left(-s^{*},-q^{\ast}\right)\right\\}.\end{array}$
(D${}^{\lambda}\left(x^{\ast}\right)$)

Setting $z^{\ast}=s^{\ast}+x^{\ast}$, it follows

$\begin{array}[]{l}\underset{\underset{\alpha\in\mathbb{R}_{+}^{k},\beta\in\mathbb{R}_{+}^{p},}{\left(z^{*},q^{\ast}\right)\in\mathbb{R}^{n}\times\mathbb{R}^{m}}}{\sup}\left\\{\varphi^{*}\left(x^{*}\right)-(\lambda^{-1}F+f)^{*}\left(z^{\ast},q^{\ast}\right)\right.\\\
\qquad\quad\qquad\qquad\qquad\quad-\left.\left(\displaystyle\sum_{i=1}^{k}\
\alpha_{i}G_{i}+{\displaystyle\sum_{j=1}^{p}}\
\beta_{j}g_{j}\right)^{\ast}\left(x^{\ast}-z^{*},-q^{\ast}\right)\right\\}.\end{array}$
(D${}^{\lambda}\left(x^{\ast}\right)$)

Taking the infimum of (D${}^{\lambda}\left(x^{\ast}\right)$) for
$x^{*}\in\operatorname{dom}\varphi^{*}$, we arrived at the desired dual
problem (Dλ). Finally, from [7, Proposition 2.1], we have
${\mathcal{V}}\eqref{calm3}\geq{\mathcal{V}}\eqref{weak-problem-stand}$. ∎

In general, the strong duality between (Pλ) and (Dλ) does not necessarily
hold. To overcome this situation, we introduce the following slater CQ:

$\left\\{\begin{array}[]{l}\exists(\bar{x},\bar{y})\in\text{dom}\
\left(\lambda^{-1}F+f\right)\cap{\displaystyle\bigcap^{k}_{i=1}}\
\text{ri}\left(\text{dom}G_{i}\right)\cap{\displaystyle\bigcap^{p}_{j=1}}\
\text{ri}\left(\text{dom}g_{j}\right)\,\text{such that}\\\
g_{j}(\bar{x},\bar{y})<0,\ \ \forall j=1,\dots,p,\\\
G_{i}(\bar{x},\bar{y})<0,\ \ \forall i=1,\dots,k.\end{array}\right.$ (4.9)

The following result provides a strong duality result for problem (Pλ).

######  Theorem 4.5.

Let $F$, $f$, $g_{1}$, …, $g_{p}$, and $G_{1}$, …, $G_{k}$ be extended real-
valued convex functions on $\mathbb{R}^{n}\times\mathbb{R}^{m}$. Moreover,
suppose that CQ $\left(\ref{cq-slater-lambda}\right)$ is satisfied and
$\varphi$ is lower semicontinuous. Then, the strong duality between (Pλ) and
(Dλ) holds; that is, ${\mathcal{V}}\eqref{calm3}={\mathcal{V}}\eqref{weak-
problem-stand}$ and the dual problem (Dλ) has an optimal solution.

###### Proof.

Let $x^{\ast}\in\text{dom}\ \varphi^{\ast}$ and consider the following problem

$\left\\{\begin{array}[]{ll}\inf\ \lambda^{-1}F(x,y)+f(x,y)-\langle
x,x^{\ast}\rangle+\varphi^{\ast}(x^{\ast})&\\\
\left(x,y\right)\in\mathbb{R}^{n}\times\mathbb{R}^{m}&\\\ G_{i}(x,y)\leqslant
0\quad\quad i=1,\dots,k,&\\\ g_{j}(x,y)\leqslant 0\quad\quad
j=1,\dots,p.\end{array}\right.$ (P${}^{\lambda}\left(x^{\ast}\right)$)

Since, $\lambda^{-1}F(x,y)+f(x,y)-\langle
x,x^{\ast}\rangle+\varphi^{\ast}(x)$, $G_{i}$, with $i=1,\dots,k$ and $g_{j}$
with $j=1,\dots,p$, are convex and proper we can introduce the Lagrange dual
problem to (P${}^{\lambda}\left(x^{\ast}\right)$) with
$\alpha=\left(\alpha_{1},\cdots,\alpha_{k}\right)\in\mathbb{R}_{+}^{k}$ and
$\beta=\left(\beta_{1},\cdots,\beta_{k}\right)\in\mathbb{R}_{+}^{p}$ as dual
variables

$\begin{array}[]{ll}\underset{\left(\alpha,\beta\right)\in\mathbb{R}_{+}^{k}\times\mathbb{R}_{+}^{p}}{\sup}\underset{\left(x,y\right)\in\mathbb{R}^{n}\times\mathbb{R}^{m}}{\inf}&\bigg{\\{}\lambda^{-1}F(x,y)+f(x,y)-\langle
x,x^{\ast}\rangle\\\
&+\varphi^{\ast}(x^{\ast})+\displaystyle\sum_{i=1}^{k}\alpha_{i}G_{i}\left(x,y\right)+\sum_{j=1}^{p}\beta_{j}g_{j}\left(x,y\right)\bigg{\\}}.\end{array}$
(D${}^{\lambda}\left(x^{\ast}\right)$)

Since (4.9) condition holds, it follows from [20, Theorem 28.2] that the
optimal objective values of (P${}^{\lambda}\left(x^{\ast}\right)$) and its
Lagrange dual (D${}^{\lambda}\left(x^{\ast}\right)$) are equal and, moreover,
there exists an optimal solution
$\bar{\alpha}=\left(\bar{\alpha}_{1},\cdots,\bar{\alpha}_{k}\right)\in\mathbb{R}_{+}^{k}$
and
$\bar{\beta}=\left(\bar{\beta}_{1},\cdots,\bar{\beta}_{k}\right)\in\mathbb{R}_{+}^{p}$
of (D${}^{\lambda}\left(x^{\ast}\right)$) such that

$\begin{array}[]{lcl}{\mathcal{V}}\eqref{strong-
wc-p}&=&\underset{\left(\alpha,\beta\right)\in\mathbb{R}_{+}^{k}\times\mathbb{R}_{+}^{p}}{\sup}\underset{\left(x,y\right)\in\mathbb{R}^{n}\times\mathbb{R}^{m}}{\inf}\bigg{\\{}\lambda^{-1}F(x,y)+f(x,y)-\langle
x,x^{\ast}\rangle\\\
&&+\varphi^{\ast}(x^{\ast})+\displaystyle\sum_{i=1}^{k}\alpha_{i}G_{i}\left(x,y\right)+\sum_{j=1}^{p}\beta_{j}g_{j}\left(x,y\right)\bigg{\\}}\\\
&=&\underset{\left(x,y\right)\in\mathbb{R}^{n}\times\mathbb{R}^{m}}{\inf}\left\\{\lambda^{-1}F(x,y)+f(x,y)\right.\\\
&&\qquad\qquad\qquad-\left.\langle
x,x^{\ast}\rangle+\varphi^{\ast}(x)+\displaystyle\sum_{i=1}^{k}\bar{\alpha}_{i}G_{i}\left(x,y\right)+\sum_{j=1}^{p}\bar{\beta}_{j}g_{j}\left(x,y\right)\right\\}.\end{array}$

Since, $\text{dom}\
\left(\lambda^{-1}F+f-\langle\cdot,x^{\ast}\rangle+\varphi^{\ast}(x^{\ast})\right)=dom\left(\lambda^{-1}F+f\right)$,
we have

${\displaystyle\bigcap^{k}_{i=1}}\ \text{ri}\
dom\left(G_{i}\right)\cap{\displaystyle\bigcap^{p}_{j=1}}\ \text{ri}\
dom\left(g_{j}\right)\cap\text{ri}\
dom\left(\lambda^{-1}F+f\right)\neq\emptyset.$

Hence, one can deduce from Proposition 2.4 that

$\begin{array}[]{lcl}{\mathcal{V}}\eqref{strong-
wc-p}&=&-\bigg{(}\lambda^{-1}F+f-x^{\ast}+\varphi^{\ast}(x^{\ast})+\displaystyle\sum_{i=1}^{k}\bar{\alpha}_{i}G_{i}+\sum_{j=1}^{p}\bar{\beta}_{j}g_{j}\bigg{)}^{\ast}\left(0\right)\\\
&=&\underset{\left(s^{\ast},q^{\ast}\right)\in\mathbb{R}^{n}\times\mathbb{R}^{m}}{\sup}\bigg{\\{}\varphi^{*}\left(x^{*}\right)-(\lambda^{-1}F+f)^{*}\left(s^{*}+x^{\ast},q^{\ast}\right)\\\
&&\qquad\qquad\qquad\quad-\left.\left({\displaystyle\sum_{i=1}^{k}}\
\bar{\alpha}_{i}G_{i}+{\displaystyle\sum_{j=1}^{p}}\bar{\beta}_{j}g_{j}\right)^{\ast}\left(-s^{\ast},-q^{\ast}\right)\right\\}\end{array}$

and that there exists $\bar{s}^{\ast}\in\mathbb{R}^{n}$ and
$\bar{q}^{\ast}\in\mathbb{R}^{m}$ such that the supremum is attained. Thus

${\mathcal{V}}\eqref{strong-
wc-p}=\varphi^{*}\left(x^{*}\right)-(\lambda^{-1}F+f)^{*}\left(\bar{s}^{\ast}+x^{\ast},\bar{q}^{\ast}\right)-\left({\displaystyle\sum_{i=1}^{k}}\
\bar{\alpha}_{i}G_{i}+{\displaystyle\sum_{j=1}^{p}}\bar{\beta}_{j}g_{j}\right)^{\ast}\left(-\bar{s}^{\ast},-\bar{q}^{\ast}\right).$

Setting $\bar{z}^{\ast}=\bar{s}^{\ast}+x^{\ast}$, we get

${\mathcal{V}}\eqref{strong-
wc-p}=\varphi^{*}\left(x^{*}\right)-(\lambda^{-1}F+f)^{*}\left(\bar{z}^{\ast},\bar{q}^{\ast}\right)-\left({\displaystyle\sum_{i=1}^{k}}\
\bar{\alpha}_{i}G_{i}+{\displaystyle\sum_{j=1}^{p}}\bar{\beta}_{j}g_{j}\right)^{\ast}\left(x^{\ast}-\bar{z}^{\ast},-\bar{q}^{\ast}\right).$

Hence, ${\mathcal{V}}\eqref{strong-wc-p}={\mathcal{V}}\eqref{strong-wc-d}$.
Since, $x^{\ast}$ is arbitrary choosen in $\text{dom}\ \varphi^{\ast}$, then
${\mathcal{V}}\eqref{calm3}={\mathcal{V}}\eqref{weak-problem-stand}$. Thus,
the proof is complete. ∎

######  Remark 4.6.

To compute the conjugate function of the value fucntion $\varphi$, we asume
that $K\left(x\right)$ is independent of $x$. Thus, we set for all
$x\in\mathbb{R}^{n}$,
$K\left(x\right)=K=\\{y\in\mathbb{R}^{m}|g\left(y\right)\leq 0\\}$. Then

$\varphi^{*}(x^{*})=(f+\delta_{\mathbb{R}^{n}\times K})^{*}(0,x^{*})$

and we have

$\displaystyle\varphi^{*}(x^{*})$
$\displaystyle=\underset{x\in\mathbb{R}^{n}}{\sup}\bigg{\\{}\langle
x^{*},x\rangle-\varphi(x):x\in\mathbb{R}^{n}\bigg{\\}}$
$\displaystyle=\underset{x\in\mathbb{R}^{n}}{\sup}\bigg{\\{}\langle
x^{*},x\rangle-\underset{y\in\mathbb{R}^{m}}{\inf}\Big{\\{}f(x,y)+\delta_{K}(y)\Big{\\}}\bigg{\\}}$
$\displaystyle=\underset{x\in\mathbb{R}^{n}}{\sup}\
\underset{y\in\mathbb{R}^{m}}{\sup}\bigg{\\{}\langle
x^{*},x\rangle-f(x,y)-\delta_{K}(y)\bigg{\\}}$
$\displaystyle=\underset{x,y}{\sup}\bigg{\\{}\langle
x^{*},x\rangle-(f(x,y)+\delta_{K}(y))\bigg{\\}}$
$\displaystyle=(f+\delta_{\mathbb{R}^{n}\times K})^{*}(0,x^{*}).$

###  4.2 Duality under further regularity conditions

In general, weak duality (hence, strong duality) between (Pλ) and (Dλ) does
not necessarily hold in many situations, including when $\varphi$ is not lower
semicontinuous. In order to describe the weak and strong dualities between
(Pλ) and (Dλ), we modify the structure of the dual problem as

$\underset{x^{*}\in\operatorname{dom}\varphi^{*}}{\inf}\underset{\underset{\alpha\in\mathbb{R}_{+}^{k},\beta\in\mathbb{R}_{+}^{p},\left(z^{*},q^{\ast}\right)\in\operatorname{dom}F^{*}\cap\operatorname{dom}f^{*}}{(u_{i}^{*},v_{i}^{*})\in\operatorname{dom}G_{i}^{*},(u_{j}^{*},v_{j}^{*})\in\operatorname{dom}g_{j}^{*}}}{\sup}\bigg{\\{}\psi\left(x^{\ast},z^{\ast},q^{\ast},u^{\ast},v^{\ast},\alpha,\beta\right)-\delta^{\ast}_{\mathbb{R}^{n}\times\mathbb{R}^{m}}\left(s^{\ast},t^{\ast}\right)\bigg{\\}},$
(D${}_{m}^{\lambda}$)

where $\psi$ is given by

$\psi\left(x^{\ast},z^{\ast},q^{\ast},u^{\ast},v^{\ast},\alpha,\beta\right)=\varphi^{*}\left(x^{*}\right)-(\lambda^{-1}F+f)^{*}\left(z^{*},q^{\ast}\right)-\displaystyle\sum_{i=1}^{k}\alpha_{i}G_{i}^{*}\left(u_{i}^{*},v_{i}^{*}\right)-\sum_{j=1}^{p}\beta_{j}g_{j}^{*}\left(u_{j}^{*},v_{j}^{*}\right)$

with $u^{\ast}=\left(u^{\ast}_{1},\cdots,u^{\ast}_{k+p}\right)$,
$v^{\ast}=\left(v^{\ast}_{1},\cdots,v^{\ast}_{k+p}\right)$,
$s^{\ast}=x^{\ast}-z^{*}-\displaystyle\sum_{i=1}^{k}\alpha_{i}u_{i}^{*}-\sum_{j=1}^{p}\beta_{j}u_{j}^{*}$,
and
$t^{\ast}=-q^{\ast}-\displaystyle\sum_{i=1}^{k}\alpha_{i}v_{i}^{*}-\sum_{j=1}^{p}\beta_{j}v_{j}^{*}$.

Secondly, we exploit the semi-further regularity condition (SFRC) and further
regularity condition (SFRC) introduced in [22]. The cited regularities are
based on the properties of the epigraph of the conjugate functions. To
proceed, we set

$\Gamma=\operatorname{epi}(\lambda^{-1}F+f)^{*},\ \
\Lambda=\underset{i=1}{\bigcup^{k}}\operatorname{epi}G_{i}^{*},\ \
\Pi=\underset{j=1}{\bigcup^{p}}\operatorname{epi}g_{j}^{*}.$

Based on the above sets, we introduce the characteristic set ${\mathcal{R}}$
defined by

${\mathcal{R}}:=\underset{x^{*}\in\operatorname{dom}{\varphi}^{*}}{\bigcap}\big{(}\Gamma+\operatorname{cone}\left(\Lambda\cup\Pi\right)+\operatorname{epi}\delta^{*}_{\mathbb{R}^{n}\times\mathbb{R}^{m}}-\left(\left(x^{*},0\right);{\varphi}^{*}(x^{*})\right)\big{)}.$

Considering the possible relationships between $\mathcal{R}$ and
$\operatorname{epi}\left(\lambda^{-1}F+f-\varphi+\delta_{\mathcal{\mathcal{S}}}\right)^{*}$,
we introduce the following regularity conditions.

######  Definition 4.7.

The family
$\left((\lambda^{-1}F+f),\varphi,\delta_{\mathbb{R}^{n}\times\mathbb{R}^{m}},G_{i},g_{j}\right)$,
$i=1,\dots,k$, $j=1,\dots,p$ is said to satisfy the semi-further regularity
condition (SFRC) if

$\mathcal{R}\cap\left(\\{0_{\mathbb{R}^{n}\times\mathbb{R}^{m}}\\}\times\mathbb{R}\right)\subseteq\operatorname{epi}\left(\lambda^{-1}F+f-\varphi+\delta_{\mathcal{S}}\right)^{*}\cap\left(\\{0_{\mathbb{R}^{n}\times\mathbb{R}^{m}}\\}\times\mathbb{R}\right).$
(4.10)

If equality holds in $\left(\ref{sfrc-def}\right)$, we say that the further
regularity condition (FRC) is satisfied.

######  Remark 4.8.

In general, neither

$\mathcal{R}\subseteq\operatorname{epi}\left((\lambda^{-1}F+f)-\varphi+\delta_{\mathcal{S}}\right)^{*}\
\ \text{nor}\ \
\operatorname{epi}\left((\lambda^{-1}F+f)-\varphi+\delta_{\mathcal{S}}\right)^{*}\subseteq\mathcal{R}$

holds necessarily. But when $\varphi$ is convex, one gets

$\mathcal{R}\subseteq\operatorname{epi}\left((\lambda^{-1}F+f)-\varphi+\delta_{\mathcal{S}}\right)^{*}.$

Indeed, by Proposition $\ref{cl2}\ (ii)$, we have

$\displaystyle\left((\lambda^{-1}F+f)-\varphi\right)^{*}$
$\displaystyle=\left(\inf\left(\lambda^{-1}F+f-x^{*}+{\varphi}^{*}(x^{*})\right)\right)^{*}$
$\displaystyle=\sup\left(\lambda^{-1}F+f-x^{*}+{\varphi}^{*}(x^{*})\right)^{*}.$

This, together with $(\ref{eqr-1})\ \text{and Proposition}\ \ref{cl2}\ (i)$,
implies that

$\displaystyle\operatorname{epi}\left((\lambda^{-1}F+f)-\varphi\right)^{*}$
$\displaystyle=\underset{x^{*}\in\operatorname{dom}\varphi^{*}}{\bigcap}\operatorname{epi}\left(\lambda^{-1}F+f-x^{*}+{\varphi}^{*}(x^{*})\right)^{*}$
$\displaystyle=\underset{x^{*}\in\operatorname{dom}\varphi^{*}}{\bigcap}\operatorname{epi}(\lambda^{-1}F+f)^{*}-(x^{*},{\varphi}^{*}(x^{*})).$

Thus,

$\begin{array}[]{l}\operatorname{epi}\left((\lambda^{-1}F+f)-\varphi\right)^{*}+\operatorname{cone}\left(\Lambda\cup\Pi\right)+\operatorname{epi}\delta^{*}_{\mathbb{R}^{n}\times\mathbb{R}^{m}}\\\
=\underset{x^{*}\in\operatorname{dom}{\varphi}^{*}}{\displaystyle\bigcap}\left(\Gamma+\operatorname{cone}\left(\Lambda\cup\Pi\right)+\operatorname{epi}\delta^{*}_{\mathbb{R}^{n}\times\mathbb{R}^{m}}-(x^{*},{\varphi}^{*}(x^{*}))\right)\\\
=\mathcal{R}.\end{array}$

On the other hand, using the equality $(3.5)$ in [16], we obtain

$\operatorname{epi}\left((\lambda^{-1}F+f)-\varphi\right)^{*}+\operatorname{cone}\left(\Lambda\cup\Pi\right)+\operatorname{epi}\delta^{*}_{\mathbb{R}^{n}\times\mathbb{R}^{m}}\subseteq\operatorname{epi}\left((\lambda^{-1}F+f)-\varphi+\delta_{\mathcal{S}}\right)^{*}.$

Consequently,

$\mathcal{R}\subseteq\operatorname{epi}\left((\lambda^{-1}F+f)-\varphi+\delta_{\mathcal{S}}\right)^{*}.$

######  Remark 4.9.

It can be seen that the strong duality for (Pλ) and (D${}_{m}^{\lambda}$)
holds if and only if ${\mathcal{V}}\eqref{calm3}={\mathcal{V}}\eqref{form-3}$
and for any $x^{*}\in\operatorname{dom}\varphi^{*}$, we can find points
$\left(z^{\ast},q^{\ast}\right)\in\operatorname{dom}(\lambda^{-1}F+f)^{*}$,
$\left(u_{i}^{\ast},v_{i}^{\ast}\right)\in\operatorname{dom}G_{i}^{*}$,
$i=1,\cdots,k$,
$\left(u_{j}^{\ast},v_{j}^{\ast}\right)\in\operatorname{dom}g_{j}^{*}$,
$j=1,\cdots,p$, $\mu_{i}\in\mathbb{R}_{+}$, $i=1,\cdots,k$,
$\nu_{j}\in\mathbb{R}_{+}$, $j=1,\cdots,p$ and
$\left(s^{\ast},t^{\ast}\right)\in\mathbb{R}^{n}\times\mathbb{R}^{m}$ such
that we have

$\varphi\left(x^{\ast}\right)-(\lambda^{-1}F+f)^{*}\left(z^{\ast},q^{\ast}\right)-{\displaystyle\sum^{k}_{i=1}}\
\mu_{i}G^{\ast}_{i}\left(u_{i}^{\ast},v_{i}^{\ast}\right)-{\displaystyle\sum^{p}_{j=1}}\
\nu_{j}g^{\ast}_{j}\left(u_{j}^{\ast},v_{j}^{\ast}\right)-\delta^{*}_{\mathbb{R}^{n}\times\mathbb{R}^{m}}\left(s^{\ast},t^{\ast}\right)\geq{\mathcal{V}}\eqref{form-3},$

with
$s^{\ast}=x^{\ast}-z^{*}-\displaystyle\sum_{i=1}^{k}\mu_{i}u_{i}^{*}-\sum_{j=1}^{p}\nu_{j}u_{j}^{*}$,
and
$t^{\ast}=-q^{\ast}-\displaystyle\sum_{i=1}^{k}\mu_{i}v_{i}^{*}-\sum_{j=1}^{p}\nu_{j}v_{j}^{*}$.

The following theorems provide weak and strong Fenchel–Lagrange duality
results with regards to an optimization problem of the form (Pλ).

######  Theorem 4.10 (Weak Fenchel–Lagrange duality).

Let $\lambda>0$ and $F$, $f$, $G_{i}$, $g_{j}$, $i=1,\dots,k$, $j=1,\dots,p$
be proper convex functions. The family
$\left((\lambda^{-1}F+f),\;\varphi,\delta_{\mathbb{R}^{n}\times\mathbb{R}^{m}},\;G_{i},\;g_{j}\right)$,
$i=1,\dots,k$, $j=1,\dots,p$ satisfies (SFRC) if and only if the weak duality
between (Pλ) and (D${}_{m}^{\lambda}$) holds.

###### Proof.

Suppose that the weak duality between (Pλ) and (D${}_{m}^{\lambda}$) does not
hold. Then,

${\mathcal{V}}\eqref{calm3}<-\zeta<{\mathcal{V}}\eqref{form-3}$

for some $\zeta\in\mathbb{R}$. From (D${}_{m}^{\lambda}$), for any
$x^{*}\in\operatorname{dom}{\varphi}^{*}$, there exist
$\alpha\in\mathbb{R}_{+}^{k}$, $\beta\in\mathbb{R}_{+}^{p}$,
$\left(z^{*},q^{\ast}\right)\in\operatorname{dom}F^{*}\cap\operatorname{dom}f^{*}$,
$(u_{i}^{*},v_{i}^{*})\in\operatorname{dom}G_{i}^{*}$, and
$(u_{j}^{*},v_{j}^{*})\in\operatorname{dom}g_{j}^{*}$ such that

$\varphi^{*}\left(x^{*}\right)-(\lambda^{-1}F+f)^{*}\left(z^{*},q^{\ast}\right)-\displaystyle\sum_{i=1}^{k}\alpha_{i}G_{i}^{*}\left(u_{i}^{*},v_{i}^{*}\right)-\sum_{j=1}^{p}\beta_{j}g_{j}^{*}\left(u_{j}^{*},v_{j}^{*}\right)-\delta^{\ast}_{\mathbb{R}^{n}\times\mathbb{R}^{m}}\left(s^{\ast},t^{\ast}\right)\geqslant-\zeta,$

with
$s^{\ast}=x^{\ast}-z^{*}-\displaystyle\sum_{i=1}^{k}\alpha_{i}u_{i}^{*}-\sum_{j=1}^{p}\beta_{j}u_{j}^{*}$,
and
$t^{\ast}=-q^{\ast}-\displaystyle\sum_{i=1}^{k}\alpha_{i}v_{i}^{*}-\sum_{j=1}^{p}\beta_{j}v_{j}^{*}$.
Thus,

$\delta^{\ast}_{\mathbb{R}^{n}\times\mathbb{R}^{m}}\left(s^{\ast},t^{\ast}\right)\leq\varphi^{*}\left(x^{*}\right)-(\lambda^{-1}F+f)^{*}\left(z^{*},q^{\ast}\right)-\displaystyle\sum_{i=1}^{k}\alpha_{i}G_{i}^{*}\left(u_{i}^{*},v_{i}^{*}\right)-\sum_{j=1}^{p}\beta_{j}g_{j}^{*}\left(u_{j}^{*},v_{j}^{*}\right)+\zeta.$

It follows that

$\left(\left(s^{\ast},t^{*}\right);\varphi^{*}\left(x^{*}\right)-(\lambda^{-1}F+f)^{*}\left(z^{*},q^{\ast}\right)-\displaystyle\sum_{i=1}^{k}\alpha_{i}G_{i}^{*}\left(u_{i}^{*},v_{i}^{*}\right)-\sum_{j=1}^{p}\beta_{j}g_{j}^{*}\left(u_{j}^{*},v_{j}^{*}\right)+\zeta\right)\in\text{epi}\delta^{\ast}_{\mathbb{R}^{n}\times\mathbb{R}^{m}}.$

Or equivalently,

$\begin{array}[]{l}\left(0,\zeta\right)\in\left(-\left(s^{\ast},t^{*}\right);-\varphi^{*}\left(x^{*}\right)+(\lambda^{-1}F+f)^{*}\left(z^{*},q^{\ast}\right)\right.\\\
\qquad\qquad\qquad\quad\left.+\displaystyle\sum_{i=1}^{k}\alpha_{i}G_{i}^{*}\left(u_{i}^{*},v_{i}^{*}\right)-\sum_{j=1}^{p}\beta_{j}g_{j}^{*}\left(u_{j}^{*},v_{j}^{*}\right)\right)+\text{epi}\delta^{\ast}_{\mathbb{R}^{n}\times\mathbb{R}^{m}}.\end{array}$

Writing $\left(s^{\ast},t^{*}\right)$ as

$\left(s^{\ast},t^{*}\right)=-\left(z^{*},q^{*}\right)-\left(\displaystyle\sum_{i=1}^{k}\alpha_{i}\left(u_{i}^{*},v_{i}^{*}\right)\right)-\left(\displaystyle\sum_{j=1}^{p}\beta_{i}\left(u_{j}^{*},v_{j}^{*}\right)\right)+\left(x^{\ast},0\right),$

one deduces that

$\begin{array}[]{lcl}\left(0;\zeta\right)&\in&\left(\left(z^{\ast},q^{\ast}\right);(\lambda^{-1}F+f)^{*}\left(z^{*},q^{*}\right)\right)-\left(\left(x^{\ast},0\right);\varphi^{*}\left(x^{*}\right)\right)\\\
&&+\displaystyle\sum_{i=1}^{k}\alpha_{i}\left(\left(u_{i}^{*},v_{i}^{*}\right);G^{\ast}_{i}\left(u_{i}^{*},v_{i}^{*}\right)\right)\displaystyle\sum_{j=1}^{p}\beta_{j}\left(\left(u_{j}^{*},v_{j}^{*}\right);g^{\ast}_{j}\left(u_{j}^{*},v_{j}^{*}\right)\right)+\operatorname{epi}\delta^{*}_{\mathbb{R}^{n}\times\mathbb{R}^{m}}.\end{array}$

Consequently,

$\left(0;\zeta\right)\in\big{(}\Gamma+\operatorname{cone}\left(\Lambda\cup\Pi\right)+\operatorname{epi}\delta^{*}_{\mathbb{R}^{n}\times\mathbb{R}^{m}}-\left(\left(x^{*},0\right);{\varphi}^{*}(x^{*})\right).$

Since $x^{\ast}\in\operatorname{dom}\varphi^{\ast}$ is arbitrary, we have that
$(0,\zeta)\in\mathcal{R}$. Now, since the family
$\left((\lambda^{-1}F+f),\;\varphi,\;\delta_{\mathbb{R}^{n}\times\mathbb{R}^{m}}\right)$,
$G_{i}$, $g_{j}$ for $i=1,\dots,k$, $j=1,\dots,p$ satisfies (SFRC), we have
that

$(0,\zeta)\in\operatorname{epi}\left(\lambda^{-1}F+f-\varphi+\delta_{\mathcal{S}}\right)^{*}.$

Remarking that

${\mathcal{V}}\eqref{calm3}=\inf\\{\left(\lambda^{-1}F+f\right)\left(x,y\right)-\varphi\left(x\right)+\delta_{\mathcal{S}}\left(x,y\right)\\}=-\left(\lambda^{-1}F+f-\varphi+\delta_{\mathcal{S}}\right)^{\ast}\left(0\right),$

one can deduce

$(0,\zeta)\in\operatorname{epi}\left(\lambda^{-1}F+f-\varphi+\delta_{\mathcal{S}}\right)^{*}\
\ {\mathcal{V}}\eqref{calm3}\geqslant-\zeta,$ (4.11)

Hence, ${\mathcal{V}}\eqref{calm3}\geqslant-\zeta$. This contradicts
${\mathcal{V}}\eqref{calm3}<-\zeta$. Thus, the weak duality between problem
(Pλ) and problem (D${}_{m}^{\lambda}$) holds.

Conversely, suppose the weak duality between (Pλ) and (D${}_{m}^{\lambda}$)
holds. Lets $(0,\zeta)\in\mathcal{R}$ and $x^{\ast}\in\text{dom}\varphi$. By
definition, we have

$\left(x^{\ast},\zeta+\varphi\left(x^{\ast}\right)\right)\in\operatorname{epi}(\lambda^{-1}F+f)^{*}+\operatorname{cone}\left(\underset{i=1}{\bigcup^{k}}\operatorname{epi}G_{i}^{*}\cup\underset{j=1}{\bigcup^{p}}\operatorname{epi}g_{j}^{*}\right)+\operatorname{epi}\delta^{*}_{\mathbb{R}^{n}\times\mathbb{R}^{m}}.$

Then there exist
$\left(\left(z^{\ast},q^{\ast}\right);\gamma\right)\in\operatorname{epi}(\lambda^{-1}F+f)^{*}$,
$\left(\left(u_{i}^{\ast},v_{i}^{\ast}\right);\gamma_{i}\right)\in\operatorname{epi}G_{i}^{*}$,
$i=1,\cdots,k$,
$\left(\left(u_{j}^{\ast},v_{j}^{\ast}\right);\gamma_{j}\right)\in\operatorname{epi}g_{j}^{*}$,
$j=1,\cdots,p$, $\mu_{i}\in\mathbb{R}_{+}$, $i=1,\cdots,k$,
$\nu_{j}\in\mathbb{R}_{+}$, $j=1,\cdots,p$ and
$\left(\left(s^{\ast},t^{\ast}\right);\sigma\right)\in\operatorname{epi}\delta^{*}_{\mathbb{R}^{n}\times\mathbb{R}^{m}}$
such that

$\left(\left(x^{\ast},0\right),\zeta+\varphi\left(x^{\ast}\right)\right)=\left(\left(z^{\ast},q^{\ast}\right);\gamma\right)+{\displaystyle\sum^{k}_{i=1}}\
\mu_{i}\left(\left(u_{i}^{\ast},v_{i}^{\ast}\right);\gamma_{i}\right)+{\displaystyle\sum^{p}_{j=1}}\
\nu_{i}\left(\left(u_{j}^{\ast},v_{j}^{\ast}\right);\gamma_{j}\right)+\left(\left(s^{\ast},t^{\ast}\right);\sigma\right).$

Or equivalently,

$\begin{array}[]{rcl}\left(x^{\ast},0\right)&=&\left(z^{\ast},q^{\ast}\right)+{\displaystyle\sum^{k}_{i=1}}\
\mu_{i}\left(u_{i}^{\ast},v_{i}^{\ast}\right)+{\displaystyle\sum^{p}_{j=1}}\
\nu_{i}\left(u_{j}^{\ast},v_{j}^{\ast}\right)+\left(s^{\ast},t^{\ast}\right),\\\
\zeta+\varphi\left(x^{\ast}\right)&=&\gamma+{\displaystyle\sum^{k}_{i=1}}\
\mu_{i}\gamma_{i}+{\displaystyle\sum^{p}_{j=1}}\
\nu_{j}\gamma_{j}+\sigma.\end{array}$ (4.12)

Using the definition of epigraph, we obtain

$(\lambda^{-1}F+f)^{*}\left(z^{\ast},q^{\ast}\right)+{\displaystyle\sum^{k}_{i=1}}\
\mu_{i}G^{\ast}_{i}\left(u_{i}^{\ast},v_{i}^{\ast}\right)+{\displaystyle\sum^{p}_{j=1}}\
\nu_{j}g^{\ast}_{j}\left(u_{j}^{\ast},v_{j}^{\ast}\right)+\delta^{*}_{\mathbb{R}^{n}\times\mathbb{R}^{m}}\left(s^{\ast},t^{\ast}\right)\leq\zeta+\varphi\left(x^{\ast}\right).$

Hence,

$-\zeta\leq\varphi\left(x^{\ast}\right)-(\lambda^{-1}F+f)^{*}\left(z^{\ast},q^{\ast}\right)-{\displaystyle\sum^{k}_{i=1}}\
\mu_{i}G^{\ast}_{i}\left(u_{i}^{\ast},v_{i}^{\ast}\right)-{\displaystyle\sum^{p}_{j=1}}\
\nu_{j}g^{\ast}_{j}\left(u_{j}^{\ast},v_{j}^{\ast}\right)-\delta^{*}_{\mathbb{R}^{n}\times\mathbb{R}^{m}}\left(s^{\ast},t^{\ast}\right).$

Using the first equality in $\left(\ref{expression1}\right)$, we get
${\mathcal{V}}\eqref{form-3}\geqslant-\zeta$. Then
${\mathcal{V}}\eqref{calm3}\geqslant{\mathcal{V}}\eqref{form-3}\geqslant-\zeta$,
which implies that
$(0,\zeta)\in\operatorname{epi}\left(\lambda^{-1}F+f-\varphi+\delta_{\mathcal{S}}\right)^{*}$
by $\left(\ref{lemme-i}\right)$. Then the family
$\left((\lambda^{-1}F+f),\varphi,\delta_{\mathbb{R}^{n}\times\mathbb{R}^{m}},G_{i},g_{j}\right)$,
$i=1,\dots,k$, $j=1,\dots,p$ satisfies (SFRC). ∎

######  Theorem 4.11 (Strong Fenchel–Lagrange duality).

Let $\lambda>0$ and $F,f,G_{i},g_{j},i=1,\dots,k,j=1,\dots,p$ be proper convex
functions. The family
$\left((\lambda^{-1}F+f),\varphi,\delta_{\mathbb{R}^{n}\times\mathbb{R}^{m}},G_{i},g_{j}\right)$,
$i=1,\dots,k$, $j=1,\dots,p$ satisfies (FRC) if and only if the strong duality
between (Pλ) and (D${}_{m}^{\lambda}$) holds.

###### Proof.

Suppose that the family
$\left((\lambda^{-1}F+f),\varphi,\delta_{\mathbb{R}^{n}\times\mathbb{R}^{m}},G_{i},g_{j}\right)$,
$i=1,\dots,k$, $j=1,\dots,p$ satisfies $(FRC)$. Then, it satisfies $(SFRC)$.
By Theorem 4.10 ,
${\mathcal{V}}\eqref{calm3}\geqslant{\mathcal{V}}\eqref{form-3}$. Now, If
${\mathcal{V}}\eqref{calm3}=-\infty$, then we get strong duality for (Pλ) and
(D${}_{m}^{\lambda}$) via weak duality. So, we assume that
${\mathcal{V}}\eqref{calm3}=-\zeta\in\mathbb{R}$. Then, from
$\left(\ref{lemme-i}\right)$,

$(0,\zeta)\in\operatorname{epi}\left(\lambda^{-1}F+f-\varphi+\delta_{\mathcal{S}}\right)^{*}.$

Since the family
$\left((\lambda^{-1}F+f),\varphi,\delta_{\mathbb{R}^{n}\times\mathbb{R}^{m}},G_{i},g_{j}\right)$,
$i=1,\dots,k$, $j=1,\dots,p$ satisfies $(FRC)$, we have that
$(0,\zeta)\in\mathcal{R}$. Thus, from the proof of Theorem 4.10,
${\mathcal{V}}\eqref{form-3}\geqslant-\zeta$ and for any
$x^{*}\in\operatorname{dom}\varphi^{*}$, there exist
$\left(\left(z^{\ast},q^{\ast}\right);\gamma\right)\in\operatorname{epi}(\lambda^{-1}F+f)^{*}$,
$\left(\left(u_{i}^{\ast},v_{i}^{\ast}\right);\gamma_{i}\right)\in\operatorname{epi}G_{i}^{*}$,
$i=1,\cdots,k$,
$\left(\left(u_{j}^{\ast},v_{j}^{\ast}\right);\gamma_{j}\right)\in\operatorname{epi}g_{j}^{*}$,
$j=1,\cdots,p$, $\mu_{i}\in\mathbb{R}_{+}$, $i=1,\cdots,k$,
$\nu_{j}\in\mathbb{R}_{+}$, $j=1,\cdots,p$, and
$\left(\left(s^{\ast},t^{\ast}\right);\sigma\right)\in\operatorname{epi}\delta^{*}_{\mathbb{R}^{n}\times\mathbb{R}^{m}}$
such that

$-\zeta\leq\varphi\left(x^{\ast}\right)-(\lambda^{-1}F+f)^{*}\left(z^{\ast},q^{\ast}\right)-{\displaystyle\sum^{k}_{i=1}}\
\mu_{i}G^{\ast}_{i}\left(u_{i}^{\ast},v_{i}^{\ast}\right)-{\displaystyle\sum^{p}_{j=1}}\
\nu_{j}g^{\ast}_{j}\left(u_{j}^{\ast},v_{j}^{\ast}\right)-\delta^{*}_{\mathbb{R}^{n}\times\mathbb{R}^{m}}\left(s^{\ast},t^{\ast}\right).$

By Remark 4.9, we obtain the strong duality between (Pλ) and
(D${}_{m}^{\lambda}$).

Conversely, assuming that strong duality between (Pλ) and
(D${}_{m}^{\lambda}$) holds, then by Remark 4.9, we have the equality
${\mathcal{V}}\eqref{calm3}={\mathcal{V}}\eqref{form-3}$ and for any
$x^{*}\in\operatorname{dom}\varphi^{*}$, there exist
$\left(z^{\ast},q^{\ast}\right)\in\operatorname{dom}(\lambda^{-1}F+f)^{*}$,
$\left(u_{i}^{\ast},v_{i}^{\ast}\right)\in\operatorname{dom}G_{i}^{*}$,
$i=1,\cdots,k$,
$\left(u_{j}^{\ast},v_{j}^{\ast}\right)\in\operatorname{dom}g_{j}^{*}$,
$j=1,\cdots,p$, $\mu_{i}\in\mathbb{R}_{+}$, $i=1,\cdots,k$,
$\nu_{j}\in\mathbb{R}_{+}$, $j=1,\cdots,p$ and
$\left(s^{\ast},t^{\ast}\right)\in\mathbb{R}^{n}\times\mathbb{R}^{m}$ such
that we have

$\varphi\left(x^{\ast}\right)-(\lambda^{-1}F+f)^{*}\left(z^{\ast},q^{\ast}\right)-{\displaystyle\sum^{k}_{i=1}}\
\mu_{i}G^{\ast}_{i}\left(u_{i}^{\ast},v_{i}^{\ast}\right)-{\displaystyle\sum^{p}_{j=1}}\
\nu_{j}g^{\ast}_{j}\left(u_{j}^{\ast},v_{j}^{\ast}\right)-\delta^{*}_{\mathbb{R}^{n}\times\mathbb{R}^{m}}\left(s^{\ast},t^{\ast}\right)\geqslant{\mathcal{V}}\eqref{form-3},$

with
$s^{\ast}=x^{\ast}-z^{*}-\displaystyle\sum_{i=1}^{k}\alpha_{i}u_{i}^{*}-\sum_{j=1}^{p}\beta_{j}u_{j}^{*}$,
and
$t^{\ast}=-q^{\ast}-\displaystyle\sum_{i=1}^{k}\alpha_{i}v_{i}^{*}-\sum_{j=1}^{p}\beta_{j}v_{j}^{*}$.
Let
$(0,\zeta)\in\operatorname{epi}\left(\lambda^{-1}F+f-\varphi+\delta_{\mathcal{S}}\right)^{*}$.
By $\left(\ref{lemme-i}\right)$, ${\mathcal{V}}\eqref{calm3}\geqslant-\zeta$.
Then, from the strong duality,
${\mathcal{V}}\eqref{form-3}={\mathcal{V}}\eqref{calm3}\geqslant-\zeta$. By
the proof of Theorem 4.10, $(0,\zeta)\in\mathcal{R}$ and hence, the result.∎

###  4.3 Duality under the closedness condition

In the above subsections, the Slater condition, (FRC), and (SFRC) are used.
However, these conditions are often not satisfied for many problems in
applications. To overcome this drawback, we use another constraint
qualification, labeled as “closedness condition”, which has been developed and
used for convex (infinite) optimization problems. In this case, a Toland-
Fenchel-Lagrange duality is investigated. To proceed, let us assume that
$\mathcal{S}\cap\operatorname{dom}(\lambda^{-1}F+f)\neq\emptyset$ and $F$,
$f$, and $\varphi$ are functions such that $F$ and $f$ are proper lower
semicontinuous (l.s.c.) and convex, while $\varphi$ is proper convex and
satisfies $\varphi^{**}=\varphi$. Here, $\mathcal{S}$ is the feasible set of
(Pλ) stated in $\left(\ref{eq4}\right)$.

We denote ${\mathcal{A}}$ by

$\mathcal{A}:=\underset{\alpha\in\mathbb{R}_{+}^{k}}{\bigcup}\operatorname{epi}(\alpha
G)^{*}\bigcup\underset{\beta\in\mathbb{R}_{+}^{p}}{\bigcup}\operatorname{epi}(\beta
g)^{*}+\operatorname{epi}\delta^{*}_{\mathbb{R}^{n}\times\mathbb{R}^{m}},$

and introduce the closedness condition defined by

$\operatorname{epi}(\lambda^{-1}F+f)^{*}+\mathcal{A}\ \text{ is closed}.$ (CC)

The closedness condition (CC) can be traced to Burachik and Jeyakumar [9] and
was used later to derive optimality conditions for convex cone constrained
optimization problems. Different types of sufficient conditions for (CC) are
given in [9].

We are interested here in another form of duality called Tolland-Fenchel-
Lagrange duality, which takes the following form:

$\begin{array}[]{l}\inf_{(x^{*},y^{*})\in\mathbb{R}^{n}\times\mathbb{R}^{m}}\
\underset{\underset{\left(\alpha,\beta\right)\in\mathbb{R}_{+}^{k+p}}{\left(z^{\ast},q^{\ast}\right)\in\mathbb{R}^{n+m}}}{\max}\
\left\\{{\varphi}^{*}(x^{*})+\delta_{\mathbb{R}^{m}}^{\ast}\left(y^{\ast}\right)\right.\\\
\qquad\qquad\qquad-\left.\left(\lambda^{-1}F+f\right)^{*}\left(z^{\ast},q^{\ast}\right)-\left(\alpha
G+\beta
g\right)^{\ast}\left(x^{\ast}-z^{\ast},y^{\ast}-q^{\ast}\right)\right\\}.\end{array}$
(D${}_{TFL}^{\lambda}$)

######  Theorem 4.12.

Consider the primal and the dual problem (Pλ) and (D${}_{TFL}^{\lambda}$).
Suppose the constaint qualification (CC) holds. Then, the strong duality
holds; i.e., ${\mathcal{V}}\eqref{calm3}={\mathcal{V}}\eqref{cc-dual}$.

###### Proof.

By definition of a primal problem,

${\mathcal{V}}\eqref{calm3}=\inf_{(x,y)\in\mathbb{R}^{n}\times\mathbb{R}^{m}}\left(\lambda^{-1}F+f+\delta_{\mathcal{S}}-{\varphi}\right)(x,y).$

Using the classical Toland dulality, we obtain

${\mathcal{V}}(\mathcal{P}^{\lambda})=\inf_{(x^{*},y^{*})\in\mathbb{R}^{n}\times\mathbb{R}^{m}}\left\\{{\varphi}^{*}(x^{*})+\delta_{\mathbb{R}^{m}}^{\ast}\left(y^{\ast}\right)-\left(\lambda^{-1}F+f+\delta_{\mathcal{S}}\right)^{*}\left(x^{*},y^{*}\right)\right\\}.$
(4.13)

Now, consider the function
$\psi:\mathbb{R}^{n+m}\times\mathbb{R}^{n+m}\times\mathbb{R}^{k+p}\rightarrow\mathbb{R}\cup\\{+\infty\\}$
given by

$\psi\left(x,y,z,q,\nu,\mu\right)=\left\\{\begin{array}[]{lcl}\left(\lambda^{-1}F+f\right)\left(x+z,y+q\right),&&\text{if}\
\left(G\left(x,y\right),g\left(x,y\right)\right)+\left(\nu,\mu\right)\in-\mathbb{R}_{+}^{k+p},\\\
+\infty&&\text{otherwise}.\end{array}\right.$

Let
$\left(x^{\ast},y^{\ast},z^{\ast},q^{\ast},\alpha,\beta\right)\in\mathbb{R}^{n+m}\times\mathbb{R}^{n+m}\times\mathbb{R}^{k+p}$.
Using the same technique as in [5], we calculate the conjugate of $\psi$ as

$\psi^{\ast}\left(x^{\ast},y^{\ast},z^{\ast},q^{\ast},\alpha,\beta\right)=\left(\lambda^{-1}F+f\right)^{*}\left(z^{\ast},q^{\ast}\right)+\left(\alpha
G+\beta
g\right)^{\ast}\left(x^{\ast}-z^{\ast},y^{\ast}-q^{\ast}\right)+\delta_{-\mathbb{R}_{+}^{k+p}}^{\ast}\left(\alpha,\beta\right).$

Observing that
$\delta_{-\mathbb{R}_{+}^{k+p}}^{\ast}\left(\alpha,\beta\right)=0$ if
$\left(\alpha,\beta\right)\in\mathbb{R}_{+}^{k+p}$, one deduces from the last
equality that

$\begin{array}[]{l}\psi^{\ast}\left(x^{\ast},y^{\ast},z^{\ast},q^{\ast},\alpha,\beta\right)=\\\
\qquad\qquad\left\\{\begin{array}[]{lcl}\left(\lambda^{-1}F+f\right)^{*}\left(z^{\ast},q^{\ast}\right)+\left(\alpha
G+\beta
g\right)^{\ast}\left(x^{\ast}-z^{\ast},y^{\ast}-q^{\ast}\right)&&\text{if}\
\left(\alpha,\beta\right)\in\mathbb{R}_{+}^{k+p},\\\
+\infty&&\text{otherwise}.\end{array}\right.\end{array}$

On the other hand, we have

$\begin{array}[]{lcl}\left(\lambda^{-1}F+f+\delta_{\mathcal{S}}\right)^{*}\left(x^{*},y^{*}\right)&=&{\displaystyle\sup_{\left(x,y\right)\in{\mathcal{S}}}}\
\\{\langle\left(x,y\right),\left(x^{\ast},y^{\ast}\right)\rangle-\left(\lambda^{-1}F+f\right)\left(x,y\right)\\}\\\
&=&{\displaystyle\sup_{\left(x,y\right)\in\mathbb{R}^{n}\times\mathbb{R}^{m}}}\
\\{\langle\left(x,y\right),\left(x^{\ast},y^{\ast}\right)\rangle-\psi\left(x,y,0,0,0,0\right)\\}.\end{array}$
(4.14)

Since,
$Pr_{\mathbb{R}^{n}\times\mathbb{R}^{m}\times\mathbb{R}}\left(\text{epi}\
\psi^{\ast}\right)=\operatorname{epi}(\lambda^{-1}F+f)^{*}+\mathcal{A}$, it
follows from [10, Theorem 3.1] that for all
$\left(x^{\ast},y^{\ast}\right)\in\mathbb{R}^{n}\times\mathbb{R}^{m}$,

$\begin{array}[]{l}{\displaystyle\sup_{\left(x,y\right)\in\mathbb{R}^{n}\times\mathbb{R}^{m}}}\
\\{\langle\left(x,y\right),\left(x^{\ast},y^{\ast}\right)\rangle-\psi\left(x,y,0,0,0,0\right)\\}\\\
\qquad\qquad\qquad\qquad\qquad\quad={\displaystyle\min_{\left(z^{\ast},q^{\ast}\right)\in\mathbb{R}^{n+m},\left(\alpha,\beta\right)\in\mathbb{R}^{k+p}}}\
\psi^{\ast}\left(x^{\ast},y^{\ast},z^{\ast},q^{\ast},\alpha,\beta\right).\end{array}$
(4.15)

Combining $\left(\ref{cc-p1}\right)$ and $\left(\ref{cc-p2}\right)$, we arrive
at

$\begin{array}[]{l}\left(\lambda^{-1}F+f+\delta_{\mathcal{S}}\right)^{*}\left(x^{*},y^{*}\right)\\\
\qquad\qquad\qquad={\displaystyle\min_{\left(z^{\ast},q^{\ast}\right)\in\mathbb{R}^{n+m},\left(\alpha^{\ast},\beta^{\ast}\right)\in\mathbb{R}_{+}^{k+p}}}\
\left(\lambda^{-1}F+f\right)^{*}\left(z^{\ast},q^{\ast}\right)+\left(\alpha^{\ast}G+\beta^{\ast}g\right)^{\ast}\left(x^{\ast}-z^{\ast},y^{\ast}-q^{\ast}\right).\end{array}$

Inserting the latter equality in $\left(\ref{eq8}\right)$ we obtain

$\begin{array}[]{l}{\mathcal{V}}\eqref{calm3}=\inf_{(x^{*},y^{*})\in\mathbb{R}^{n}\times\mathbb{R}^{m}}\
\underset{\underset{\left(\alpha,\beta\right)\in\mathbb{R}_{+}^{k+p}}{\left(z^{\ast},q^{\ast}\right)\in\mathbb{R}^{n+m}}}{\max}\
\left\\{{\varphi}^{*}(x^{*})+\delta_{\mathbb{R}^{m}}^{\ast}\left(y^{\ast}\right)\right.\\\
\qquad\qquad\qquad-\left.\left(\lambda^{-1}F+f\right)^{*}\left(z^{\ast},q^{\ast}\right)-\left(\alpha
G+\beta
g\right)^{\ast}\left(x^{\ast}-z^{\ast},y^{\ast}-q^{\ast}\right)\right\\}.\end{array}$

Hence, ${\mathcal{V}}\eqref{calm3}={\mathcal{V}}\eqref{cc-dual}.$ ∎

##  5 Duality without partial calmness

###  5.1 Under a generalized Slater condition

In this section, we do not assume that (P) has optimal solutions, also no
convexity assumption is imposed. Let $\epsilon>0$ and consider the following
reguralized problem of (P)

${\displaystyle\min_{x,y}}\ F\left(x,y\right)\ \text{s.t.}\
G_{i}\left(x,y\right)\leq 0,\;\;i\in
I_{k}:=\\{1,\cdots,k\\},\;\;y\in{\mathcal{S}}_{\epsilon}\left(x\right),$ (Pϵ)

where for each $x\in\mathbb{R}^{n}$, ${\mathcal{S}}_{\epsilon}\left(x\right)$
is the set of $\epsilon$-approximate optimal solutions of the lower level
problem (L[$x$]); that is

${\mathcal{S}}_{\epsilon}\left(x\right)=\\{y\in
K\left(x\right)|\;\;f\left(x,y\right)-\varphi\left(x\right)\leq\epsilon\\}.$

Then, it is clear that problem (Pϵ) can be reformulated as the following
single-level optimization problem involving the optimal value function:

$\left\\{\begin{array}[]{ll}{\displaystyle\min_{x,y}}\ F(x,y)\\\\[3.44444pt]
G_{i}(x,y)\leq 0&\forall i\in I_{k}=\\{1,\dots,k\\},\\\ g_{j}(x,y)\leq
0&\forall j\in I_{p}=\\{1,\dots,p\\},\\\ f(x,y)-\varphi(x)\leq\epsilon.\\\
\end{array}\right.$ (LLVFϵ)

Next, we recall the relation between any accumulation point of a sequence of
regularized optimal solutions (i.e., of problem (LLVFϵ)) and the optimal
solution of (P). To this end, let $\left(\epsilon_{k}\right)_{k}$ be a
sequence of positive scalar such that $\epsilon_{k}\searrow 0$, we denote
problem $\left(\mbox{LLVF}_{\epsilon_{k}}\right)$ by
$\left(\mbox{LLVF}_{k}\right)$. We need the following Slater-type condition
for the lower level problem:

######  Assumption 5.1.

For any $x\in\mathbb{R}^{n}$ satisfying the upper-level inequality
constraints, and any nonempty subset $J_{p}$ of $I_{p}$, there exist
$y\in\mathbb{R}^{m}$ such that $g_{j}\left(x,y\right)<0$ for all $j\in J_{p}$.

######  Theorem 5.1.

[3] Let $\left(\epsilon_{k}\right)_{k}$ a sequence of positive scalar such
that $\epsilon_{k}\searrow 0$ and $\left(x_{k},y_{k}\right)_{k}$ be a sequence
of optimal solutions of the regularized problems
$\left(\mbox{LLVF}_{k}\right)$ with $k\in\mathbb{N}$. Suppose that

  1. 1.

${\mathcal{C}}:=\\{\left(x,y\right)\in\mathbb{R}^{n}\times\mathbb{R}^{m}|\;\;G_{i}\left(x,y\right)\leq
0,\;\;i\in I_{k}\\}$ is a compact set;

  2. 2.

$\left(\bar{x},\bar{y}\right)$ is an accumulation point of the sequence
$\left(x_{k},y_{k}\right)_{k}$;

  3. 3.

Assumption 5.1 holds.

Then, $\left(\bar{x},\bar{y}\right)$ is an optimal solution of problem (LLVF).

Subsequently, based on the study given by Fabin, Fernando, and Cristian [15],
we give a formulation of dual problem of (LLVFϵ), then we provide a new
complete characterization of strong duality. To proceed, for any $\epsilon>0$,
we consider the Lagrangian

$L_{\epsilon}\left(\varsigma,\alpha,\beta,\gamma,x,y\right):=\varsigma
F(x,y)+\gamma\left(f(x,y)-\varphi(x)-\epsilon\right)+{\displaystyle\sum_{i=1}^{k}}\
\alpha_{i}G_{i}(x,y)+{\displaystyle\sum_{j=1}^{p}}\ \beta_{j}g_{j}(x,y)$

and define the dual problem (Dϵ) of (LLVFϵ) as

$\underset{\underset{\gamma\in\mathbb{R}}{\left(\alpha,\beta\right)\in\mathbb{R}_{+}^{k+p}}}{\sup}\
{\displaystyle\inf_{\left(x,y\right)\in\mathbb{R}^{n}\times\mathbb{R}^{m}}}\
L_{\epsilon}\left(1,\alpha,\beta,\gamma,x,y\right).$ (Dϵ)

It can be seen that for all $\alpha\in\mathbb{R}_{+}^{k}$,
$\beta\in\mathbb{R}_{+}^{p}$, and $\gamma\in\mathbb{R}$, we have

${\displaystyle\inf_{\left(x,y\right)\in\mathbb{R}^{n}\times\mathbb{R}^{m}}}\
L_{\epsilon}\left(\varsigma,\alpha,\beta,\gamma,x,y\right)\;\;\leq\;\;\varsigma{\mathcal{V}}\left({\mathcal{P}}_{\epsilon}\right),\;\;\,\forall\varsigma\geq
0,$

which corresponds to a weak duality condition. To provide the strong duality
result, we introduce some regularity conditions. To proceed, define

$\Psi_{\epsilon}\left(\mathbb{R}^{n}\times\mathbb{R}^{m}\right):=\left\\{\left(F(x,y),\,f(x,y)-\varphi\left(x\right)-\epsilon,\,G(x,y),\,g(x,y)\right)\in\mathbb{R}^{2+k+p}:\;\,(x,y)\in\mathbb{R}^{n}\times\mathbb{R}^{m}\right\\}$

and consider the following assumptions:

######  Assumption 5.2.

It holds that

$\text{cone}\
\bigg{(}int\bigg{[}\text{co}\left(\Psi_{\epsilon}\left(\mathbb{R}^{n}\times\mathbb{R}^{m}\right)\right)-{\mathcal{V}}\eqref{w-p-
c-P}\left(1,0_{\mathbb{R}^{1+k+p}}\right)+\left(\mathbb{R}_{+}\times\mathbb{R}^{1+k+p}_{+}\right)\bigg{]}\bigg{)}\;\;\mbox{
is pointed.}$

######  Assumption 5.3.

$\left(0,0\right)\notin
int\bigg{(}\text{co}\left(\Psi_{\epsilon}\left(\mathbb{R}^{n}\times\mathbb{R}^{m}\right)\right)-{\mathcal{V}}\eqref{w-p-
c-P}\left(1,0_{\mathbb{R}^{1+k+p}}\right)+\left(\mathbb{R}_{+}\times\mathbb{R}^{1+k+p}_{+}\right)\bigg{)}$.

######  Theorem 5.2.

Let $\epsilon>0$. Suppose that ${\mathcal{V}}\eqref{w-p-c-P}$ is finite and
that

$int\bigg{(}\text{co}\left(\Psi_{\epsilon}\left(\mathbb{R}^{n}\times\mathbb{R}^{m}\right)\right)+\left(\mathbb{R}_{+}\times\mathbb{R}^{1+k+p}_{+}\right)\bigg{)}\neq\emptyset.$
(5.1)

Then, for each $\epsilon>0$, Assumption 5.2 (resp. Assumption 5.3) holds if
and only if there exists a vector
$\left(\bar{\varsigma},\bar{\gamma},\bar{\alpha},\bar{\beta}\right)\neq 0$
such that

${\displaystyle\inf_{\left(x,y\right)\in\mathbb{R}^{n}\times\mathbb{R}^{m}}}\
L_{\epsilon}\left(\bar{\varsigma},\bar{\alpha},\bar{\beta},\bar{\gamma},x,y\right)=\bar{\varsigma}{\mathcal{V}}\eqref{w-p-
c-P}.$

###### Proof.

The result follows from [15, Theorem 3.1]. ∎

Next, we provide a strong duality result when $\bar{\varsigma}>0$. For this
result, we need the assumption

$\overline{cone}\,\left(\left(f-\varphi-\epsilon,\;G,\;g\right)\left(\mathbb{R}^{n}\times\mathbb{R}^{m}\right)+\mathbb{R}_{+}^{1+k+p}\right)=\mathbb{R}^{1+k+p}.$
(5.2)

The qualification condition (5.2) is a generalized form of the Slater
condition for problem (LLVFϵ). Note that thanks to our regularization,
condition (5.2) can be fulfilled.

######  Theorem 5.3.

Let $\epsilon>0$ and suppose that ${\mathcal{V}}\eqref{w-p-c-P}$ is finite and
condition (5.1) holds. Furthermore, if condition (5.2) is satisfied, then
strong duality between (LLVFϵ) and (Dϵ) holds; i.e., ${\mathcal{V}}\eqref{w-p-
c-P}={\mathcal{V}}\eqref{dual-w-p-c-P}$. Moreover, there exists a Lagrange
multiplier vector
$\left(\bar{\gamma},\bar{\alpha},\bar{\beta}\right)\in\mathbb{R}_{+}\times\mathbb{R}^{k}_{+}\times\mathbb{R}^{p}_{+}$
such that we have

${\mathcal{V}}\eqref{w-p-
c-P}={\displaystyle\inf_{\left(x,y\right)\in\mathbb{R}^{n}\times\mathbb{R}^{m}}}\
L_{\epsilon}\left(1,\bar{\alpha},\bar{\beta},\bar{\gamma},x,y\right).$

###### Proof.

The result follows from [15, Corollary 3.2]. ∎

###  5.2 Without a Slater condition

To close this section, we provide a new characterization of strong duality for
bilevel optimization problem, covering situations where a Slater-type
condition may fail. To proceed, consider the special bilevel program

${\displaystyle\min_{x,y}}\ F\left(x,y\right)\ \text{s.t.}\ x\in
X,y\in{\mathcal{S}}\left(x\right),$ (Ps)

where, $X\subset\mathbb{R}^{n}$ and for each $x\in X$,
${\mathcal{S}}\left(x\right)$ is the set of optimal solutions of the lower
level problem (L[$x$]), which in this case is given

${\mathcal{S}}\left(x\right)=\left\\{y\in
Y|\;f\left(x,y\right)-\varphi\left(x\right)\leq 0\right\\},$

where the lower level feasible set is $Y\subset\mathbb{R}^{m}$. As before,
problem (Ps) can take the form

$\left\\{\begin{array}[]{l}{\displaystyle\min_{x,y}}\ F\left(x,y\right)\\\
\left(x,y\right)\in X\times Y,\\\ f\left(x,y\right)-\varphi\left(x\right)\leq
0.\end{array}\right.$ (LLVFs)

With
$L\left(1,\gamma,x,y\right):=F\left(x,y\right)+\gamma\left(f\left(x,y\right)-\varphi\left(x\right)\right)$,
the dual of problem (Ds) is given by

${\displaystyle\sup_{\gamma\in\mathbb{R}_{+}}}\
{\displaystyle\inf_{\left(x,y\right)\in X\times Y}}\
L\left(1,\gamma,x,y\right).$ (Ds)

To provide our result, denote the feasible set of problem (LLVFs) by

${\mathcal{F}}:=\left\\{\left(x,y\right)\in X\times
Y|\;\,f\left(x,y\right)-\varphi\left(x\right)\leq 0\right\\}.$

The set of optimal solutions of problem (LLVFs) is given as

${\mathcal{O}}:=\arg\min\left\\{F\left(x,y\right)|\left(x,y\right)\in{\mathcal{F}}\right\\}$

and

$\begin{array}[]{lcl}{\mathcal{F}}^{-}&:=&\\{\left(x,y\right)\in X\times
Y|\;\,f\left(x,y\right)-\varphi\left(x\right)<0\\},\\\
{\mathcal{F}}^{=}&:=&\\{\left(x,y\right)\in X\times
Y|\;\,f\left(x,y\right)-\varphi\left(x\right)=0\\},\\\
{\mathcal{F}}^{+}&:=&\\{\left(x,y\right)\in X\times
Y|\;\,f\left(x,y\right)-\varphi\left(x\right)>0\\}.\end{array}$

Analogously, we introduce the following sets

$\begin{array}[]{lcl}\Xi^{-}&:=&\\{\left(x,y\right)\in X\times
Y|\;\,F\left(x,y\right)<{\mathcal{V}}\eqref{spe-bilevel-llvf}\\},\\\
\Xi^{=}&:=&\\{\left(x,y\right)\in X\times
Y|\;\,F\left(x,y\right)={\mathcal{V}}\eqref{spe-bilevel-llvf}\\},\\\
\Xi^{+}&:=&\\{\left(x,y\right)\in X\times
Y|\;\,F\left(x,y\right)>{\mathcal{V}}\eqref{spe-bilevel-llvf}\\}.\end{array}$

######  Remark 5.4.

Based on the structure of bilevel optimization problems, one can deduce that
we have ${\mathcal{F}}^{-}={\mathcal{F}}^{+}=\emptyset$.

Also, due to the lack of the Slater condition, the strong duality requires a
closed-cone constraint qualification. To proceed, set

$\Psi\left(X\times
Y\right)=\left\\{\left(F\left(x,y\right),\,f\left(x,y\right)-\varphi\left(x\right)\right)\in\mathbb{R}^{2}\left|(x,y)\in
X\times Y\right.\right\\},$

and consider the following assumption

######  Assumption 5.4.

$\text{cone}\ \left(\text{co}\left(\Psi\left(X\times
Y\right)\right)-{\mathcal{V}}\eqref{spe-bilevel-
llvf}\left(1,0\right)+int\left(\mathbb{R}^{2}_{+}\right)\right)$ is pointed.

Based on the above construction we characterize Assumption 5.4.

######  Proposition 5.5.

Consider the problem (LLVFs). Suppose that ${\mathcal{F}}\neq\emptyset$ and
that ${\mathcal{V}}\eqref{spe-bilevel-llvf}$ is finite. The following
assertions hold:

  1. 1.

Suppose that ${\mathcal{O}}\neq\emptyset$. Then, $\text{cone}\
\bigg{(}\text{co}\left(\Psi\left(X\times
Y\right)\right)-{\mathcal{V}}\eqref{spe-bilevel-
llvf}\left(1,0\right)+int\left(\mathbb{R}^{2}_{+}\right)\bigg{)}$ is pointed
if and only if ${\mathcal{O}}\cap{\mathcal{F}}^{=}\neq\emptyset$ and
$\Xi^{+}\cap{\mathcal{F}}^{=}\neq\emptyset$.

  2. 2.

Assume that ${\mathcal{O}}=\emptyset$. Then, $\text{cone}\
\bigg{(}\text{co}\left(\Psi\left(X\times
Y\right)\right)-{\mathcal{V}}\eqref{spe-bilevel-
llvf}\left(1,0\right)+int\left(\mathbb{R}^{2}_{+}\right)\bigg{)}$ is pointed
if and only if $\Xi^{+}\cap{\mathcal{F}}^{=}\neq\emptyset$.

The following theorem provides a complete characterization of strong duality
for our bilevel program.

######  Theorem 5.6.

Consider problem (LLVFs). Assume that ${\mathcal{F}}\neq\emptyset$ and that
${\mathcal{V}}\eqref{spe-bilevel-llvf}$ is finite. The following assertions
are equivalent.

  1. 1.

Strong duality holds; i.e., ${\mathcal{V}}\eqref{spe-bilevel-
llvf}={\mathcal{V}}\eqref{dual-spe-bilevel-llvf}$;

  2. 2.

$\text{cone}\ \bigg{(}\text{co}\left(\Psi\left(X\times
Y\right)\right)-{\mathcal{V}}\eqref{spe-bilevel-
llvf}\left(1,0\right)+int\left(\mathbb{R}^{2}_{+}\right)\bigg{)}$ is pointed.

###### Proof.

It can be deduced from Proposition 5.5; cf. [15, Theorem 4.1 and Corollary
4.2]. ∎

##  6 Conclusion

In this paper, we have been given a duality approach for problem (P). Since
the bilevel programming problem (P) does not satisfy the Slater condition,
which is the key apparatus to establish strong duality, we have first provided
an overview of some standard duality results to show that they are not
applicable to our problem (P). Afterwards, the concept of partial calmness is
used to establish weak and strong duality results for problem (P). In
particular, Langrange, Fenchel-Lagrange, and Toland-Fenchel-Lagrange duality
concepts were investigated for this problem, under some suitable conditions.
For the first class of results, we introduce a regularization for problem (P).
Then, we establish sufficient conditions ensuring strong duality for the
obtained regularized problem (P) under a generalized Slater-type condition
without the convexity assumptions and without. Finally, we have provided a
strong duality result for a geometrically constrained bilevel optimization
problem without the Slater-condition.

## References

  * [1] A. Aboussoror, S. Adly and F.E. Saissi, A Duality approach for a alass of semivectorial bilevel programming problems, Vietnam journal of mathematics. 46 (2018) 197-214.
  * [2] A. Aboussoror and S. Adly, A Fenchel-Lagrange duality approach for a bilevel programming problem with extremal value function, Journal of Optimization Theory and Applications. 149 (2011) 254-268.
  * [3] A. Aboussoror, S. Adly and F.E. Saissi, An extended Fenchel-Lagrange duality approach and optimality conditions for strong bilevel programming problems, SIAM Journal on Optimization. 27(2) (2017) 1230-1255.
  * [4] R.I. Bot, E.R. Csetnek and A. Moldovan, Revisiting some duality theorems via the quasirelative interior in convex optimization, Journal of Optimization Theory and Applications. 139 (2008) 67-84.
  * [5] R.I. Bot, E.R. Csetnek and G. Wanka, Sequential optimality conditions in convex programming via perturbation approach, Journal of Convex Analysis. 15 (2008) 149-164.
  * [6] R.I. Bot, I.B.Hodrea and G. Wanka, Some new Farkas-type results for inequality systems with DC functions, Faculty of Mathematics, Chemnitz University of Technology. D-09107 Chemnitz, Germany, 2007.
  * [7] R.I. Bot, G. Kassay and G. Wanka, Strong duality for generalized convex optimization problems, Journal of Optimization Theory and Applications. 127 (2005) 45-70.
  * [8] R.I. Bot and G. Wanka, On the relations between different dual problems in convex mathematical programming, Operations Research Proceedings. (2001) 255-262.
  * [9] R.S. Burachik and V. Jeyakumar, A dual condition for the convex subdifferential sum formula with applications, Journal of Convex Analysis. 12 (2005) 279-290.
  * [10] R.S. Burachik, V. Jeyakumar and Z.Y. Wu, Necessary and sufficient conditions for stable conjugate duality, nonlinear analysis theory methods and applications. 64 (2006) 1998-2006.
  * [11] S. Dempe, Foundations of bilevel programming, Kluwer Academic Publishers, 2002.
  * [12] S. Dempe and S. Dutta, Is bilevel programming a special case of mathematical programming with equilibrium constraints? Mathematical Programming. 131(1-2) (2012) 37-48.
  * [13] S. Dempe and A.B. Zemkoho, Bilevel Optimization: Advances and Next Challenges, Springer, 2020.
  * [14] I. Ekeland and R. Temam, Convex analysis and variational problems, Amsterdam: NorthHolland Publishing Company, 1976.
  * [15] F-B. Fabin, F-B. Fernando and V. Cristian, A complete characterization of strong duality in nonconvex optimization with a single constraint, Journal of Global Optimization. 53 (2012) 185-201.
  * [16] D.H. Fang, C. Li and K.F. Ng, Constraint qualifications for extended Farkas’s lemmas and Lagrangian dualities in convex infinite programming, SIAM Journal on Optimization. 20 (2009) 1311-1332.
  * [17] J. Gauvin and F. Dubeau, Differential properties of the marginal function in mathematical programming, Mathematics programmes of study. 18 (1982) 101-119.
  * [18] J.E. Martinez-Legaz and M. Volle, Duality in D.C. programming: The case of several D.C. constraints, Journal of Mathematical Analysis and Applications. 237 (1999) 657-671.
  * [19] R.T. Rockafellar, Convex analysis, Princeton: Princeton University Press, 1970.
  * [20] R.T. Rockafellar and R.J-B. Wets, Variational Analysis, Springer-Verlag, Berlin, Heidelberg, 1998.
  * [21] Y. Shehu, P.T. Vuong and A.B. Zemkoho, An inertial extrapolation method for convex simple bilevel optimization, Optimization Methods and Software. 36(1) (2021) 1-19.
  * [22] X-K. Sun, Regularity conditions characterizing Fenchel-Lagrange duality and Farkas-type results in DC infinite programming, Journal of Mathematical Analysis and Applications. 414 (2014) 590-611.
  * [23] J.J. Ye and D.L. Zhu, Optimality conditions for bilevel programming problems. Optimization. 33 (1995) 9-27. With Erratum in Optimization, 39 (1997) 361-366.
  * [24] C. Z$\check{a}$linescu, Convex Analysis in General Vector Spaces, World Scientific, River Edge, New Jersey, 2002.