Improved algorithms and novel applications
of the FrankWolfe.jl library

**Mathieu Besançon***

Université Grenoble Alpes, Inria, Laboratoire d'Informatique de Grenoble

MATHIEU.BESANCON@INRIA.FR

**Sébastien Designolle**

Zuse Institute Berlin, Germany

DESIGNOLLE@ZIB.DE

**Jannis Halbey**

Zuse Institute Berlin, Germany

Technische Universität Berlin, Germany

HALBEY@ZIB.DE

**Deborah Hendrych**

Zuse Institute Berlin, Germany

Technische Universität Berlin, Germany

HENDRYCH@ZIB.DE

**Dominik Kuzinowicz**

Zuse Institute Berlin, Germany

Technische Universität Berlin, Germany

KUZINOWICZ@ZIB.DE

**Sebastian Pokutta***

Zuse Institute Berlin, Germany

Technische Universität Berlin, Germany

POKUTTA@ZIB.DE

**Hannah Troppens**

Zuse Institute Berlin, Germany

TROPPENS@ZIB.DE

**Daniel Viladrich Herrmannsdoerfer**

Zuse Institute Berlin, Germany

VILADRICH@ZIB.DE

**Elias Wirth**

Technische Universität Berlin, Germany

Zuse Institute Berlin, Germany

WIRTH@MATH.TU-BERLIN.DE

Abstract

Frank-Wolfe (FW) algorithms have emerged as an essential class of methods for constrained optimization, especially on large-scale problems. In this paper, we summarize the algorithmic design choices and progress made in the last years of the development of FrankWolfe.jl, a Julia package gathering high-performance implementations of state-of-the-art FW variants. We review key use cases of the library in the recent literature, which match its original dual purpose: first, becoming the de-facto toolbox for practitioners applying FW methods to their problem, and second, offering a modular ecosystem to algorithm designers who experiment with their own variants and implementations of algorithmic blocks. Finally, we demonstrate the performance of several FW variants on important problem classes in several experiments, which we curated in a separate repository for continuous benchmarking.

1. Introduction

In the last decade, Frank-Wolfe (FW) algorithms have gained significant traction in various applications at the intersection of constrained and nonlinear optimization. We present a summary of progress made over the last years of the FrankWolfe.jl package, including recent advances in FW algorithms that have been integrated into the package, its extensions developed as companion packages, and selected applications from the literature that leveraged FrankWolfe.jl for computational experiments or further development of other

<footnote>∗ Corresponding authors. All authors are listed alphabetically.</footnote>
software libraries.

FrankWolfe.jl was initially introduced in Besançon et al. (2022) after its release in 2021 and we refer interested readers to this article for prominent features of the first releases. In this paper, we will primarily highlight progress made after this initial publication and available in the 0.4.7 version. The rest of this paper is structured as follows. Section 2 introduces the new FW-based algorithms implemented in the package, Section 3 reviews the different step-size strategies introduced from the literature, Section 4 details new feasible regions and corresponding linear minimization oracles. Section 5 presents the new active set abstraction and different implementations for specific use cases. Section 6 introduces mechanisms to dynamically modify the algorithm run. The appendix contains the pseudo-code for the main new FW variants, a selection of recent applications of the package in the literature, and a benchmark suite and results we developed to monitor the performance of the different algorithms.

Throughout the paper and unless specified otherwise, we will consider optimization problems of the form:

$$ \min_{x \in \mathcal{X}} f(x), $$

with $\mathcal{X}$ a closed, convex subset of a Hilbert space and $f: \mathcal{X} \to \mathbb{R}$ a differentiable objective function. The iteration count of algorithms will be denoted with $t$ and the iterate at the current iteration as $x_t$. For $n \in \mathbb{N}$, we also note $[n] := \{1, \dots, n\}$. We denote the unit simplex in $\mathbb{R}^n$ as $\Delta_n$. We will now briefly outline the algorithmic improvements and developments in FrankWolfe.jl, including new algorithms, step-size strategies, and oracles.

# 2. New Frank-Wolfe algorithms

In the following, we provide an overview of new FW variants implemented in FrankWolfe.jl. For details on the algorithms and theoretical guarantees, we refer the interested reader to the original papers. The pseudo-code for the different algorithms are presented in Appendix A.

## 2.1 Blended Pairwise Conditional Gradients (BPCG)

The *Blended Pairwise Conditional Gradients* (BPCG) algorithm from Tsuji et al. (2022) is an improved variant of the *Pairwise Conditional Gradients* (PCG) method. Unlike PCG, BPCG eliminates swap steps, which may hinder primal progress and limit applicability in infinite-dimensional settings. BPCG combines PCG with the blending criterion from the *Blended Conditional Gradients* (BCG) algorithm (Braun et al., 2019a), leading to better convergence rates and improved performance. It is straightforward to implement, avoids complex gradient alignment procedures (such as the ones, e.g., in Rinaldi & Zeffiro (2020; 2023)), and ensures solutions are sparse, making it particularly effective for applications like sparse signal recovery and kernel herding. Numerical experiments in Tsuji et al. (2022) demonstrate that BPCG produces sparser solutions than PCG, offering significant advantages in computational efficiency and performance, which is in line with the performance evaluation of our implementation in FrankWolfe.jl and of the benchmarks presented in Appendix C.

The pseudo-code is provided in Algorithm A.2 in Appendix A. The implementation in FrankWolfe.jl uses the relaxed criterion with $\kappa = 2.0$ from (Tsuji et al., 2022, Section 3.4) in Line (6) instead of $\kappa = 1.0$, for significantly enhanced sparsity while maintaining almost identical convergence speed in iteration and time. In the description of Algorithm A.2 we use $c[x_t](a_t)$ to denote the weight of $a_t$ in the convex decomposition of $x_t$ that the algorithm maintains. This is the current default FW variant if an active set can be maintained. We highlight that sparsity of the active set provides multiple algorithmic advantages, including faster convergence (see Section 6.2) and lower iteration costs, since active set operations usually have a cost linear in the number of vertices.

## 2.2 Pairwise Conditional Gradients (PCG)

We added an implementation of the *Pairwise Conditional Gradients* (PCG) from Lacoste-Julien & Jaggi (2015) similar to the Away-step Frank-Wolfe algorithm in FrankWolfe.jl. PCG performs a pairwise step
which consists in a direction $d_t := a_t - v_t$ following notation of Algorithm A.2. The algorithm also features an optional lazification mechanism introduced in Braun et al. (2019b) similar to the other ones, i.e., the possibility to avoid expensive calls to the exact linear minimization oracle (LMO) at every iteration, using vertices readily available for directions and maintaining an estimate of the dual gap.

## 2.3 Decomposition-Invariant Conditional Gradients (DICG)

The Decomposition-Invariant Conditional Gradients (DICG) corresponds to the algorithm defined in Garber & Meshi (2016) for the case of “simplex-like” polytopes and Bashiri & Zhang (2017) for general polytopes. The motivation for the algorithm is two-fold. First, typically fast FW variants on polytopes rely on an active set which induces a storage cost at least proportional to the active set complexity of the optimal solution and to the size of the in-memory representation of the vertices. Second, the evolution of the convex decomposition of the iterates throughout the algorithm depends on the steps that are performed and the set of directions available for local steps (i.e., steps depending on the active set) depends on the current convex decomposition. DICG thus aims at building decomposition-invariant iterations that do not rely on storage nor exploitation of a set of active vertices. We consider the case of polytopes inscribed in the 0-1 hypercube for simplicity of exposure. We will denote the current face of the iterate $x$:

$$ \mathcal{F}(\mathbf{x}) = \{\mathbf{y} \in \mathcal{X}, y_i = x_i \forall i \in [n], x_i \in \{0, 1\}\}. $$

The key aspect of DICG is considering “extended” linear minimization oracles that can compute extreme points of a face of the polytope. In many cases, such a restricted oracle is not computationally more expensive than the original oracle and will reduce the algorithm complexity compared to the original LMO. As an example, the standard LMO for the Birkhoff polytope consists of performing the Hungarian algorithm with the costs provided by the gradient. The decomposition-invariant oracle also requires being able to fix a variable to zero, which consists in forbidding a row/column pair in the Hungarian algorithm, or to fix a variable to one, which removes a row and a column and performs the algorithm on a submatrix.

The initial convergence analysis of DICG from Garber & Meshi (2016) was complemented in Wirth et al. (2024) with an affine-independent convergence rate under an assumption of error bound on the objective function.

## 2.4 Blended Decomposition-Invariant Conditional Gradients

The Blended Decomposition-Invariant Conditional Gradients (BDICG) algorithm is the natural combination of the DICG algorithm with the blending used in the BPCG algorithm, resulting in an even faster DICG variant and bearing resemblance to the in-face Frank-Wolfe algorithm of Freund et al. (2017), however without relying on expensive oracles. The pseudo-code is presented in Algorithm A.1. Furthermore, decomposition-invariant algorithms naturally fit optimization problems on polytopes, while it is not obvious they would provide much or any benefit on other convex sets which were the focus of the in-face Frank-Wolfe algorithm.

The convergence of BDICG has been studied in an affine-invariant setting in Wirth et al. (2024) under a sharpness assumption of the objective function on polytopes, the established rate is sublinear, improves over the classic $O(t^{-1})$ in the general case, and recovers the linear rate in the case of strongly convex functions that is common for FW variants with enhanced directions (away or blended pairwise steps).

## 2.5 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 proposed in Beck et al. (2015) and Lacoste-Julien et al. (2013). Additionally, the implementation offers flexibility in the updating mechanism of different blocks, including the update direction and step size. In addition to the standard FW step used in the original papers, we also provide a blended pairwise step.

Another Frank-Wolfe-based algorithm with a block structure was proposed in Braun et al. (2024) and its convergence rate established in the convex and nonconvex settings. In contrast with previous work on FW with a block structure, it considers partial block updates under a cyclic assumption from the proximity operator literature. This notably allows for provable convergence while updating blocks at different frequencies, e.g.,
based on the computational cost of the corresponding LMOs. The numerical experiments in Braun et al. (2024) were conducted with the new algorithm implemented on top of FrankWolfe.jl.

<caption>**Algorithm 2.1** Block-Coordinate Frank-Wolfe (BCFW)</caption>

**Require:** Convex smooth function $f: \times_{i=1}^{m} \mathcal{X}_i \to \mathbb{R}$, starting vertex $\mathbf{x}_0 \in \times_{i=1}^{m} \mathcal{X}_i$, step size $\gamma$.
**Ensure:** Points $\mathbf{x}_1, \dots, \mathbf{x}_T$ in $\times_{i=1}^{m} \mathcal{X}_i$.
1: **for** $t \in 0 \dots T$ **do**
2: &nbsp;&nbsp;&nbsp;&nbsp;Choose set of blocks $I_t \subset \{1, \dots, m\}$.
3: &nbsp;&nbsp;&nbsp;&nbsp;$$ \mathbf{g}_t \leftarrow \nabla f(\mathbf{x}_t) $$
4: &nbsp;&nbsp;&nbsp;&nbsp;**for** $i = 1$ **to** $m$ **do**
5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $i \in I_t$ **then**
6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$ \mathbf{v}_t^i \leftarrow \operatorname*{argmin}_{\mathbf{v} \in \mathcal{X}_i} \langle \mathbf{g}_t^i, \mathbf{v} \rangle $$
7: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$ \mathbf{x}_{t+1}^i \leftarrow \mathbf{x}_t^i + \gamma_t^i (\mathbf{v}_t^i - \mathbf{x}_t^i) $$
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**else**
9: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$$ \mathbf{x}_{t+1}^i \leftarrow \mathbf{x}_t^i $$
10: **end if**
11: **end for**
12: **end for**
13: **return** $\mathbf{x}_T$

## 2.6 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, see Braun et al. (2023). However, unlike von Neumann's original algorithm, the algorithm utilizes linear minimization oracles to avoid projections. The key idea of ALM lies in rewriting the feasibility problem as an optimization problem over the product of the given sets. This reformulation also allows us to solve optimization problems over intersections of convex sets by simply extending the objective function. Therefore, ALM enables combining different constraints and their corresponding LMOs in a single optimization problem. Our implementation is up to minor modifications identical to the Split Conditional Gradients (SCG) algorithm from Woodstock & Pokutta (2024).

## 2.7 A note on dual gaps

Many methods for lazyfying textbook algorithms use an upper bound $\Phi$ on the strong FW gap rather than the standard FW gap as a criterion to select the desired step. However, throughout the package, we estimate the standard FW gap via $\Phi$ and not the strong FW gap. The reason is to be able to use $\Phi$ as a stopping criterion in a fashion consistent with the standard FW gap; moreover strong convexity parameters (and pyramidal width parameters) required for geometric strong convexity bounds relying on the strong FW gap are usually unknown. Our choice in the package is justified by the argumentation in Braun et al. (2019a, Proof of Theorem 3.1), which shows that a bound on the standard FW gap induces a bound on the strong FW gap, when algorithms use any steps that imply away steps.

With the notation of Algorithms A.2 and A.1: if the FW gap satisfies

$$ \langle \nabla f(\mathbf{x}_t), \mathbf{x}_t - \mathbf{v}_t \rangle \le \Phi, $$

then the strong FW gap satisfies:

$$ \langle \nabla f(\mathbf{x}_t), \mathbf{a}_t - \mathbf{v}_t \rangle \le k\Phi, $$

with $k$ being a small positive constant, typically $k = 2$.
# 3. New step-size strategies

We next present new step sizes from the recent literature which have been implemented in FrankWolfe.jl. These step sizes have been shown to perform well under particular settings or classes of problems (e.g., polytope constraints, generalized self-concordant functions, or optimum in the interior).

## 3.1 Open-loop step sizes

The FW algorithm with line-search or short-step is known to converge at rates not faster than $\Omega(t^{-1-\epsilon})$ for any $\epsilon > 0$ in the setting of Wolfe's lower bound (Wolfe, 1970; Canon & Cullum, 1968). This setting assumes that the feasible region is a polytope, the optimal solutions lie in the relative interior of an at least one-dimensional face, and the objective is strongly convex. Recently, open-loop step sizes of the form

$$ \gamma_t = \frac{\ell}{t + \ell} \quad \text{for } \ell \in \mathbb{N}_{\ge 1} $$

have been identified as a means to achieve faster convergence rates of up to $O(t^{-2})$ in Wolfe's setting (Bach, 2021; Wirth et al., 2023b,c). This line of research culminated in the development of automatically adapting step-size rules, such as

$$ \gamma_t = \frac{2 + \log(t + 1)}{t + 2 + \log(t + 1)}, \quad (1) $$

that adapt to the geometry of the problem setting to achieve rates most often optimal among open-loop step sizes up to an initial burn-in phase of potential lower convergence speed (Pokutta, 2024). To facilitate further experimentation, the FrankWolfe.jl package implements all of the above step sizes using the Agnostic and GeneralizedAgnostic step-size options. It also supports general functions $g: \mathbb{N} \to \mathbb{R}_{\ge 0}$, allowing for step sizes of the form

$$ \gamma_t = \frac{g(t)}{t + g(t)} \quad (2) $$

to facilitate further experimentations.

## 3.2 Monotonic open-loop step sizes

In Carderera et al. (2021; 2024), the study of FW algorithms for generalized self-concordant functions motivated the introduction of a modification of the open-loop step size ensuring monotonic primal progress. The step size consists of:

$$ \begin{gathered} \gamma_t = \max_{N \in \mathbb{N}_{\ge N_t}} \gamma(N) := \frac{2^{-N}}{2 + t} \\ \text{s.t. } \mathbf{x}_t - \gamma \mathbf{d}_t \in \text{dom}(f) \\ f(\mathbf{x}_t - \gamma \mathbf{d}_t) < f(\mathbf{x}_t), \end{gathered} $$

where $N_t$ is the number of halving steps performed across previous iterations, starting from $N_1 = 1$. The corresponding procedure halves the step derived from the open-loop step size until the iterate lies in the domain of $f$ and yields primal progress. The domain membership criterion may appear redundant with monotonicity. In practice, however, a domain oracle can be called first to short-circuit the evaluation and avoid calls to the objective function, since it is in most cases less demanding than function evaluations. Despite its simplicity, the monotonic open-loop step size is sufficient to ensure convergence at the “usual” rates $(1/t$ in general and linear convergence for e.g. uniformly convex feasible regions or strongly convex functions over polytopes) for generalized self-concordant functions despite the absence of a global Lipschitz constant.

## 3.3 Adaptive step sizes

In Pedregosa et al. (2020), an adaptive step-size strategy was proposed that dynamically estimates the smoothness constant. While extremely powerful with great real-world performance, this step-size strategy
often suffers from numerical instabilities due to the test criterion employed, which basically relies on repeatedly testing the smoothness inequality for different estimations of the smoothness constant. In order to overcome these numerical instabilities, an alternative adaptive step-size strategy was proposed in Pokutta (2024), which is similar in nature to the one in Pedregosa et al. (2020), however uses the alternative test:

$$ \langle \nabla f(\mathbf{x}_{t+1}), \mathbf{x}_t - \mathbf{v}_t \rangle \ge 0, $$

to accept an estimate $\tilde{L}$, where $\mathbf{x}_{t+1}$ is chosen according to the short step with smoothness estimate $\tilde{L}$. In Pokutta (2024), it was shown that this test is equivalent to the original smoothness inequality test from Pedregosa et al. (2020) but provides significantly improved numerical stability. The adaptive step-size procedure is given in Algorithm 3.1. This step-size strategy is the default strategy in FrankWolfe.jl.

<caption>**Algorithm 3.1 Modified adaptive step-size strategy**</caption>

**Require:** Objective function $f$, smoothness estimate $\tilde{L}$, feasible point $\mathbf{x}$ and direction $\mathbf{d}$ with $\langle \nabla f(\mathbf{x}), \mathbf{d} \rangle \ge 0$, progress parameters $\eta \le 1 < \tau$, maximum step $\gamma^{\max}$
1: $M \leftarrow \eta \tilde{L}$
2: **while** true **do**
3: &nbsp;&nbsp;&nbsp;&nbsp; $\gamma \leftarrow \min \left\{ \frac{\langle \nabla f(\mathbf{x}), \mathbf{d} \rangle}{M \|\mathbf{d}\|^2}, \gamma^{\max} \right\}$
4: &nbsp;&nbsp;&nbsp;&nbsp; **if** $\langle \nabla f(\mathbf{x} - \gamma \mathbf{d}), \mathbf{d} \rangle \ge 0$ **then**
5: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\tilde{L}^* \leftarrow M$
6: &nbsp;&nbsp;&nbsp;&nbsp; **return** $\tilde{L}^*, \gamma$
7: **end if**
8: $M \leftarrow \tau M$
9: **end while**

## 3.4 Secant step sizes

We implemented a secant-based line search strategy introduced in Hendrych et al. (2025) and which works particularly well for generalized self-concordant functions. Although it requires gradient evaluations during the line search procedure, experimental results showed its promising performance in several scenarios due to its favorable convergence properties (assuming suitable function properties). We highlight that we added a domain oracle with an initial bound on the maximum step size to enable the use of the line search for generalized self-concordant functions when $\mathcal{X} \not\subset \text{dom}(f)$, i.e., one has to verify that a point is within the domain before being able to evaluate a gradient.

## 4. Linear Minimization Oracles

Since the first version of the package, multiple linear minimization oracles were added to support solving different types of problems.

**Spectraplex** The spectraplex (respectively, unit spectraplex) is the intersection of the cone of positive semidefinite matrices with an equality (respectively, inequality) constraint on the trace of the matrix:

$$ S_{\tau} = \{ X \in \mathbb{S}_{+}^{n}, \text{Tr}(X) = \tau \}. $$

The spectraplex is the convex hull of symmetric outer products $vv^T$ such that $\|v\| = \sqrt{\tau}$, and given a direction, a minimizing extreme point is given by computing the leading eigenvector of the negative direction.

**Hypersimplex** The hypersimplex of radius $\tau$ is the convex hull of nonnegative vectors with $K$ coordinates taking value $\tau$ and all others set to zero, and can be expressed as:

$$ \mathcal{H}_{K, \tau} = \left\{ \mathbf{x} \in [0, \tau]^n, \sum_{i} x_i = K\tau \right\}. $$
**Algorithm 3.2** Secant step-size strategy

**Require:** Objective function $f$, feasible points $\mathbf{x}$, direction $\mathbf{d}$ with $\langle\nabla f(\mathbf{x}), \mathbf{d}\rangle \ge 0$, $\gamma^{\max}$

1: **while** $\mathbf{x} - \gamma^{\max}\mathbf{d} \notin \text{dom}(f)$ **do**

2: $\gamma^{\max} \leftarrow \gamma^{\max}/2$

3: **end while**

4: $\gamma_{-1} \leftarrow 0$, $\gamma_0 \leftarrow \gamma^{\max}$

5: $\mathbf{x}_{-1} \leftarrow \mathbf{x}$, $\mathbf{x}_0 \leftarrow \mathbf{x} - \gamma_0 \mathbf{d}$

6: **for** $k \in 1...K$ **do**

7: &nbsp;&nbsp;&nbsp;&nbsp;**if** $\langle\nabla f(\mathbf{x}_{k-1}), -\nabla f(\mathbf{x}_{k-2}), \mathbf{d}\rangle \approx 0$ **then**

8: &nbsp;&nbsp;&nbsp;&nbsp;**return** $\gamma_{k-1}$

9: **end if**

10: $\tilde{\gamma}_k \leftarrow \gamma_{k-1} - \langle\nabla f(\mathbf{x}_{k-1}), \mathbf{d}\rangle \frac{\gamma_k - \gamma_{k-1}}{\langle\nabla f(\mathbf{x}_{k-1}) - \nabla f(\mathbf{x}_{k-2}), \mathbf{d}\rangle}$

11: $\gamma_k \leftarrow \text{project}_{[0, \gamma^{\max}]}(\tilde{\gamma}_k)$

12: $\mathbf{x}_k \leftarrow \mathbf{x} - \gamma_k \mathbf{d}$

13: **end for**

14: **return** $(\gamma_{k_{\min}})_{k \in 1...K}$ minimizing the function value.

The linear oracle consists in setting the $K$ entries corresponding to the smallest gradient values to $\tau$. A hypersimplex oracle was used in Macdonald et al. (2022) to compute the $K$ most relevant pixels for the classification of images.

**Symmetric oracle and symmetric Frank-Wolfe algorithm** Suppose that there is a group $G$ acting on the underlying vector space containing $\mathcal{X}$ and such that for all $\mathbf{x} \in \mathcal{X}$ and $g \in G$:

$$f(g \cdot \mathbf{x}) = f(\mathbf{x}) \quad \text{and} \quad g \cdot \mathbf{x} \in \mathcal{X}.$$

Then, the computations can be performed in the subspace invariant under the action of $G$. Let us indeed consider an optimal solution $\mathbf{x}^* \in \mathcal{X}$ and its group average (also called Reynolds operator) defined by

$$\mathcal{R}(\mathbf{x}) = \frac{1}{|G|} \sum_{g \in G} g \cdot \mathbf{x}.$$

By convexity of $f$ and $\mathcal{X}$, and with the invariance properties above, we have that $\mathcal{R}(\mathbf{x}^*) \in \mathcal{X}$ and

$$f(\mathcal{R}(\mathbf{x}^*)) = f\left(\frac{1}{|G|} \sum_{g \in G} g \cdot \mathbf{x}^*\right) \le \frac{1}{|G|} \sum_{g \in G} f(g \cdot \mathbf{x}^*) = f(\mathbf{x}^*),$$

so that $\mathcal{R}(\mathbf{x}^*)$ is a symmetric optimal solution.

Similarly, the LMO can be performed on $\mathcal{R}(\mathcal{X})$. If this additional invariance constraint can be exploited to directly accelerate the LMO, one can explicitly work in the invariant subspace. Otherwise, the package offers a way to pre- and post-process the gradient so that the full LMO can be called within a algorithm working in the reduced subspace.

```cpp
struct SubspaceLMO{LMO,TD,TI} <: LinearMinimizationOracle
    lmo::LMO
    deflate::TD
    inflate::TI
end
struct SubspaceVector{HasMultiplicities,T,DT} <: AbstractVector{T}
    data::DT
    vec::Vector{T}
    mul::Vector{T}
end
```
Practically, the iterate lives in a reduced subspace, here the image of the Reynolds operator, and the gradient is first inflated before being passed to the full LMO, from which the output is then deflated, which amounts to projecting onto the symmetric subspace in this case. The speedups obtained have various origins:

* The number of iterations is reduced, roughly by a factor corresponding to the average size of the orbits of the outputs of the nonsymmetrized LMO.

* For active set-based methods, the active set also benefits from this reduction, which can have a noticeable impact on the speed of the search over it when its size becomes quite large.

* When the memory size of the symmetrized iterate is smaller than the original one, basic in-place operations performed at each iteration are also faster, which can make a significant difference for large numbers of lazy iterations. For this purpose, the structure SubspaceVector simplifies the physical reduction of the memory footprint of the iterate; see the corresponding example in the documentation, named Accelerations for quadratic functions and symmetric problems.

Note that this dimension reduction does not only work for symmetric instances, but, generally, for all cases where the space of a natural LMO is larger than the subspace in which the computations are effectively happening. The collaborative filtering below is such a nonsymmetric example, although the benchmarks do not exploit the dimension reduction.

# 5. Abstract and specialized active set structures

Many FW variants operate on the explicit decomposition of the current iterate into a convex combination of a subset of vertices $S$:

$$ (\lambda, S) : \mathbf{x} = \sum_{k \in S} \lambda_k \mathbf{v}_k. $$

Although the active set typically refers to the subset $S$ with nonzero weights, we use it within FrankWolfe.jl to refer to the tuple $(\lambda, S)$ captured together with $\mathbf{x}$ in a data structure. Keeping the three elements in a single structure allows, for instance, for fast updates when few weights are changed, or specialized operations for particular atom types.

A default ActiveSet structure is used in typical calls to the active set-based algorithms. The active set constitutes the essential part of the state of these algorithms, and they can therefore all be called with an already created active set as argument, for instance, to warm-start them.

**ActiveSetQuadraticProductCaching.** We also implemented a second active set type for convex quadratic minimization with the objective written as:

$$ f(\mathbf{x}) = \frac{1}{2} \mathbf{x}^{\top} A \mathbf{x} + \mathbf{b}^{\top} \mathbf{x}. $$

This active set was used in particular in the huge-scale projection problem tackled in Designolle et al. (2023). The main idea is to avoid the computation of scalar products $\langle \mathbf{v}_1, \mathbf{v}_2 \rangle$ or quadratic forms $\langle \mathbf{v}_1, A\mathbf{v}_2 \rangle$ within the active set as needed to obtain the away and local vertices $\mathbf{a}_t$ and $\mathbf{s}_t$ (see, e.g., Algorithm A.2). This relies on pre-computing some specific values that can be used, thanks to the linearity of the gradient, to efficiently recover these scalar products at a reduced computational cost.

Formally, if the objective function has a gradient $\nabla f(\mathbf{x}) = A\mathbf{x} + \mathbf{b}$, then, since the current iterate is a convex combination of the atoms of the active set, i.e., $\mathbf{x}_t = \sum_j c[\mathbf{x}_t](\mathbf{v}_j)\mathbf{v}_j$, we have:

$$ \langle \nabla f(\mathbf{x}_t), \mathbf{v}_i \rangle = \sum_j c[\mathbf{x}_t](\mathbf{v}_j) \langle A\mathbf{v}_j, \mathbf{v}_i \rangle + \langle \mathbf{b}, \mathbf{v}_i \rangle \quad \forall i \in S. \quad (3) $$

By storing all values $\langle A\mathbf{v}_j, \mathbf{v}_i \rangle$ and $\langle \mathbf{b}, \mathbf{v}_i \rangle$ for $i, j \in S$, we can maintain an up-to-date value of Equation (3) according to potential modifications from previous iterations. Since at most two coefficients $c[\mathbf{x}_t](\mathbf{v}_j)$ can have changed compared to $c[\mathbf{x}_{t-1}](\mathbf{v}_j)$, the cost of this update is small compared to the computation of a scalar product.
**ActiveSetQuadraticLinearSolve.** In the case of convex quadratic problems, we can further exploit the current active set to gain immediate improvement without additional Frank-Wolfe steps. At any iteration, we can attempt to minimize $f$ over $\text{conv}(\{\mathbf{v}_k\}_{k \in S})$, which is equivalent to the corrective step performed by the Fully-Corrective Frank-Wolfe (FCFW) algorithm. Computing this step can however be as hard as the original problem.

Optimality conditions imply that the inner product of the gradient at an optimal point $\mathbf{x}_{\text{opt}}$ with any feasible direction has to be nonnegative. It suffices to check this for vertices in the active set,

$$ \langle \nabla f(\mathbf{x}_{\text{opt}}), \mathbf{v}_k - \mathbf{x}_{\text{opt}} \rangle \geq 0 \quad \text{for } k \in S. $$

Note that this is equivalent to the Frank-Wolfe gap of $f$ over $\text{conv}(\{\mathbf{v}_k\}_{k \in S})$ being nonpositive at $\mathbf{x}_{\text{opt}}$.

In Halbey et al. (2025), a proposed approach is to relax the problem and minimize over the affine space spanned by the current active vertices $\text{aff}(\{\mathbf{v}_k\}_{k \in S})$. The gradient has to be orthogonal to the affine space, which leads to equality constraints. Furthermore, we can use the directions $\mathbf{v}_{\tilde{k}} - \mathbf{v}_k$ for a fixed $\tilde{k} \in S$ instead of $\mathbf{v}_k - \mathbf{x}_{\text{opt}}$ as they span the same space,

$$ \langle \nabla f(\mathbf{x}_{\text{opt}}), \mathbf{v}_k - \mathbf{v}_{\tilde{k}} \rangle = 0 \quad \text{for } k \in S \setminus \{\tilde{k}\}. $$

Given the convex quadratic objective with gradient $\nabla f(\mathbf{x}) = A\mathbf{x} + \mathbf{b}$ and using barycentric coordinates $\tilde{\lambda}$, $\mathbf{x}_{\text{opt}} = \sum_{k \in S} \mathbf{v}_k \tilde{\lambda}_k = V\tilde{\lambda}$, and we can rewrite this as:

$$ \langle A V \tilde{\lambda} + \mathbf{b}, \mathbf{v}_k - \mathbf{v}_{\tilde{k}} \rangle = 0 \quad \text{for } k \in S \setminus \{\tilde{k}\} \\ \sum_{k \in S} \tilde{\lambda}_k = 1. $$

Note that the system consists of $|S|$ equations with affinely independent columns and has therefore at least one solution.

In order to obtain a point in the convex hull of the active set, we need to recover a nonnegative weight vector $\lambda$. We can enforce the nonnegativity directly and solve the resulting linear program (LP) with standard solvers even at a large scale, at a cost that is comparable or lower to many LMOs. In some cases however, this LP is infeasible, namely if the solution space of the linear system does not intersect with the $|S|$-simplex.

This motivated an alternative direct solving process using Wolfe's step used in Wolfe's minimum norm point algorithm (Wolfe, 1976). One can use the current weights $\lambda'$ and find the point on the segment $[\lambda', \tilde{\lambda}]$ that is the closest to $\lambda'$ in the simplex through a simple ratio test. Importantly, this ensures that at least one vertex will be dropped from the active set since the minimum ratio is achieved when at least one entry is zero, assuming $\tilde{\lambda}$ had negative entries.

This quadratic correction approach is detailed in Halbey et al. (2025) and implemented as an active set type that can be used on top of either a standard active set or the ActiveSetQuadraticProductCaching type presented before.

# 6. Dynamic algorithmic modifications

In this section, we present two mechanisms dynamically modifying the execution of FW algorithms, namely callbacks allowing the user to collect information and stop the algorithm, and the pivoting framework which rewrites iterates.

## 6.1 Dynamic stopping criterion with callbacks

A callback mechanism was introduced in the early versions of FrankWolfe.jl without any algorithmic effect. This enabled users, e.g., to print additional logs or record information about each iteration. We added a convention that callbacks can return a Boolean flag indicating whether the algorithm should continue or terminate. The callback can determine this condition based on the current state, gap, iteration count, time, etc, enabling an adaptive termination. We illustrate with a use case below in which we terminate BPCG as soon as the active set contains ten atoms.
```R
f(x) = 1/2 * norm(x :- 1)^2
grad!(storage, x) = storage := (x :- 1)
lmo = FrankWolfe.KSparseLMO(5, 2.0)
x0 = FrankWolfe.computeExtreme_point(lmo, ones(100))
```

```R
function build_callback(maxVertices)
  return function callback(state, active_set, args...)
    return length(active_set.atoms) <= maxVertices
  end
end
```

```R
# callback initialization with a maximum of ten vertices
callback = build_callback(10)
```

```R
FrankWolfe.blended_pairwise_conditionalgradient(f, grad!, lmo, x0, callback=callback)
```

We also use this example to highlight a common pattern to build callbacks using a closure receiving the callback parameters. This ensures both flexibility and performance by avoiding the declaration of `maxVertices` as a global variable.

## 6.2 The pivoting Frank-Wolfe framework

Although FW algorithms empirically maintain a sparse combination of extreme points of the feasible region, this sparsity can rarely be explicitly ensured or constrained. Indeed, even for a simple least-square objective, an $l_1$-norm ball constraint will be sparsity-inducing while keeping the problem tractable, whereas an explicit cardinality constraint would imply losing convergence guarantees or polynomial-time convergence.

This complexity gap naturally leads to the question of whether we can build FW-based algorithms with explicit guarantees on the active set cardinality beyond the trivial bound $\min\{t, |V|\}$ with $t$ the number of iterations and $V$ the set of vertices of the feasible region (considered infinite if the region is not a polytope).

Wirth et al. (2025) introduced a general framework for active set size control in FW algorithms, ensuring that the number of vertices remains below the Carathéodory bound of $n + 1$ vertices to form any iterate (Carathéodory, 1907), with $n$ the dimension of the feasible region which may be much lower than the ambient dimension, with an implementation building on top of FrankWolfe.jl. The pivoting framework essentially maintains a sparse matrix representing active vertices, the weights of these vertices forming the current iterate $\mathbf{x}_t$ being the solution to a linear system formed with this matrix and a right-hand side based on $\mathbf{x}_t$. The result complements previous work by Beck & Shtern (2017) which also proposed an active set control, but further exploits potential sparsity of the iterates and offers more control on the accumulation of numerical errors. Wirth et al. (2025) also established an optimal face identification property for BPCG on polytopes, as was shown for AFW by Bomze et al. (2020). Informally, the identification property states that if the objective function is convex and if the minimizer of the problem is unique and lies on a face of the polytope, then there exists a finite number of iterations after which all iterates lie on the face and do not leave it again.

## 7. Conclusion

This paper presents an overview of the last years of development of the FrankWolfe.jl package, with new algorithms developed and integrated since its inception, new oracles and step-size strategies. We also highlighted a few applications of FrankWolfe.jl, both in the form of new packages leveraging it and research that leveraged it for computations. The diversity of applications of both types shows the success of the package in its two targeted use cases: as a ready-to-use toolbox for computational research and as a platform for further algorithmic development of Frank-Wolfe-based methods. Future work on the package and ecosystem will include further variants for generalized settings, and applications leveraging FW subproblems within a more complex task.
# Acknowledgments

The authors acknowledge the work of all contributors and the feedback from users of the package. We thank in particular Victor Thouvenot for contributions to the Python wrapper and combinatorial oracle companion package, and Zev Woodstock for work on the block-coordinate Frank-Wolfe. Research reported in this paper was partially supported through the Research Campus Modal funded by the German Federal Ministry of Education and Research (fund numbers 05M14ZAM,05M20ZBM) and the Deutsche Forschungsgemeinschaft (DFG) through the DFG Cluster of Excellence MATH+. The work of Mathieu Besançon benefited from the support of the FMJH Program PGMO and from MIAI at Université Grenoble Alpes (grant ANR-19-P3IA-0003). Part of this work was conducted while Sebastian Pokutta was visiting Tokyo University via a JSPS International Research Fellowship.

# References

Agrawal, A., Amos, B., Barratt, S., Boyd, S., Diamond, S., and Kolter, J. Z. Differentiable convex optimization layers. *Advances in neural information processing systems*, 32, 2019a.

Agrawal, A., Barratt, S., Boyd, S., Busseti, E., and Moursi, W. M. Differentiating through a cone program. *Journal of Applied and Numerical Optimization*, 2019b.

Amos, B. and Kolter, J. Z. Optnet: Differentiable optimization as a layer in neural networks. In *International Conference on Machine Learning*, pp. 136–145. PMLR, 2017.

Avis, D., Imai, H., and Ito, T. On the relationship between convex bodies related to correlation experiments with dichotomic observables. *J. Phys. A*, 39(36):11283, Aug 2006. doi: 10.1088/0305-4470/39/36/010. URL https://dx.doi.org/10.1088/0305-4470/39/36/010.

Bach, F. On the effectiveness of Richardson extrapolation in data science. *SIAM Journal on Mathematics of Data Science*, 3(4):1251–1277, 2021.

Bach, F., Lacoste-Julien, S., and Obozinski, G. On the equivalence between herding and conditional gradient algorithms. In *Proceedings of the International Conference on Machine Learning*, pp. 1355–1362. PMLR, 2012.

Bashiri, M. A. and Zhang, X. Decomposition-invariant conditional gradient for general polytopes with line search. *Advances in neural information processing systems*, 30, 2017.

Beck, A. and Shtern, S. Linearly convergent away-step conditional gradient for non-strongly convex functions. *Mathematical Programming*, 164:1–27, 2017.

Beck, A., Pauwels, E., and Sabach, S. The cyclic block conditional gradient method for convex optimization problems. *SIAM Journal on Optimization*, 25(4):2024–2049, 2015. doi: 10.1137/15M1008397. URL https://doi.org/10.1137/15M1008397.

Berthet, Q., Blondel, M., Teboul, O., Cuturi, M., Vert, J.-P., and Bach, F. Learning with differentiable perturbed optimizers. *Advances in neural information processing systems*, 33:9508–9519, 2020.

Besançon, M., Carderera, A., and Pokutta, S. FrankWolfe.jl: A high-performance and flexible toolbox for Frank-Wolfe algorithms and conditional gradients. *INFORMS Journal on Computing*, 2022.

Besançon, M., Dias Garcia, J., Legat, B., and Sharma, A. Flexible differentiable optimization via model transformations. *INFORMS Journal on Computing*, 36(2):456–478, 2024.

Blondel, M., Martins, A. F., and Niculae, V. Learning with Fenchel-Young losses. *Journal of Machine Learning Research*, 21(35):1–69, 2020.
Blondel, M., Berthet, Q., Cuturi, M., Frostig, R., Hoyer, S., Llinares-López, F., Pedregosa, F., and Vert, J.-P. Efficient and modular implicit differentiation. *Advances in neural information processing systems*, 35: 5230–5242, 2022.

Bomze, I. M., Rinaldi, F., and Zeffiro, D. Active set complexity of the away-step Frank-Wolfe algorithm. *SIAM Journal on Optimization*, 30(3):2470–2500, 2020.

Braun, G., Pokutta, S., Tu, D., and Wright, S. Blended conditional gradients. In *International Conference on Machine Learning*, pp. 735–743. PMLR, 2019a.

Braun, G., Pokutta, S., and Zink, D. Lazifying conditional gradient algorithms. *Journal of Machine Learning Research*, 20(71):1–42, 2019b.

Braun, G., Carderera, A., Combettes, C. W., Hassani, H., Karbasi, A., Mokhtari, A., and Pokutta, S. Conditional gradient methods. *arXiv preprint arXiv:2211.14103*, 2022.

Braun, G., Pokutta, S., and Weismantel, R. Alternating linear minimization: Revisiting von Neumann's alternating projections. *arXiv preprint arXiv:2212.02933*, 2023. URL https://arxiv.org/abs/2212.02933.

Braun, G., Pokutta, S., and Woodstock, Z. Flexible block-iterative analysis for the Frank-Wolfe algorithm, 2024. URL https://arxiv.org/abs/2409.06931.

Brierley, S., Navascués, M., and Vértesi, T. Convex separation from convex optimization for large-scale problems. *arXiv:1609.05011*, 2016. URL https://arxiv.org/abs/1609.05011.

Brunner, N., Cavalcanti, D., Pironio, S., Scarani, V., and Wehner, S. Bell nonlocality. *Rev. Mod. Phys.*, 86:419–478, Apr 2014. doi: 10.1103/RevModPhys.86.419. URL https://link.aps.org/doi/10.1103/RevModPhys.86.419.

Canon, M. D. and Cullum, C. D. A tight upper bound on the rate of convergence of Frank-Wolfe algorithm. *SIAM Journal on Control*, 6(4):509–516, 1968.

Carathéodory, C. Über den Variabilitätsbereich der Koeffizienten von Potenzreihen, die gegebene Werte nicht annehmen. *Mathematische Annalen*, 64(1):95–115, 1907.

Carderera, A., Besançon, M., and Pokutta, S. Simple steps are all you need: Frank-Wolfe and generalized self-concordant functions. *Advances in Neural Information Processing Systems*, 34:5390–5401, 2021.

Carderera, A., Besançon, M., and Pokutta, S. Scalable Frank-Wolfe on generalized self-concordant functions via simple steps. *SIAM Journal on Optimization*, 2024.

Combettes, C. W. and Pokutta, S. Revisiting the approximate Carathéodory problem via the Frank-Wolfe algorithm. *Math. Program.*, 197(1):191–214, Jan 2023. ISSN 1436-4646. doi: 10.1007/s10107-021-01735-x. URL https://doi.org/10.1007/s10107-021-01735-x.

Dalle, G., Baty, L., Bouvier, L., and Parmentier, A. Learning with combinatorial optimization layers: a probabilistic approach. *arXiv preprint arXiv:2207.13513*, 2022.

Designolle, S., Iommazzo, G., Besançon, M., Knebel, S., Gelß, P., and Pokutta, S. Improved local models and new Bell inequalities via Frank-Wolfe algorithms. *Physical Review Research*, 5(4):043059, 2023.

Designolle, S., Vértesi, T., and Pokutta, S. Better bounds on Grothendieck constants of finite orders. *arXiv preprint arXiv:2409.03739*, 2024a. URL https://arxiv.org/abs/2409.03739.

Designolle, S., Vértesi, T., and Pokutta, S. Symmetric multipartite Bell inequalities via Frank-Wolfe algorithms. *Physical Review A*, 109(2):022205, 2024b.
Diviánszky, P., Bene, E., and Vértesi, T. Qutrit witness from the Grothendieck constant of order four. *Phys. Rev. A*, 96:012113, Jul 2017. doi: 10.1103/PhysRevA.96.012113. URL https://link.aps.org/doi/10.1103/PhysRevA.96.012113.

Freund, R. M., Grigas, P., and Mazumder, R. An extended Frank-Wolfe method with “in-face” directions, and its application to low-rank matrix completion. *SIAM Journal on optimization*, 27(1):319–346, 2017.

Garber, D. and Meshi, O. Linear-memory and decomposition-invariant linearly convergent conditional gradient algorithm for structured polytopes. *Advances in neural information processing systems*, 29, 2016.

Gilbert, E. G. An iterative procedure for computing the minimum of a quadratic form on a convex set. *J. SIAM Control*, 4(1):61–80, 1966. doi: 10.1137/0304007. URL https://doi.org/10.1137/0304007.

Halbey, J., Rakotomandimby, S., Besançon, M., Designolle, S., and Pokutta, S. Efficient quadratic corrections for Frank-Wolfe algorithms, 2025. URL https://arxiv.org/abs/2506.02635.

Hazan, E. and Luo, H. Variance-reduced and projection-free stochastic optimization. In *International Conference on Machine Learning*, pp. 1263–1271. PMLR, 2016.

Heldt, D., Kreuzer, M., Pokutta, S., and Poulisse, H. Approximate computation of zero-dimensional polynomial ideals. *Journal of Symbolic Computation*, 44(11):1566–1591, 2009.

Hendrych, D., Troppens, H., Besançon, M., and Pokutta, S. Convex mixed-integer optimization with Frank-Wolfe methods. *arXiv preprint arXiv:2208.11010*, 2022.

Hendrych, D., Besançon, M., and Pokutta, S. Solving the optimal experiment design problem with mixed-integer convex methods. In *Proceedings of Symposium on Experimental Algorithms*, 2024.

Hendrych, D., Besançon, M., Martínez-Rubio, D., and Pokutta, S. Secant line search for Frank-Wolfe algorithms. In *The 42nd International Conference on Machine Learning*, 2025.

Hirsch, F., Quintino, M. T., Vértesi, T., Navascués, M., and Brunner, N. Better local hidden variable models for two-qubit Werner states and an upper bound on the Grothendieck constant $K_G(3)$. *Quantum*, 1:3, Apr 2017. ISSN 2521-327X. URL https://doi.org/10.22331/q-2017-04-25-3.

Kolmogorov, V. Blossom V: a new implementation of a minimum cost perfect matching algorithm. *Mathematical Programming Computation*, 1:43–67, 2009.

Kuzinowicz, D. and Wirth, E. ApproximateVanishingIdeals.jl, 2023. https://github.com/ZIB-IOL/ApproximateVanishingIdeals.jl.

Lacoste-Julien, S. and Jaggi, M. On the global linear convergence of Frank-Wolfe optimization variants. In Cortes, C., Lawrence, N. D., Lee, D. D., Sugiyama, M., and Garnett, R. (eds.), *Advances in Neural Information Processing Systems (NIPS)*, volume 28, pp. 496–504. Curran Associates, December 2015. URL http://papers.nips.cc/paper/5925-on-the-global-linear-convergence-of-frank-wolfe-optimization-variants.pdf.

Lacoste-Julien, S., Jaggi, M., Schmidt, M., and Pletscher, P. Block-coordinate Frank-Wolfe optimization for structural SVMs. In Dasgupta, S. and McAllester, D. (eds.), *Proceedings of the 30th International Conference on Machine Learning*, volume 28 of *Proceedings of Machine Learning Research*, pp. 53–61, Atlanta, Georgia, USA, 17–19 Jun 2013. PMLR. URL https://proceedings.mlr.press/v28/lacoste-julien13.html.

Limbeck, J. *Computation of approximate border bases and applications*. PhD thesis, Universität Passau, 2013.
Livni, R., Lehavi, D., Schein, S., Nachliely, H., Shalev-Shwartz, S., and Globerson, A. Vanishing component analysis. In *Proceedings of the International Conference on Machine Learning*, pp. 597–605. PMLR, 2013.

Macdonald, J., Besançon, M. E., and Pokutta, S. Interpretable neural networks with Frank-Wolfe: Sparse relevance maps and relevance orderings. In Chaudhuri, K., Jegelka, S., Song, L., Szepesvari, C., Niu, G., and Sabato, S. (eds.), *Proceedings of the 39th International Conference on Machine Learning*, volume 162 of *Proceedings of Machine Learning Research*, pp. 14699–14716. PMLR, 17–23 Jul 2022. URL https://proceedings.mlr.press/v162/macdonald22a.html.

Mokhtari, A., Hassani, H., and Karbasi, A. Stochastic conditional gradient methods: From convex minimization to submodular maximization. *Journal of machine learning research*, 21(105):1–49, 2020.

Pedregosa, F., Negiar, G., Askari, A., and Jaggi, M. Linearly convergent Frank-Wolfe with backtracking line-search. In Chiappa, S. and Calandra, R. (eds.), *Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics*, (AISTATS), volume 108 of *Proceedings of Machine Learning Research*, pp. 1–10. PMLR, 2020. URL http://proceedings.mlr.press/v108/pedregosa20a/pedregosa20a.pdf.

Pokutta, S. The Frank-Wolfe algorithm: a short introduction. *Jahresbericht der Deutschen Mathematiker-Vereinigung*, 126(1):3–35, 2024. URL https://arxiv.org/abs/2311.05313.

Rinaldi, F. and Zeffiro, D. A unifying framework for the analysis of projection-free first-order methods under a sufficient slope condition. *arXiv preprint arXiv:2008.09781*, 2020.

Rinaldi, F. and Zeffiro, D. Avoiding bad steps in Frank-Wolfe variants. *Computational Optimization and Applications*, 84(1):225–264, 2023.

Rothvoß, T. The matching polytope has exponential extension complexity. *Journal of the ACM (JACM)*, 64 (6):1–19, 2017.

Schäfer, G. Weighted matchings in general graphs. Master's thesis, Universität des Saarlandes, Saarbrücken, 2000. Master's thesis, Fachbereich Informatik.

Sharma, K., Hendrych, D., Besançon, M., and Pokutta, S. Network design for the traffic assignment problem with mixed-integer Frank-Wolfe. In *INFORMS Optimization Society Annual Conference Proceedings*. INFORMS, 2024.

Tsuji, K. K., Tanaka, K., and Pokutta, S. Pairwise conditional gradients without swap steps and sparser kernel herding. In *International Conference on Machine Learning*, pp. 21864–21883. PMLR, 2022.

Welling, M. Herding dynamical weights to learn. In *Proceedings of the 26th annual international conference on machine learning*, pp. 1121–1128, 2009.

Wirth, E. and Besançon, M. KernelHerding.jl, 2022. https://github.com/ZIB-IOL/KernelHerding.jl.

Wirth, E. and Pokutta, S. Conditional gradients for the approximately vanishing ideal. In *Proceedings of the International Conference on Artificial Intelligence and Statistics*, pp. 2191–2209. PMLR, 2022.

Wirth, E., Kera, H., and Pokutta, S. Approximate vanishing ideal computations at scale. In *Proceedings of the International Conference on Learning Representations*, 2023a.

Wirth, E., Kerdreux, T., and Pokutta, S. Acceleration of Frank-Wolfe algorithms with open-loop step-sizes. In *International Conference on Artificial Intelligence and Statistics*, pp. 77–100. PMLR, 2023b.

Wirth, E., Pena, J., and Pokutta, S. Accelerated affine-invariant convergence rates of the Frank-Wolfe algorithm with open-loop step-sizes. *arXiv preprint arXiv:2310.04096*, 2023c. URL https://arxiv.org/Abs/2310.04096.
Wirth, E., Pena, J., and Pokutta, S. Fast convergence of Frank-Wolfe algorithms on polytopes. arXiv preprint arXiv:2406.18789, 2024. URL https://arxiv.org/abs/2406.18789.

Wirth, E., Besançon, M., and Pokutta, S. The pivoting framework: Frank-Wolfe algorithms with active set size control. In *The 28th International Conference on Artificial Intelligence and Statistics*, 2025. URL https://arxiv.org/abs/2407.11760.

Wolfe, P. Convergence theory in nonlinear programming. *Integer and Nonlinear Programming*, pp. 1–36, 1970.

Wolfe, P. Finding the nearest point in a polytope. *Mathematical Programming*, 11:128–149, 1976.

Woodstock, Z. and Pokutta, S. Splitting the conditional gradient algorithm. *arXiv preprint arXiv:2311.05381*, 2024. URL https://arxiv.org/abs/2311.05381.

# Appendix A. Pseudo-code for the new Frank-Wolfe variants

We present in this section the pseudo-code for the Frank-Wolfe variants introduced in the package.

<caption>**Algorithm A.1 Blended Decomposition-Invariant Conditional Gradients**</caption>

**Require:** Starting extreme point $\mathbf{x}_0$.
1: **for** $t \in 0...T$ **do**
2: &nbsp;&nbsp;&nbsp;&nbsp; $\mathbf{v}_t \leftarrow \operatorname*{argmin}_{\mathbf{v} \in \mathcal{X}} \langle \nabla f(\mathbf{x}_t), \mathbf{v} \rangle$
3: &nbsp;&nbsp;&nbsp;&nbsp; $\mathbf{s}_t \leftarrow \operatorname*{argmin}_{\mathbf{v} \in \mathcal{F}(\mathbf{x})} \langle \nabla f(\mathbf{x}_t), \mathbf{v} \rangle$
4: &nbsp;&nbsp;&nbsp;&nbsp; $\mathbf{a}_t \leftarrow \operatorname*{argmax}_{\mathbf{v} \in \mathcal{F}(\mathbf{x})} \langle \nabla f(\mathbf{x}_t), \mathbf{v} \rangle$
5: &nbsp;&nbsp;&nbsp;&nbsp; **if** $\kappa \langle \nabla f(\mathbf{x}_t), \mathbf{a}_t - \mathbf{s}_t \rangle \ge \langle \nabla f(\mathbf{x}_t), \mathbf{x}_t - \mathbf{v}_t \rangle$ **then**
6: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\mathbf{d}_t \leftarrow \mathbf{a}_t - \mathbf{s}_t$
7: &nbsp;&nbsp;&nbsp;&nbsp; **else**
8: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\mathbf{d}_t \leftarrow \mathbf{x}_t - \mathbf{v}_t$
9: &nbsp;&nbsp;&nbsp;&nbsp; **end if**
10: &nbsp;&nbsp;&nbsp;&nbsp; $\gamma_t \leftarrow \operatorname*{argmin}_{\gamma \in [0, \gamma_t^{\max}]} f(\mathbf{x}_t - \gamma_t \mathbf{d}_t)$
11: &nbsp;&nbsp;&nbsp;&nbsp; $\mathbf{x}_{t+1} \leftarrow \mathbf{x}_t - \gamma_t \mathbf{d}_t$
12: **end for**
13: **return** $\mathbf{x}_t$

In Line (6) of Algorithm A.1, we include a scaling factor $\kappa$ for the test that allows to promote sparsity, as already found atoms are reused, similar to Line (6) in Algorithm A.2. The default value is $\kappa = 2.0$ in the package.

# Appendix B. Overview of use cases and connected ecosystem

We next review a few use cases which leveraged FrankWolfe.jl for different applications, from structured machine learning to mixed-integer convex optimization. We then highlight key elements of the ecosystem surrounding FrankWolfe.jl, namely the Python interface and the companion package for linear oracles.

**Interpretable Predictions with Rate-Distortion Explanations** One of the prominent features of FW algorithms is the sparsity they induce in the iterates, in the sense of iterates being formed as a convex combination of a typically low number of extreme points of the feasible region. When extreme points are themselves sparse, this directly results in sparse iterates in the traditional sense of a low support. This sparsity of iterates not only holds at the optimum but throughout the whole solving process, making the method particularly suitable to large-scale learning problems for which the optimization procedure is typically
**Algorithm A.2 Blended Pairwise Conditional Gradients (BPCG)**

**Require:** Convex smooth function $f$, starting vertex $x_0 \in \text{vert}(X)$.

**Ensure:** Points $x_1, \dots, x_T \in X$.

1: $S_0 \leftarrow \{x_0\}$

2: **for** $t \in 0 \dots T-1$ **do**

3: $\mathbf{a}_t \leftarrow \operatorname*{argmax}_{v \in S_t} \langle \nabla f(\mathbf{x}_t), \mathbf{v} \rangle$ ▶ away vertex

