1
$\begingroup$

I know if a dual is unbounded then the primal is unfeasible and vice versa, but I don't know why they can't both be unbounded. Is it because it's impossible to have linear constraints that are unbounded in the direction of the gradient and the opposite direction?

$\endgroup$
1
$\begingroup$

Note: although unbounded primal is sufficient for an infeasible dual, it is not a necessary condition. Because there can be a case when both are infeasible. When one is infeasible we can say that the other is either unbounded or infeasible.

Given primal (P) normal max-LP: \begin{equation*} \begin{aligned} & \underset{\vec{x}}{\text{max}} & & z=\vec{c}^T\vec{x} \\ & \text{subject to} & & A\vec{x} \leq \vec{b}, \\ & & &\,\,\,\,\vec{x} \geq \vec{0} \end{aligned} \end{equation*}

and dual (D) normal min-LP: \begin{equation*} \begin{aligned} & \underset{\vec{y}}{\text{min}} & & w=\vec{b}^T\vec{y} \\ & \text{subject to} & & A\vec{y} \geq \vec{c}, \\ & & & \,\,\,\,\vec{y} \geq \vec{0} \end{aligned} \end{equation*}

Lemma 1 (weak duality): If $\vec{x}$ is feasible for (P) and $\vec{y}$ is feasible for (D), we have $z=\vec{c}^T\vec{x}\leq\vec{b}^T\vec{y}=w$.

Proof:

$\vec{x}$ is feasible for (P) $\Rightarrow$ $A\vec{x} \leq \vec{b}$, $\vec{x}\geq\vec{0}$

$\vec{y}$ is feasible for (D) $\Rightarrow$ $A\vec{y} \geq \vec{c}$, $\vec{x}\geq\vec{0}$

$\vec{y}^T(A\vec{x}\leq\vec{b}) \Rightarrow \vec{y}^T A\vec{x}\leq\vec{y}^T\vec{b}={w}$

$(A^T\vec{y}\geq\vec{c})^T \Rightarrow (\vec{y}^TA\geq\vec{c}^T)\vec{x} \Rightarrow \vec{y}^TA\vec{x} \geq\vec{c}^T\vec{x}=z$

combining, we get $z=\vec{c}^T\vec{x}\leq\vec{b}^T\vec{y}=w\,\,\square$

Lemma 2 (Strong Duality): if $z=\vec{c}^T\vec{x}=\vec{b}^T\vec{y}=w$ for feasible $\vec{x}$,$\vec{y}$ in (P) and (D), respectively, then $\vec{x}$,$\vec{y}$ are optimal for (P) and (D), respectively.

Proof: All z values lie below all w values (Lemma 1). Hence when z=w, we get optimality for both.

Lemmas 3&4: If (P) is unbounded, then (D) is infeasible. Similarly if (D) is unbounded, (P) is infeasible.

Explanation: If (P) is unbounded, we can push z up without limits. Hence there are no finite w values, i.e, there are no feasible $\vec{y}$ for (D).

$\endgroup$
  • $\begingroup$ Just wanted to say that is one slick proof of weak duality :) $\endgroup$ – Math1000 Oct 17 '19 at 6:11
  • $\begingroup$ Wait, I don't see how$(A^T\vec y\geqslant \vec c)^T \implies (\vec y^TA\geqslant \vec c^T)\vec x$. Where is $x$ on the left-hand side? $\endgroup$ – Math1000 Oct 17 '19 at 6:14
  • $\begingroup$ I am post multiplying $\vec{x}$ on both sides. $\endgroup$ – John Karasev Oct 17 '19 at 15:34
  • $\begingroup$ It must be missing in the left-hand side then, a typo perhaps? $\endgroup$ – Math1000 Oct 17 '19 at 18:40
0
$\begingroup$

Well, it is because of the weak duality theorem

$\endgroup$
  • $\begingroup$ I thought that's why if the primal is unbounded then the dual is infeasible $\endgroup$ – Dylan Y Oct 17 '19 at 6:10
  • $\begingroup$ Given primal max and dual min, any feasible solution for the primal is a lower bound for the solution to the dual. Conversely, any feasible solution for the dual is an upper bound for the primal. We clearly cannot have the first quantity strictly greater than the second, which is what would be necessary for both LPs to be unbounded. $\endgroup$ – Math1000 Oct 17 '19 at 6:17
  • $\begingroup$ @DylanY Well, if a linear program is infeasible, it can't be unbounded since it has to be feasible to be unbounded. $\endgroup$ – UnbelieveTable Oct 17 '19 at 8:26

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.