Let $K\subset \mathbb{R}^2$ be a closed convex and pointed cone, $A$ be a $2\times 2$ square matrix and $b, c\in \mathbb{R}^2$. Consider the problem $ (P)\quad \min\{\langle c, x\rangle: Ax\geq_K b\}, $ and its dual $ (D)\quad \max\{\langle b, y\rangle: A^Ty=c,\; y\in K^*\}, $ where $ K^*=\{y\in\mathbb{R}^2: \langle x, y\rangle\geq 0, \forall x\in K\}. $ I would like to construct $(P)$ and $(D)$ such that $ \inf(P)-\sup(D)>0. $ Thank you for all comments and helping.
Duality gap in cone programming
2
$\begingroup$
linear-programming
convex-optimization
1 Answers
1
You are looking for a case where strong duality does not hold, so either the primal problem or the dual one must not be strictly feasible.
Consider the following optimization problem from the slides of Prof. L. Vandenberghe for EE236 in UCLA: \begin{align} &\operatorname*{Minimize}\limits_{x\in\mathbb{R}}\ x_1,\\ &\mathrm{subject to:}\\ &\begin{bmatrix}0 & x_1\\x_1 & x_2\end{bmatrix} \succeq 0,\\ &x_1\geq -1. \end{align}
The optimal value of this problem is $p^\star = 0$, whereas its dual is
\begin{align} &\operatorname*{Maximize}\limits_{y\in\mathbb{R},\, Y\in\mathbb{R}^{2\times 2}}\ -y,\\ &\mathrm{subject to:}\\ &Y\succeq 0,\\ &2Y_{12}+y = 1,\\ &y\geq 0\\ &Y_{22}=0, \end{align}
whose optimal value is $d^\star = -1$.