Proximal algorithms and temporal difference methods for solving fixed point problems
Abstract In this paper we consider large fixed point problems and solution with proximal algorithms. We show that for linear problems there is a close connection between proximal iterations, which are prominent in numerical analysis and optimization, and multistep methods of the tempo...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer US
2021
|
| Online Access: | https://hdl.handle.net/1721.1/131865 |
| _version_ | 1811069675640979456 |
|---|---|
| author | Bertsekas, Dimitri P |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Bertsekas, Dimitri P |
| author_sort | Bertsekas, Dimitri P |
| collection | MIT |
| description | Abstract
In this paper we consider large fixed point problems and solution with proximal algorithms. We show that for linear problems there is a close connection between proximal iterations, which are prominent in numerical analysis and optimization, and multistep methods of the temporal difference type such as TD(
$$\lambda $$
λ
), LSTD(
$$\lambda $$
λ
), and LSPE(
$$\lambda $$
λ
), which are central in simulation-based exact and approximate dynamic programming. One benefit of this connection is a new and simple way to accelerate the standard proximal algorithm by extrapolation towards a multistep iteration, which generically has a faster convergence rate. Another benefit is the potential for integration into the proximal algorithmic context of several new ideas that have emerged in the approximate dynamic programming context, including simulation-based implementations. Conversely, the analytical and algorithmic insights from proximal algorithms can be brought to bear on the analysis and the enhancement of temporal difference methods. We also generalize our linear case result to nonlinear problems that involve a contractive mapping, thus providing guaranteed and potentially substantial acceleration of the proximal and forward backward splitting algorithms at no extra cost. Moreover, under certain monotonicity assumptions, we extend the connection with temporal difference methods to nonlinear problems through a linearization approach. |
| first_indexed | 2024-09-23T08:14:10Z |
| format | Article |
| id | mit-1721.1/131865 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T08:14:10Z |
| publishDate | 2021 |
| publisher | Springer US |
| record_format | dspace |
| spelling | mit-1721.1/1318652023-12-22T19:11:46Z Proximal algorithms and temporal difference methods for solving fixed point problems Bertsekas, Dimitri P Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Abstract In this paper we consider large fixed point problems and solution with proximal algorithms. We show that for linear problems there is a close connection between proximal iterations, which are prominent in numerical analysis and optimization, and multistep methods of the temporal difference type such as TD( $$\lambda $$ λ ), LSTD( $$\lambda $$ λ ), and LSPE( $$\lambda $$ λ ), which are central in simulation-based exact and approximate dynamic programming. One benefit of this connection is a new and simple way to accelerate the standard proximal algorithm by extrapolation towards a multistep iteration, which generically has a faster convergence rate. Another benefit is the potential for integration into the proximal algorithmic context of several new ideas that have emerged in the approximate dynamic programming context, including simulation-based implementations. Conversely, the analytical and algorithmic insights from proximal algorithms can be brought to bear on the analysis and the enhancement of temporal difference methods. We also generalize our linear case result to nonlinear problems that involve a contractive mapping, thus providing guaranteed and potentially substantial acceleration of the proximal and forward backward splitting algorithms at no extra cost. Moreover, under certain monotonicity assumptions, we extend the connection with temporal difference methods to nonlinear problems through a linearization approach. 2021-09-20T17:30:42Z 2021-09-20T17:30:42Z 2018-03-02 2020-09-24T21:34:30Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/131865 en https://doi.org/10.1007/s10589-018-9990-5 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ Springer Science+Business Media, LLC, part of Springer Nature application/pdf Springer US Springer US |
| spellingShingle | Bertsekas, Dimitri P Proximal algorithms and temporal difference methods for solving fixed point problems |
| title | Proximal algorithms and temporal difference methods for solving fixed point problems |
| title_full | Proximal algorithms and temporal difference methods for solving fixed point problems |
| title_fullStr | Proximal algorithms and temporal difference methods for solving fixed point problems |
| title_full_unstemmed | Proximal algorithms and temporal difference methods for solving fixed point problems |
| title_short | Proximal algorithms and temporal difference methods for solving fixed point problems |
| title_sort | proximal algorithms and temporal difference methods for solving fixed point problems |
| url | https://hdl.handle.net/1721.1/131865 |
| work_keys_str_mv | AT bertsekasdimitrip proximalalgorithmsandtemporaldifferencemethodsforsolvingfixedpointproblems |