Hi everyone! 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.
http://www.freeimagehosting.net/2sgmg
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:
http://www.freeimagehosting.net/7jfcz
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!
