1
$\begingroup$

I was trying to solve this exercise when my primal is $\min c'x$ $s.t: \ Ax=b \ , x \geq 0 $.

For the => proof i think i solved it. This helped me a lot. But the reverse, i think is more complicated. I can use complementary slackness:

$y_{i}^*(b_{i}-A_{i}x^*)=0$ and show that $x^*$ is involved to at least $m$ l.i. columns of $A$. But it could be a degenerate solution.

How can i proove that $x^*$ is non-degenerate if i know that $y^*$ is a non degenerate optimal solution of the dual problem?

I know that if the minimization problem is defined in a polyhedron in standard form, the reduced costs must be $0$ when the basic solution is optimal. Reading Bertsimas and Tsitsiklis's book (linear) in p.163 they say that dual degeneracy is obtained when there is a non-basic variable with reduced costs different to zero. Ok, i know that, this is degeneracy in primal, how it implies degeneracy in dual? Thanks!

$\endgroup$

1 Answer 1

1
$\begingroup$

I think you wanted to say "dual degeneracy is obtained when there is a non-basic variable with a reduced cost of zero".

If you could prove the first direction, that the non-degenerate optimal solution to primal => non-degenerate optimal solution to dual, then the reverse shouldn't be that hard. Because we know that the dual of the dual is primal.

We can go into more details too. What's the relation between primal and dual problems?

The dual problem is:

max y'b

s.t.
y'A <= c
y free  --> if you're primal was in standard form, then y>=0

We have $y_{i}^*(b_{i}-A_{i}x^*)=0$ (1). You can also write the complementary slackness for dual:

$x_{i}^*(c_{i}-y'^*A_{i})=0$ (2)

(btw, you see that the slack on the dual constraints are $c - y'A$ which are the reduced costs for the primal problem.)

Now, when the primal solution is non-degenerate in the optimal solution, $x_i^* >0 \Rightarrow \text{(from 2)}\ c_{i}-y'^*A_{i}=0$

Now, when $x_i$ is degenerate and in the basis, it is 0 and its reduced is 0. Also, when $x_i = 0$, then its slack is 0, which means $b_{i}-A_{i}x^*=0$.

So, on one hand $x_i^*=0 \Rightarrow c_{i}-y'^*A_{i}>=0$ i.e. dual slack variable is non-negative, but on the other hand $b_{i}-A_{i}x^*=0 \Rightarrow y_{i}>=0$ i.e. dual variable is in the basis, which means its slack should be zero. $\Rightarrow y_i^* = 0$ too, thus degeneracy.

I hope this helped.

$\endgroup$

You must log in to answer this question.

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