Prove: If the primal is unbounded, then the dual is infeasible.


What I tried:

Let the primal be:

Max/Min $z=c_1x_1 + ... + c_nx_n$

s.t.

$$a_{11}x_1 + a_{12}x_2 + ... + a_{1n}x_n \le b_1$$

$$a_{21}x_1 + a_{22}x_2 + ... + a_{2n}x_n \le b_2$$

$$\vdots$$

$$a_{m1}x_1 + a_{m2}x_2 + ... + a_{mn}x_n \le b_m$$

$$x_1, ..., x_n \ge 0$$

Let $l$ represent the $l$th iteration.

If we have some basic feasible solution while the primal is unbounded, then there exists some non-basic variable $x_k$ whose coefficients in the $lth$ iteration are $a_{1kl}, a_{2kl}, ..., a_{mkl} \le 0$ and $z_{kl} - c_k < 0$ where

$$z_{kl} = a_{1kl}c_{b_{1l}} + a_{2kl}c_{b_{2l}} + ... + a_{mkl}c_{b_{ml}}$$

where $c_{b_{1l}}, ..., c_{b_{ml}}$ are the coefficients in the objective function corresponding to the $m$ basic variables at iteration $l$, namely, $b_{1l}, ..., b_{ml}$.

Then the dual contains a row that looks like:

$$a_{1kl}y_1 + a_{2kl}y_2 + ... + a_{mkl}y_m \ge c_k$$

$\because \ a_{1kl}, a_{2kl}, ..., a_{mkl} \le 0$ and $y_j \ge 0$,

we have

$$a_{1kl}y_1 + a_{2kl}y_2 + ... + a_{mkl}y_m \le 0$$

The primal is infeasible if $z_{kl} \ge 0 \ \because$ we would have $c_k > 0$.

What if $z_{kl} < 0$?

Since $a_{1kl}, a_{2kl}, ..., a_{mkl}$ and $a_{1kl}c_{b_{1l}} + a_{2kl}c_{b_{2l}} + ... + a_{mkl}c_{b_{ml}} \le 0$, I guess $c_{b_{1l}}, ..., c_{b_{ml}} \ge 0$.

I'm not sure how to conclude the dual is infeasible in the case that $z_{kl} < 0$.


Did I go wrong somewhere? How can I approach this? Is there another way I can prove this?


Also, my book says that this is a corollary to complementary slackness. What's the relevance of complementary slackness?

asked 19 Apr '16, 15:21

BCLC's gravatar image

BCLC
8311
accept rate: 0%

If you use weak duality, you will get your proof right away.

(20 Apr '16, 03:16) Sune

@sune Afaik, weak duality says $$cx \le b^{T}y$$ So if $$cx = \infty$$, then $$b^{T}y = \infty$$. If wrong, why? If right, then it seems that the dual is unbounded? If not, why? If so, how does that mean that the dual is infeasible?

(20 Apr '16, 10:03) BCLC

Weak duality says that \(b^Ty\geq \infty\) for all \(y\) feasible for the dual. Suppose the dual had a feasible solution, say \(\tilde{y}\). Evaluate the value of \(\tilde{y}\) and get a contradiction.

(20 Apr '16, 14:27) Sune

@Sune I don't quite see what exactly is the contradiction. Are feasible solutions necessarily finite? I just thought they needed to be positive. Oh wait are you saying that $$b^{T}y$$ is going to be negative?

(22 Apr '16, 05:56) BCLC

A finite sum of finite numbers is usually finite.

(22 Apr '16, 06:32) Sune

Thanks @Sune ^-^ Post as answer?

(23 Apr '16, 00:39) BCLC
showing 5 of 6 show 1 more comments
Be the first one to answer this question!
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×231
×20
×17
×8
×3

Asked: 19 Apr '16, 15:21

Seen: 1,033 times

Last updated: 23 Apr '16, 00:39

OR-Exchange! Your site for questions, answers, and announcements about operations research.