3
$\begingroup$

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:

  1. 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.
  2. 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?
$\endgroup$
3
  • 1
    $\begingroup$ In many cases, primal-dual solution algorithms which simultaneously solve both the primal and dual are used. With both primal and dual optimal solutions, you can confirm optimality by checking the KKT conditions and seeing that the primal and dual objective values are equal (for problems with strong duality.) $\endgroup$ Commented Jul 10, 2018 at 2:41
  • $\begingroup$ @BrianBorchers primal-dual algorithms never require a dual form though, they simply solve the KKT conditions $\endgroup$
    – LinAlg
    Commented Jul 10, 2018 at 13:25
  • $\begingroup$ I found out that it is not complete. Given $d$ = dual solution and $p$ = primal solution to an optimization problem -> then $d<=p$. If now the optimization problem is convex and the unequality constraints convex and the equality constraint affine, then $d=p$. So we can use the dual problem as a method to get a lower bound and in some circumstances as the solution for our primal equation. There are often cases that solving the primal equation is difficult, so you use the dual one to get a solution for it. But I will mark your reply as the answer. $\endgroup$
    – Code Pope
    Commented Jul 24, 2018 at 12:50

1 Answer 1

1
$\begingroup$
  1. 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!

  2. I find the approach in this answer of mine the most practical one.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .