A dual algorithm for the solution of nonlinear variational problems via finite element approximation

By D. Gabay, B. Mercier. 1976

For variational problems of the form Infv∈V{f(Av)+g(v)} , we propose a dual method which decouples the difficulties relative to the functionals f and g from the possible ill-conditioning effects of the linear operator A. The approach is based on the use of an Augmented Lagrangian functional and leads to an efficient and simply implementable algorithm. We study also the finite element approximation of such problems, compatible with the use of our algorithm. The method is finally applied to solve several problems of continuum mechanics.

Subfields: Numerical Methods & Scientific Computing

How researchers see this paper

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

In Numerical Methods & Scientific Computing

Citations in the corpus

Frank-Wolfe Splitting via Augmented Lagrangian Method (2018, methodology): “One of the most popular algorithms in this framework is the alternating direction method of multipliers ( ADMM ), proposed by Glowinski and Marroco (1975), studied by Gabay and Mercier (1976), and revisited many times; see for instance (Boyd et al., 2011; Yan and Yin, 2016).”
Optimization Methods for Large-Scale Machine Learning (2016, methodology): “There are important methods that are not included in our presentation—such as the alternating direction method of multipliers (ADMM) [54, 61, 64] and the expectation-maximization (EM) method and its variants [45, 153]—but our study covers many of the core algorithmic frameworks in optimization for m”
GADMM: Fast and Communication Efficient Framework for Distributed Machine Learning (2019, methodology): “Consensus optimization underlies most of the primal methods, while dual decomposition and ADMM are the most popular among the primal-dual algorithms (Glowinski and Marroco, 1975; Gabay and Mercier, 1975; Boyd et al., 2011; Jaggi et al., 2014; Ma et al., 2017; Deng et al., 2017).”
Computational Optimal Transport (2018, methodology): “more recently by Galichon and Salanié [2009]. This regularization has received recently renewed attention in data sciences (including machine learning, vision, graphics and imaging) following [Cuturi, 2013], who showed that Sinkhorn’s algorithm provides a scalable way to approximate optimal transpor”
A Generalized Forward-Backward Splitting (2011, methodology): “It was shown that applying the Douglas-Rachford scheme leads to the alternating direction method of multipliers (ADMM) [37, 44, 45, 46, 47].”
Fast ℓ1-minimization algorithms and an application in robust face recognition: A review (2010, background): “ADM can be attributed to the early works of [22], [21].”
Global Convergence of ADMM in Nonconvex Nonsmooth Optimization (2015, unknown): “The original ADMM was proposed in [20,18].”
Randomized First-Order Methods for Saddle Point Optimization (2014, unknown): “1) can be solved effectively by using primal-dual algorithms [8, 2, 5, 23] and Alternating Direction Method of Multipliers (ADMM) methods [4, 12, 6, 19].”
Robust Low-Rank Tensor Recovery: Models and Algorithms (2013, methodology): “2), we develop an alternating direction augmented Lagrangian (ADAL) method [21, 19](1) to take advantage of the problem structure.”
Alternating Direction Method with Self-Adaptive Penalty Parameters for Monotone Variational Inequalities (2000, methodology): “In order to improve such methods, some researchers suggested to use methods that replace the constant β in ( 6 )‐(8) by a variable penalty sequence {β k}. For example, Nagurney et al. (Ref.”
Stochastic Dual Coordinate Ascent with Alternating Direction Method of Multipliers (2014, methodology): “ADMM is an effective optimization method to solve a composite optimization problem described as minx f(x) + g(y) s.t. Ax + By = 0 (Gabay and Mercier, 1976; Boyd et al., 2010; Qin and Goldfarb, 2012).”
Walkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimization (2018, methodology): “Walkman can be derived by modifying existing algorithms to use a random walk, for example, ADMM [31], [32] or PPG [33].”
Removing Multiplicative Noise by Douglas-Rachford Splitting Methods (2010, background): “As pointed out by Esser in [27], this algorithm can be traced back to the ADMM proposed in [34, 38].”
An Augmented Lagrangian Approach to the Constrained Optimization Formulation of Imaging Inverse Problems (2009, methodology): “The simplest answer to these questions is given in the form of the so-called ADMM [24], [32], [33], which is simply an ALM/MM in which only one NLBGS step is performed in each outer iteration.”