Playing with Duality: An Overview of Recent Primal Dual Approaches for Solving Large Scale Optimization Problems
Optimization methods are at the core of many problems in signal/image proce ssing, computer vision, and machine learning. For a long time, it has been recognized that looking at the dual o f an ptimization problem may drastically simplify its solution. Deriving efficient strategies which jointly brings into play th e primal and the dual problems is however a more recent idea which has generated many important new contributions in the last years. These novel developments are grounded on recent advances in convex an alysis, discrete optimization, parallel processing, and nonsmooth optimization with emphasis on sparsity issues. In this paper, we aim at presenting the principles of primal dual approaches, while giving an overview of numerical me thods which have been proposed in different contexts. We show the benefits which can be drawn from primal dual algo rithms both for solving large scale convex optimization problems and discrete ones, and we provide various applicatio n examples to illustrate their usefulness.