Optimal Design of Resolvent Splitting Algorithms
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916378783514624 |
|---|---|
| author | Bassett, Robert L Barkley, Peter |
| author_facet | Bassett, Robert L Barkley, Peter |
| contents | In this paper, we introduce a novel semidefinite programming framework for designing custom frugal resolvent splitting algorithms which find a zero in the sum of n monotone operators. This framework features a number of design choices which facilitate creating resolvent splitting algorithms with specific communication structure. We illustrate these design choices using a variety of constraint sets and objective functions, as well as the use of a mixed-integer SDP to minimize time per iteration or required number of communications between the resolvents which define the splitting. Using the Performance Estimation Problem (PEP) framework, we provide parameter selections, such as step size, which for high dimensional problems provide optimal contraction factors in the algorithms. Among the algorithm design choices we introduce, we provide a characterization of algorithm designs which provide minimal convergence time given structural properties of the monotone operators, resolvent computation times, and communication latencies. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_16159 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Optimal Design of Resolvent Splitting Algorithms Bassett, Robert L Barkley, Peter Optimization and Control 49M37, 65K05 In this paper, we introduce a novel semidefinite programming framework for designing custom frugal resolvent splitting algorithms which find a zero in the sum of n monotone operators. This framework features a number of design choices which facilitate creating resolvent splitting algorithms with specific communication structure. We illustrate these design choices using a variety of constraint sets and objective functions, as well as the use of a mixed-integer SDP to minimize time per iteration or required number of communications between the resolvents which define the splitting. Using the Performance Estimation Problem (PEP) framework, we provide parameter selections, such as step size, which for high dimensional problems provide optimal contraction factors in the algorithms. Among the algorithm design choices we introduce, we provide a characterization of algorithm designs which provide minimal convergence time given structural properties of the monotone operators, resolvent computation times, and communication latencies. |
| title | Optimal Design of Resolvent Splitting Algorithms |
| topic | Optimization and Control 49M37, 65K05 |
| url | https://arxiv.org/abs/2407.16159 |