A nonsmooth Frank-Wolfe algorithm through a dual cutting-plane approach
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_ | 1866916180400275456 |
|---|---|
| author | Mazanti, Guilherme Moquet, Thibault Pfeiffer, Laurent |
| author_facet | Mazanti, Guilherme Moquet, Thibault Pfeiffer, Laurent |
| contents | An extension of the Frank-Wolfe Algorithm (FWA), also known as Conditional Gradient algorithm, is proposed. In its standard form, the FWA allows to solve constrained optimization problems involving $β$-smooth cost functions, calling at each iteration a Linear Minimization Oracle. More specifically, the oracle solves a problem obtained by linearization of the original cost function. The algorithm designed and investigated in this article, named Dualized Level-Set (DLS) algorithm, extends the FWA and allows to address a class of nonsmooth costs, involving in particular support functions. The key idea behind the construction of the DLS method is a general interpretation of the FWA as a cutting-plane algorithm, from the dual point of view. The DLS algorithm essentially results from a dualization of a specific cutting-plane algorithm, based on projections on some level sets. The DLS algorithm generates a sequence of primal-dual candidates, and we prove that the corresponding primal-dual gap converges with a rate of $O(1/\sqrt{t})$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_18744 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A nonsmooth Frank-Wolfe algorithm through a dual cutting-plane approach Mazanti, Guilherme Moquet, Thibault Pfeiffer, Laurent Optimization and Control 90C25 90C30 90C46 An extension of the Frank-Wolfe Algorithm (FWA), also known as Conditional Gradient algorithm, is proposed. In its standard form, the FWA allows to solve constrained optimization problems involving $β$-smooth cost functions, calling at each iteration a Linear Minimization Oracle. More specifically, the oracle solves a problem obtained by linearization of the original cost function. The algorithm designed and investigated in this article, named Dualized Level-Set (DLS) algorithm, extends the FWA and allows to address a class of nonsmooth costs, involving in particular support functions. The key idea behind the construction of the DLS method is a general interpretation of the FWA as a cutting-plane algorithm, from the dual point of view. The DLS algorithm essentially results from a dualization of a specific cutting-plane algorithm, based on projections on some level sets. The DLS algorithm generates a sequence of primal-dual candidates, and we prove that the corresponding primal-dual gap converges with a rate of $O(1/\sqrt{t})$. |
| title | A nonsmooth Frank-Wolfe algorithm through a dual cutting-plane approach |
| topic | Optimization and Control 90C25 90C30 90C46 |
| url | https://arxiv.org/abs/2403.18744 |