\subsection{Notation}
In this paper, we will consider functions from $\HH$ to $\RX$.
The fact that we allow functions to take $+\infty$ value is useful in modern optimization to
discard some ``forbidden part" of the space when searching for an optimal solution
(for example, in image processing problems, the components of the solution often are intensity values which must be nonnegative).
The \emph{domain} of a function $f\colon \HH \to \RX$ is the subset of $\HH$ where this function takes finite values, i.e.
$\dom f = \menge{x\in \HH}{f(x) < +\infty}$. A function with a nonempty domain is said to be
\emph{proper}. A function $f$ is \emph{convex} if 
\begin{equation}
\big(\forall (x,y)\in (\HH)^2\big)
(\forall \lambda \in [0,1])\qquad f(\lambda x + (1-\lambda) y) \le \lambda f(x) + (1-\lambda) f(y).
\end{equation}
The class of functions for which most of the main results in convex analysis have been established
is $\Gamma_0(\HH)$, the class of proper, convex, lower-semicontinuous functions from
$\HH$ to $\RX$. Recall that a function  $f\colon \HH \to \RX$ is lower-semicontinuous if its \emph{epigraph}
$\epi f = \menge{(x,\zeta) \in \dom f \times \RR}{f(x) \le \zeta}$ is a closed set (see Fig. \ref{fig:lowersemi}).

\begin{figure}[htb]
\begin{center}
\begin{tabular}{@{}c@{}c@{}}
\scalebox{1.0}{\input{sci_ex1.pstex_t}} \hspace{1cm} & \hspace{1cm}  \scalebox{1.0}{\input{sci_ex2w.pstex_t}}
\end{tabular}
\end{center}
\caption{\small Illustration of the lower-semicontinuity property.}\label{fig:lowersemi}
\end{figure}

If $C$ is a nonempty subset of $\HH$, the \emph{indicator function} of $C$ is defined as
\begin{equation}\label{e:defindicator}
(\forall x \in \HH) \qquad \iota_C(x) = \begin{cases}
0 & \mbox{if $x\in C$}\\
+\infty & \mbox{otherwise.}
\end{cases}
\end{equation}
This function belongs to $\Gamma_0(\HH)$ if and only if $C$ is a nonempty closed convex set.


The Moreau \emph{subdifferential} of a function $f\colon \HH \to \RX$ at $x\in \HH$ is defined as
\begin{equation}
\partial f(x) = \menge{u\in\HH}{(\forall y \in \HH)\;\; f(y) \ge f(x)+\scal{(y-x)}{u}}.
\end{equation}
Any vector $u$ in $\partial f(x)$ is called a \emph{subgradient} of $f$ at $x$ (see Fig. \ref{fig:subgrad}).

\begin{figure}[htb]
\begin{center}
\begin{tabular}{@{}c@{}c@{}}
\scalebox{1.0}{\input{sousdiff1.pstex_t}} \hspace{1cm} & \hspace{1cm}  \scalebox{1.0}{\input{sousdiff4.pstex_t}}
\end{tabular}
\end{center}
\caption{\small Examples of subgradients $u$ of a function $f$ at $x$.}\label{fig:subgrad}
\end{figure}


Fermat's rule states that $0$ is a subgradient of $f$ at $x$ if and only if $x$
belongs to the set 
of global minimizers of $f$.
If $f$ is a proper convex function which is differentiable at $x$, then its subdifferential
at $x$ reduces to the singleton consisting of its gradient, i.e. $\partial f(x) = \{\nabla f(x)\}$.
Note that, in the nonconvex case, extended definitions of the subdifferential may be useful such as
the \emph{limiting subdifferential} \cite{Mordukhovich06}, but this one reduces to the Moreau subdifferential when the function
is convex.

