Polytope Conditioning and Linear Convergence of the Frank–Wolfe Algorithm

Jan Ossenbrink () and Joern Hoppmann ()
Additional contact information
Jan Ossenbrink: Department of Management, Technology, and Economics, ETH Zurich, 8092 Zurich, Switzerland; Stanford Graduate School of Business, Stanford University, Stanford, California 94305
Joern Hoppmann: Department of Management, Technology, and Economics, ETH Zurich, 8092 Zurich, Switzerland; Department of Business Administration, Economics, and Law, University of Oldenburg, 26129 Oldenburg, Germany

Mathematics of Operations Research, 2019, vol. 44, issue 1, 1319-1348

Abstract: It is well known that the gradient descent algorithm converges linearly when applied to a strongly convex function with Lipschitz gradient. In this case, the algorithm’s rate of convergence is determined by the condition number of the function. In a similar vein, it has been shown that a variant of the Frank–Wolfe algorithm with away steps converges linearly when applied to a strongly convex function with Lipschitz gradient over a polytope. In a nice extension of the unconstrained case, the algorithm’s rate of convergence is determined by the product of the condition number of the function and a certain condition number of the polytope. We shed new light on the latter type of polytope conditioning. In particular, we show that previous and seemingly different approaches to define a suitable condition measure for the polytope are essentially equivalent to each other. Perhaps more interesting, they can all be unified via a parameter of the polytope that formalizes a key premise linked to the algorithm’s linear convergence. We also give new insight into the linear convergence property. For a convex quadratic objective, we show that the rate of convergence is determined by a condition number of a suitably scaled polytope.

Keywords: linear convergence; Frank–Wolfe; polytope conditioning (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1287/moor.2017.0910 (application/pdf)

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:inm:ormoor:v:44:y:2019:i:1:p:1319-1348

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().