Polytope Conditioning and Linear Convergence of the Frank-Wolfe Algorithm

• 成果类型: Article
• 署名作者: Pena, Javier; Rodriguez, Daniel
• 署名单位: Carnegie Mellon University; Carnegie Mellon University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2017.0910
• 发表日期: 2019
• 页码: 1-18

摘要

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.