2
$\begingroup$

I understand the concept of duality in convex optimization. However, I am not able to understand how we can use it to solve problems.

Primal problems can be directly solved using Newton's method or some other method. So, what is the practical use of duality? Is it just used to get a quick lower bound in case of weak duality? How does it really simplify the problem? Is it useful for problems with discontinuous domains?

$\endgroup$
3
  • $\begingroup$ Suppose you have a non-convex problem. Find its dual, which happens to be convex. Do you see a use now? $\endgroup$ Commented Feb 25, 2019 at 19:10
  • $\begingroup$ It is very hard for novices to see such use without further explanation regarding how solving the dual helps us obtain something more than a bound on the primal optimal value. I am talking from experience in teaching. $\endgroup$ Commented Feb 25, 2019 at 19:29
  • $\begingroup$ This is really helpful. Thanks Rodrigo and Alex $\endgroup$
    – Kyan
    Commented Feb 26, 2019 at 18:13

1 Answer 1

4
$\begingroup$

There are several uses:

  1. When the primal is convex, when constructing the dual you obtained a rule for computing primal optimal solution from the dual. If the dual is, in some sense, easier, you can solve it instead of the primal.
  2. As a stopping criterion. There are algorithms which solve a convex primal and dual at the same time. At each iteration, the gap between the objective functions of the primal and the dual bounds the distance from the optimal value. Thus, you obtain an algorithm which is guaranteed to produce an optimal solution up to any desired accuracy.
  3. There are many cases in which a dual of a dual, when the primal is nonconvex, serves as a kind of approximation (known as relaxation), which serves as a heuristic for solving the primal. When the relaxation xan be proved to be tight, it actually solves the primal.
  4. In the construction and analysis of optimization algorithms. For example, the well-known Augmented Lagrangian method on a primal problem is equivalent to running the Proximal Point method on its dual. Thus, some convergence properties of one method can be used to prove convergence properties of the other.
  5. In branch and bound algorithms for nonconvex problems. The basic computational step of these algorithms requires obtaining lower bounds on the optimal value of nonconvex problems.
$\endgroup$
2
  • $\begingroup$ This really helps, Thanks $\endgroup$
    – Kyan
    Commented Feb 26, 2019 at 18:12
  • 1
    $\begingroup$ @Kyan Then accept the answer :) $\endgroup$ Commented Feb 27, 2019 at 10:05

You must log in to answer this question.

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