2017/10/19 by Hong‐Kun Xu, Xu, Hong-Kun · 1 citation
Computer Science · Engineering · Mathematics · #49M37 #65K05 #90C25 #FOS: Mathematics #Numerical methods in inverse problems #Optimization and Control (math.OC) #Optimization and Variational Analysis #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.1710.07367
openalex publication_date 2017/10/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Frank-Wolfe algorithm, a very first optimization method and also known as the conditional gradient method, was introduced by Frank and Wolfe in 1956. Due to its simple linear subproblems, the Frank-Wolfe algorithm has recently been received much attention for solving large-scale structured optimization problems arising from many applied areas such as signal processing and machine learning. In this paper we will discuss in detail the convergence analysis of the Frank-Wolfe algorithm in Banach spaces. Two ways of the selections of the stepsizes are discussed: the line minimization search method and the open loop rule. In both cases, we prove the convergence of the Frank-Wolfe algorithm in the case where the objective function f has uniformly continuous (on bounded sets) Fréchet derivative f'. We introduce the notion of the curvature constant of order σ∈ (1,2] and obtain the rate O(\frac1kσ-1) of convergence of the Frank-Wolfe algorithm. In particular, this rate reduces to O((1)/(kν)) if f' is ν-Hölder continuous for ν∈ (0,1], and to O((1)/(k)) if f' is Lipschitz continuous. A generalized Frank-Wolfe algorithm is also introduced to address the problem of minimizing a composite objective function. Convergence of iterates of both Frank-Wolfe and generalized Frank-Wolfe algorithms are investigated.