\subsection{Proximity operator}
A concept which has been of growing importance in recent developments in optimization is the concept of \emph{proximity
operator}. It must be pointed out that the proximity operator was introduced in the early work by J.~J.~Moreau (1923-2014) \cite{Moreau_J_1965_bsmf_Proximite_eddueh}. The proximity operator of a function $f\in \Gamma_0(\HH)$
is defined as
\begin{equation}
\prox_f\colon \HH \to \HH\colon x \mapsto \argmind{y\in \HH}{f(y) + \frac12 \|y-x\|^2}
\end{equation}
where $\|\cdot\|$ denotes the Euclidean norm.
For every $x\in \HH$, $\prox_f x$ can thus be interpreted as the result of a regularized minimization of $f$ 
in the neighborhood of $x$. Note that the minimization to be performed to calculate $\prox_f x$ always has a unique solution.
Fig. \ref{fig:proxpowerp} shows the variations of the $\prox_f$ function when $f\colon \RR \to \RR\colon x \mapsto |x|^p$ with $p\ge 1$. In the case when $p=1$, the classical soft-thesholding operation is obtained.

\begin{figure}[htb]
\begin{center}
\includegraphics[width=7.5cm]{images/proxpower.eps}
\end{center}
\vspace{-0.2cm}
\begin{center}
\caption{\small Graph of $\prox_{|\cdot|^p}$. 
This   power $p$ function is often used to regularize inverse problems.} \label{fig:proxpowerp}
\end{center}
\end{figure}

In the case when $f$ is equal to the indicator function of a nonempty closed convex set $C\subset \HH$, the proximity operator of $f$
reduces to the projection $P_C$ onto this set, i.e. $(\forall x \in \HH)$ $P_C x = \argmind{y\in C}{\|y-x\|}$.


This shows that proximity operators can be viewed as extensions of projections onto convex sets. The proximity operator enjoys many
properties of the projection, in particular it is firmly nonexpansive.
The firm nonexpansiveness can be viewed as a generalization of the strict contraction property 
which is the engine behind the Banach-Picard fixed point theorem. This property makes the proximity operator successful 
in ensuring the convergence of fixed point algorithms grounded on its use. For more details about proximity operators and their rich properties,
the reader is refered to the tutorial papers in \cite{Combettes_P_2010_inbook_proximal_smsp,Bach_F_2012_j-ftml_optimization_sip,Parikh_N_2013_j-found-tml_prox_algo}.
The definition of the proximity operator can be extended to nonconvex lower-semicontinuous functions which are lower bounded by an affine function, but $\prox_f x$ is no longer guaranteed to be uniquely defined at any given point $x$.

\subsection{Conjugate function}
A fundamental notion when dealing with duality issues is the notion of \emph{conjugate function}.
The conjugate of a function $f\colon \HH \to \RX$ is the function $f^*$ defined as
\begin{equation}\label{e:deffconj}
f^*\colon \HH \to \RX\colon
u \mapsto \sup_{x\in \HH} \big(\scal{u}{x} -f(x)\big).
\end{equation}
This concept was introduced by A. M.~Legendre (1752-1833) in the one-variable case, and it was generalized by M.~W.~Fenchel (1905-1988).
A graphical illustration of the conjugate function is provided in Fig. \ref{fig:conj}.
In particular, for every vector $x \in \HH$ such that the supremum in \eqref{e:deffconj} is attained, $u$ is a subgradient of $f$ at $x$.

\begin{figure}[htb]
\begin{center}
\begin{tabular}{@{}c@{}c@{}}
\scalebox{1.0}{\input{conj1.pstex_t}} \hspace{1cm} & \hspace{1cm}  \scalebox{1.0}{\input{conj3.pstex_t}}
\end{tabular}
\end{center}
\caption{\small Graphical interpretation of the conjugate function.}\label{fig:conj}
\end{figure}

