Worst-case analysis of restarted primal-dual hybrid gradient on totally unimodular linear programs
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910766985117696 |
|---|---|
| author | Hinder, Oliver |
| author_facet | Hinder, Oliver |
| contents | We analyze restarted PDHG on totally unimodular linear programs. In particular, we show that restarted PDHG finds an $ε$-optimal solution in $O( H m_1^{2.5} \sqrt{\textbf{nnz}(A)} \log(H m_2 /ε) )$ matrix-vector multiplies where $m_1$ is the number of constraints, $m_2$ the number of variables, $\textbf{nnz}(A)$ is the number of nonzeros in the constraint matrix, $H$ is the largest absolute coefficient in the right hand side or objective vector, and $ε$ is the distance to optimality of the outputted solution. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_03988 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Worst-case analysis of restarted primal-dual hybrid gradient on totally unimodular linear programs Hinder, Oliver Optimization and Control We analyze restarted PDHG on totally unimodular linear programs. In particular, we show that restarted PDHG finds an $ε$-optimal solution in $O( H m_1^{2.5} \sqrt{\textbf{nnz}(A)} \log(H m_2 /ε) )$ matrix-vector multiplies where $m_1$ is the number of constraints, $m_2$ the number of variables, $\textbf{nnz}(A)$ is the number of nonzeros in the constraint matrix, $H$ is the largest absolute coefficient in the right hand side or objective vector, and $ε$ is the distance to optimality of the outputted solution. |
| title | Worst-case analysis of restarted primal-dual hybrid gradient on totally unimodular linear programs |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2309.03988 |