Frank-Wolfe and friends: a journey into projection-free first-order optimization methods
From MaRDI portal
Publication:2240671
DOI10.1007/S10288-021-00493-YzbMATH Open1479.90131arXiv2106.10261OpenAlexW3198484963MaRDI QIDQ2240671FDOQ2240671
Damiano Zeffiro, Immanuel M. Bomze, F. Rinaldi
Publication date: 4 November 2021
Published in: 4OR (Search for Journal in Brave)
Abstract: Invented some 65 years ago in a seminal paper by Marguerite Straus-Frank and Philip Wolfe, the Frank-Wolfe method recently enjoys a remarkable revival, fuelled by the need of fast and reliable first-order optimization methods in Data Science and other relevant application areas. This review tries to explain the success of this approach by illustrating versatility and applicability in a wide range of contexts, combined with an account on recent progress in variants, both improving on the speed and efficiency of this surprisingly simple principle of first-order optimization.
Full work available at URL: https://arxiv.org/abs/2106.10261
first-order methodssparse optimizationstructured optimizationconditional gradientprojection-free methods
Convex programming (90C25) Large-scale problems in mathematical programming (90C06) Nonlinear programming (90C30)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Exact matrix completion via convex optimization
- First-order methods of smooth convex optimization with inexact oracle
- Conditional gradient algorithms with open loop step size rules
- Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm
- Conditional gradient algorithms for norm-regularized smooth convex optimization
- Two Algorithms for the Minimum Enclosing Ball Problem
- An active-set algorithmic framework for non-convex optimization problems over the simplex
- Evolution towards the maximum clique
- Solving standard quadratic optimization problems via linear, semidefinite and copositive pro\-gramming
- Atomic decomposition by basis pursuit
- Finding the nearest point in A polytope
- Finding the Point of a Polyhedron Closest to the Origin
- A review on algorithms for maximum clique problems
- New analysis and results for the Frank-Wolfe method
- Concave programming for minimizing the zero-norm over polyhedral sets
- A framework for and empirical study of algorithms for traffic assignment
- Simplicial decomposition in nonlinear programming algorithms
- Approximate minimum enclosing balls in high dimensions using core-sets
- Rates of Convergence for Conditional Gradient Algorithms Near Singular and Nonsingular Extremals
- Linear convergence of a modified Frank–Wolfe algorithm for computing minimum-volume enclosing ellipsoids
- An extension of the frank and Wolfe method of feasible directions
- Some comments on Wolfe's ‘away step’
- A Linearly Convergent Variant of the Conditional Gradient Algorithm under Strong Convexity, with Applications to Online and Stochastic Optimization
- Scalable robust matrix recovery: Frank-Wolfe meets proximal methods
- Linearly convergent away-step conditional gradient for non-strongly convex functions
- Lexicographically Optimal Base of a Polymatroid with Respect to a Weight Vector
- The Cyclic Block Conditional Gradient Method for Convex Optimization Problems
- A Tight Upper Bound on the Rate of Convergence of Frank-Wolfe Algorithm
- Learning with Submodular Functions: A Convex Optimization Perspective
- Conditional gradient sliding for convex optimization
- Simplified versions of the conditional gradient method
- An Extended Frank--Wolfe Method with “In-Face” Directions, and Its Application to Low-Rank Matrix Completion
- A modified Frank--Wolfe algorithm for computing minimum-area enclosing ellipsoidal cylinders: theory and algorithms
- Polytope Conditioning and Linear Convergence of the Frank–Wolfe Algorithm
- The condition number of a function relative to a set
- First-order and stochastic optimization methods for machine learning
- Active Set Complexity of the Away-Step Frank--Wolfe Algorithm
- First-order Methods for the Impatient: Support Identification in Finite Time with Convergent Frank--Wolfe Variants
- A General Regularized Continuous Formulation for the Maximum Clique Problem
Cited In (8)
- Two-stage stochastic standard quadratic optimization
- Avoiding bad steps in Frank-Wolfe variants
- First-order Methods for the Impatient: Support Identification in Finite Time with Convergent Frank--Wolfe Variants
- Frank-Wolfe-type methods for a class of nonconvex inequality-constrained problems
- FrankWolfe.jl: A High-Performance and Flexible Toolbox for Frank–Wolfe Algorithms and Conditional Gradients
- 21 volumes for the 21st century
- Catching-up algorithm with approximate projections for Moreau's sweeping processes
- The Frank-Wolfe algorithm: a short introduction
Uses Software
Recommendations
- Title not available (Why is that?) 👍 👎
- Title not available (Why is that?) 👍 👎
- A regularization of the Frank-Wolfe method and unification of certain nonlinear programming methods 👍 👎
- A modified Frank-Wolfe algorithm and its convergence properties 👍 👎
- Revisiting the approximate Carathéodory problem via the Frank-Wolfe algorithm 👍 👎
- Extension of the Frank-Wolfe algorithm to concave nondifferentiable objective functions 👍 👎
- On the Frank–Wolfe algorithm for non-compact constrained optimization problems 👍 👎
- Short paper -- A note on the Frank-Wolfe algorithm for a class of nonconvex and nonsmooth optimization problems 👍 👎
- Frank-Wolfe style algorithms for large scale optimization 👍 👎
- Riemannian optimization via Frank-Wolfe methods 👍 👎
This page was built for publication: Frank-Wolfe and friends: a journey into projection-free first-order optimization methods
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2240671)
