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\nprocessing, computer vision, and machine learning. For a long time, it has been\nrecognized that looking at the dual of an optimization problem may drastically\nsimplify its solution. Deriving efficient strategies which jointly brings into\nplay the primal and the dual problems is however a more recent idea which has\ngenerated many important new contributions in the last years. These novel\ndevelopments are grounded on recent advances in convex analysis, discrete\noptimization, parallel processing, and non-smooth optimization with emphasis on\nsparsity issues. In this paper, we aim at presenting the principles of\nprimal-dual approaches, while giving an overview of numerical methods which\nhave been proposed in different contexts. We show the benefits which can be\ndrawn from primal-dual algorithms both for solving large-scale convex\noptimization problems and discrete ones, and we provide various application\nexamples to illustrate their usefulness.\n