4: $\mathbf{s}_t \leftarrow \operatorname*{argmin}_{v \in S_t} \langle \nabla f(\mathbf{x}_t), \mathbf{v} \rangle$ ▶ local FW

5: $\mathbf{v}_t \leftarrow \operatorname*{argmin}_{v \in V(P)} \langle \nabla f(\mathbf{x}_t), \mathbf{v} \rangle$ ▶ global FW

6: **if** $\kappa \langle \nabla f(\mathbf{x}_t), \mathbf{a}_t - \mathbf{s}_t \rangle \ge \langle \nabla f(\mathbf{x}_t), \mathbf{x}_t - \mathbf{v}_t \rangle$ **then** ▶ pairwise step

7: $\mathbf{d}_t \leftarrow \mathbf{a}_t - \mathbf{s}_t$

8: $\lambda_t^* \leftarrow c[\mathbf{x}_t](\mathbf{a}_t)$

9: $\gamma_t \leftarrow \operatorname*{argmin}_{\gamma \in [0, \lambda_t^*]} f(\mathbf{x}_t - \gamma \mathbf{d}_t)$

10: **if** $\gamma_t < \lambda_t^*$ **then** ▶ descent step

11: $S_{t+1} \leftarrow S_t$

12: **else** ▶ drop step

13: $S_{t+1} \leftarrow S_t \setminus \{\mathbf{a}_t\}$

14: **end if**

15: **else** ▶ FW step

16: $\mathbf{d}_t \leftarrow \mathbf{x}_t - \mathbf{v}_t$

17: $\gamma_t \leftarrow \operatorname*{argmin}_{\gamma \in [0,1]} f(\mathbf{x}_t - \gamma \mathbf{d}_t)$

18: $S_{t+1} \leftarrow S_t \cup \{\mathbf{v}_t\}$ ▶ or $S_{t+1} \leftarrow \{\mathbf{v}_t\}$ if $\gamma_t = 1$

19: **end if**

20: $\mathbf{x}_{t+1} \leftarrow \mathbf{x}_t - \gamma_t \mathbf{d}_t$

21: **end for**

22: **return** $\mathbf{x}_T$

terminated fairly early. In Macdonald et al. (2022), this property is exploited within the *Rate-Distortion Explanation* (RDE) framework. Informally, this framework tackles the problem of finding a sparse set of relevant input features with which the prediction model can keep the expected training loss low, while the irrelevant features are replaced with Gaussian noise. Denoting by $\mathbf{x}$ the filter applied on features to quantify their relevance (zero being an irrelevant feature and one an important feature), $D(\mathbf{x})$ is the distortion obtained when applying the filter $\mathbf{x}$, with $D(\mathbf{1}) = 0$ by convention, and $D(\mathbf{0})$ being the expected loss of a (Gaussian) random input. The RDE problem is expressed as:

$$ (k\text{-RDE}) \min_{\mathbf{x}} D(\mathbf{x}) \\ \text{s.t.} \quad \mathbf{x} \in \mathcal{X} = \{\mathbf{x} \in [0, 1]^n, \sum_i x_i \le k\}. $$

$\mathcal{X}$ is the intersection of a $k$-sparse polytope with the nonnegative orthant, it is the convex hull of vertices formed as the sum of at most $k$ vectors of the standard basis. The problem (k-RDE) requires a prior choice of $k$ controlling the sparsity level and does not provide a complete overview of the trade-off between sparsity of the explanation and predictive power. A way to obtain an explanation for multiple sparsity levels is to rank features instead of simply activating or deactivating them. Once features are ranked from the most to least relevant, a $k$-sparse explanation can be obtained by selecting the $k$ first features according to the ranking. Optimizing an ordering of the feature is equivalent to finding a permutation matrix for the features in their initial order in $[n]$. Optimizing over permutation matrices leads to hard combinatorial problems which are intractable at the scale considered for RDE. We can relax the problem by optimizing over their convex hull,
the Birkhoff polytope, consisting of all doubly stochastic matrices. This results in the following problem:

$$ (\text{Ord-RDE}) \min_{\Pi \in B_n} \frac{1}{n-1} \sum_{k \in [n-1]} D(\Pi \mathbf{p}_k), $$

with $B_n$ the Birkhoff polytope for $n \times n$ matrices, $\mathbf{p}_k$ the vector with $k$ ones and $n-k$ zeros. The problem (Ord-RDE) optimizes the ordering of features that will perform best on average over all rates. Computational experiments from Macdonald et al. (2022) showed that (Ord-RDE) performed well across all rates, close enough to (k-RDE) trained for the specific rate and much better than an ordering obtained from the average of all rates consisting in $n-1$ distinct (k-RDE) problems.

A generic interface for Stochastic Frank-Wolfe (SFW) algorithms was in particular implemented to support this work, allowing users to define their own batch size and momentum, with for instance the growing batch size algorithm of Hazan & Luo (2016) or the momentum of Mokhtari et al. (2020). We refer the interested reader to Braun et al. (2022, Section 4.1) for a recent review of SFW algorithms.

**InferOpt.jl and differentiable combinatorial layers** Differentiable optimization has been a notorious recent advance in machine learning, enabling the integration of arbitrary convex optimization problems as layers in neural networks, see the seminal work in Amos & Kolter (2017); Agrawal et al. (2019b) for quadratic and conic layers and Agrawal et al. (2019a); Besançon et al. (2024); Blondel et al. (2022) for several implementations. These approaches however fail to differentiate through linear optimization with respect to the objective function, which can be expressed as:

$$ \underset{v \in \mathcal{X}}{\operatorname{argmin}} \langle \theta, v \rangle, $$

since the derivative of such problem w.r.t. $\theta$ leads to a zero Jacobian almost everywhere when $\mathcal{X}$ is a polytope. An approach originally proposed in Berthet et al. (2020); Blondel et al. (2020) consists in regularizing the problem with a random perturbation of $\theta$, resulting in a probability distribution over $v \in \mathcal{X}$ or equivalently, to the addition of a strongly convex regularizer to the original combinatorial problem. The work in Dalle et al. (2022) applies FW methods to solve the regularized problem, and derives the equivalent probability distribution over vertices from the weights of the vertices of $\mathcal{X}$ in the final convex decomposition. Their package InferOpt.jl leverages FrankWolfe.jl to solve the FW problems, extract the probability distribution and compute Jacobians of the regularized problems, making combinatorial layers compatible with automatic differentiation to integrate them into learning pipelines.

**Boscia.jl and first-order mixed-integer convex optimization** In Hendrych et al. (2022), FrankWolfe.jl was combined with a branch-and-bound framework to tackle a subclass of Mixed-Integer Nonlinear Problems (MINLP)

$$ \min_{x \in \mathcal{X}} f(x), $$

where $f$ is a differentiable convex function and $\mathcal{X}$ is a nonconvex set containing linear, combinatorial, and integrality constraints. The FW variants implemented in FrankWolfe.jl are used to solve the node problems with the distinction that the LMO solves the mixed-integer linear problem under additional bound constraints

$$ \min_{v \in \mathcal{X} \cap [u, l]} \langle \nabla f(x), v \rangle. $$

This results in obtaining integral feasible solutions, and thus a primal bound, from the root node. Due to the expensiveness of the LMO, the lazification capabilities of the FW variants are heavily utilized. The active set decomposition facilitates the warm-starting of the children nodes and the error adaptiveness enables a tightening of the solving precision with an increasing depth in the tree. Through the callback mechanism, the evaluation of a node can be stopped dynamically if either the dual bound has reached the primal bound of the tree or there is a user-specified number of better candidate nodes to investigate.
Boscia.jl has successfully been applied to the Optimal Experiment Design Problem (OEDP) under the D-criterion and A-criterion in Hendrych et al. (2024). OEDP amounts to choosing a subset of experiments maximizing the information gain and under the two mentioned criteria leads to Np-hard problems.

Another use case of Boscia.jl is the Network Design Problem for Traffic Assignment, see Sharma et al. (2024). The goal is to add edges to an existing design such that the traffic flow cost and the design cost are minimized. On both of the aforementioned problems, Boscia.jl showed promising performance results.

**BellPolytopes.jl and large-scale projections for nonlocality** In quantum information theory, more precisely in Bell nonlocality (Brunner et al., 2014), a question of interest is the membership problem for the so-called local polytope. In the bipartite setting, this polytope is affinely equivalent to the cut polytope (Avis et al., 2006) and practical instances are too large to be solved via facet enumeration or linear programming. Instead, a FW approach can be taken to solve the approximate Carathéodory problem for this polytope (Combettes & Pokutta, 2023). The corresponding works by Designolle et al. (2023; 2024a;b) utilize BPCG and leading sparse decompositions and separating hyperplanes that beat the current state-of-the-art from the literature (Hirsch et al., 2017; Diviánszky et al., 2017). These previous results relied on a rediscovered standard FW algorithm (Brierley et al., 2016) attributed to Gilbert (1966).

Formally, the task at hand is to find the Euclidean distance between a tensor of size $m^N$ and the N-partite local correlation polytope which is defined by its vertices $d\vec{a}^{(1)}...\vec{a}^{(N)}$, which are rank-one tensors labelled by $\vec{a}^{(n)} = a_1^{(n)}...a_m^{(n)}$ for $n \in [N]$ such that $a_{x_n}^{(n)} = \pm 1$ and with entries expressed as:

$$d_{x_1...x_N}^{\vec{a}^{(1)}...\vec{a}^{(N)}} = \prod_{n=1}^{N} a_{x_n}^{(n)}.$$

Since the objective function is quadratic, its gradient is linear and the LMO reduces, in the bipartite case, to a Quadratic Unconstrained Binary Optimisation (QUBO) instance. In practice, heuristic solutions for this LMO are good enough to provide progress throughout the algorithm. On the one hand, when the focus is on the construction of an explicit decomposition of points lying inside of the local polytope, this approximate LMO suffices. Note that the results in Designolle et al. (2023) take a final extra step to convert the numerical output of the algorithm into an analytical decomposition of the point of interest at the expense of a slight geometrical contraction that can be of interest for similar membership problems. On the other hand, for points outside of the local polytope, the LMO must be solved exactly once at the end of the algorithm. In the multipartite case, symmetry could be exploited by Designolle et al. (2024b) to significantly reduce the dimension and accelerate the (exact) LMO by enumerating only the orbits of vertices. Notice that the acceleration described in Section 5 for quadratic objective functions was introduced to fit the needs of this use case. We refer the reader interested in more hands-on details to the corresponding example in the documentation, entitled Accelerations for quadratic functions and symmetric problems.

**ApproximateVanishingIdeals.jl** In the context of classification, approximate vanishing ideal algorithms generate feature transformations into a high-dimensional space in which the dataset becomes linearly separable (Heldt et al., 2009; Limbeck, 2013; Livni et al., 2013; Wirth & Pokutta, 2022; Wirth et al., 2023a). The latter two works study the Oracle Approximate Vanishing Ideal (OAVI) algorithm, in which the feature transformation is created by solving several Least Absolute Shrinkage and Selection Operator (LASSO) problems with FW variants. The solutions generated by the FW variants are sparse convex combinations of vertices of the feasible region, thus leading to robust and interpretable feature transformations. The ApproximateVanishingIdeals.jl package (Kuzinowicz & Wirth, 2023) implements most of the existing approximate vanishing ideal algorithms and relies on the FrankWolfe.jl implementations of the FW algorithms for solving the LASSO subproblems in OAVI.

**KernelHerding.jl** The kernel herding algorithm is a method for learning in Markov random field models (Welling, 2009) and is equivalent to the FW algorithm (Bach et al., 2012). The only existing software option for kernel herding is the KernelHerding.jl package (Wirth & Besançon, 2022), which builds on FrankWolfe.jl.
**Python interface** We developed `frankwolfe-py`, a Python interface exposing the same functionalities as the native Julia package. All computations are run in Julia, offering the performance with little overhead. The package lets users call the solver with `juliacall`, but also define their own custom oracles, objective function and gradient thanks to `PythonCall`. We present below a simple example using the Python package.

```python
from frankwolfepy import frankwolfe
import numpy as np

def f(x):
    return np.lINALG.NORM(x)**2

def grad/storage,x:
    for i in range(len(x)):
        storage[i] = x[i]

# Create the Linear Minimization Oracle
lmoProb = frankwolfe.ProbabilitySimplexOracle(1)

# Compute first point
x0 = frankwolfe.compute_extreme_point(lmoProb, np(zeros(5)))

# Call the algorithm and get the result tuple
result = frankwolfe.frank_wolfe(f, grad, lmoProb, x0)
```

**CombinatorialLinearOracles.jl** As highlighted in Section 4, many linear minimization oracles have been introduced. Implementing some oracles directly in `FrankWolfe.jl` would however excessively increase the number of dependencies and load time, along with the scope of the package. For these reasons, we introduced a companion package `CombinatorialLinearOracles.jl` to collect important combinatorial oracles, in particular for graph-related problems, in which the corresponding oracle typically corresponds to finding a subset of edges or vertices of minimum or maximum weight. Two examples already implemented are minimum-weight spanning trees using the Kruskal algorithm implemented in `Graphs.jl` and minimum-weight matching using the `BlossomV` solver (Kolmogorov, 2009) for the perfect matching subroutine and the reduction from Schäfer (2000). A linear oracle for maximum-weight matching is of particular importance since it can be called in polynomial time in the size of the input graph, while any polytope representation has to be of exponential size (Rothvoß, 2017).

## Appendix C. Benchmarks and computational evaluation

Lastly, we have developed a benchmark repository<fnref n="1" /> for `FrankWolfe.jl` using the `BenchmarkTools.jl` package. We have benchmarked the original Frank-Wolfe algorithm (Standard), the lazified FW version (Lazy FW), Away-Frank-Wolfe (AFW), Pairwise Conditional Gradient (PCG), Blended Conditional Gradient (BCG), Blended Pairwise Conditional Gradient (BPCG), Decomposition Invariant Conditional Gradient (DICG) and Blended Decomposition Invariant Conditional Gradient (BDICG). Note that the latter two variants can only be applied to problems over 0/1 polytopes and thus, will only be benchmarked on some of the problems. Additionally, we have benchmarked the lazified versions of Standard, AFW, PCG, BCG and BPCG and the `ActiveSetQuadraticProductCaching` on the applicable problems. The dual gap tolerance is set to the default value of 1e-7. The line search is also the default one, namely adaptive step size introduced in Section 3.3. The benchmarks will be continuously extended to contain more problems and new variants. The tables Tables 1 to 10 of the benchmarks in Appendix D display the geometric mean of the solving time and final dual gap over multiple samples and average estimated memory consumption. Note that the memory values may be misleading because progress and hence allocations vastly differ between the variants.

In the following, we introduce the problems and showcase the performance of the different FW variants on them.

<footnote n="1">1. The benchmark repository is available at https://github.com/ZIB-IOL/Benchmarks_for_FrankWolfe_and_Boscia.</footnote>
**Birkhoff polytope** Given a dimension $n \in \mathbb{N}$, we generate a fixed random matrix $\tilde{\mathbf{X}} \in (0, 1)^{n \times n}$ and consider the problem:

$$ \min_{\mathbf{X}} \frac{1}{n^2} \|\mathbf{X} - \tilde{\mathbf{X}}\|_F^2 \\ \text{s.t. } \mathbf{X} \in B_n, $$

where $B_n$ denotes the Birkhoff polytope, i.e., the set of doubly stochastic matrices. A call to the LMO corresponds to a call to the Hungarian algorithm computing an optimal linear assignment.

**Nuclear norm ball for collaborative filtering** For dimension $n \in \mathbb{N}$ and a given $k \in \mathbb{N}$, we generate a fixed matrix $\tilde{\mathbf{X}} \in \mathbb{R}^{n \times n}$ of rank $k$. After that, we randomly choose missing entries and consider the objective function:

$$ \min_{\mathbf{X}} \frac{1}{2} \sum_{(i,j) \in P} (X_{ij} - \tilde{X}_{ij})^2 \\ \text{s.t. } \|\mathbf{X}\|_{\text{nuc}} \le \tau, $$

where $P$ is the set of present entries, $\| \cdot \|_{\text{nuc}}$ is the nuclear norm, and $\tau$ is a hyperparameter. The LMO for the nuclear norm ball consists in computing the negative-most singular vector pair of the gradient matrix.

**The Optimal Experiment Design under the A-criterion and D-criterion** The aim of the Optimal Experiment Design problem is to select the subset of experiments maximizing the information gain about the observed system. The size of the subset is fixed and is usually significantly smaller than the number of total experiments. The natural formulation is a MINLP but there is a continuous formulation called the limit problem whose feasible region is the standard probability simplex (Hendrych et al., 2024). There are different information measures. Two popular ones are the A-criterion

$$ \min_{\mathbf{x}} \operatorname{tr} \left( (\mathbf{A}^{\top} \operatorname{diag}(\mathbf{x}) \mathbf{A})^{-1} \right) \\ \text{s.t. } \mathbf{x} \in \Delta_n $$

and the D-criterion

$$ \min_{\mathbf{x}} \log \det (\mathbf{A}^{\top} \operatorname{diag}(\mathbf{x}) \mathbf{A}) \\ \text{s.t. } \mathbf{x} \in \Delta_n. $$

The matrix $\mathbf{A}$ encodes the a priori information about the experiments. The variables $\mathbf{x}$ can be interpreted as a probability distribution over experiments.

**Poisson regression** The Poisson regression problem aims to model count data where we assume that our data points $y_i$ follow a Poisson distribution. The matrix $\mathbf{X}$ encodes the coefficients for the linear estimation of the expected values of $y_i$. Note that $\mathbf{x}_i$ denotes the $i$-th row of $\mathbf{X}$.

$$ \min_{\mathbf{w}, b} \sum_{i=1}^{n} \exp (\mathbf{w}^{\top} \mathbf{x}_i + b) - y_i (\mathbf{w}^{\top} \mathbf{x}_i + b) + \alpha \|\mathbf{w}\|^2 \\ \text{s.t. } -N \le w_i \le N \quad \forall i \in [n] \\ b \in [-N, N]. $$

**Probability simplex** For dimensions $(m, n) \in \mathbb{N}^2$ we create a fixed random, normally distributed matrix $\mathbf{A} \in \mathbb{R}^{m \times n}$ and a random normally distributed vector $b \in \mathbb{R}^m$ and consider the minimization problem

