19
$\begingroup$

When I heard someone discussing LP the other day, I heard him say, "Well, we could just solve the dual."

I know that both the primal LP and its dual must have the same optimal objective value (assuming both are feasible and bounded). I also understand complementary slackness (the product of all primal variables and dual slack variables is 0, as is the product of all dual variables and primal slack variables).

To me, solving the dual gives you some useful information about the solution of the primal:

  1. The final objective value, which restricts you to an $n-1$ hyperplane
  2. All nonzero dual slack variables require primal variables of 0.

But aside from this information, to me it doesn't seem that solving the dual truly solves the primal LP. Knowing the optimal objective value can help (given this, simply find the primal feasible point with that objective value), as can knowing which primal variables are 0. But the latter is LP-specific: if the dual problem has many zeroes in the solution, then there isn't information about the primal variables.

My question is this: when people say "We'll solve the dual," does that mean it actually solves the primal or that it simply gives useful information that can help to faster solve the primal?

Thanks for your help, none of my colleagues could answer.

EDIT: My main question is equivalent to "How can we prove there are enough equations to determine all variables?" Please see comment to answer below.

$\endgroup$
  • $\begingroup$ i think yes .you should read chapter 6 of introduction to operation research (Hillier and lieberman) $\endgroup$ – M.H Jan 27 '13 at 18:48
14
$\begingroup$

There are two aspects of this.

  1. If you use the simplex method or some variant of it, you are actually simultaneously solving the primal and dual. That is, from an optimal simplex tableau you can read off both an optimal solution to the primal and an optimal solution to the dual.
  2. From an optimal solution of either primal or dual, complementary slackness reduces the other one (at least in nondegenerate cases) to a relatively simple matter of solving a system of $m$ linear equations in $m$ unknowns.

EDIT: Here's a typical example. Consider the (primal) problem P:

$$ \eqalign{\text{maximize } & 2 x_1 +16 x_2 +2 x_3 \cr \text{subject to} &\cr & 2 x_1 + x_2 - x_3 \le -3 \cr & -3 x_1 + x_2 + 2 x_3 \le 12 \cr & x_1, x_2, x_3 \ge 0 }$$

and suppose you know that $x_1 = 0$, $x_2 = 2$, $x_3 = 5$ (and thus slack variables $\xi_1 = 0$, $\xi_2 = 0$) is an optimal solution. The dual problem (with decision variables $y_1, y_2$ and slack variables $\eta_1, \eta_2, \eta_3$) has equations

$$ \eqalign{ 2 y_1 - 3 y_2 - \eta_1 &= 2\cr y_1 + y_2 - \eta_2 &= 16\cr -y_1 + 2 y_2 - \eta_3 &= 2\cr}$$ But complementary slackness tells you $\eta_2 = 0$ and $\eta_3 = 0$. Putting these in and solving the second and third equations $$ \eqalign{ y_1 + y_2 &= 16\cr -y_1 + 2 y_2 &= 2\cr}$$ you get $y_1 = 10$, $y_2 = 6$, and then in the first equation $\eta_1 = 0$.

$\endgroup$
  • $\begingroup$ Thank you. If the original problem has n variables with k constraints (k slack variables), where $u \leq n$ of those variables are nonzero and $v \leq 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. 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 \leq n$ i.e. $k \leq u + v$)? $\endgroup$ – user Apr 4 '13 at 21:11
2
$\begingroup$

This is wrong, as pointed out by others on this page. See my other answer for a (hopefully) correct one

It's maybe a little too late, but as I had the same doubt, I decided to write an answer for future reference.

The key is to understand that one supposes your solution is a vertex. If it is not one, is not too hard to find a vertex that is optimal starting from your optimal solution.

I shall use the notation Oliver introduced in his comment to the other answer. That is, assume the original problem has $n$ variables with $k$ constraints ($k$ slack variables), where $u\le n$ of those variables are nonzero and $v\le k$ slack variables are nonzero.

Once you have a vertex, you know that you have equalities for at least $n$ of the $k+n$ inequalities (the $k$ "matrix" constraints and the $n$ nonnegativity ones). This is because in an $n$ dimensional space (of the original variables), a point is the intersection of (at least) $n$ hyperplanes.

Those are exactly the $k-v$ slack variables that are zero and $n-u$ variables that are zero, so you have:

$$(k-v)+(n-u)\geq n\Rightarrow k\leq u+v$$

Thus (per Oliver's comment about the dual problem having $k$ variables with $n$ constraints) we can "guarantee the number of unknowns in the dual does not exceed the number of equations in the dual".

$\endgroup$
  • $\begingroup$ Welcome to Math.SE. You chose an interesting Question to tackle for your first effort, but in posting after such a long passage of time there is little reason to hurry the effort. The Original Poster included a number of specific points in relating solution of the dual to the primal LP. Your post seems less clear than the Question in this respect. If you plan on sticking around, you'll probably want to learn MathJax and $\LaTeX$ in order to use mathematical symbols and formulas in your posts. $\endgroup$ – hardmath May 12 '15 at 22:43
  • $\begingroup$ Thanks for feedback, but the other answer plus the OP comment reduces the problem to a much simpler format, proving an inequality. Do you, after reading his comment and understanding that I'm using the same notation still believe my post is not very clear? $\endgroup$ – user2759511 May 14 '15 at 12:44
  • $\begingroup$ About using Latex: you're certainly right, but considering how simple the formulae were , I really don't believe that it impairs at all the unsderstanding. Kind of a lame excuse, I know $\endgroup$ – user2759511 May 14 '15 at 12:47
  • $\begingroup$ I found it difficult to follow your train of thought, which to you I'm sure was quite natural. One aspect of this is that I arrived at your post expecting an Answer to the original Question rather than a response to a Comment on a different Answer. I appreciate you are indicating the connection, but visually it challenges the Reader to look back to the place where "the notation Oliver introduced" is defined, then resume following your train of thought. $\endgroup$ – hardmath May 14 '15 at 13:07
  • $\begingroup$ Another aspect is the ASCII math notation you settled for. I suspect if you had not written it yourself, you'd immediately spot the ambiguity of >= and <= for inequalities alongside => for implication. I'd be happy to try my hand at formatting your post with $LaTeX$ to convince you of its utility. $\endgroup$ – hardmath May 14 '15 at 13:09
0
$\begingroup$

Seeing as my other answer was deleted (apparently 6 people reviewed my answer and not one of them decided to correct the mistake that renders user2759511's answer useless) I will write a more complete answer.

Given a solution to the primal, finding the solution to the dual amounts to proving strong duality. Of course, there are cases where you can use complementary slackness to determine a dual solution, and of course there are many algorithms that do in fact solve the primal and dual essentially simultaneously (e.g. simplex you can easily get the dual solution once the algorithm completes) but it seems that the original question is looking for a complete way to do this, and I don't think there is anything "easier" than proving strong duality.

$\endgroup$
  • $\begingroup$ This does not provide an answer to the question. Once you have sufficient reputation you will be able to comment on any post; instead, provide answers that don't require clarification from the asker. - From Review $\endgroup$ – Alexis Olson Oct 7 '16 at 3:14
  • $\begingroup$ What are you talking about? This does answer the question-- an optimal solution to the dual of a program does not in general allow you to get an optimal solution to the primal. $\endgroup$ – Scrub Nov 13 '16 at 4:44
  • $\begingroup$ The other answers are absolutely incorrect, for the reason I gave in my now deleted answer (which was pointing out an obvious mistake in the inequalities). In fact you can show that if you have an algorithm that can solve a primal if given a dual solution in some time bound, you can solve the primal without the dual solution in the same time bound. (I got this as a homework problem.) $\endgroup$ – Scrub Dec 9 '16 at 23:32
  • $\begingroup$ E.g. if the primal objective function is $0$ (and the primal is feasible), $0$ is an optimal solution of the dual, and obviously that doesn't help you find a feasible solution of the primal (though it does tell you that a feasible solution exists). This is one of the "degenerate cases" I was excluding in my answer. I don't think it makes my answer "absolutely incorrect". $\endgroup$ – Robert Israel Jan 25 '17 at 23:56
  • $\begingroup$ On a second reading, your answer is reasonable, but I think your definition of nondegenerate is too narrow. The other answer has a sign error though. (Updated my answer to reflect this.) $\endgroup$ – Scrub Feb 1 '17 at 15:42
0
$\begingroup$

As many have already commented, my first answer is completely wrong.
In fact there is no general way to use the solution of the dual in order to get the solution of the primal that is not about as hard as actually solving the primal.
We must first see that in general solving a feasibility problem is as hard as solving a general LP problem (see here).
Then if we have a feasibility problem that has a solution, we know that it's dual must also have a solution(strong duality of linear programming). However the value of the solution of a feasibility problem is 0 and therefore the value of the solution of the dual is also 0.
Finally , all the inequalities of the dual are of the form $\le0$. It follows that all variables being zero is a solution to the dual, because it satisfies the positivity constraints, the inequality constraints and the value of the function is the optimal one (zero).
Therefore (one of) the optimal solution of the dual is all variables zero, all slack variables zero, which we can compute without even reading the input. It's obvious that this solution is perfectly useless for actually finding a solution to the primal. It follows that in general it is not possible to solve the primal by solving the dual.
It is true however that you can find out if the primal has an optimal solution and its value.

$\endgroup$

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.