3
$\begingroup$

How do I prove an optimal solution to dual is not unique if an optimal solution to the primal is degenerate and unique?


What I tried:

Let the primal be

$$\max z=cx$$

subject to

$$Ax \le b, x \ge 0$$

Let the dual be

$$\min z'=b^Ty$$

subject to

$$A^Ty \le c^T, y \ge 0$$

Let the (we assume there is only one) primal solution be

basic variables: $(x_{B_1}, x_{B_2}, ..., x_{B_i})$

non-basic variables: $(x_{NB_1}, x_{NB_2}, ..., x_{NB_i})$

Let a (there could be more than one) dual solution be

basic variables: $(y_{B'_1}, y_{B'_2}, ..., y_{B'_i})$

non-basic variables: $(y_{NB'_1}, y_{NB'_2}, ..., y_{NB'_i})$

By degeneracy of primal solution, one of the basic variables is zero:

$$x_{B_{i_0}} = 0$$

Zero or not, since it's a primal basic variable, we have:

$$z_{B_{i_0}} - c_{B_{i_0}} = 0 = y_{B_{i_0}}$$

Note that $y_{B_{i_0}}$ is not necessarily the same as $y_{B'_{i_0}}$

By uniqueness of primal solution, all of the non-basic variables of primal have positive reduced cost:

$$z_{NB_1} - c_{NB_1} > 0$$

$$\vdots$$

$$z_{NB_i} - c_{NB_i} > 0$$

To show that the dual has alternative solutions, we must show that one of these is true:

$$z_{NB'_1} - b_{NB'_1} = 0$$

$$\vdots$$

$$z_{NB'_i} - b_{NB'_i} = 0$$

I think I could prove this assuming

$$\text{non-basic = slack}$$

which is not necessarily true of course.

How then might I prove this?

$\endgroup$
4
+300
$\begingroup$

You can find a proof of the statement in the table that you quote in the book

Linear and Integer Programming: Theory and Practice, Second Edition
pages 141-145, proof of Theorem 4.5.

However the exact statement is that existance of a degenerate and (additionally) unique solution of the primal implies multiple solutions to the dual.


Using the notation of the the above cited book, the proof of this statement proceeds as follows:

Let $x^*$ be a primal optimal basic feasible solution with basis variables $x_B^*$ (from this and due to the duality theorems you already know that the dual has a finite optimal solution). Since it is degenerate then there exists $$x_{i_0}^*=0, \qquad \text{ with } i_0 \in B$$ But the variable $y_{j_0}^*$ (that corresponds to $x_{i_0}$) of the corresponding dual basic feasible solution $y^*$ is nonbasic and therefore $$y_{j_0}^*=0 \tag1$$ On the other the Strong Complementary Slackness Theorem

(Theorem 3.6 of the book) implies that (given that primal in standard form has an optimal solution) there exists a pair of primal and dual optimal solutions $x^*$ and $y^*$ such that for each pair of complementary dual variables $(x_i^*,y_j^*)$ it holds that either $x_i^*>0$ or $y_j^*>0$ (or both).

Thus, due to uniqueness of the primal optimal solution (so this assumption is necessary for this proof) there is a dual optimal solution (not necessarily basic feasible) for which $$y_{j_0}^*> 0 \tag{2}$$
Relations $(1)$ and $(2)$ together imply that there exist multiple optimal dual solutions.


Edit 1: According to this question and answer you can see that it is impossible that both the primal and the dual have simultaneously multiple solutions. Together with the above proof this answers your question.

$\endgroup$
  • 3
    $\begingroup$ I wrote out the quoted proof in case that you cannot access the book online. I think the assumption of uniqueness is necessary, so you cannot drop it. $\endgroup$ – Jimmy R. Dec 7 '14 at 13:04
  • 2
    $\begingroup$ The homework link that you posted also uses the fact of uniqueness, so it is correct. See my edit and the link I added. It is not possible that both the primal and the dual have simultaneously multiple solutions. $\endgroup$ – Jimmy R. Dec 7 '14 at 13:35
  • 1
    $\begingroup$ Stef I would like to add further that the 300 points I gave up for this bounty as well as all the question and answering I've done over the past 8 or so months that led me to accummulating such were all worth this comprehensive answer. Again, thanks. $\endgroup$ – BCLC Dec 7 '14 at 13:40
  • 2
    $\begingroup$ To be honest I feel a little ashamed and not worth the bounty because my answer did not add innovative knowledge. Contrary it was based on searching of the correct sources and quoting them here. If you need I can always assign a bounty to one of your already given answers and return the points to you. However, thanks for your generous gesture and your kind words! $\endgroup$ – Jimmy R. Dec 7 '14 at 13:46
  • 2
    $\begingroup$ Let us continue this discussion in chat. $\endgroup$ – Jimmy R. Dec 7 '14 at 13:53

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.