TL;DR: This blog is a brief update on recent developments in $\texttt{FrankWolfe.jl}$, our open-source Julia package for Frank-Wolfe and Conditional Gradient methods. The latest version introduces new algorithmic variants, improved step-size strategies, and expanded applications across constrained optimization problems. We also briefly discuss its integration with companion libraries and use cases in real-world problems.

Introduction

Frank-Wolfe (FW) algorithms have gained significant attention in the constrained optimization community due to their projection-free nature and versatility. Over the past years, $\texttt{FrankWolfe.jl}$ has served as a high-performance and flexible open-source toolbox for implementing and experimenting with FW variants in Julia. This post summarizes recent advancements from the last 4 years, including newly integrated algorithms, new and improved step-size strategies, and expanded application areas. These updates, available in version 0.4.7+, aim to enhance the usability and computational efficiency of FW methods across various domains.

Note. This is just a quick and highly incomplete overview here with many more features explained in our release paper.

New Algorithmic Variants

Several new Frank-Wolfe variants have been incorporated into the package, broadening its applicability and improving performance. Below are some key additions:

Blended Pairwise Conditional Gradients (BPCG)

Unlike Pairwise Conditional Gradients (PCG), which uses swap steps that may limit primal progress, BPCG eliminates these swaps and refines the balance between vertex selection and descent directions. This modification improves performance in high-dimensional and infinite-dimensional spaces.

Decomposition-Invariant Conditional Gradients (DICG)

The Decomposition-Invariant Conditional Gradients (DICG) algorithm for “simplex-like” polytopes and its extension for general polytopes, addresses two main challenges in FW variants on polytopes. First, fast FW variants often rely on an active set, which incurs storage costs proportional to the active set complexity and the size of the vertices’ in-memory representation. Second, the evolution of the convex decomposition of iterates depends on the performed steps and the available directions for local steps, which in turn depend on the current convex decomposition. A key aspect of DICG is the use of “extended” linear minimization oracles that can compute extreme points of a face of the polytope. Often, such a restricted oracle is not more computationally expensive than the original oracle and can reduce the algorithm’s complexity.

Blended Decomposition-Invariant Conditional Gradients (BDICG)

The Blended Decomposition-Invariant Conditional Gradients (BDICG) algorithm combines the DICG algorithm with the blending technique used in the BPCG algorithm, resulting in an even faster DICG variant. This approach bears resemblance to the in-face Frank-Wolfe algorithm, but without relying on expensive oracles. Decomposition-invariant algorithms are particularly well-suited for optimization problems on polytopes, although their benefits for other convex sets, which were the focus of the in-face Frank-Wolfe algorithm, are less clear.

Block-Coordinate Frank-Wolfe (BCFW)

The Block-Coordinate Frank-Wolfe (BCFW) algorithm is designed for optimization problems with block-separable constraints. Our implementation allows for a custom update order unifying the cyclic and random block variants. Additionally, the implementation offers flexibility in the updating mechanism of different blocks, including the update direction, step size, and also partial updates. In addition to the standard FW step used in the original papers, we also provide a blended pairwise step.

Alternating Linear Minimization (ALM)

The Alternating Linear Minimization (ALM) algorithm is inspired by von Neumann’s alternating projections algorithm for solving feasibility problems over intersections of convex sets. However, unlike von Neumann’s original algorithm, ALM utilizes linear minimization oracles (LMOs) to avoid projections, making it more efficient for certain optimization problems. The key idea of ALM lies in rewriting the feasibility problem as an optimization problem over the product of the given sets. This reformulation allows us to solve optimization problems over intersections of convex sets by simply extending the objective function.

Away-Step and Lazy Variants

The package now includes refined Away-Step Frank-Wolfe and Lazy Conditional Gradient algorithms that dynamically balance exploration and exploitation in constrained optimization, while mimizing the number of linear minimization oracle (LMO) calls.

New Step-Size Strategies

Selecting the optimal step size is crucial for the performance of FW methods. The package now supports:

  • Monotonic open-loop step sizes, enforcing a monotonic decrease of the objective function.
  • Adaptive backtracking step sizes, improving robustness across different problem settings.
  • Secant-method based step sizes, leveraging second-order information to accelerate convergence.
  • Rational arithmetic step sizes, ensuring numerical stability in certain exact optimization scenarios.

Getting Started

To install the latest version, use the Julia package manager:

(@v1.6) pkg> add FrankWolfe

For more details, examples, and documentation, visit the GitHub repository.