Optimization Online


First-order methods for the impatient: support identification in finite time with convergent Frank-Wolfe variants

Immanuel M. Bomze (immanuel.bomze***at***univie.ac.at)
Francesco Rinaldi (rinaldi***at***math.unipd.it)
Samuel Rota Bulo' (samuel***at***mapillary.com)

Abstract: In this paper, we focus on the problem of minimizing a non-convex 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. This, to the best of our knowledge, is the first time a manifold identification property has been shown for such a class of methods.

Keywords: surface identification, manifold identification, active set, finite convergence

Category 1: Nonlinear Optimization (Constrained Nonlinear Optimization )

Citation: Technical Report, 2018

Download: [PDF]

Entry Submitted: 07/03/2018
Entry Accepted: 07/03/2018
Entry Last Modified: 04/02/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society