1
$\begingroup$

If consider a primal and Dual LP of the following form \begin{equation*} \text{minimize} \hspace{.8em} C^{\top}x\\ \text{subject to} \hspace{.8em} Ax = b\\ \hspace{2 cm} x \ge 0 \end{equation*} and the Dual of this LP is \begin{equation*} \text{minimize} \hspace{.8em} b^{\top}y\\ \text{subject to} \hspace{.8em} A^{\top}y \le C\\ \end{equation*} Then from the weak duality theorem i know that if the primal is unbounded, then the dual is infeasible, but the converse is not true. I need to construct an example where the primal and dual are both infeasible. Can it happen that the dual is infeasible but the primal is bounded?

What i think is : (1) i think the first one is possible i.e both primal and dual infeasible, i think the example where $C=1,b=-1,A=0$ works ? (2) The second one seems to be absurd i.e if the primal has an optimal solution then the duality theorem says that the dual has an optimal solution as well i.e dual is feasible.

$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

If $C$ is the all one vector and $A=0$, then the dual is feasible, hence the counter example is not valid.

However, let's try to change your attempt by a little bit, let $C$ be the vector of every entry being $-1$, in that case, the dual is not feasible. Neither is primal.

Can it happen that the dual is infeasible but the primal is bounded.

No, that would violate strong duality.

$\endgroup$
3
  • $\begingroup$ Yes, thanks, was very obvious ! $\endgroup$
    – Siddhartha
    Mar 22, 2020 at 10:37
  • $\begingroup$ one doubt , this generally depends on the form in which we formulate the LP right ? i.e if i write the P-D pair as $$\begin{equation*}\text{minimize} \hspace{.8em} C^{\top}x\\\text{subject to} \hspace{.8em} Ax \le b\\\end{equation*}$$ $$\begin{equation*}\text{maximize} \hspace{.8em} -b^{\top}y\\\text{subject to} \hspace{.8em} A^{\top}y+C=0 ,~ y \ge 0\\\end{equation*}$$ Then $C=1,b=-1,A=0$ works ! $\endgroup$
    – Siddhartha
    Mar 22, 2020 at 10:45
  • 1
    $\begingroup$ yes, one should be clear which convention/ form one is talking about. $\endgroup$
    – Siong Thye Goh
    Mar 22, 2020 at 10:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .