primal vs dual

[kentor]

Hello,

I'm trying to understand something and I just can't wrap my head
around it. Given a primal form of a problem we are trying to maximize
the objective function. We can also convert this problem to its dual
and then look for a minimization of the problem. What I don't
understand is why do we want to take the dual if we can solve the LP
with the primal form ? I don't understand what is the Dual's purpose
or maybe I'm missing the concept. Thanks for your help.

[tc...@lsa.umich.edu]

In article <2b0f6645-5223-412f...@l13g2000yqb.googlegroups.com>,

The simplest reason for considering the dual is that in some cases,
the dual problem turns out to be easier to solve. In other cases,
going back and forth between the primal and the dual works better in
practice than working with just one or the other by itself. Having both
perspectives increases the size of your toolkit.

Considering the dual also lets you get bounds on the solution to your
problem, which is particularly useful if finding the optimal solution is
very time-consuming. Specifically, any feasible solution for the dual
problem gives you a bound on the cost of the primal problem.

Duality allows you to prove some useful theoretical results, e.g., the
Farkas Lemma. If you have an infeasible linear program, it would be nice
to have a succinct certificate that it is infeasible, instead of just
blindly trusting a computer program that says, "There is no solution."
The Farkas Lemma tells you that if a set of inequalities Ax <= b has no
solution, then you can exhibit a nonnegative linear combination of these
inequalities that is an obvious contradiction (i.e., a vector y >= 0 such
that y^T A = 0 and y^T b = -1). The Farkas Lemma is most naturally proved
using duality.

Later on, you may go on to study integer linear programs. In many cases,
it is not possible to solve these problems exactly. Sometimes the dual
formulation of the problem suggests heuristics for approximating the
problem that might not be so obvious from the primal formulation.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences

[kentor]

On Nov 5, 10:10 pm, tc...@lsa.umich.edu wrote:
> In article <2b0f6645-5223-412f-9da2-8cc3c034d...@l13g2000yqb.googlegroups.com>,

Thank you, that is very helpful

[deepakc]

Hello Kentor,

Tim correctly mentioned that Dual formulations help to obtain bounds
on the primal solution. If the primal is a minimization problem, then
the dual's solution is a lower bound for the primal's solution. If the
primal is a maximization problem, then the dual's solution is an upper
bound for the primal's solution. If the primal is convex (like in
LPs), then the dual's solution is actually EQUAL to the dual's
solution.

Here, I would also like to add on to what Tim said. In the case of LP,
another reason why we may wish to convert an LP into its dual is to
reduce the number of variables. Example, if the primal has 10
variables and 2 constraints, then the dual would have only 2
variables. As you probably already know, there exists strongly
polynomial algorithms for an LP with 2 unknowns, whereas there exist
only weakly polynomial algorithms for LPs with more than 2 unknowns.

Thanks,
-Deepak

[kentor]

This is also very helpful thank you very much!