It must be emphasized that, even if $f$ is nonconvex, $f^*$ is a (non necessarily proper) lower-semicontinuous convex function.
In addition, when $f \in \Gamma_0(\HH)$, then $f^* \in \Gamma_0(\HH)$, and also the biconjugate of $f$ (that is the conjugate of its conjugate)
is equal to $f$. This means that we can express any function $f$ in $\Gamma_0(\HH)$ as
\begin{equation}
(\forall x \in \HH)\qquad f(x) = \sup_{u\in \HH} \big(\scal{x}{u} -f^*(u)\big).
\end{equation}
A geometrical interpretation of this result is that the epigraph of any proper lower-semicontinuous convex function always is an intersection of closed half-spaces.

As we have seen, the subdifferential plays an important role in the characterization of the minimizers of a function. A natural question is thus to enquire about the relations existing between the subdifferential of a function $f\colon \HH \to \RX$
and the subdifferential of its conjugate function. An answer is provided by the following important properties:
\begin{align}\label{e:subdifconj}
u\in \partial f(x)\quad &\Rightarrow \quad x \in \partial f^*(u) \qquad \mbox{if $f$ is proper}\nonumber\\
u\in \partial f(x)\quad &\Leftrightarrow \quad x \in \partial f^*(u) \qquad \mbox{if $f \in \Gamma_0(\HH)$.}
\end{align}
Another important property is Moreau's decomposition formula which links the proximity operator of a function
$f\in \Gamma_0(\HH)$ to the proximity operator of its conjugate:
\begin{equation}\label{e:moreaudec}
(\forall x \in \HH)(\forall \gamma \in \RPP) \qquad x = \prox_{\gamma f} x + \gamma\,\prox_{\gamma^{-1} f^*} (\gamma^{-1} x).
\end{equation} 
Other useful properties of the conjugation operation are listed in Table~\ref{t:propconj},\footnote{Throughout the paper, $\inte S$ denotes the interior of a set $S$.} where a parallel is drawn with the multidimensional Fourier transform, which is a more familiar tool in signal and image processing.
Conjugation also makes it possible to build an insightful bridge between the main two kinds of nonsmooth convex functions encountered in signal and image processing problems, namely indicator functions of feasibility constraints and sparsity measures (see framebox below.


\refstepcounter{numperceuse}
\begin{table}[hptb]
\centering
\caption{\small Parallelism between properties of the Legendre-Fenchel conjugation \cite{Combettes_P_2010_inbook_proximal_smsp} and of the Fourier transform.
$f$ is a function defined on $\HH$, $f^*$ denotes its conjugate, $\widehat{f}$  is its Fourier transform such that
$\widehat{f}(\nu) = \int_{\HH} f(x) \exp(-\jmath 2\pi \scal{\nu}{x}) dx$ where $\nu\in \HH$ and 
$\jmath$ is the imaginary unit (a similar notation is used for other functions), $h$, $g$, and $(f_m)_{1\le m \le M}$ 
are functions defined on $\HH$, $(\varphi_j)_{1\le j \le N}$ are functions
defined on $\RR$, $\psi$  is an even function defined on $\RR$, $\widetilde{\psi}$ is defined as 
$\widetilde{\psi}(\rho) = 2\pi \rho^{(2-N)/2}\int_0^{+\infty} r^{N/2} J_{(N-2)/2}(2\pi r \rho) \psi(r) dr$ where
$\rho \in \RR$ and $J_{(N-2)/2}$ is the Bessel function of order $(N-2)/2$, and $\delta$ denotes the Dirac distribution. (Some properties of the Fourier transform may require some technical assumptions.)
}\label{t:propconj}
\vspace{0.4cm}
\begin{tabular}{|p{0.4cm} l|l|l||l|l|}
\cline{3-6}
 \multicolumn{2}{c}{ } & \multicolumn{2}{|c||}{conjugation} & \multicolumn{2}{c|}{Fourier transform}\\
\hline
& Property & $h(x)$ & $h^*(u)$ & $h(x)$ & $\widehat{h}(\nu)$\\
\hline
\hline
\thenumperceuse\refstepcounter{numperceuse} &
invariant function & $\frac12 \|x\|^2$ & $\frac12 \|u\|^2$ & $\exp(-\pi \|x\|^2) $ &  $\exp(-\pi \|\nu\|^2)$\\
\hline
\thenumperceuse\refstepcounter{numperceuse} &
translation & $f(x-c)$ & $f^*(u)+\scal{u}{c}$ & $f(x-c)$ & $\exp(-\jmath 2\pi \scal{\nu}{c} ) \widehat{f}(\nu)$\\
 & $c\in \HH$           &                      &          &  &\\
\hline
\thenumperceuse\refstepcounter{numperceuse} &
dual translation & $f(x)+\scal{x}{c}$ & $f^*(u-c)$ & $\exp(\jmath 2\pi \scal{x}{c} )f(x-c)$ & $\widehat{f}(\nu-c)$\\
& $c\in \HH$           &                      &          & & \\
\hline
\thenumperceuse\refstepcounter{numperceuse} &
scalar multiplication & $\alpha f(x)$ & $\alpha f^*\left(\frac{u}{\alpha}\right)$ & $\alpha f(x)$ & $\alpha \widehat{f}(\nu)$\\
& $\alpha \in \RPP$           &                      &          & & \\
\hline
\thenumperceuse\refstepcounter{numperceuse} &
invertible linear transform & $f(Lx)$ & $f^*\big((L^{-1})^\top u\big)$ & $f(Lx)$ & $\frac{1}{|\operatorname{det}(L)|}\widehat{f}\big((L^{-1})^\top\nu\big)$\\
& $L \in \RR^{N\times N}$ invertible           &                      &          & & \\
\hline
\thenumperceuse\refstepcounter{numperceuse} &
scaling & $f\left(\frac{x}{\alpha}\right)$ & $f^*(\alpha u)$ & $f\left(\frac{x}{\alpha}\right)$ & $|\alpha| \widehat{f}(\alpha \nu)$\\
& $\alpha \in \RR^*$           &                      &          & & \\
\hline
\thenumperceuse\refstepcounter{numperceuse} &
reflection & $f(-x)$ & $f^*(-u)$ & $f(-x)$ & $\widehat{f}(-\nu)$\\
\hline
\thenumperceuse\refstepcounter{numperceuse} &
separability & $\displaystyle\sum_{j=1}^N \varphi_j(x^{(j)})$ & $\displaystyle\sum_{j=1}^N \varphi_j^*(u^{(j)})$ & $\displaystyle\prod_{j=1}^N \varphi_j(x^{(j)})$ & $\displaystyle\prod_{j=1}^N \widehat{\varphi}_j(\nu^{(j)})$\\
&             &   $x = (x^{(j)})_{1\le j \le N}$  &   $u = (u^{(j)})_{1\le j \le N}$       & $x = (x^{(j)})_{1\le j \le N}$ & 
$\nu = (\nu^{(j)})_{1\le j \le N}$\\
\hline
\thenumperceuse\refstepcounter{numperceuse} \label{e:definfconv} &
isotropy & $\psi(\|x\|)$ & $\psi^*(\|u\|)$ & $\psi(\|x\|)$ & $\widetilde{\psi}(\|\nu\|)$\\
\hline
\thenumperceuse\refstepcounter{numperceuse} \label{e:sumdual} &
inf-convolution & $(f\infconv g)(x)$ & $f^*(u)+g^*(u)$ & $(f\star g)(x)$ & $\widehat{f}(\nu)\widehat{g}(\nu)$\\
&   /convolution   &  $\displaystyle=\inf_{y\in \HH} f(y)+g(x-y)$                     &          & $\displaystyle=\int_{\HH} f(y) g(x-y) dy$ & \\
\hline
\thenumperceuse\refstepcounter{numperceuse}  &
sum/product & $f(x)+g(x)$ & $(f^* \infconv g^*)(u)$ & $f(x)g(x)$ & $(\widehat{f}\star \widehat{g})(\nu)$\\
&             &   $f \in \Gamma_0(\HH)$, $g \in \Gamma_0(\HH)$ &          & & \\
&             &   $\dom f \cap \inte(\dom g) \neq \emp$ &          & & \\
\hline
\thenumperceuse\refstepcounter{numperceuse} &
identity element   & $\iota_{\{0\}}(x)$ & $0$ & $\delta(x)$ & $1$\\
&  of convolution           &                      &          & & \\
\hline
\thenumperceuse\refstepcounter{numperceuse} &
identity element  & $0$ & $\iota_{\{0\}}(u)$ & $1$ & $\delta(\nu)$\\
&  of addition/product           &                      &          & & \\
\hline
\thenumperceuse\refstepcounter{numperceuse} &
offset & $f(x)+\alpha$ & $f^*(u)-\alpha$ & $f(x)+\alpha$ & $\widehat{f}(\nu)+\alpha \delta(\nu)$\\
& $\alpha \in \RR$           &                      &          & & \\
\hline
\thenumperceuse\refstepcounter{numperceuse} &
infinum/sum & $\displaystyle\inf_{1\le m \le M} f_m(x) $ & $\displaystyle\sup_{1\le m \le M} f_m^*(u)$ & $\displaystyle\sum_{m=1}^M f_m(x)$ & 
$\displaystyle\sum_{m=1}^M \widehat{f}_m(\nu)$\\
\hline
\thenumperceuse\refstepcounter{numperceuse} &
value at $0$ & \multicolumn{2}{c||}{$f^*(0) = -\inf f$ } & \multicolumn{2}{c|}{$\displaystyle\widehat{f}(0) = \int_{\HH} f(x) dx$ } \\
\hline
\end{tabular}
\end{table}


\begin{center}
\framebox{\label{bo:consup}
\begin{minipage}{14cm}
\footnotesize\sffamily 
{CONJUGATES OF SUPPORT FUNCTIONS}

The support function of a set $C\subset\HH$ is defined as
\begin{equation}\label{e:defsupfonc}
(\forall u \in \HH)\qquad \sigma_C(u) = \sup_{x\in C} \scal{u}{x}.
\end{equation}
In fact, a function $f$ is the support function of a nonempty closed
convex set $C$ if and only if it belongs to $\Gamma_0(\HH)$ and
it is positively homogeneous \cite{Bauschke_H_2011_book_con_amo}, i.e.
\[
(\forall x \in \HH)(\forall \alpha \in \RPP)\qquad f(\alpha x) = \alpha f(x).
\]
Examples of such functions are norms, e.g. the $\ell_1$-norm:
\[
\big(\forall x = (x^{(j)})_{1\le j \le N} \in \HH\big) \qquad f(x) = \|x\|_1 = \sum_{j=1}^N |x^{(j)}|
\]
 which is a useful convex sparsity-promoting measure in LASSO estimation \cite{Tibshirani_R_1996_j-roy-stat-soc-b_regression_ssv}
and in compressive sensing \cite{Candes_E_J_j-ieee-spm-introduction-rcs_2008}. Another famous
example is the Total Variation semi-norm \cite{Rudin_L_1992_tv_atvmaopiip} which is popular in image processing 
for retrieving constant areas with sharp contours.
An important property is that, if $C$ is a nonempty closed convex set, the conjugate of its support 
function is the indicator function of $C$. For example, the conjugate function
of the $\ell_1$-norm is the indicator function of the hypercube $[-1,1]^N$.
This shows that using sparsity measures are equivalent in the dual domain to imposing some constraints.
\end{minipage}.
}
\end{center}


\subsection{Duality results}\label{se:dualres}
A wide array of problems in signal and image processing can be expressed under the following variational form: 
\begin{equation}\label{e:primal}
\minimize{x\in \HH}{f(x)+g(Lx)}
\end{equation}
where $f\colon \HH \to \RX$, $g\colon \GG\to \RX$, and $L \in \RR^{K\times N}$.
Problem \eqref{e:primal} is usually referred to as the \emph{primal problem}
which is associated with the following \emph{dual problem} \cite{Rockafellar_R_T_1970_book_Convex_A,Bot_R_2010_book_conjugate_dco,Bauschke_H_2011_book_con_amo}:
\begin{equation}\label{e:dual}
\minimize{v\in \GG}{f^*(-L^\top v)+g^*(v)}.
\end{equation}
The latter problem may be easier to solve than the former one, especially when $K$ is much smaller than $N$.

A question however is to know whether solving the dual problem may bring some information on the solution
of the primal one. A first answer to this question is given by the Fenchel-Rockafellar duality theorem
which basically states that solving the dual problem provides a lower bound on the minimum value which can be obtained in the 
primal one. More precisely, 
if $f$ and $g$ are proper functions and if $\mu$ and $\mu^*$ denote the infima of the functions
minimized in the primal and dual problems, respectively, then \emph{weak duality} holds, which means that 
$\mu \ge - \mu^*$. If $\mu$ is finite,
$\mu+\mu^*$ is called the \emph{duality gap}. In addition, if $f\in \Gamma_0(\HH)$ and $g\in \Gamma_0(\GG)$, then, under
appropriate qualification conditions,\footnote{For example, this property is satisfied if the intersection of the 
interior of the domain of $g$ and the image of the domain of $f$ by $L$ is nonempty.} there always exists a solution to the dual
problem and the duality gap vanishes. When the duality gap is equal to zero, it is said that \emph{strong duality} holds.

\begin{center}
\framebox{\label{fb:cons_sharing}
\begin{minipage}{14cm}
\footnotesize\sffamily 
{CONSENSUS AND SHARING ARE DUAL PROBLEMS}

Suppose that our objective is to minimize a composite function $\sum_{m=1}^M g_m$
where the potential $g_m\colon \HH \to \RX$ is computed at the vertex of index $m\in \{1,\ldots,M\}$ of a graph.
A classical technique to perform this task in a distributed or parallel
manner \cite{Boyd_S_2011_j-found-tml_distributed_osl_admm} consists of reformulating this problem as a \emph{consensus problem},
where a variable is assigned to each vertex, and the defined variables $x_1,\ldots,x_M$ are updated so as to reach a consensus:
$x_1 = \ldots = x_M$. This means that, in the product space $(\HH)^M$ the original optimization problem can be rewritten as
\[
\minimize{\xb=(x_1,\ldots,x_M)\in (\HH)^M}{\iota_D(\xb)+\underbrace{\sum_{m=1}^M g_m(x_m)}_{\mbox{$g(\xb)$}}}
\]
where $D$ is the vector space defined as $D = \menge{\xb=(x_1,\ldots,x_M)\in (\HH)^M}{x_1 = \ldots = x_M}$.

By noticing that the conjugate of the indicator function of a vector space is the indicator function of its orthogonal complement,
it is easy to see that the dual of this consensus problem has the following form:
\[
\minimize{\vb=(v_1,\ldots,v_M)\in (\HH)^M}{\iota_{D^\bot}(\vb)+\underbrace{\sum_{m=1}^M g_m^*(v_m)}_{\mbox{$g^*(\vb)$}}
}
\]
where $D^\bot = \menge{\vb=(v_1,\ldots,v_M)\in (\HH)^M}{v_1+\cdots+v_M = 0}$ is the orthogonal complement of $D$.
By making the variable change $(\forall m \in \{1,\ldots,M\})$ $v_m = u_m-u/M$ where $u$ is some given vector in $\HH$,
and by setting $h_m(u_m) = -g_m^*(u_m-u/M)$, the latter minimization can be reexpressed as
\[
\maximize{\substack{u_1\in \HH,\ldots,u_M\in \HH\\ u_1+\cdots+u_M = u}}{\sum_{m=1}^M h_m(u_m)}.
\] 
This problem is known as a \emph{sharing problem} where one wants to allocate a given resource $u$
between $M$ agents while maximizing the sum of their welfares
evaluated through their individual utility functions $(h_m)_{1\le m \le M}$.


\end{minipage}.
}
\end{center}


Another useful result follows from the fact that, by using the definition of the conjugate function of $g$,
Problem~\eqref{e:primal} can be reexpressed as the following saddle-point problem:
\begin{equation}\label{e:saddleprob}
\mbox{Find}\qquad \inf_{x\in \HH}\sup_{v\in \GG}\big(f(x) + \scal{Lx}{v} - g^*(v)\big).
\end{equation}
In order to find a saddle point $(\widehat{x},\widehat{v})\in \HH \times \GG$, it thus appears natural to impose
the inclusion relations:
\begin{equation}
-L^\top\widehat{v} \in \partial f(\widehat{x}),\qquad
L \widehat{x}  \in \partial g^*(\widehat{v}).
\end{equation}
A pair $(\widehat{x},\widehat{v})$ satisfying the above conditions is called a \emph{Kuhn-Tucker point}.
Actually, under some technical assumption, by using Fermat's rule and \eqref{e:subdifconj}, it can be proved  that, if 
$(\widehat{x},\widehat{v})$ is a Kuhn-Tucker point, then $\widehat{x}$ is a solution to the primal problem
and $\widehat{v}$ is a solution to the dual one. This property especially holds when $f\in \Gamma_0(\HH)$
and $g\in \Gamma_0(\GG)$.
\subsection{Duality in linear programming}\label{se:dualLP}
In linear programming (LP) \cite{Bertsimas_D_1997_book_introduction_lo}, we are interested in convex optimization problems of the form:
\begin{equation}\label{e:primalLP}
\text{Primal-LP}:\qquad \minimize{x\in [0,+\infty[^N}{c^\top x}\quad\text{s.t.}\quad Lx \ge b,
\end{equation}
where $L = (L^{(i,j)})_{1\le i \le K,1\le j \le N}\in \RR^{K\times N}$, $b\in \RR^K$, and $c\in \RR^N$.\footnote{The vector inequality 
in \eqref{e:primalLP} means that $Lx-b \in \RP^K$.}
The above formulation can be viewed as a special case of \eqref{e:primal} where
\begin{equation}
(\forall x \in \HH) \quad f(x) = c^\top x + \iota_{[0,+\infty[^N}(x),\qquad
(\forall z \in \GG) \quad g(z) = \iota_{[0,+\infty[^K}(z-b).
\end{equation}
By using
the properties of the conjugate function and by setting $y = -v$, it is readily shown that
the dual problem \eqref{e:dual} can be reexpressed as
\begin{equation}\label{e:dualLP}
\text{Dual-LP}:\qquad \maximize{y\in [0,+\infty[^K}{b^\top y}\quad\text{s.t.}\quad L^\top y \le c.
\end{equation}
Since $f$ is a convex function, strong duality holds in LP. If $\widehat{x} = (\widehat{x}^{(j)})_{1\le j \le N}$ is a solution to
Primal-LP, a solution $\widehat{y} = (\widehat{y}^{(i)})_{1\le i \le K}$ to Dual-LP can be obtained by the \emph{primal complementary slackness condition}:
\begin{equation}\label{e:slackprimal}
(\forall j\in \{1,\ldots,N\}) \quad\text{such that}\quad \widehat{x}^{(j)} > 0, \qquad
\sum_{i=1}^K L^{(i,j)}\, \widehat{y}^{(i)} = c^{(j)}.
\end{equation}
whereas, if $\widehat{y}$ is a solution to Dual-LP, a solution $\widehat{x}$ to Primal-LP can be obtained
by the \emph{dual complementary slackness condition}:
\begin{equation}\label{e:slackdual}
(\forall i\in \{1,\ldots,K\}) \quad\text{such that}\quad \widehat{y}^{(i)} > 0, \qquad
\sum_{j=1}^N L^{(i,j)}\, \widehat{x}^{(j)} = b^{(i)}.
\end{equation}
{"config": "arxiv", "file": "1406.5429/background.tex"}