$$ \min_{\mathbf{x}} \frac{1}{m} \|A\mathbf{x} + b\|_2^2 \\ \text{s.t. } \mathbf{x} \in \Delta_n. $$
**K-sparse polytope** Given a dimension $n \in \mathbb{N}$ and a $K < n$, we generate a fixed random vector $\tilde{x} \in [100]^n$. Let $\mathbf{y} = \frac{1}{\|\mathbf{x}\|_1} \tilde{x}$ and consider the optimization problem:

$$ \begin{array}{ll} \min_{\mathbf{x}} & \|\mathbf{x} - \mathbf{y}\|_2^2 \\ \text{s.t.} & \mathbf{x} \in \mathcal{B}_1(K) \cap \mathcal{B}_\infty \end{array} $$

where $\mathcal{B}_1(K)$ denotes the $\ell_1$-norm ball of radius $K$ and $\mathcal{B}_\infty$ the unit $\ell_\infty$-norm ball. The LMO consists in selecting the $K$ lowest entries of the gradient.

**Spectrahedron** Lastly, we have a quadratic over the spectraplex $S_\tau$ introduced in Section 4. For a matrix $\mathbf{Y} \in \mathbb{R}^{n \times n}$ and observed entries $P \subset [n] \times [n]$, we consider the problem:

$$ \begin{array}{ll} \min_{\mathbf{x}} & \frac{1}{2} \sum_{(i,j) \in P} (X_{ij} - Y_{ij})^2 \\ \text{s.t.} & \mathbf{X} \in S_\tau \end{array} $$

where $\tau$ is between 1.0 and 8.0. Similarly to the nuclear norm ball, the LMO consists in computing the eigenvector associated with the most negative eigenvalue of the gradient, assuming w.l.o.g. that the function is invariant under transposes (thus preserves symmetries).

In Figure 1, we compare the number of optimally solved instances of the baseline variants for all problems. The geometric mean and geometric standard deviation of the dual gaps are shown in Figure 2. The hardest problem is the Nuclear Norm Ball problem, see Figure 1 (d), where most variants already timeout for the smaller dimension. Standard FW shows the best performance, both in terms of solved instances and dual gaps. This suggests that the active set is quite large and the FW vertex computed in any given iteration is not part of the active set at that point.

We observe a similar performance pattern for the Birkhoff problem, both Optimal Design problems, the Poisson problem and the Simplex problem. While the decomposition-invariant methods outperform BPCG, especially for higher dimension, BCG is clearly the best performer. This superior performance indicates that the weights of the vertices are shifted around considerably. In this case, BCG has the advantages since it can move weights between multiple vertices simultaneously whereas both BPCG and the decomposition-invariant methods move weights only between two vertices. Observe that on all variants, standard FW achieves small dual gap values even for the timed out instances on all five problems with exception of the Poisson instances of large dimension.

On the problem over the K-sparse polytope, standard FW and PCG showcase the best performance. Note that the objective of the problem is strongly convex and the optimal solution is likely in the strict interior. This together with the fact that the corresponding LMO is not very expensive explain the good performance of standard FW. For the timed out instances, the quality of the achieved dual gap varies significantly.

There is no clear best performer on the Spectrahedron problem, see Table 8. Standard FW performs well for smaller dimensions. The active set-based methods are superior for larger dimension, in particular BPCG. Considering that the LMO of the Spectrahedron is comparatively expensive since it requires an eigenvalue decomposition, the observed results are to be expected.

Figures 3 and 4 showcase the performance of the lazified versions of the methods (there applicable). We can clearly observe that lazification has a positive impact if the LMO of the corresponding problem is computationally expensive as is the case for the Spectrahedron, the Nuclear Norm Ball, the Poisson Problem and most notably the K-Sparse Polytope. It should be pointed out that the Poisson Problem was modelled using `MathOptInterface.jl`, hence the LMO performed by an LP solver instead of a specialised routine.

In the benchmarks, the usage of `ActiveSetQuadraticProductCaching` is beneficial in cases where the Hessian of the corresponding objective function is trivial, i.e., the unit matrix. This can be seen for the problem over the Spectrahedron, where the gain are quite substantial for BCG and BPCG Figures 5 and 6. In contrast, the Simplex problem show a slow down, which can be understood when considering the cost of computing, as explained after Equation (3), many scalar products involving large matrix-vector
<figure><img src="image_1.png" /><figcaption>Figure 1: Number of solved instances for base variants.</figcaption></figure>

multiplications: this introduces a significant overhead which only pays off after a certain number of iterations. Note also that the number of atoms in the active set plays an important role in this trade-off: the more there are, the more interesting it can become to use *ActiveSetQuadraticProductCaching*.

To summarize, the choice of the most suitable variant depends on the cost of the LMO, the location of the optimal solution (strict interior or face), strong convexity of the objective, and geometry of the feasible region (polytope or nonlinear). Standard FW is by design less memory-intensive but struggle if the LMO is more
<figure><img src="image_2.png" /><figcaption>Figure 2: Geometric mean of dual gaps of base variants.</figcaption></figure>

costly or the optimal solution is on a face. The active set-based methods are the optimal choice for problems of larger dimensions. While DICG requires less memory and provides directions well-aligned with the negative gradient, the second LMO call to compute the in-face vertex can cause computational overhead, as it is in many cases as expensive as the standard LMO. Lazification can be a great addition if the LMO is very expensive and is, in particular, effective within BPCG. Likewise, utilizing the ActiveSetQuadraticProductCaching can provide an advantage when optimizing a quadratic over the feasible region with expensive LMO. The design of this diverse benchmark set precisely highlights the importance of the different FW methods for different types of problem classes, motivating their inclusion in the package.

## Appendix D. Benchmark tables
<figure><img src="image_3.png" /><figcaption>Figure 3: Number of solved instances for lazified variants.</figcaption></figure>
<figure><img src="image_4.png" /><figcaption>Figure 4: Geometric mean and geometric standard deviation of dual gaps for lazified variants.</figcaption></figure>
<figure><img src="image_5.png" /><figcaption>Figure 5: Number of solved instances for active set variants with product caching.</figcaption></figure>
<figure><img src="image_6.png" /><figcaption>Figure 6: Geometric mean and geometric standard deviation of dual gaps for active set variants with product caching.</figcaption></figure>
<table><caption>Table 1: Performance comparison on the A-Criterion optimal design problem. Entries marked with * timed out.</caption><thead><tr><th rowspan="2">Dim</th><th colspan="2">Standard</th><th colspan="2">AFW</th><th colspan="2">PCG</th><th colspan="2">BCG</th><th colspan="2">BPCG</th><th colspan="2">DICG</th><th colspan="2">BDICG</th></tr><tr><th>Time (s)</th><th>Average memory (GB)</th><th>Time (s)</th><th>Average memory (GB)</th><th>Dual gap</th><th>Time (s)</th><th>Average memory (GB)</th><th>Dual gap</th><th>Time (s)</th><th>Average memory (GB)</th><th>Dual gap</th><th>Time (s)</th><th>Average memory (GB)</th><th>Dual gap</th><th>Time (s)</th><th>Average memory (GB)</th></tr></thead><tbody><tr><td>100</td><td>7.76e2</td><td>1.30e-7</td><td>3.62e-1</td><td>6.93e-1</td><td>1.07e-7</td><td>2.32e-1</td><td>4.55e-1</td><td>1.00e-7</td><td>2.75e-1</td><td>2.64e-1</td><td>1.20e-7</td><td>2.97e-1</td><td>6.19e-1</td><td>1.00e-7</td><td>2.47e-1</td><td>4.95e-1</td><td>1.03e-7</td><td>2.45e-1</td><td>5.03e-1</td><td>1.14e-7</td></tr><tr><td>250</td><td>3.60e3*</td><td>1.36e-3</td><td>1.64e-6</td><td>5.14e-1</td><td>1.42e-1</td><td>1.06e-7</td><td>2.58e-1</td><td>7.42</td><td>1.00e-7</td><td>1.18e-1</td><td>3.36</td><td>1.16e-7</td><td>3.79e-1</td><td>1.01e-1</td><td>1.00e-7</td><td>1.95e-1</td><td>7.47</td><td>1.02e-7</td><td>2.56e-1</td><td>7.72</td></tr><tr><td>400</td><td>3.60e3*</td><td>1.73e-3</td><td>3.19e-6</td><td>1.09e-2</td><td>4.97e-1</td><td>1.00e-7</td><td>8.45e-1</td><td>3.73e-1</td><td>1.00e-7</td><td>3.28e-1</td><td>1.57e-1</td><td>1.23e-7</td><td>1.15e-2</td><td>4.99e-1</td><td>1.00e-7</td><td>9.07e-1</td><td>3.86e-1</td><td>1.04e-7</td><td>8.00e-1</td><td>3.83e-1</td><td>1.01e-7</td></tr><tr><td>550</td><td>3.60e3*</td><td>1.92e-3</td><td>6.67e-6</td><td>3.97e-2</td><td>2.08e-1</td><td>1.02e-7</td><td>2.09e-1</td><td>8.01e-2</td><td>1.00e-7</td><td>8.41e-1</td><td>4.85e-1</td><td>1.00e-7</td><td>2.38e-1</td><td>1.39e-1</td><td>1.00e-7</td><td>1.82e-1</td><td>1.14e-2</td><td>1.00e-7</td><td>2.04e-2</td><td>1.11e-2</td><td>1.02e-7</td></tr><tr><td>700</td><td>3.60e3*</td><td>2.15e-3</td><td>1.00e-5</td><td>8.10e-2</td><td>4.57e-2</td><td>1.01e-7</td><td>4.20e-2</td><td>2.47e-2</td><td>1.00e-7</td><td>1.88e-2</td><td>1.19e-2</td><td>1.16e-7</td><td>5.08e-2</td><td>3.19e-2</td><td>1.00e-7</td><td>4.38e-2</td><td>2.55e-2</td><td>1.02e-7</td><td>3.93e-2</td><td>2.61e-2</td><td>1.00e-7</td></tr><tr><td>850</td><td>3.60e3*</td><td>2.38e-3</td><td>1.21e-5</td><td>1.36e-3</td><td>9.26e-2</td><td>1.01e-7</td><td>7.82e-2</td><td>4.99e-2</td><td>1.00e-7</td><td>3.45e-2</td><td>2.45e-2</td><td>1.13e-7</td><td>7.68e-2</td><td>6.26e-2</td><td>1.00e-7</td><td>6.86e-2</td><td>5.08e-2</td><td>1.00e-7</td><td>6.81e-2</td><td>5.18e-2</td><td>1.00e-7</td></tr></tbody></table>

<table><caption>Table 2: Performance comparison on the Birkhoff problem. Entries marked with * timed out.</caption><thead><tr><th rowspan="2">Dim</th><th colspan="2">Standard</th><th colspan="2">AFW</th><th colspan="2">PCG</th><th colspan="2">BCG</th><th colspan="2">BPCG</th><th colspan="2">DICG</th><th colspan="2">BDICG</th></tr><tr><th>Time (s)</th><th>Average memory (GB)</th><th>Dual gap</th><th>Time (s)</th><th>Average memory (GB)</th><th>Dual gap</th><th>Time (s)</th><th>Average memory (GB)</th><th>Dual gap</th><th>Time (s)</th><th>Average memory (GB)</th><th>Dual gap</th><th>Time (s)</th><th>Average memory (GB)</th><th>Dual gap</th><th>Time (s)</th><th>Average memory (GB)</th></tr></thead><tbody><tr><td>10000</td><td>3.60e3*</td><td>7.25e-2</td><td>3.29e-7</td><td>4.09e-2</td><td>1.33e-2</td><td>1.22e-7</td><td>3.09e-1</td><td>1.49e-1</td><td>1.00e-7</td><td>3.43e-2</td><td>1.05e-2</td><td>1.00e-7</td><td>7.41e-2</td><td>2.08e-2</td><td>1.00e-7</td><td>5.59e-1</td><td>1.47e-1</td><td>1.18e-7</td><td>6.48e-1</td><td>1.43e-1</td><td>1.16e-7</td></tr><tr><td>62500</td><td>3.60e3*</td><td>6.62e-2</td><td>9.44e-7</td><td>2.30e-7</td><td>4.89e-2</td><td>1.16e-7</td><td>1.99e-2</td><td>8.18e-1</td><td>1.26e-7</td><td>2.80e-3</td><td>5.48e-2</td><td>1.00e-7</td><td>3.60e3*</td><td>8.05e-2</td><td>2.53e-7</td><td>6.04e-2</td><td>8.12e-1</td><td>1.17e-7</td><td>7.78e-2</td><td>7.91e-1</td><td>1.17e-7</td><td></td></tr><tr><td>160000</td><td>3.60e3*</td><td>6.37e-2</td><td>1.56e-6</td><td>3.60e3*</td><td>5.23e-2</td><td>1.39e-7</td><td>6.51e-2</td><td>2.19e-2</td><td>1.00e-7</td><td>3.60e3*</td><td>5.42e-2</td><td>1.69e-7</td><td>3.60e3*</td><td>6.05e-2</td><td>4.49e-7</td><td>2.14e-3</td><td>1.77e-2</td><td>1.08e-7</td><td>2.82e-3</td><td>1.60e-2</td><td>1.16e-7</td><td></td></tr><tr><td>422500</td><td>3.60e3*</td><td>6.94e-2</td><td>2.81e-6</td><td>3.60e3*</td><td>4.50e-2</td><td>3.05e-7</td><td>2.58e-3</td><td>6.22e-2</td><td>1.00e-7</td><td>3.60e3*</td><td>4.74e-2</td><td>3.70e-7</td><td>3.60e3*</td><td>6.00e-2</td><td>7.11e-7</td><td>3.60e3*</td><td>2.44e-2</td><td>1.73e-7</td><td>3.60e3*</td><td>1.90e-2</td><td>2.34e-7</td><td></td></tr><tr><td>640000</td><td>3.60e3*</td><td>6.99e-2</td><td>3.43e-6</td><td>3.60e3*</td><td>4.27e-2</td><td>3.98e-7</td><td>1.90e-3</td><td>3.59e-2</td><td>1.86e-7</td><td>3.60e3*</td><td>4.52e-2</td><td>4.80e-7</td><td>3.60e3*</td><td>5.71e-7</td><td>8.52e-7</td><td>3.60e3*</td><td>2.17e-2</td><td>2.27e-7</td><td>3.60e3*</td><td>1.75e-2</td><td>3.11e-7</td><td></td></tr><tr><td>1000000</td><td>3.60e3*</td><td>6.88e-2</td><td>4.26e-6</td><td>3.60e3*</td><td>4.27e-2</td><td>5.55e-7</td><td>3.51e-3</td><td>5.64e-2</td><td>1.51e-7</td><td>3.60e3*</td><td>4.17e-2</td><td>6.57e-7</td><td>3.60e3*</td><td>5.78e-2</td><td>9.54e-7</td><td>3.60e3*</td><td>2.24e-2</td><td>3.44e-7</td><td>3.60e3*</td><td>1.89e-2</td><td>4.87e-7</td><td></td></tr></tbody></table>

<table><caption>Table 3: Performance comparison on the D-Criterion optimal design problem. Entries marked with * timed out.</caption><thead><tr><th rowspan="2">Dim</th><th colspan="2">Standard</th><th colspan="2">AFW</th><th colspan="2">PCG</th><th colspan="2">BCG</th><th colspan="2">BPCG</th><th colspan="2">DICG</th><th colspan="2">BDICG</th></tr><tr><th>Time (s)</th><th>Average memory (GB)</th><th>Dual gap</th><th>Time (s)</th><th>Average memory (GB)</th><th>Dual gap</th><th>Time (s)</th><th>Average memory (GB)</th><th>Dual gap</th><th>Time (s)</th><th>Average memory (GB)</th><th>Dual gap</th><th>Time (s)</th><th>Average memory (GB)</th><th>Dual gap</th><th>Time (s)</th><th>Average memory (GB)</th></tr></thead><tbody><tr><td>100</td><td>3.07e3</td><td>6.35e-3</td><td>1.07e-7</td><td>3.03e-1</td><td>4.67e-1</td><td>1.06e-7</td><td>2.06e-1</td><td>3.18e-1</td><td>1.00e-7</td><td>3.62e-1</td><td>1.77e-1</td><td>1.38e-7</td><td>1.86e-1</td><td>4.03e-1</td><td>1.00e-7</td><td>2.02e-1</td><td>3.09e-1</td><td>1.06e-7</td><td>2.11e-1</td><td>3.39e-1</td><td>1.01e-7</td></tr><tr><td>250</td><td>3.60e3*</td><td>1.44e-3</td><td>1.58e-5</td><td>4.49e-1</td><td>1.13e-1</td><td>1.05e-7</td><td>1.73e-1</td><td>5.96</td><td>1.00e-7</td><td>7.00</td><td>2.14</td><td>1.11e-7</td><td>2.37e-1</td><td>7.19</td><td>1.00e-7</td><td>1.78e-1</td><td>5.92</td><td>1.06e-7</td><td>2.19e-1</td><td>6.05</td><td>1.03e-7</td></tr><tr><td>400</td><td>3.60e3*</td><td>1.73e-3</td><td>6.11e-5</td><td>1.34e-2</td><td>5.98e-1</td><td>1.00e-7</td><td>6.84e-1</td><td>3.21e-1</td><td>1.00e-7</td><td>2.27e-1</td><td>1.04e-1</td><td>1.01e-7</td><td>8.56e-1</td><td>3.94e-1</td><td>1.00e-7</td><td>7.40e-1</td><td>3.24e-1</td><td>1.04e-7</td><td>8.45e-1</td><td>3.27e-1</td><td>1.02e-7</td></tr><tr><td>550</td><td>3.60e3*</td><td>1.95e-3</td><td>1.48e-4</td><td>3.19e-2</td><td>1.84e-2</td><td>1.02e-7</td><td>1.48e-2</td><td>9.73e-1</td><td>1.00e-7</td><td>4.14e-1</td><td>3.25e-1</td><td>1.43e-7</td><td>2.17e-2</td><td>1.16e-2</td><td>1.00e-7</td><td>2.03e-2</td><td>1.02e-2</td><td>1.01e-7</td><td>1.56e-2</td><td>1.03e-2</td><td>1.00e-7</td></tr><tr><td>700</td><td>3.60e3*</td><td>2.81e-3</td><td>2.59e-4</td><td>8.04e-2</td><td>4.43e-2</td><td>1.02e-7</td><td>4.01e-2</td><td>2.42e-2</td><td>1.00e-7</td><td>1.11e-2</td><td>8.06e-1</td><td>1.18e-7</td><td>4.54e-2</td><td>2.93e-2</td><td>1.00e-7</td><td>4.46e-2</td><td>2.47e-2</td><td>1.00e-7</td><td>4.09e-2</td><td>2.49e-2</td><td>1.01e-7</td></tr><tr><td>850</td><td>3.60e3*</td><td>2.76e-3</td><td>4.71e-4</td><td>1.55e-3</td><td>9.42e-2</td><td>1.01e-7</td><td>6.80e-2</td><td>5.08e-2</td><td>1.00e-7</td><td>1.89e-2</td><td>1.65e-2</td><td>1.14e-7</td><td>8.90e-2</td><td>6.09e-2</td><td>1.00e-7</td><td>7.46e-2</td><td>5.29e-2</td><td>1.00e-7</td><td>7.37e-2</td><td>5.36e-2</td><td>1.00e-7</td></tr></tbody></table>

