Playing with Duality: An overview of recent primal?dual approaches for solving large-scale optimization problems

By Nikos Komodakis, Jean-Christophe Pesquet. IEEE Signal Processing Magazine, 2014

416 citations recorded by the source corpus.

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. However, deriving efficient strategies that jointly bring into play the primal and dual problems is a more recent idea that has generated many important new contributions in recent years. These novel developments are grounded in the recent advances in convex analysis, discrete optimization, parallel processing, and nonsmooth optimization with an emphasis on sparsity issues. In this article, we aim to present the principles of primal-dual approaches while providing an overview of the numerical methods that have been proposed in different contexts. Last but not least, primal-dual methods lead to algorithms that are easily parallelizable. Today, such parallel algorithms are becoming increasingly important for efficiently handling high-dimensional problems.

Subfields: Artificial Intelligence, Computational Mechanics, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/ead24eff5b8809bf2680bf5313fba35575675f81

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Numerical Analysis

Citations in the corpus

Stochastic Approximations and Perturbations in Forward-Backward Splitting for Monotone Operators (2015, background): “Particular cases of such fixed metric primalalgorithm can be found in [12, 15, 30, 34, 35].”
Stein Unbiased GrAdient estimator of the Risk (SUGAR) for Multiple Parameter Selection (2014, methodology): “We invite the interested reader to consult [41] for a detailed review on primal-dual algorithms.”
Visualizing Big Data with augmented and virtual reality: challenges and research agenda (2015, background): “Ivo Dinov for his research scope listed another data’s multi-dimensional characteristics [30] such as data size, incompleteness, incongruency, complex representation, multiscale nature and heterogeneity of its sources [31, 32].”
Proximal Splitting Algorithms: A Tour of Recent Advances, with New Twists. (2020, background): “There is an extensive literature about proximal splitting algorithms for solving convex optimization problems, with applications in various fields [9,13–20].”
A primal-dual algorithm with optimal stepsizes and its application in decentralized consensus optimization (2017, background): “Inter-ested readers are referred to [13,22] for the comparison of diﬀerent primal-dual algorithms for minimizing the sum of three functions.”
Linear convergence of primal-dual gradient methods and their performance in distributed optimization (2019, positive): “Assume b = 0 and consider the forward-backward gradient algorithm [32]: { wi = wi−1 − μw ( ∇J(wi−1) +Bλi−1 ) (22a) λi = λ ′ i−1 + μλB(2wi − wi−1) (22b) By using a change of variable trick, the analysis of (22) directly follows from Theorem 1 with ρ = μλ.”
Bayesian computation: a summary of the current state, and samples backwards and forwards (2015, background): “We refer the reader to Komodakis and Pesquet (2014) for an overview of recent dual and primal–dual algorithms and guidelines for parallel implementations.”
A Domain Agnostic Measure for Monitoring and Evaluating GANs (2018, background): “We conclude our discussion by pointing out the vast literature on duality used in the optimization community as a convergence criterion for min-max saddle point problems, see e.g. [23, 14].”
Bayesian computation: a perspective on the current state, and sampling backwards and forwards (2015, background): “We refer the reader to (Komodakis and Pesquet 2014) for an overview of recent dual and primal-dual algorithms and guidelines for parallel implementations.”
Conic Optimization via Operator Splitting and Homogeneous Self-Dual Embedding (2013, background): “Since then a rich literature has developed around ADMM and related methods [21, 24, 30, 32, 34, 36, 38, 39, 46, 50].”
Dualize, Split, Randomize: Fast Nonsmooth Optimization Algorithms (2020, methodology): “The application of splitting methods for monotone inclusions in particular product spaces is a powerful framework to analyze and derive primal–dual optimization algorithms [11,13–16].”
Proximal Markov chain Monte Carlo algorithms (2013, background): “Komodakis and Pesquet (2014) presents these algorithms in the primal-dual framework and provides clear guidelines for parallel and distributed implementations.”
A New Primal–Dual Algorithm for Minimizing the Sum of Three Functions with a Linear Operator (2016, methodology): “As noted in [23], there was no generalization of PAPC for three functions at that time.”