Optimization – Prove Optimal Solution to Dual is Not Unique if Primal is Degenerate and Unique

convex optimizationduality-theoremslinear programmingoperations researchoptimization

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?

Best Answer

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.

Related Question