<table><caption>Table 4: Performance comparison on the Nuclear problem. Entries marked with * timed out.</caption><thead><tr><th rowspan="2">Dim</th><th colspan="2">Standard</th><th colspan="2">AFW</th><th colspan="2">PCG</th><th colspan="2">BCG</th><th colspan="2">BPCG</th><th colspan="2">DICG</th><th colspan="2">BDICG</th></tr><tr><th>Time (s)</th><th>Average memory (GB)</th><th>Dual gap</th><th>Time (s)</th><th>Average memory (GB)</th><th>Dual gap</th><th>Time (s)</th><th>Average memory (GB)</th><th>Dual gap</th><th>Time (s)</th><th>Average memory (GB)</th><th>Dual gap</th><th>Time (s)</th><th>Average memory (GB)</th><th>Dual gap</th><th>Time (s)</th><th>Average memory (GB)</th></tr></thead><tbody><tr><td>10000</td><td>1.34e-1</td><td>8.05e-1</td><td>1.00e-7</td><td>3.60e3*</td><td>1.26e-1</td><td>1.80e-3</td><td>3.60e3*</td><td>1.86e-1</td><td>1.44e-3</td><td>3.60e3*</td><td>1.20e-4</td><td>1.64e-2</td><td>1.36e-1</td><td>3.41e-1</td><td>1.00e-7</td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>62500</td><td>4.49e-2</td><td>2.78</td><td>1.02e-7</td><td>3.60e3*</td><td>1.47</td><td>2.59</td><td>3.60e3*</td><td>1.50</td><td>4.11</td><td>3.60e3*</td><td>9.94e-5</td><td>4.96e-5</td><td>3.60e3*</td><td>1.76</td><td>1.79e-1</td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>160000</td><td>3.60e3*</td><td>2.23e-1</td><td>4.12e-5</td><td>3.60e3*</td><td>1.69</td><td>1.58e-2</td><td>3.60e3*</td><td>1.37</td><td>5.93e-3</td><td>3.60e3*</td><td>6.91e-3</td><td>7.76e-8</td><td>3.60e3*</td><td>2.08</td><td>2.78</td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>302500</td><td>3.60e3*</td><td>2.45e-1</td><td>2.52e-4</td><td>3.60e3*</td><td>1.49</td><td>2.84e-3</td><td>3.60e3*</td><td>1.52</td><td>4.39e-6</td><td>3.60e3*</td><td>7.39e-3</td><td>1.19e-10</td><td>3.60e3*</td><td>2.23</td><td>2.74e-3</td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>490000</td><td>3.60e3*</td><td>2.26e-1</td><td>9.25e-4</td><td>3.60e3*</td><td>1.41</td><td>2.52e-6</td><td>3.60e3*</td><td>1.48</td><td>3.96e-8</td><td>3.60e3*</td><td>5.72e-3</td><td>8.63e-10</td><td>3.60e3*</td><td>2.31</td><td>3.92e-6</td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>722500</td><td>3.60e3*</td><td>1.00e-1</td><td>2.09e-3</td><td>3.60e3*</td><td>1.45</td><td>7.63e-7</td><td>3.60e3*</td><td>1.48</td><td>2.14e-9</td><td>3.60e3*</td><td>6.26e-3</td><td>2.15e-11</td><td>3.60e3*</td><td>2.42</td><td>1.39e-8</td><td></td><td></td><td></td><td></td><td></td></tr></tbody></table>
<table><caption>Table 5: Performance comparison on the Poisson problem. Entries marked with * timed out.</caption><thead><tr><th rowspan="2">Dim</th><th colspan="2">Standard</th><th colspan="2">AFW</th><th colspan="2">PCG</th><th colspan="2">BCG</th><th colspan="2">BPCG</th><th colspan="2">DICG</th><th colspan="2">BDICG</th></tr><tr><th>Time (s)</th><th>Average memory (GB)</th><th>Time (s)</th><th>Average memory (GB)</th><th>Time (s)</th><th>Average memory (GB)</th><th>Time (s)</th><th>Average memory (GB)</th><th>Time (s)</th><th>Average memory (GB)</th><th>Time (s)</th><th>Average memory (GB)</th><th>Time (s)</th><th>Average memory (GB)</th></tr></thead><tbody><tr><td>100</td><td>3.60e3*</td><td>2.11e3</td><td>3.27e-5</td><td>4.23</td><td>1.74</td><td>1.00e-7</td><td>2.92</td><td>1.98</td><td>1.00e-7</td><td>7.93e-1</td><td>9.38e-1</td><td>1.00e-7</td><td>2.88</td><td>2.08</td><td>1.00e-7</td><td>1.43e1</td><td>2.20</td><td>1.42e-7</td><td>2.02e1</td><td>2.51</td><td>1.42e-7</td></tr><tr><td>250</td><td>3.60e3*</td><td>2.05e3</td><td>1.34e-3</td><td>1.00e2</td><td>4.57e1</td><td>1.00e-7</td><td>3.23e1</td><td>2.54e1</td><td>1.00e-7</td><td>1.05e1</td><td>1.01e1</td><td>1.34e-7</td><td>4.57e1</td><td>3.69e1</td><td>1.00e-7</td><td>8.96e1</td><td>3.44e1</td><td>1.83e-7</td><td>1.26e2</td><td>3.68e1</td><td>1.83e-7</td></tr><tr><td>400</td><td>3.60e3*</td><td>1.31e3</td><td>1.04e-2</td><td>6.41e2</td><td>2.48e2</td><td>1.00e-7</td><td>2.88e2</td><td>1.54e2</td><td>1.00e-7</td><td>1.20e2</td><td>7.23e1</td><td>1.12e-7</td><td>3.07e2</td><td>1.72e2</td><td>1.00e-7</td><td>2.97e2</td><td>1.25e2</td><td>1.96e-7</td><td>3.48e2</td><td>1.30e2</td><td>1.96e-7</td></tr><tr><td>650</td><td>3.60e3*</td><td>1.10e3</td><td>5.36e-2</td><td>3.49e3</td><td>1.24e3</td><td>2.27e-6</td><td>1.78e3</td><td>7.64e2</td><td>1.00e-7</td><td>9.47e2</td><td>4.74e2</td><td>1.00e-7</td><td>1.86e3</td><td>8.41e2</td><td>1.00e-7</td><td>1.82e3</td><td>7.38e2</td><td>1.58e-7</td><td>2.08e3</td><td>7.59e2</td><td>1.58e-7</td></tr><tr><td>800</td><td>3.60e3*</td><td>1.38e3</td><td>7.16e-2</td><td>3.60e3*</td><td>1.24e3</td><td>7.59e-2</td><td>3.60e3*</td><td>1.40e3</td><td>3.11e-3</td><td>3.25e3</td><td>1.41e3</td><td>4.24e-5</td><td>3.60e3*</td><td>1.41e3</td><td>4.95e-2</td><td>3.60e3*</td><td>1.34e3</td><td>1.13e-2</td><td>3.60e3*</td><td>1.34e3</td><td>3.87e-2</td></tr><tr><td>1000</td><td>3.60e3*</td><td>1.25e3</td><td>1.05e-1</td><td>3.60e3*</td><td>1.00e3</td><td>1.09e-1</td><td>3.60e3*</td><td>1.35e3</td><td>9.57e-2</td><td>3.60e3*</td><td>1.54e3</td><td>8.79e-1</td><td>3.60e3*</td><td>1.31e3</td><td>1.89e-1</td><td>3.60e3*</td><td>1.29e3</td><td>1.00e-1</td><td>3.60e3*</td><td>1.25e3</td><td>1.11e-1</td></tr></tbody></table>

<table><caption>Table 6: Performance comparison on the Simplex problem. Entries marked with * timed out.</caption><thead><tr><th rowspan="2">Dim</th><th colspan="2">Standard</th><th colspan="2">AFW</th><th colspan="2">PCG</th><th colspan="2">BCG</th><th colspan="2">BPCG</th><th colspan="2">DICG</th><th colspan="2">BDICG</th></tr><tr><th>Time (s)</th><th>Average memory (GB)</th><th>Time (s)</th><th>Average memory (GB)</th><th>Time (s)</th><th>Average memory (GB)</th><th>Time (s)</th><th>Average memory (GB)</th><th>Time (s)</th><th>Average memory (GB)</th><th>Time (s)</th><th>Average memory (GB)</th><th>Time (s)</th><th>Average memory (GB)</th></tr></thead><tbody><tr><td>5000, 2500</td><td>3.35e3</td><td>1.03e3</td><td>1.28e-6</td><td>3.18</td><td>7.44e-1</td><td>1.00e-7</td><td>3.55</td><td>4.18e-1</td><td>1.00e-7</td><td>8.53e-1</td><td>1.40e-1</td><td>1.07e-7</td><td>3.77</td><td>4.48e-1</td><td>1.00e-7</td><td>2.48</td><td>4.12e-1</td><td>1.00e-7</td><td>1.57</td><td>4.07e-1</td><td>1.00e-7</td></tr><tr><td>5000, 6000</td><td>3.60e3*</td><td>3.06e2</td><td>7.64e-6</td><td>1.70e1</td><td>1.04</td><td>1.00e-7</td><td>1.66e1</td><td>5.95e-1</td><td>1.00e-7</td><td>2.56</td><td>2.10e-1</td><td>1.00e-7</td><td>1.36e1</td><td>6.51e-1</td><td>1.00e-7</td><td>7.53</td><td>5.84e-1</td><td>1.00e-7</td><td>7.23</td><td>5.76e-1</td><td>1.00e-7</td></tr><tr><td>7000, 3500</td><td>3.60e3*</td><td>6.95e2</td><td>3.36e-6</td><td>1.69e1</td><td>1.13</td><td>1.00e-7</td><td>8.18</td><td>6.47e-1</td><td>1.00e-7</td><td>1.30</td><td>2.20e-1</td><td>1.00e-7</td><td>9.49</td><td>6.95e-1</td><td>1.00e-7</td><td>4.93</td><td>6.37e-1</td><td>1.00e-7</td><td>4.39</td><td>6.31e-1</td><td>1.00e-7</td></tr><tr><td>7000, 8500</td><td>3.60e3*</td><td>4.96e2</td><td>1.38e-5</td><td>2.88e1</td><td>3.52</td><td>1.00e-7</td><td>2.44e1</td><td>1.95</td><td>1.00e-7</td><td>3.84</td><td>6.18e-1</td><td>1.14e-7</td><td>4.79e1</td><td>2.09</td><td>1.00e-7</td><td>1.44e1</td><td>1.94</td><td>1.00e-7</td><td>1.33e1</td><td>1.91</td><td>1.00e-7</td></tr><tr><td>10000, 5000</td><td>3.60e3*</td><td>2.32e2</td><td>6.27e-6</td><td>3.05e1</td><td>1.02</td><td>1.00e-7</td><td>1.27e1</td><td>5.82e-1</td><td>1.00e-7</td><td>2.77</td><td>2.40e-1</td><td>1.12e-7</td><td>1.68e1</td><td>6.37e-1</td><td>1.00e-7</td><td>9.87</td><td>5.54e-1</td><td>1.00e-7</td><td>8.99</td><td>5.60e-1</td><td>1.00e-7</td></tr><tr><td>10000, 12000</td><td>3.60e3*</td><td>1.81e2</td><td>2.11e-5</td><td>8.07e1</td><td>2.81</td><td>1.00e-7</td><td>4.68e1</td><td>1.62</td><td>1.00e-7</td><td>9.93</td><td>5.91e-1</td><td>1.21e-7</td><td>6.06e1</td><td>1.79</td><td>1.00e-7</td><td>3.02e1</td><td>1.56</td><td>1.00e-7</td><td>2.93e1</td><td>1.56</td><td>1.00e-7</td></tr><tr><td>20000, 10000</td><td>3.60e3*</td><td>1.36e2</td><td>2.25e-5</td><td>7.61e1</td><td>2.81</td><td>1.00e-7</td><td>7.45e1</td><td>1.59</td><td>1.00e-7</td><td>1.29e1</td><td>6.89e-1</td><td>1.13e-7</td><td>8.22e1</td><td>1.75</td><td>1.00e-7</td><td>4.01e1</td><td>1.56</td><td>1.00e-7</td><td>3.90e1</td><td>1.55</td><td>1.00e-7</td></tr><tr><td>20000, 24000</td><td>3.60e3*</td><td>1.03e2</td><td>5.22e-5</td><td>2.06e2</td><td>6.12</td><td>1.00e-7</td><td>1.29e2</td><td>3.47</td><td>1.00e-7</td><td>2.94e1</td><td>1.41</td><td>1.00e-7</td><td>2.28e1</td><td>3.90</td><td>1.00e-7</td><td>1.10e2</td><td>3.37</td><td>1.00e-7</td><td>1.15e2</td><td>3.40</td><td>1.00e-7</td></tr></tbody></table>

<table><caption>Table 7: Performance comparison on the Sparse problem. Entries marked with * timed out.</caption><thead><tr><th rowspan="2">Dim</th><th colspan="2">Standard</th><th colspan="2">AFW</th><th colspan="2">PCG</th><th colspan="2">BCG</th><th colspan="2">BPCG</th><th colspan="2">DICG</th><th colspan="2">BDICG</th></tr><tr><th>Time (s)</th><th>Average memory (GB)</th><th>Time (s)</th><th>Average memory (GB)</th><th>Time (s)</th><th>Average memory (GB)</th><th>Time (s)</th><th>Average memory (GB)</th><th>Time (s)</th><th>Average memory (GB)</th><th>Time (s)</th><th>Average memory (GB)</th><th>Time (s)</th><th>Average memory (GB)</th></tr></thead><tbody><tr><td>10000</td><td>1.35e1</td><td>4.86e1</td><td>1.35e-7</td><td>1.40e1</td><td>4.88e1</td><td>1.00e-7</td><td>3.51</td><td>1.12e1</td><td>1.00e-7</td><td>9.06</td><td>1.07e1</td><td>1.00e-7</td><td>5.82</td><td>2.12e1</td><td>1.00e-7</td></tr><tr><td>40000</td><td>5.52e1</td><td>1.97e2</td><td>1.20e-7</td><td>5.66e1</td><td>2.00e2</td><td>1.00e-7</td><td>5.14e1</td><td>1.75e2</td><td>1.00e-7</td><td>1.11e2</td><td>1.59e2</td><td>1.35e-7</td><td>1.162</td><td>3.95e2</td><td>1.00e-7</td></tr><tr><td>80000</td><td>9.09e2</td><td>3.03e3</td><td>1.30e-7</td><td>9.23e2</td><td>3.07e3</td><td>1.42e-7</td><td>2.01e2</td><td>7.44e2</td><td>1.00e-7</td><td>3.60e3*</td><td>1.21e4</td><td>5.44e-7</td><td>1.30e3</td><td>4.36e3</td><td>1.63e-7</td></tr><tr><td>140000</td><td>2.10e2</td><td>7.37e2</td><td>1.00e-7</td><td>1.92e2</td><td>7.56e-2</td><td>1.00e-7</td><td>7.40e2</td><td>2.28e3</td><td>1.00e-7</td><td>3.60e3*</td><td>1.12e4</td><td>6.34e-7</td><td>5.44e2</td><td>1.99e3</td><td>1.80e-7</td></tr><tr><td>200000</td><td>3.60e3*</td><td>1.26e4</td><td>1.29e-6</td><td>3.60e3*</td><td>1.21e4</td><td>1.78e-6</td><td>3.60e3*</td><td>1.17e4</td><td>4.46e-5</td><td>3.60e3*</td><td>1.26e4</td><td>4.25e-6</td><td>3.60e3*</td><td>1.22e4</td><td>4.16e-5</td></tr><tr><td>350000</td><td>3.60e3*</td><td>1.19e4</td><td>1.46e-5</td><td>3.60e3*</td><td>1.19e4</td><td>1.58e-5</td><td>3.60e3*</td><td>1.12e4</td><td>1.51e-3</td><td>3.60e3*</td><td>1.15e4</td><td>6.90e-6</td><td>3.60e3*</td><td>1.20e4</td><td>4.92e-4</td></tr><tr><td>500000</td><td>3.60e3*</td><td>1.14e4</td><td>4.64e-3</td><td>3.60e3*</td><td>1.17e4</td><td>4.63e-3</td><td>3.60e3*</td><td>1.11e4</td><td>1.92e-2</td><td>3.60e3*</td><td>1.10e4</td><td>4.01e-4</td><td>3.60e3*</td><td>1.16e4</td><td>2.36e-4</td></tr></tbody></table>

