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.

trinomial tree

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$



\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



$$\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$$


$$\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$$


$$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



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!

  • $\begingroup$ 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~ $\endgroup$ – Higgs88 Jul 20 '12 at 15:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.