Blended Conditional Gradients: the unconditioning of conditional gradients
Preprint
Abstract
We present a blended conditional gradient approach for minimizing a smooth convex function over a polytope P, combining the Frank--Wolfe algorithm (also called conditional gradient) with gradient-based steps, different from away steps and pairwise steps, but still achieving linear convergence for strongly convex functions, along with good practical performance. Our approach retains all favorable properties of conditional gradient algorithms, notably avoidance of projections onto P and maintenance of iterates as sparse convex combinations of a limited number of extreme points of P. The algorithm is lazy, making use of inexpensive inexact solutions of the linear programming subproblem that characterizes the conditional gradient approach. It decreases measures of optimality (primal and dual gaps) rapidly, both in the number of iterations and in wall-clock time, outperforming even the lazy conditional gradient algorithms of [arXiv:1410.8816]. We also present a streamlined version of the algorithm for the probability simplex.Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- The condition number of a function relative to a setMathematical Programming, 2020
- An Extended Frank--Wolfe Method with “In-Face” Directions, and Its Application to Low-Rank Matrix CompletionSIAM Journal on Optimization, 2017
- Forward–Backward Greedy Algorithms for Atomic Norm RegularizationIEEE Transactions on Signal Processing, 2015
- New analysis and results for the Frank–Wolfe methodMathematical Programming, 2014
- MIPLIB 2010Mathematical Programming Computation, 2011
- An extension of the frank and Wolfe method of feasible directionsMathematical Programming, 1974