2
$\begingroup$

Is the formulation of dual problem easier than the primal problem to solve, so that duality provides convenience for solving the optimization problem?

Or, does the dual formulation provide a useful theoretical instrument to prove theorems or show properties of optimization problems?

I am not clear about the motivation to study the duality in optimization. Some examples can be very helpful! Thanks!

$\endgroup$
2
  • 1
    $\begingroup$ It's interesting to note that Nesterov in his book Introductory Lectures on Convex Optimization did not even discuss the dual problem. In the preface he says, "Any concept or fact included in the book is absolutely necessary for the analysis of at least one optimization scheme. Surprisingly enough, none of the material presented requires any facts from duality theory. Thus, this topic is completely omitted. This does not mean, of course, that the author neglect this fundamental concept. However, we hope that for the first treatment of the subject such a compromise is acceptable." $\endgroup$
    – littleO
    Commented Aug 9, 2018 at 19:44
  • 1
    $\begingroup$ Many convex optimization algorithms can be interpreted as iterative methods for solving the KKT conditions. When we solve the KKT conditions, we are simultaneously solving the primal and the dual problem. For example, I think primal-dual interior point methods can be motivated by the idea of solving the KKT conditions using Newton's method. (This simple idea does not quite work because of the inequality constraints in the KKT conditions, so we modify the idea slightly to make it workable and discover interior point methods.) $\endgroup$
    – littleO
    Commented Aug 9, 2018 at 19:47

2 Answers 2

3
$\begingroup$

One major reason is that the dual problem helps you to derive lower bounds (in the case of minimization) on the achievable objective. This can be exploited when developing solvers.

$\endgroup$
5
  • $\begingroup$ And what is the purpose of finding lower bounds? $\endgroup$ Commented Jul 21, 2021 at 15:17
  • 1
    $\begingroup$ to know how good solutions there possibly could be (if you have a solution, i.e. an upper bound, if you have a lower bound you can use that to judge how good the solution is) $\endgroup$ Commented Jul 21, 2021 at 17:14
  • $\begingroup$ So I understand that I can gradually decrease the gap to a certain tolerance, that's when my solution is relatively good, right? $\endgroup$ Commented Jul 21, 2021 at 17:44
  • 1
    $\begingroup$ If your dual algorithm has given a lower bound of say 56 and your solution has objective value 56.0000001, you know you cannot find anything much better and if that is close enough, you can terminate the search. $\endgroup$ Commented Jul 21, 2021 at 18:46
  • $\begingroup$ Thank you very much Johan Löfberg $\endgroup$ Commented Jul 21, 2021 at 23:33
1
$\begingroup$

Duality makes the problem easier most of the times it is being used for example an optimization problem with 3 variables and 10 constraints has a duality with 3 constraints and 10 variables. This is because the complexity of an optimization problem mostly depends on the number of constraints not variables.

$\endgroup$

You must log in to answer this question.

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