A Nonsmooth Frank–Wolfe Algorithm Through a Dual Cutting-Plane Approach

Guilherme Mazanti, Thibault Moquet and Laurent Pfeiffer ()
Additional contact information
Guilherme Mazanti: Université Paris-Saclay, CNRS, CentraleSupélec, Inria, Laboratoire des signaux et systèmes
Thibault Moquet: Université Paris-Saclay, CNRS, CentraleSupélec, Inria, Laboratoire des signaux et systèmes
Laurent Pfeiffer: Université Paris-Saclay, CNRS, CentraleSupélec, Inria, Laboratoire des signaux et systèmes

Journal of Optimization Theory and Applications, 2025, vol. 207, issue 2, No 10, 49 pages

Abstract: Abstract 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 $$\beta $$ β -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})$$ O ( 1 / t ) .

Keywords: Frank–Wolfe algorithm; Conditional Gradient algorithm; cutting-plane algorithms; simplicial algorithms; duality in convex analysis; nonsmooth optimization; 90C25; 90C30; 90C46 (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-025-02752-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:207:y:2025:i:2:d:10.1007_s10957-025-02752-y

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-025-02752-y

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().