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

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 ) .