How to use duality in optimization?

Question

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?

Answer 1

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.