A Primal-Dual Frank-Wolfe Algorithm for Linear Programming
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909122867232768 |
|---|---|
| author | Hough, Matthew Vavasis, Stephen A. |
| author_facet | Hough, Matthew Vavasis, Stephen A. |
| contents | We present two first-order primal-dual algorithms for solving saddle point formulations of linear programs, namely FWLP (Frank-Wolfe Linear Programming) and FWLP-P. The former iteratively applies the Frank-Wolfe algorithm to both the primal and dual of the saddle point formulation of a standard-form LP. The latter is a modification of FWLP in which regularizing perturbations are used in computing the iterates. We show that FWLP-P converges to a primal-dual solution with error $O(1/\sqrt{k})$ after $k$ iterations, while no convergence guarantees are provided for FWLP. We also discuss the advantages of using FWLP and FWLP-P for solving very large LPs. In particular, we argue that only part of the matrix $A$ is needed at each iteration, in contrast to other first-order methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_18514 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Primal-Dual Frank-Wolfe Algorithm for Linear Programming Hough, Matthew Vavasis, Stephen A. Optimization and Control 90C05, 65K05 G.1.6 We present two first-order primal-dual algorithms for solving saddle point formulations of linear programs, namely FWLP (Frank-Wolfe Linear Programming) and FWLP-P. The former iteratively applies the Frank-Wolfe algorithm to both the primal and dual of the saddle point formulation of a standard-form LP. The latter is a modification of FWLP in which regularizing perturbations are used in computing the iterates. We show that FWLP-P converges to a primal-dual solution with error $O(1/\sqrt{k})$ after $k$ iterations, while no convergence guarantees are provided for FWLP. We also discuss the advantages of using FWLP and FWLP-P for solving very large LPs. In particular, we argue that only part of the matrix $A$ is needed at each iteration, in contrast to other first-order methods. |
| title | A Primal-Dual Frank-Wolfe Algorithm for Linear Programming |
| topic | Optimization and Control 90C05, 65K05 G.1.6 |
| url | https://arxiv.org/abs/2402.18514 |