I have a problem about the duality gap of the primitive problem and the dual problem.
This problem comes from a probabilistic model named Lagrangian UVM.
As this figure shows, this is a trinomial tree containing $N+1$ periods: $n=0,1,2,...,N$.
At the $n^{th}$ period there are $2n+1$ nodes: $k=n,....,1,0,-1,...,-n$.
We identify each node by
$S^{(n)}_k=S_0M^n(\frac{U}{M})^k,\ \ -n\leq k\leq n,\ \ 0\leq n\leq N$
with $UD=M^2$ and $S_0>0$ supposed to be constant.
For any continous function $F(S)$ dominated by a polynomial we denote
$F^{(N)}_k=F(S^{(N)}_k),\ \ -N\leq k\leq N$
We define $F^{(n)}_k$ par by induction: $\forall 0\leq n\leq N-1,\ \ -n\leq k\leq n$
$F_k^{(n)}=P_U(p_k^{(n)})F_{k+1}^{(n+1)}+P_M(p_k^{(n)})F_k^{(n+1)}+P_D(p_k^{(n)})F_{k-1}^{(n+1)}$
with
\begin{eqnarray*} &&P_U(p^{(n)}_k)=\alpha p^{(n)}_k\\ &&P_M(p^{(n)}_k)=1-2p^{(n)}_k\\ &&P_D(p^{(n)}_k)=\beta p^{(n)}_k \end{eqnarray*}
where $\alpha, \beta$ are constants satisfying $0<\alpha<\beta$ and $\alpha+\beta=2$.
Then we get for every $F$ a function $f(p):=F^{(0)}_0(p)$
$p\in\mathcal{P}=\left(p=(p_0^{(0)},p_1^{(1)},p_0^{(1)},p_{-1}^{(1)},...,p_{N-1}^{(N-1)},...,p_0^{(N-1)},...,p_{1-N}^{(N-1)}) :\frac{1}{2\gamma}\leq p_k^{(n)}\leq\frac{1}{2}\right)$
with $\gamma>1$.
Given $G(S)$ and $F(S)$, we obtain in the same way $g(p)$ and $f(p)$.
Having $C\in\mathbf{R}$ and $\epsilon>0$ such that $\mathcal{P}_{\epsilon}=\left(p\in\mathcal{P}|\ \ |f(p)-C|\leq\epsilon\right)$ is not empty.
My question is the following
$\mathrm{P}$ \begin{eqnarray*} &&\max_{p\in\mathcal{P}}g(p)\\ &&s.t. |f(p)-C|\leq\epsilon \end{eqnarray*}
$\mathrm{D}$ $\min_{\lambda\in\mathbf{R}}\max_{p\in\mathcal{P}} g(p)+\lambda(f(p)-C)+|\lambda|\epsilon$
Is $\mathrm{P}$ equivalent to $\mathrm{D}$?
Firstly we can show $\mathrm{D}\geq\mathrm{P}$: $\forall p\in\mathcal{P}_{\epsilon}$,
$g(p)+\lambda(f(p)-C)+|\lambda|\epsilon\geq g(p)-|\lambda||f(p)-C|+|\lambda|\epsilon\geq g(p)-|\lambda|\epsilon+|\lambda|\epsilon=g(p)$
which gives
$\max_{p\in\mathcal{P}}g(p)+\lambda(f(p)-C)+|\lambda|\epsilon\geq\max_{p\in\mathcal{P}_{\epsilon}}g(p)$
Hence
$\min_{\lambda\in\mathbf{R}}\max_{p\in\mathcal{P}} [g(p)+\lambda(f(p)-C)]+|\lambda|\epsilon\geq\max_{p\in\mathcal{P}_{\epsilon}}g(p)$
The difficulty is the reverse. Since $g(p)+\lambda f(p)$ is neither convex neither concave for $N>1$, we can not apply directly the optimization theory. By the construction we find that $g(p)$ and $f(p)$ are affine with respect to every component $p_k^{(n)}$, and so is $g(p)+\lambda f(p)$.
Hence, its supremum is reached for some $p$ in $\mathcal{P}_{bin}$:
$\underbrace{\{\frac{1}{2\gamma},\frac{1}{2}\}\times\{\frac{1}{2\gamma},\frac{1}{2}\} \times\cdots\{\frac{1}{2\gamma},\frac{1}{2}\}}$ $N^2$
Set
$\varphi(\lambda)=\sup_{p\in\mathcal{P}}g(p)+\lambda f(p)=\sup_{p\in\mathcal{P}_{\text{bin}}}g(p)+\lambda f(p)$
$\varphi_{\epsilon}(\lambda)=\varphi(\lambda)-\lambda C+|\lambda|\epsilon$
Then we can prove that $\varphi(\lambda)$ is continuous, convex and piecewise affine. So is $\varphi_{\epsilon}(\lambda)$. As the following graph shows:
I have an idea but I can not complete it.
If $\lambda^{\ast}$ is a minimizer of $\varphi_{\epsilon}(\lambda)$, then we have
$\Delta\lambda>0, \ \ p^{-}({\lambda^{\ast}}), p^{+}({\lambda}^{\ast})\in\mathcal{P}_{\text{bin}}$
such that
$\varphi_{\epsilon}(\lambda)=g(p^{-}({\lambda^{\ast}}))+\lambda f(p^{-}({\lambda^{\ast}}))-\lambda C+|\lambda|\epsilon,\ \ \forall\lambda\in[\lambda^{\ast}-\Delta\lambda,\lambda^{\ast}]$
$\varphi_{\epsilon}(\lambda)=g(p^{+}({\lambda{\ast}}))+\lambda f(p^{+}({\lambda^{\ast}}))-\lambda C+|\lambda|\epsilon,\ \ \forall\lambda\in[\lambda^{\ast},\lambda^{\ast}+\Delta\lambda]$
As $\lambda^{\ast}$ minimizes $\varphi_{\epsilon}(\lambda)$, we have
$f(p^{-}({\lambda^{\ast}}))-C+\text{sign}(\lambda^{\ast})\epsilon\leq 0,\ \ f(p^{+}({\lambda^{\ast}}))-C+\text{sign}(\lambda^{\ast})\epsilon\geq 0,\ \ |\lambda^{\ast}|>0$
$f(p^{-}({\lambda^{\ast}}))-C-\epsilon\leq 0,\ \ f(p^{+}({\lambda^{\ast}}))-C+\epsilon\geq 0,\ \lambda^{\ast}=0$
Define
$U=\left(p\in\mathcal{P}|g(p)+\lambda^{\ast} f(p)=g(p^{-}({\lambda^{\ast}}))+\lambda^{\ast} f(p^{-}({\lambda^{\ast}}))\right)$
then $p^{-}({\lambda^{\ast}}),p^{+}({\lambda^{\ast}})\in U$.
Once we can prove that $U$ is path-connected, that is to say that there exists a continuous path $\gamma(z)$ defined over $[0,1]$ taking values in $U$ such that
\begin{eqnarray*} \gamma(0)&=&p^{-}({\lambda^{\ast}})\\ \gamma(1)&=&p^{+}({\lambda^{\ast}}) \end{eqnarray*}
we can show the equivalence.
Take for example the first case
$f(\gamma(0))-C+\text{sign}(\lambda^{\ast})\epsilon\leq 0,\ \ f(\gamma(1))-C+\text{sign}(\lambda^{\ast})\epsilon\geq 0$
By intermediate value theorem we have $z_0\in[0,1]$ such that $f(\gamma(z_0))-C+\text{sign}(\lambda^{\ast})\epsilon=0$.
Then $\gamma(z_0)\in U$ satisfies
$\gamma(z_0)\in\mathcal{P}_{\epsilon}$
$\min_{\lambda\in\mathbf{R}}\varphi_{\epsilon}(\lambda)=\varphi_{\epsilon}(\lambda^{\ast})=g(\gamma(z_0))\leq\sup_{p\in\mathcal{P}^N_{\epsilon}}g(p)$
which offers a proof. But I do not know how to prove $U$ is path-connected. Does someone have an idea? Thanks a lot for help!