9
$\begingroup$

I'm interested in portfolio optimization and there's a lot of modelizations out there using duality theory. Since I didn't study that yet, I searched around the net to understand what it means and kind of did. But I still have one issue : what does duality theory gives us ?

I mean, from where I stand, here is how I see it : We have a "primal" optimization problem with some variables and some constraints, we then "build" a dual problem with new variables (each old constraint -> one new variable) and new contraints. Then, in order to find a solution for our original problem, we solve the second one, the dual one.

My question is : What characteristics does the dual problem have that makes it simpler or more useful to solve ? What's the differences between the primal problem and the dual one ?

Also, if anyone has a good reference for the course, that explains what's behind it and gives practical examples, I would very much like to have it !

Thank you all.

$\endgroup$
7
$\begingroup$

That's a pretty heavy question for this forum, and its answer is worthy of a semester-long discussion in a university course. The short answer is that (for convex optimization) the dual problem can give you a lower bound on your objective function (for minimization).

In addition, the values of the dual variables are related to the sensitivity of your objective function to your constraint values. Lastly, the nonzero dual variables indicate which primal constraints are "tight". This is known as "complementary slackness".

The dual problem is not necessarily any easier to solve than the primal, but it does give good information to solvers. LP solvers in particular will track the solution to both problems simultaneously. Then, since the dual problem gives a bound on the primal objective value, the solver has some idea of how close it is to a global optimum. In fact, for a linear program, the primal and dual have identical optima, so virtually all modern LP solvers use it to at least track solution progress.

For a more in-depth discussion of the topic, I encourage you to pick up any linear/convex optimization text. I personally like "Introduction to linear optimization" by Bertsimas and Tsitsiklis.

$\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.