<table><caption>Table 8: Performance comparison on the Spectrahedron problem. Entries marked with * timed out.</caption><thead><tr><th rowspan="2">Dim</th><th colspan="2">Standard</th><th colspan="2">AFW</th><th colspan="2">PCG</th><th colspan="2">BCG</th><th colspan="2">BPCG</th><th colspan="2">DICG</th><th colspan="2">BDICG</th></tr><tr><th>Time (s)</th><th>Average memory (GB)</th><th>Time (s)</th><th>Average memory (GB)</th><th>Time (s)</th><th>Average memory (GB)</th><th>Time (s)</th><th>Average memory (GB)</th><th>Time (s)</th><th>Average memory (GB)</th><th>Time (s)</th><th>Average memory (GB)</th><th>Time (s)</th><th>Average memory (GB)</th></tr></thead><tbody><tr><td>10000</td><td>5.05e-2</td><td>6.41e-3</td><td>1.92e-7</td><td>1.52e-2</td><td>2.85e-3</td><td>1.17e-7</td><td>1.53e-2</td><td>2.88e-3</td><td>1.00e-7</td><td>1.55e-2</td><td>2.33e-2</td><td>1.19e-7</td><td>2.17e-2</td><td>3.51e-3</td><td>1.00e-7</td></tr><tr><td>62500</td><td>4.15e-2</td><td>1.05e-2</td><td>1.00e-7</td><td>6.81e-2</td><td>1.08e-2</td><td>1.00e-7</td><td>8.42e-2</td><td>1.11e-2</td><td>1.00e-7</td><td>1.04e-1</td><td>4.24e-2</td><td>1.42e-7</td><td>5.81e-2</td><td>1.07e-2</td><td>1.00e-7</td></tr><tr><td>250000</td><td>2.02e1</td><td>4.18e-1</td><td>2.33e-7</td><td>3.27e1</td><td>2.27e-1</td><td>1.67e-7</td><td>7.83e1</td><td>1.44e-1</td><td>1.00e-7</td><td>1.63e1</td><td>6.33</td><td>1.24e-7</td><td>2.29e1</td><td>1.87e-1</td><td>1.00e-7</td></tr><tr><td>490000</td><td>1.28e1</td><td>3.02e-1</td><td>2.02e-7</td><td>4.55e1</td><td>3.31e-1</td><td>1.24e-7</td><td>2.19e2</td><td>2.91e-1</td><td>1.00e-7</td><td>2.46e1</td><td>1.08e1</td><td>1.10e-7</td><td>3.18e1</td><td>3.17e-1</td><td>1.00e-7</td></tr><tr><td>722500</td><td>6.98e2</td><td>3.27</td><td>3.10e-7</td><td>3.52e3</td><td>2.39</td><td>4.90e-7</td><td>3.12e3</td><td>1.35</td><td>4.29e-7</td><td>2.71e2</td><td>4.70e2</td><td>1.31e-7</td><td>1.70e3</td><td>8.13</td><td>1.02e-7</td></tr><tr><td>1000000</td><td>1.93e3</td><td>7.63</td><td>2.35e-7</td><td>3.60e3*</td><td>2.45</td><td>7.86e-7</td><td>3.60e3*</td><td>1.53</td><td>6.88e-7</td><td>5.81e2</td><td>9.73e2</td><td>1.45e-7</td><td>2.94e3</td><td>1.34e1</td><td>1.94e-7</td></tr></tbody></table>
<table><caption>Table 9: Performance comparison of lazified variants. Entries marked with * timed out.</caption><thead><tr><th rowspan="2">Problem</th><th rowspan="2">Dim</th><th colspan="3">Standard</th><th colspan="3">Away</th><th colspan="3">PCG</th><th colspan="3">BCG</th><th colspan="3">BPCG</th></tr><tr><th>Time (s)</th><th>Average memory (GB)</th><th>Dual gap</th><th>Time (s)</th><th>Average memory (GB)</th><th>Dual gap</th><th>Time (s)</th><th>Average memory (GB)</th><th>Dual gap</th><th>Time (s)</th><th>Average memory (GB)</th><th>Dual gap</th><th>Time (s)</th><th>Average memory (GB)</th><th>Dual gap</th></tr></thead><tbody><tr><td rowspan="6">A-Criterion</td><td colspan="18">n</td></tr><tr><td>100</td><td>1.20e3</td><td>2.29e3</td><td>1.00e-7</td><td>3.62e-1</td><td>9.16e-1</td><td>1.07e-7</td><td>2.32e-1</td><td>5.84e-1</td><td>1.00e-7</td><td>2.75e-1</td><td>2.64e-1</td><td>1.20e-7</td><td>2.97e-1</td><td>6.92e-1</td><td>1.00e-7</td></tr><tr><td>250</td><td>3.60e3*</td><td>1.46e3</td><td>1.39e-6</td><td>5.14e1</td><td>1.48e1</td><td>1.06e-7</td><td>2.58e1</td><td>8.69</td><td>1.00e-7</td><td>1.18e1</td><td>3.36</td><td>1.16e-7</td><td>3.79e1</td><td>1.07e1</td><td>1.00e-7</td></tr><tr><td>400</td><td>3.60e3*</td><td>1.58e3</td><td>4.95e-6</td><td>1.09e2</td><td>7.46e1</td><td>1.00e-7</td><td>8.45e1</td><td>4.30e1</td><td>1.00e-7</td><td>3.28e1</td><td>1.57e1</td><td>1.23e-7</td><td>1.15e2</td><td>4.93e1</td><td>1.00e-7</td></tr><tr><td>550</td><td>3.60e3*</td><td>2.02e3</td><td>3.60e-5</td><td>3.97e2</td><td>2.20e2</td><td>1.02e-7</td><td>2.09e2</td><td>1.24e2</td><td>1.00e-7</td><td>8.41e1</td><td>4.85e1</td><td>1.00e-7</td><td>2.38e2</td><td>1.44e2</td><td>1.00e-7</td></tr><tr><td>700</td><td>3.60e3*</td><td>2.16e3</td><td>4.84e-5</td><td>8.10e2</td><td>4.88e2</td><td>1.01e-7</td><td>4.20e2</td><td>2.80e2</td><td>1.00e-7</td><td>1.88e2</td><td>1.19e2</td><td>1.16e-7</td><td>5.08e2</td><td>3.21e2</td><td>1.00e-7</td></tr><tr><td>850</td><td>3.60e3*</td><td>2.49e3</td><td>3.43e-5</td><td>1.36e3</td><td>9.74e2</td><td>1.01e-7</td><td>7.82e2</td><td>5.69e2</td><td>1.00e-7</td><td>3.45e2</td><td>2.45e2</td><td>1.13e-7</td><td>7.68e2</td><td>6.48e2</td><td>1.00e-7</td></tr><tr><td rowspan="6">Birkhoff</td><td colspan="18">n</td></tr><tr><td>10000</td><td>3.60e3*</td><td>1.73e3</td><td>5.27e-7</td><td>4.09e2</td><td>2.01e2</td><td>1.22e-7</td><td>3.43e2</td><td>2.13e2</td><td>1.00e-7</td><td>3.09e1</td><td>1.49e1</td><td>1.00e-7</td><td>7.41e2</td><td>2.19e2</td><td>1.00e-7</td></tr><tr><td>62500</td><td>3.60e3*</td><td>1.69e3</td><td>1.53e-6</td><td>2.30e3</td><td>7.11e2</td><td>1.16e-7</td><td>2.80e3</td><td>1.22e3</td><td>1.00e-7</td><td>1.99e2</td><td>8.18e1</td><td>1.26e-7</td><td>3.60e3*</td><td>1.42e3</td><td>2.53e-7</td></tr><tr><td>160000</td><td>3.60e3*</td><td>1.57e3</td><td>2.90e-6</td><td>3.60e3*</td><td>1.09e3</td><td>1.39e-7</td><td>3.60e3*</td><td>1.62e3</td><td>1.69e-7</td><td>6.51e2</td><td>2.19e2</td><td>1.00e-7</td><td>3.60e3*</td><td>1.67e3</td><td>4.49e-7</td></tr><tr><td>422500</td><td>3.60e3*</td><td>1.58e3</td><td>2.19e-6</td><td>3.60e3*</td><td>9.81e2</td><td>3.05e-7</td><td>3.60e3*</td><td>1.60e3</td><td>3.70e-7</td><td>2.58e3</td><td>6.22e2</td><td>1.00e-7</td><td>3.60e3*</td><td>1.68e3</td><td>7.11e-7</td></tr><tr><td>640000</td><td>3.60e3*</td><td>1.57e3</td><td>3.84e-6</td><td>3.60e3*</td><td>8.06e2</td><td>3.98e-7</td><td>3.60e3*</td><td>1.53e3</td><td>4.80e-7</td><td>1.90e3</td><td>3.59e2</td><td>1.86e-7</td><td>3.60e3*</td><td>1.43e3</td><td>8.52e-7</td></tr><tr><td>1000000</td><td>3.60e3*</td><td>1.52e3</td><td>2.48e-6</td><td>3.60e3*</td><td>8.40e2</td><td>5.55e-7</td><td>3.60e3*</td><td>1.18e3</td><td>6.57e-7</td><td>3.51e3</td><td>5.64e2</td><td>1.51e-7</td><td>3.60e3*</td><td>1.25e3</td><td>9.54e-7</td></tr><tr><td rowspan="6">D-Criterion</td><td colspan="18">n</td></tr><tr><td>100</td><td>3.56e3</td><td>6.22e3</td><td>1.45e-7</td><td>3.03e-1</td><td>5.51e-1</td><td>1.06e-7</td><td>2.06e-1</td><td>3.41e-1</td><td>1.00e-7</td><td>3.62e-1</td><td>1.77e-1</td><td>1.38e-7</td><td>1.86e-1</td><td>4.41e-1</td><td>1.00e-7</td></tr><tr><td>250</td><td>3.60e3*</td><td>1.97e3</td><td>1.34e-5</td><td>4.49e1</td><td>1.13e1</td><td>1.05e-7</td><td>1.73e1</td><td>6.30</td><td>1.00e-7</td><td>7.00</td><td>2.14</td><td>1.11e-7</td><td>2.37e1</td><td>7.37</td><td>1.00e-7</td></tr><tr><td>400</td><td>3.60e3*</td><td>1.87e3</td><td>8.52e-5</td><td>1.34e2</td><td>6.37e1</td><td>1.00e-7</td><td>6.84e1</td><td>3.50e1</td><td>1.00e-7</td><td>2.27e1</td><td>1.04e1</td><td>1.01e-7</td><td>8.56e1</td><td>4.10e1</td><td>1.00e-7</td></tr><tr><td>550</td><td>3.60e3*</td><td>2.04e3</td><td>3.11e-4</td><td>3.19e2</td><td>1.93e2</td><td>1.02e-7</td><td>1.48e2</td><td>1.08e2</td><td>1.00e-7</td><td>4.14e1</td><td>3.25e1</td><td>1.43e-7</td><td>2.17e2</td><td>1.22e2</td><td>1.00e-7</td></tr><tr><td>700</td><td>3.60e3*</td><td>2.28e3</td><td>1.04e-3</td><td>8.04e2</td><td>4.59e2</td><td>1.02e-7</td><td>4.01e2</td><td>2.66e2</td><td>1.00e-7</td><td>1.11e-7</td><td>8.06e1</td><td>1.18e-7</td><td>4.54e2</td><td>2.96e2</td><td>1.00e-7</td></tr><tr><td>850</td><td>3.60e3*</td><td>2.80e3</td><td>1.19e-3</td><td>1.55e3</td><td>9.56e2</td><td>1.01e-7</td><td>6.80e2</td><td>5.58e2</td><td>1.00e-7</td><td>1.89e2</td><td>1.65e2</td><td>1.14e-7</td><td>8.90e2</td><td>6.16e2</td><td>1.00e-7</td></tr><tr><td rowspan="6">Nuclear</td><td colspan="18">n</td></tr><tr><td>10000</td><td>1.07e2</td><td>1.91e-1</td><td>1.00e-7</td><td>3.60e3*</td><td>9.21e-1</td><td>1.80e-3</td><td>3.60e3*</td><td>1.77</td><td>1.44e-3</td><td>3.60e3*</td><td>1.41e4</td><td>1.64e-2</td><td>1.36e1</td><td>4.11e-1</td><td>1.00e-7</td></tr><tr><td>62500</td><td>3.60e3*</td><td>8.77e-1</td><td>5.64e-6</td><td>3.60e3*</td><td>4.24e-1</td><td>2.59</td><td>3.60e3*</td><td>1.16</td><td>4.11</td><td>3.60e3*</td><td>1.11e4</td><td>4.96e-5</td><td>3.60e3*</td><td>3.30e-1</td><td>1.79e-1</td></tr><tr><td>160000</td><td>3.60e3*</td><td>1.08</td><td>1.24e-4</td><td>3.60e3*</td><td>8.19e-1</td><td>1.58e2</td><td>3.60e3*</td><td>1.04</td><td>5.93e3</td><td>3.60e3*</td><td>7.67e3</td><td>7.76e8</td><td>3.60e3*</td><td>6.28e-1</td><td>2.78</td></tr><tr><td>302500</td><td>3.60e3*</td><td>1.03</td><td>1.18e1</td><td>3.60e3*</td><td>9.80e-1</td><td>2.84e3</td><td>3.60e3*</td><td>7.78e-1</td><td>4.39e6</td><td>3.60e3*</td><td>7.26e3</td><td>1.19e10</td><td>3.60e3*</td><td>8.86e-1</td><td>2.74e3</td></tr><tr><td>490000</td><td>3.60e3*</td><td>1.03</td><td>1.35e-5</td><td>3.60e3*</td><td>1.06</td><td>2.52e6</td><td>3.60e3*</td><td>7.33e-1</td><td>3.96e8</td><td>3.60e3*</td><td>5.63e3</td><td>8.63e10</td><td>3.60e3*</td><td>9.13e-1</td><td>3.92e6</td></tr><tr><td>722500</td><td>3.60e3*</td><td>1.05</td><td>2.18e7</td><td>3.60e3*</td><td>1.10</td><td>7.63e7</td><td>3.60e3*</td><td>7.68e-1</td><td>2.14e9</td><td>3.60e3*</td><td>6.23e3</td><td>2.15e11</td><td>3.60e3*</td><td>9.49e-1</td><td>1.39e8</td></tr><tr><td rowspan="6">Poisson</td><td colspan="18">n</td></tr><tr><td>100</td><td>3.60e3*</td><td>4.55e-3</td><td>1.74e-5</td><td>4.23</td><td>2.10</td><td>1.00e-7</td><td>2.92</td><td>1.72</td><td>1.00e-7</td><td>7.93e-1</td><td>9.38e-1</td><td>1.00e-7</td><td>2.88</td><td>2.16</td><td>1.00e-7</td></tr><tr><td>250</td><td>3.60e3*</td><td>3.22e3</td><td>1.59e-3</td><td>1.00e2</td><td>5.42e1</td><td>1.00e-7</td><td>3.23e1</td><td>3.54e1</td><td>1.00e-7</td><td>1.05e1</td><td>1.01e1</td><td>1.34e-7</td><td>4.57e-1</td><td>3.52e-1</td><td>1.00e-7</td></tr><tr><td>400</td><td>3.60e3*</td><td>2.05e3</td><td>1.60e-2</td><td>6.41e2</td><td>2.87e2</td><td>1.00e-7</td><td>2.88e2</td><td>1.89e2</td><td>1.00e-7</td><td>1.20e2</td><td>7.23e1</td><td>1.12e-7</td><td>3.07e2</td><td>2.06e2</td><td>1.00e-7</td></tr><tr><td>650</td><td>3.60e3*</td><td>1.62e3</td><td>8.78e-2</td><td>3.49e3</td><td>1.69e3</td><td>2.27e-6</td><td>1.78e3</td><td>9.78e2</td><td>1.00e-7</td><td>9.47e2</td><td>4.74e2</td><td>1.00e-7</td><td>1.86e3</td><td>1.02e3</td><td>1.00e-7</td></tr><tr><td>800</td><td>3.60e3*</td><td>1.43e3</td><td>1.64e-1</td><td>3.60e3*</td><td>1.48e3</td><td>7.59e-2</td><td>3.60e3*</td><td>1.44e3</td><td>3.11e-3</td><td>3.25e3</td><td>1.40e3</td><td>4.24e-5</td><td>3.60e3*</td><td>1.43e3</td><td>4.95e-2</td></tr><tr><td>1000</td><td>3.60e3*</td><td>1.31e3</td><td>4.20e-1</td><td>3.60e3*</td><td>1.34e3</td><td>1.09e-1</td><td>3.60e3*</td><td>1.35e3</td><td>9.57e-2</td><td>3.60e3*</td><td>1.52e3</td><td>8.79e-1</td><td>3.60e3*</td><td>1.33e3</td><td>1.89e-1</td></tr><tr><td rowspan="6">Simplex</td><td colspan="18">m, n</td></tr><tr><td>5000, 2500</td><td>3.53e3</td><td>7.20e2</td><td>1.55e-6</td><td>3.18</td><td>8.14e-1</td><td>1.00e-7</td><td>3.55</td><td>4.98e-1</td><td>1.00e-7</td><td>8.53e-1</td><td>1.49e-1</td><td>1.07e-7</td><td>3.77</td><td>4.92e-1</td><td>1.00e-7</td></tr><tr><td>5000, 6000</td><td>3.60e3*</td><td>2.57e2</td><td>7.17e-6</td><td>1.70e1</td><td>1.23</td><td>1.00e-7</td><td>1.66e1</td><td>7.59e-1</td><td>1.00e-7</td><td>2.56</td><td>2.33e-1</td><td>1.00e-7</td><td>1.36e1</td><td>7.90e-1</td><td>1.00e-7</td></tr><tr><td>7000, 3500</td><td>3.60e3*</td><td>4.48e2</td><td>3.60e-6</td><td>1.69e1</td><td>1.27</td><td>1.00e-7</td><td>8.18</td><td>7.86e-1</td><td>1.00e-7</td><td>1.30</td><td>2.35e-1</td><td>1.00e-7</td><td>9.49</td><td>7.84e-1</td><td>1.00e-7</td></tr><tr><td>7000, 8500</td><td>3.60e3*</td><td>4.64e-2</td><td>1.00e-5</td><td>2.86e1</td><td>3.90</td><td>1.00e-7</td><td>2.44e-1</td><td>2.34</td><td>1.00e-7</td><td>3.84</td><td>6.56e-1</td><td>1.14e-7</td><td>4.79e1</td><td>2.34</td><td>1.00e-7</td></tr><tr><td>10000, 5000</td><td>3.60e3*</td><td>2.02e2</td><td>5.09e-6</td><td>3.05e1</td><td>1.21</td><td>1.00e-7</td><td>1.27e1</td><td>7.57e-1</td><td>1.00e-7</td><td>2.77</td><td>2.64e-1</td><td>1.12e-7</td><td>1.68e1</td><td>7.64e-1</td><td>1.00e-7</td></tr><tr><td>10000, 12000</td><td>3.60e3*</td><td>1.80e2</td><td>2.26e-5</td><td>8.07e1</td><td>3.42</td><td>1.00e-7</td><td>4.68e1</td><td>2.07</td><td>1.00e-7</td><td>9.93</td><td>6.58e-1</td><td>1.21e-7</td><td>6.06e1</td><td>2.16</td><td>1.00e-7</td></tr><tr><td>20000, 10000</td><td>3.60e3*</td><td>1.33e2</td><td>2.05e-5</td><td>7.61e1</td><td>3.33</td><td>1.00e-7</td><td>7.45e-1</td><td>2.10</td><td>1.00e-7</td><td>1.29e1</td><td>7.61e-1</td><td>1.13e-7</td><td>8.22e1</td><td>2.10</td><td>1.00e-7</td></tr><tr><td>20000, 24000</td><td>3.60e3*</td><td>9.86e1</td><td>5.72e-5</td><td>2.06e2</td><td>7.62</td><td>1.00e-7</td><td>1.29e2</td><td>4.76</td><td>1.00e-7</td><td>2.94e1</td><td>1.60</td><td>1.00e-7</td><td>2.28e2</td><td>4.98</td><td>1.00e-7</td></tr><tr><td rowspan="6">Sparse</td><td colspan="18">n</td></tr><tr><td>10000</td><td>1.83</td><td>6.45</td><td>1.07e-7</td><td>1.40e1</td><td>7.48</td><td>1.00e-7</td><td>3.51</td><td>1.15e1</td><td>1.00e-7</td><td>9.06</td><td>1.21e-1</td><td>1.00e-7</td><td>5.82</td><td>1.16e1</td><td>1.00e-7</td></tr><tr><td>40000</td><td>2.63e1</td><td>9.34e1</td><td>1.00e-7</td><td>5.66e1</td><td>1.73e2</td><td>1.00e-7</td><td>5.14e1</td><td>1.44e2</td><td>1.00e-7</td><td>1.11e2</td><td>1.68e2</td><td>1.35e-7</td><td>1.16e2</td><td>1.30e2</td><td>1.00e-7</td></tr><tr><td>80000</td><td>1.31e2</td><td>4.61e-2</td><td>1.00e-7</td><td>9.23e2</td><td>3.92e2</td><td>1.42e-7</td><td>2.01e2</td><td>5.38e2</td><td>1.00e-7</td><td>3.60e3*</td><td>1.11e4</td><td>5.44e-7</td><td>1.30e3</td><td>5.94e2</td><td>1.63e-7</td></tr><tr><td>140000</td><td>1.98e2</td><td>7.27e2</td><td>1.00e-7</td><td>1.92e2</td><td>1.03e3</td><td>1.00e-7</td><td>7.40e2</td><td>2.03e3</td><td>1.00e-7</td><td>3.60e3*</td><td>1.12e4</td><td>6.34e-7</td><td>5.44e-2</td><td>2.37e3</td><td>1.86e-7</td></tr><tr><td>200000</td><td>1.10e3</td><td>3.57e3</td><td>1.00e-7</td><td>3.60e3*</td><td>3.52e3</td><td>1.78e-6</td><td>3.60e3*</td><td>7.75e3</td><td>4.46e-5</td><td>3.60e3*</td><td>1.14e4</td><td>4.25e-6</td><td>3.60e3*</td><td>7.09e3</td><td>4.16e-5</td></tr><tr><td>350000</td><td>3.57e3</td><td>1.14e4</td><td>4.50e-7</td><td>3.60e3*</td><td>8.40e3</td><td>1.58e-5</td><td>3.60e3*</td><td>9.71e3</td><td>1.51e-3</td><td>3.60e3*</td><td>9.48e3</td><td>6.90e-6</td><td>3.60e3*</td><td>9.67e3</td><td>4.92e-4</td></tr><tr><td>500000</td><td>3.60e3*</td><td>1.16e4</td><td>5.71e-4</td><td>3.60e3*</td><td>1.00e4</td><td>4.63e-3</td><td>3.60e3*</td><td>9.81e3</td><td>1.92e-2</td><td>3.60e3*</td><td>9.68e3</td><td>4.01e-4</td><td>3.60e3*</td><td>9.92e3</td><td>2.36e-4</td></tr><tr><td rowspan="6">Spectrahedron</td><td colspan="18">n</td></tr><tr><td>10000</td><td>2.46e-2</td><td>2.32e-3</td><td>1.38e-7</td><td>1.52e-2</td><td>2.60e-3</td><td>1.17e-7</td><td>1.53e-2</td><td>2.44e-3</td><td>1.00e-7</td><td>1.55e-2</td><td>2.33e-2</td><td>1.19e-7</td><td>2.17e-2</td><td>2.31e-3</td><td>1.00e-7</td></tr><tr><td>62500</td><td>5.71e-2</td><td>1.07e-2</td><td>1.00e-7</td><td>6.81e-2</td><td>1.10e-2</td><td>1.00e-7</td><td>8.42e-2</td><td>1.09e-2</td><td>1.00e-7</td><td>1.04e-1</td><td>4.24e-2</td><td>1.42e-7</td><td>5.81e-2</td><td>1.09e-2</td><td>1.00e-7</td></tr><tr><td>250000</td><td>1.20e1</td><td>4.80e-2</td><td>1.05e-7</td><td>3.27e1</td><td>8.96e-2</td><td>1.67e-7</td><td>7.83e1</td><td>8.06e-2</td><td>1.00e-7</td><td>1.63e1</td><td>6.33</td><td>1.24e-7</td><td>2.29e1</td><td>4.50e-2</td><td>1.00e-7</td></tr><tr><td>490000</td><td>1.46e1</td><td>8.63e-2</td><td>2.35e-7</td><td>4.55e1</td><td>1.37e-1</td><td>1.24e-7</td><td>2.19e2</td><td>8.74e-2</td><td>1.00e-7</td><td>2.46e-1</td><td>1.08e1</td><td>1.10e-7</td><td>3.18e1</td><td>8.56e-2</td><td>1.00e-7</td></tr><tr><td>722500</td><td>1.33e3</td><td>1.44e-1</td><td>2.58e-7</td><td>3.52e3</td><td>5.48e-1</td><td>4.90e-7</td><td>3.12e3</td><td>4.13e-1</td><td>4.29e-7</td><td>2.71e2</td><td>4.70e2</td><td>1.31e-7</td><td>1.70e3</td><td>1.41e-1</td><td>1.02e-7</td></tr><tr><td>1000000</td><td>3.35e3</td><td>2.01e-1</td><td>3.00e-7</td><td>3.60e3*</td><td>8.39e-1</td><td>7.86e-7</td><td>3.60e3*</td><td>3.37e-1</td><td>6.88e-7</td><td>5.81e2</td><td>9.73e2</td><td>1.45e-7</td><td>2.94e3</td><td>2.07e-1</td><td>1.94e-7</td></tr></tbody></table>
<table><caption>Table 10: Performance comparison of the active set variants with ActiveSetQuadraticProductCaching. Entries marked with * timed out.</caption><thead><tr><th rowspan="2">Problem</th><th rowspan="2">Dim</th><th colspan="3">Away</th><th colspan="3">PCG</th><th colspan="3">BCG</th><th colspan="3">BPCG</th></tr><tr><th>Time (s)</th><th>Average memory (GB)</th><th>Dual gap</th><th>Time (s)</th><th>Average memory (GB)</th><th>Dual gap</th><th>Time (s)</th><th>Average memory (GB)</th><th>Dual gap</th><th>Time (s)</th><th>Average memory (GB)</th><th>Dual gap</th></tr></thead><tbody><tr><td rowspan="6">Birkhoff</td><td colspan="15">n</td></tr><tr><td>10000</td><td>2.05e2</td><td>9.96e1</td><td>1.22e-7</td><td>1.86e2</td><td>1.20e2</td><td>1.00e-7</td><td>2.48e1</td><td>3.44e1</td><td>1.00e-7</td><td>3.14e2</td><td>1.45e2</td><td>1.00e-7</td></tr><tr><td>62500</td><td>2.24e3</td><td>3.46e2</td><td>1.16e-7</td><td>2.35e3</td><td>5.74e2</td><td>1.00e-7</td><td>2.33e2</td><td>1.79e2</td><td>1.26e-7</td><td>3.60e3*</td><td>6.46e2</td><td>2.10e-7</td></tr><tr><td>160000</td><td>3.56e3</td><td>4.58e2</td><td>1.14e-7</td><td>3.60e3*</td><td>7.13e2</td><td>1.41e-7</td><td>6.75e2</td><td>5.32e2</td><td>1.00e-7</td><td>3.60e3*</td><td>5.21e2</td><td>3.55e-7</td></tr><tr><td>422500</td><td>3.60e3*</td><td>3.23e2</td><td>2.40e-7</td><td>3.60e3*</td><td>5.19e2</td><td>3.06e-7</td><td>2.23e3</td><td>1.13e3</td><td>1.00e-7</td><td>3.60e3*</td><td>3.93e2</td><td>5.69e-7</td></tr><tr><td>640000</td><td>3.60e3*</td><td>3.03e2</td><td>3.46e-7</td><td>3.60e3*</td><td>5.01e2</td><td>3.77e-7</td><td>1.35e3</td><td>3.37e2</td><td>1.86e-7</td><td>3.60e3*</td><td>3.71e2</td><td>6.50e-7</td></tr><tr><td>1000000</td><td>3.60e3*</td><td>3.01e2</td><td>4.17e-7</td><td>3.60e3*</td><td>4.99e2</td><td>5.11e-7</td><td>2.46e3</td><td>4.65e2</td><td>1.50e-7</td><td>3.60e3*</td><td>3.51e2</td><td>7.32e-7</td></tr><tr><td rowspan="6">Nuclear</td><td colspan="15">n</td></tr><tr><td>10000</td><td>3.60e3*</td><td>2.89e1</td><td>2.04e-4</td><td>3.60e3*</td><td>3.38e1</td><td>1.36e-3</td><td>3.60e3*</td><td>1.35e4</td><td>1.64e-2</td><td>3.60e3*</td><td>8.86e1</td><td>7.14e-7</td></tr><tr><td>62500</td><td>3.60e3*</td><td>2.29</td><td>2.78</td><td>3.60e3*</td><td>2.54</td><td>3.20</td><td>3.60e3*</td><td>1.14e4</td><td>3.16e5</td><td>3.60e3*</td><td>4.80</td><td>2.24e-4</td></tr><tr><td>160000</td><td>3.60e3*</td><td>2.48</td><td>1.28e2</td><td>3.60e3*</td><td>2.22</td><td>3.44e2</td><td>3.60e3*</td><td>7.72e3</td><td>4.94e8</td><td>3.60e3*</td><td>3.41</td><td>6.13e-1</td></tr><tr><td>302500</td><td>3.60e3*</td><td>1.48</td><td>2.96e3</td><td>3.60e3*</td><td>1.52</td><td>3.68e6</td><td>3.60e3*</td><td>7.31e3</td><td>1.19e10</td><td>3.60e3*</td><td>2.64</td><td>8.57e1</td></tr><tr><td>490000</td><td>3.60e3*</td><td>1.47</td><td>1.46e6</td><td>3.60e3*</td><td>1.52</td><td>3.43e8</td><td>3.60e3*</td><td>5.77e3</td><td>8.21e10</td><td>3.60e3*</td><td>2.64</td><td>5.93e5</td></tr><tr><td>722500</td><td>3.60e3*</td><td>1.47</td><td>7.52e7</td><td>3.60e3*</td><td>1.49</td><td>1.98e9</td><td>3.60e3*</td><td>6.02e3</td><td>2.15e11</td><td>3.60e3*</td><td>2.57</td><td>5.80e7</td></tr><tr><td rowspan="6">Simplex</td><td colspan="15">m, n</td></tr><tr><td>5000, 2500</td><td>9.60</td><td>1.80</td><td>1.00e-7</td><td>5.56</td><td>1.32</td><td>1.00e-7</td><td>1.09</td><td>2.84e-1</td><td>1.07e-7</td><td>4.72</td><td>1.32</td><td>1.01e-7</td></tr><tr><td>5000, 6000</td><td>5.71e1</td><td>4.54</td><td>1.00e-7</td><td>3.46e1</td><td>3.47</td><td>1.00e-7</td><td>6.81</td><td>4.37e-1</td><td>1.00e-7</td><td>3.31e1</td><td>3.47</td><td>1.00e-7</td></tr><tr><td>7000, 3500</td><td>2.30e1</td><td>2.94</td><td>1.00e-7</td><td>1.55e1</td><td>2.21</td><td>1.00e-7</td><td>3.17</td><td>4.99e-1</td><td>1.00e-7</td><td>1.59e1</td><td>2.21</td><td>1.00e-7</td></tr><tr><td>7000, 8500</td><td>9.10e1</td><td>7.33</td><td>1.00e-7</td><td>5.82e1</td><td>5.48</td><td>1.00e-7</td><td>1.52e1</td><td>6.83e-1</td><td>1.14e-7</td><td>6.07e1</td><td>5.46</td><td>1.00e-7</td></tr><tr><td>10000, 5000</td><td>4.45e1</td><td>4.71</td><td>1.00e-7</td><td>3.39e1</td><td>3.55</td><td>1.00e-7</td><td>7.56</td><td>8.17e-1</td><td>1.12e-7</td><td>3.17e1</td><td>3.50</td><td>1.00e-7</td></tr><tr><td>10000, 12000</td><td>2.31e2</td><td>1.22e1</td><td>1.00e-7</td><td>1.36e2</td><td>9.38</td><td>1.00e-7</td><td>3.84e1</td><td>1.27</td><td>1.21e-7</td><td>1.52e2</td><td>9.40</td><td>1.00e-7</td></tr><tr><td>20000, 10000</td><td>1.79e2</td><td>1.29e1</td><td>1.00e-7</td><td>1.17e2</td><td>9.84</td><td>1.00e-7</td><td>3.51e1</td><td>2.47</td><td>1.13e-7</td><td>1.16e2</td><td>9.49</td><td>1.00e-7</td></tr><tr><td>20000, 24000</td><td>8.94e2</td><td>3.28e1</td><td>1.00e-7</td><td>5.79e2</td><td>2.52e1</td><td>1.00e-7</td><td>1.73e2</td><td>3.70</td><td>1.00e-7</td><td>6.71e2</td><td>2.48e1</td><td>1.00e-7</td></tr><tr><td rowspan="6">Sparse</td><td colspan="15">n</td></tr><tr><td>10000</td><td>1.76e1</td><td>4.82e1</td><td>1.00e-7</td><td>3.33</td><td>1.10e1</td><td>1.00e-7</td><td>3.41</td><td>9.60</td><td>1.00e-7</td><td>6.64</td><td>2.07e1</td><td>1.02e-7</td></tr><tr><td>40000</td><td>6.82e1</td><td>2.00e2</td><td>1.16e-7</td><td>5.89e1</td><td>1.75e2</td><td>1.82e-7</td><td>1.18e2</td><td>3.22e2</td><td>1.27e-7</td><td>1.39e2</td><td>3.93e2</td><td>1.03e-7</td></tr><tr><td>80000</td><td>9.89e2</td><td>3.04e3</td><td>2.23e-6</td><td>2.31e2</td><td>7.43e2</td><td>2.25e-6</td><td>3.60e3*</td><td>1.15e4</td><td>7.43e-7</td><td>1.36e3</td><td>4.15e3</td><td>8.99e-7</td></tr><tr><td>140000</td><td>2.31e2</td><td>7.56e2</td><td>1.43e-6</td><td>7.59e2</td><td>2.28e3</td><td>4.28e-6</td><td>3.60e3*</td><td>1.12e4</td><td>1.11e-6</td><td>6.14e2</td><td>1.93e3</td><td>1.08e-6</td></tr><tr><td>200000</td><td>3.60e3*</td><td>1.16e4</td><td>1.68e-5</td><td>3.60e3*</td><td>1.09e4</td><td>5.02e-5</td><td>3.60e3*</td><td>1.14e4</td><td>5.85e-6</td><td>3.60e3*</td><td>1.11e4</td><td>4.76e-5</td></tr><tr><td>350000</td><td>3.60e3*</td><td>9.81e3</td><td>2.88e-5</td><td>3.60e3*</td><td>9.66e3</td><td>2.12e-3</td><td>3.60e3*</td><td>9.84e3</td><td>1.07e-5</td><td>3.60e3*</td><td>9.95e3</td><td>6.46e-4</td></tr><tr><td>500000</td><td>3.60e3*</td><td>9.94e3</td><td>6.42e-3</td><td>3.60e3*</td><td>9.36e3</td><td>2.99e-2</td><td>3.60e3*</td><td>9.69e3</td><td>8.31e-4</td><td>3.60e3*</td><td>1.01e4</td><td>3.22e-4</td></tr><tr><td rowspan="6">Spectrahedron</td><td colspan="15">n</td></tr><tr><td>10000</td><td>1.74e-2</td><td>2.85e-3</td><td>1.17e-7</td><td>4.26e1</td><td>2.91e1</td><td>7.73e-7</td><td>1.91e-2</td><td>2.28e-2</td><td>1.19e-7</td><td>2.60e-2</td><td>3.51e-3</td><td>1.25e-7</td></tr><tr><td>62500</td><td>4.41e-2</td><td>1.08e-2</td><td>1.00e-7</td><td>4.31</td><td>1.16</td><td>1.56e-7</td><td>7.73e-2</td><td>4.24e-2</td><td>1.42e-7</td><td>3.09e-2</td><td>1.06e-2</td><td>1.00e-7</td></tr><tr><td>250000</td><td>2.17e1</td><td>2.27e-1</td><td>1.67e-7</td><td>3.60e3*</td><td>2.12e1</td><td>5.99e-6</td><td>7.24</td><td>5.13</td><td>1.29e-7</td><td>1.12e1</td><td>1.87e-1</td><td>1.78e-7</td></tr><tr><td>490000</td><td>2.12e1</td><td>3.31e-1</td><td>1.24e-7</td><td>3.60e3*</td><td>1.31e1</td><td>7.10e-6</td><td>1.70e1</td><td>9.83</td><td>1.09e-7</td><td>1.58e1</td><td>3.17e-1</td><td>1.17e-7</td></tr><tr><td>722500</td><td>3.12e3</td><td>2.50</td><td>4.45e-7</td><td>3.60e3*</td><td>1.08e1</td><td>3.05e-5</td><td>2.07e2</td><td>9.30e2</td><td>1.29e-7</td><td>9.07e2</td><td>7.88</td><td>1.77e-7</td></tr><tr><td>1000000</td><td>3.60e3*</td><td>2.71</td><td>6.59e-7</td><td>3.60e3*</td><td>1.21e1</td><td>3.38e-5</td><td>3.43e2</td><td>7.71e2</td><td>1.45e-7</td><td>1.83e3</td><td>1.42e1</td><td>1.54e-7</td></tr></tbody></table>