Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I originally asked this question: Does solving the LP dual SOLVE the primal LP?

It was answered using an example of how the primal and dual solve each other (because of knowledge from strong duality).

However, I wanted to ask a follow up question about proving that the equations can be solved.

$A x \preceq b$ is a polytope of $n$ variables and $k$ constraints, and the slack form is $A x + x_s = b$, where $x_s \succeq 0$.

This problem has $n$ variables with $k$ constraints (so $k$ slack variables), where $u≤n$ of those variables are nonzero and $v≤k$ slack variables are nonzero. The dual has $k$ variables with $n$ constraints ($n$ slack variables); b/c of complementary slackness, $u$ of those $k$ variables and $v$ of those $n$ slack variables must all equal zero.

To prove solving the original LP solves the dual, you must show that after solving the original LP, all variables in the dual must be determined by the slack form equation for the dual. How can you guarantee the number of unknowns in the dual does not exceed the number of equations in the dual ($k−u+n−v≤n$ i.e. $k≤u+v$).

Thanks a lot for your help, this is going to bother me until I know why.

share|improve this question
    
You can find the entire dual solution using the complementary slackness. –  user62089 Apr 8 '13 at 16:22
    
@pondy I understand (did you see the linked question?). Can you provide proof that these equations must be determined? –  Oliver Apr 8 '13 at 18:54
    
Just by glancing at it are you remembering that you must add $k$ constraints for $k$ slack variables? The $x_s \ge 0$, for $s=1,...,k$ –  DiegoNolan Apr 9 '13 at 20:35
    
@DiegoNolan Good point, but I'm starting from standard form (all variables $\geq 0$), as would be solved by the simplex algorithm. –  Oliver Apr 9 '13 at 23:31
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.