I try to understand primal and dual solution for constrained optimization. So I read the article of wikipedia: Duality
Thus, I am trying to find answers for the following questions:
- Why do we need the dual form? As I have understood, the domain of the functions in dual form is convex and the dual function is concave. Thus, the optimization problem in dual is a convex optimization problem, which has just one extreme point, but in the primal form we could have many local optima. I don't know if this is correct and if this is the reason for using dual instead of primal form.
- For converting from primal to dual, what kind of method should I use? I have found the following approach. But I wasn't able to use it on the following sample:
$\min x^2+y^2 $ s.t.$-x-y+4\leq0$
I have done the following steps to convert it to dual:
I have converted to $\max_{\lambda_1}\min_{x,y} x^2+y^2+\lambda_1(-x-y+4)\\$
After that I have to rewrite in terms of (primal variable)*(expression of dual variables) plus remaining terms involving only dual variables (step 5). But I was not able to do that. How can I accomplish this in the mentioned example?
Best Answer
The concave dual objective gets maximized, which is a convex optimization problem just like the primal. We like the dual because of its elegant interpretation (in some cases), for sensitivity analysis of the primal, or for its structure. The most beautiful structure is encountered for a quadratic objective subject to a single quadratic constraint. The dual is not only convex, but the duality gap is 0 even if the primal problem is not convex!
I find the approach in this answer of mine the most practical one.