CoChat

Proximal Algorithms

Parikh, Neal, Boyd, Stephen · 2014 · Foundations and Trends® in Optimization

The DOI matches its Crossref record; 180 of the 182 references it cites were found in a registry or an index.

Abstract

This monograph is about a class of optimization algorithms called proximal algorithms. Much like Newton’s method is a standard tool for solving unconstrained smooth optimization problems of modest size, proximal algorithms can be viewed as an analogous tool for nonsmooth, constrained, large-scale, or distributed versions of these problems. They are very generally applicable, but are especially well-suited to problems of substantial recent interest involving large or high-dimensional datasets. Proximal methods sit at a higher level of abstraction than classical algorithms like Newton’s method: the base operation is evaluating the proximal operator of a function, which itself involves solving a small convex optimization problem. These subproblems, which generalize the problem of projecting a point onto a convex set, often admit closed-form solutions or can be solved very quickly with standard or simple specialized methods. Here, we discuss the many different interpretations of proximal operators and algorithms, describe their connections to many other topics in optimization and applied mathematics, survey some popular algorithms, and provide a large number of examples of proximal operators that commonly arise in practice.

Overview

Integrity signals

Registry

Crossref · 10.1561/2400000003

Cites

180 of 180 references verified0 citation errors · 0 not checkable

Statistics

Recomputing p-values needs the paper’s full text.

Verification

Claims the paper makes

This paper’s full text isn’t openly available, so its claims and self-check weren’t run. The registry and citation checks still apply.

Citations

Cites

Show all 180 references

Research works printed but not linked: 37

  1. Arrow, 1958, Studies in Linear and Nonlinear Programming
  2. Attouch, 1977, Convergence de fonctions convexes, de sous-différentiels et semi-groupes, C.R Acad. Sei. Paris, 284, 539
  3. Beck, 2010, Convex Optimization in Signal Processing and Communications, 42
  4. Bertsekas, 1999, Nonlinear Programming
  5. Bertsekas, 1989, Parallel and Distributed Computation: Numerical Methods
  6. Blackford, 1997, ScaLAPACK user’s guide, 10.1137/1.9780898719642 · DOI · Paper page
  7. Boyd, 2007, Localization and cutting-plane methods
  8. Candès, 2009, Robust principal component analysis?
  9. Chandrasekaran, 2009, Allerton 2009, 962
  10. Daniilidis, 2013, Orthogonal invariance and identifiability
  11. Demmel, 1993, Parallel numerical linear algebra, 10.1017/S096249290000235X · doi:10.1017/s096249290000235x
  12. Dempster, 1972, Covariance selection, Biometrics, 28, 157, 10.2307/2528966 · DOI · Paper page
  13. Duchi, 2008, Efficient projections onto the Q-ball for learning in high dimensions, 272
  14. Franklin, 1994, Feedback Control of Dynamic Systems, 10.1115/IMECE1994-0541 · doi:10.1115/imece1994-0541
  15. Gabay, 1983, Augmented Lagrangian Methods: Applications to the Solution of Boundary-Value Problems
  16. Goldfarb, 2011, Fast first-order methods for composite convex optimization with line search
  17. Granas, 2003, Fixed Point Theory, 10.1007/978-0-387-21593-8 · doi:10.1007/978-0-387-21593-8
  18. Lusem, 1999, Augmented Lagrangian methods and proximal point methods for convex optimization, Investigación Operativa, 8, 11
  19. Jenatton, 2010, Proximal methods for sparse hierarchical dictionary learning
  20. Kachurovskii, 1960, Monotone operators and convex functionals, Uspekhi Matematicheskikh Nauk, 15, 213
  21. Kim, 2009, ℓ1 trend filtering, SIAM Review, 51, 339, 10.1137/070690274 · DOI · Paper page
  22. Lemaire, 1989, The proximal algorithm, 73
  23. Ma, 2012, Alternating direction methods for latent variable gaussian graphical model selection
  24. Martinet, 1970, Régularisation d’inéquations variationnelles par approximations successives
  25. Martinet, 1972, Détermination approchée d’un point fixe d’une application pseudo-contractante, C.R. Acad. Sei. Paris, 274A, 163
  26. Nedic, 2010, Convex Optimization in Signal Processing and Communications
  27. Nesterov, 1983, A method of solving a convex programming problem with convergence rate O(1/k2), Soviet Mathematics Doklady, 27, 372
  28. Quattoni, 2009, An efficient projection for ℓ1,∞ regularization, 857
  29. Rockafellar, 1970, Convex Analysis, 10.1515/9781400873173 · DOI · Paper page
  30. Rockafellar, 1998, Variational Analysis, 10.1007/978-3-642-02431-3 · DOI · Paper page
  31. Tseng, 2008, On accelerated proximal gradient methods for convex-concave optimization
  32. Vandenberghe, 2010, Optimization methods for large-scale systems
  33. von Neumann, 1937, Some matrix inequalities and metrization of matrix space, Tomsk University Review, 1, 286
  34. von Neumann, Functional Operators, Volume 2: The Geometry of Orthogonal Spaces
  35. Yosida, 1968, Functional Analysis, 10.1007/978-3-662-11791-0 · doi:10.1007/978-3-662-11791-0
  36. Zarantonello, 1960, Solving functional equations by contractive averaging
  37. Zarantonello, 1971, Projections on convex sets in Hilbert space and spectral theory. I. Projections on convex sets, 237

Cited by

Items 1,001–1,007 of 1,007

Metadata

Authors
Parikh, N., & Boyd, S.
Affiliations
Stanford University (US)
Venue
Foundations and Trends® in Optimization
Publisher
Emerald
Published
2014-01-13
Volume
1
Issue
3
Pages
127-239
ISSN
  • 2167-3888 (ISSN-L)
  • 2167-3918
OpenAlex
W2913535645
Cited by
4,102
References
182
Citations by year
2026: 204 · 2025: 310 · 2024: 331 · 2023: 321 · 2022: 312 · 2021: 432 · 2020: 443 · 2019: 460 · 2018: 407 · 2017: 315 · 2016: 278 · 2015: 189 · 2014: 85
FWCI
299.06
Type
journal article
Language
en
Open access
closed
Locations
  • Foundations and Trends® in Optimization (publishedVersion)
  • now publishers, Inc. eBooks (publishedVersion)
  • CERN Document Server (European Organization for Nuclear Research) (submittedVersion)
Topics
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Optimization and Variational Analysis
  • Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
  • Physical Sciences › Computer Science › Signal Processing › Sparse and Compressive Sensing Techniques
Keywords
proximal operator, proximal algorithms, convex optimization, distributed optimization, nonsmooth optimization, large-scale optimization, high-dimensional data, projection onto convex sets, iterative optimization

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.