# equivalence between primitive and dual

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!

-
It is very kind if someone can help me for this problem. This problem derives from the model Lagrangian UVM(uncertain volatility model): $$E^{\mathbb{P}}[G]$$ s.t $$|E^{\mathbb{P}}[F]-C|\leq\epsilon$$ and I have proved that there is no duality gap between the primitive problem and the dual problem in continous case, but when we pass to the numerical framework. We meet the previous approximated problem and a natural question to ask is whether there exists the duality gap or not –  Higgs88 Jul 20 '12 at 14:48
I apologize for my question is too long. Though I tend to believe that there in no duality gap, but if someone can find a counterexample, it is also great. For example can someone prove that there is no duality gap or find a counterexample when $N=2$? Thanks again for your patience to read this question~ –  Higgs88 Jul 20 '12 at 15:02