Backing PDHG into a Corner
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908660527005696 |
|---|---|
| author | Rothberg, Edward |
| author_facet | Rothberg, Edward |
| contents | Recent enhancements to the Primal-Dual Hybrid Gradient (PDHG)
algorithm have enabled GPUs to efficiently solve large linear
programming problems, often faster than the long-dominant simplex
and interior-point methods. The solutions found by PDHG are
typically of much lower quality than those found by the
alternatives, which can be remedied by following the PDHG iterations
with a crossover step to obtain an accurate optimal basic solution.
However, the cost of this highly sequential crossover step can be
quite significant. This paper examines whether PDHG iterations can
be enhanced to push the solution into a corner of the optimal LP
face, thereby providing crossover a better starting point and
hopefully reducing its runtime. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_13894 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Backing PDHG into a Corner Rothberg, Edward Optimization and Control Recent enhancements to the Primal-Dual Hybrid Gradient (PDHG) algorithm have enabled GPUs to efficiently solve large linear programming problems, often faster than the long-dominant simplex and interior-point methods. The solutions found by PDHG are typically of much lower quality than those found by the alternatives, which can be remedied by following the PDHG iterations with a crossover step to obtain an accurate optimal basic solution. However, the cost of this highly sequential crossover step can be quite significant. This paper examines whether PDHG iterations can be enhanced to push the solution into a corner of the optimal LP face, thereby providing crossover a better starting point and hopefully reducing its runtime. |
| title | Backing PDHG into a Corner |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2511.13894 |