Playing with Duality: An Overview of Recent Primal-Dual Approaches for Solving Large-Scale Optimization Problems

Abstract

Optimization methods are at the core of many problems in signal/image processing, computer vision, and machine learning. For a long time, it has been recognized that looking at the dual of an optimization problem may drastically simplify its solution. Deriving efficient strategies which jointly brings into play the 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 analysis, discrete optimization, parallel processing, and non-smooth 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 methods which have been proposed in different contexts. We show the benefits which can be drawn from primal-dual algorithms both for solving large-scale convex optimization problems and discrete ones, and we provide various application examples to illustrate their usefulness.

References in corpus (11)

• Tightening LP Relaxations for MAP using Message Passing
• Optimal Transport with Proximal Splitting
• On the Linear Convergence of the Alternating Direction Method of Multipliers
• Adaptive Primal-Dual Hybrid Gradient Methods for Saddle-Point Problems
• Stability and Performance Limits of Adaptive Primal-Dual Networks
• Proximal Reinforcement Learning: A New Theory of Sequential Decision Making in Primal-Dual Spaces
• An Algorithm for Splitting Parallel Sums of Linearly Composed Monotone Operators, with Applications to Signal Recovery
• Deconvolution of Poissonian Images Using Variable Splitting and Augmented Lagrangian Optimization
• Convergence rate analysis of the forward-Douglas-Rachford splitting scheme
• A Primal-Dual Algorithmic Framework for Constrained Convex Minimization
• Convergence Rates with Inexact Non-expansive Operators

Cited by in corpus (5)

• A Three-Operator Splitting Scheme and its Optimization Applications
• How to learn a graph from smooth signals
• A Class of Randomized Primal-Dual Algorithms for Distributed Optimization
• Convergence rate analysis of the forward-Douglas-Rachford splitting scheme
• Convergence rate analysis of primal-dual splitting schemes