First-order methods for the impatient: support identiﬁcation in ﬁnite time with convergent Frank-Wolfe variants

Author(s): Immanuel Bomze, Francesco Rinaldi, Samuel Rota Bulò
Abstract: In this paper, we focus on the problem of minimizing a nonconvex function over the unit simplex. We analyze two well-known and widely used variants of the Frank--Wolfe algorithm and first prove global convergence of the iterates to stationary points, both when using exact and Armijo line search. Then we show that the algorithms identify the support in a finite number of iterations (the identification result does not hold for the classic Frank--Wolfe algorithm). This, to the best of our knowledge, is the first time a manifold identification property has been shown for such a class of methods.
Organisation(s): Department of Statistics and Operations Research, Research Network Data Science
External organisation(s): University of Padova, Mapillary Research, Universita Ca' Foscari, Venezia
Journal: SIAM Journal on Optimization
Volume: 29
Pages: 2211-2226
No. of pages: 16
ISSN: 1052-6234
DOI: https://doi.org/10.1137/18M1206953
Publication date: 09-2019
Peer reviewed: Yes
Austrian Fields of Science 2012: 101016 Optimisation, 101015 Operations research
Keywords
ASJC Scopus subject areas: Software, Theoretical Computer Science
Portal url: https://ucris.univie.ac.at/portal/en/publications/firstorder-methods-for-the-impatient-support-identication-in-nite-time-with-convergent-frankwolfe-variants(f3778b80-e1b0-4df1-a3ba-5feb55efa7d5).html