# Solving the Optimal Experiment Design Problem with Mixed-Integer Convex Methods

Deborah Hendrych, Mathieu Besançon, Sebastian Pokutta

► To cite this version:

Deborah Hendrych, Mathieu Besançon, Sebastian Pokutta. Solving the Optimal Experiment Design Problem with Mixed-Integer Convex Methods. 22nd International Symposium on Experimental Algorithms (SEA 2024), Jul 2024, Vienne, Austria. pp.16:1–16:22, 10.4230/LIPIcs.SEA.2024.16 . hal-04431320

HAL Id: hal-04431320

https://hal.science/hal-04431320v1

Submitted on 8 Jul 2025

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Solving Optimal Experiment Design with Mixed-Integer Convex Methods

Deborah Hendrych

Technische Universität Berlin, Germany
Zuse Institute Berlin, Germany

HENDRYCH@ZIB.DE

Mathieu Besançon

Université Grenoble Alpes, Inria, Grenoble, France
Zuse Institute Berlin, Germany

MATHIEU.BESANCON@INRIA.FR

Sebastian Pokutta

Technische Universität Berlin, Germany
Zuse Institute Berlin, Germany

POKUTTA@ZIB.DE

## Abstract

We tackle the Optimal Experiment Design Problem, which consists of choosing experiments to run or observations to select from a finite set to estimate the parameters of a system. The objective is to maximize some measure of information gained about the system from the observations, leading to a convex integer optimization problem. We leverage Boscia.jl, a recent algorithmic framework, which is based on a non-linear branch-and-bound algorithm with node relaxations solved to approximate optimality using Frank-Wolfe algorithms. One particular advantage of the method is its efficient utilization of the polytope formed by the original constraints which is preserved by the method, unlike alternative methods relying on epigraph-based formulations. We assess the method against both generic and specialized convex mixed-integer approaches. Computational results highlight the performance of the proposed method, especially on large and challenging instances.

## 1. Introduction

The Optimal Experiment Design Problem (OEDP) arises in statistical estimation and empirical studies in many applications areas from Engineering to Chemistry. For OEDP, we assume we have a matrix A consisting of the rows $v_1, \dots, v_m \in \mathbb{R}^n$ where each row represents an experiment. The ultimate aim is to fit a regression model:

$$ \min_{\theta \in \mathbb{R}^m} \|A\theta - y\|, \quad (1) $$

where y encodes the responses of the experiments and $\theta$ are the parameters to be estimated. The set of parameters with size n is assumed to be (significantly) smaller than the number of distinct experiments m. Furthermore, we assume that A has full column rank, i.e. the vectors $v_1, \dots, v_m$ span $\mathbb{R}^n$.

The problem is running all experiments, potentially even multiple times to account for errors, is often not realistic because of time and cost constraints. Thus, OEDP deals with finding a subset of size N of the experiments providing the “most information” about the experiment space (Pukelsheim, 2006; de Aguiar et al., 1995). In general, the number of allowed experiments N is in the interval $[n, m]$ in order to allow a solution to the regression model in Equation (1).

In Section 2, we investigate the necessary conditions for a function to be a valid and useful information measure. Every information function leads to a different criterion. In this paper, we focus on two popular criteria, namely the A-criterion and D-criterion, see Section 2.1.

In general, OEDP leads to a Mixed-Integer Non-Linear Problem (MINLP). There has been a lot of development in the last years in solving MINLP (Kronqvist et al., 2019). Nevertheless, the capabilities of current MINLP solvers are far away from their linear counterparts, the Mixed-Integer Problem (MIP) solvers (Bestuzheva et al., 2021), especially concerning the magnitude of the problems that can be handled. Therefore, instead of solving the actual MINLP formulation, a continuous version of OEDP, called the Limit Problem, is
often solved and the integer solution is created from the continuous solution by rounding schemes and other heuristics (Pukelsheim, 2006). This does not necessarily lead to optimal solutions, though, and the procedure is not always applicable to a given continuous solution either because it requires a certain sparsity of the continuous solution.

The goal of this paper is to compare the performance of different MINLP approaches for OEDP problems. A special focus is put on the newly proposed framework Boscia (Hendrych et al., 2025b) which can solve larger instances and significantly outperforms the other examined approaches. The new method leverages Frank-Wolfe algorithms and a formulation different from the other approaches. In Section 3, we establish the convergence of the Frank-Wolfe algorithm on the continuous relaxations of the considered OEDP problems. The different solution methods are detailed in Section 4 and evaluation of the computational experiments can be found in Section 5.

**1.1 Related work**

As mentioned, one established method of solution is the reduction to a simpler problem by removing the integer constraints and employing heuristics to generate an integer solution from the continuous solution. Recently, there have been more publications tackling the MINLP formulation of the Optimal Experiment Design Problem. These, however, concentrate on specific information measures, in particular the A-criterion, see (Nikolov et al., 2022; Ahipaşaoğlu, 2015), and the D-criterion, (Welch, 1982; Ponte et al., 2025; Li et al., 2024; Xu & Liberti, 2024; Ponte et al., 2023; Fampa & Lee, 2022; Chen et al., 2024; Ponte et al., 2024). The most general solution approach known to the authors was introduced in Ahipaşaoğlu (2021). It considers OEDP under matrix means which, in particular, includes the A-criterion and D-criterion. While the matrix means covers many information measures of interest, it still yields a restricting class of information functions. For example, the G-criterion and V-criterion are not included in this class of functions (de Aguiar et al., 1995). The newly proposed framework Boscia only requires the information measures to be either L-smooth, i.e. the gradient is Lipschitz continuous, or generalized self-concordant, thereby covering a larger group of information functions. In addition, Boscia does not suppose any prior knowledge about the structure of the problem, being thus more flexible in terms of problem formulations. On the other hand, it is highly customizable, giving the user the ability to exploit the properties of their problems to speed up the solving process. An in-depth and unified theory for the Optimal Experiment Design Problem can be found in Pukelsheim (2006).

**1.2 Contribution**

Our contribution can be summarized as follows

**Unified view on experiment design formulations.** First, we propose a unified view of multiple experiment design formulations as the optimization of a nonlinear (not necessarily Lipschitz-smooth) information function over a truncated scaled probability simplex intersected with the set of integers. Unlike most other formulations that replace the nonlinear objective with nonlinear and/or conic constraints, we preserve the original structure of the problem. Additionally, we can easily handle special cases of OEDP without any reformulations and additional constraints on OEDP since we do not suppose a specific problem structure, unlike the approach in Ahipaşaoğlu (2021).

**Convergence analysis for BPCG.** Second, we establish convergence guarantees for Frank-Wolfe algorithms on continuous relaxations of these problems by exploiting smoothness or self-concordance, and sharpness. This is necessary in order to solve the various experimental design problems with Boscia.

**Superior solution via Boscia framework.** Finally, we use the recently proposed Boscia (Hendrych et al., 2025b) framework to solve the integer optimization problem with a Frank-Wolfe method for the node relaxations of the Branch-and-Bound tree and show the effectiveness of the method on instances generated with various degrees of correlation between the parameters.

**1.3 Notation**

In the following let $\lambda_i(A)$ denote the i-th eigenvalue of matrix A; we assume that these are sorted in increasing order. Moreover, $\lambda_{\min}(A)$ and $\lambda_{\max}(A)$ denote the minimum and maximum eigenvalue of A, respectively. We
define and denote the condition number of a positive semi-definite matrix A as $κ(A) = \frac{λ_{max}(A)}{λ_{min}(A)}$. Further, let $log det(·)$ be the log-determinant of a positive definite matrix. Given matrices A and B of same dimensions, A ◦ B denotes their Hadamard product. Given a vector x, diag(x) denotes the diagonal matrix with x on its diagonal and let Diag(A) denote the diagonal of the matrix A. The cones of positive definite and positive semi-definite matrices in $ℝ^{n×n}$ will be denoted by $S_+^n$ and $S_+^n$, respectively. We will refer to them as PD and PSD cones. The set of symmetric $n × n$ matrices will be denoted by $S^n$. Let $ℝ_0$ denote the set of positive integers including 0 and for $m ∈ ℝ$ let $[m] = \{1, 2, ..., m\}$. Lastly, we denote matrices with capital letters, e.g. X, vectors with bold small letters, e.g. x, and simple small letters are scalars, e.g. λ.

## 2. The optimal experiment design problem

As stated in the introduction, OEDP aims to pick the subset of predefined size N yielding the most information about the system. So first, we have to answer the question of how to quantify information. To that end, we introduce the information matrix

$$X(\mathbf{x}) = \sum_{i=1}^{m} x_i \mathbf{v}_i \mathbf{v}_i^{\top} = A^{\top} \mathrm{diag}(\mathbf{x}) A \quad (2)$$

where $x_i ∈ ℝ_0$ denotes the number of times experiment i is to be performed. We call $x ∈ ℝ_0^m$ a design. Throughout this paper, we will use both ways of expressing $X(\mathbf{x})$ but will favor the second representation. The inverse of the information matrix is the dispersion matrix

$$D(\mathbf{x}) = \left( \sum_{i=1}^{m} x_i \mathbf{v}_i \mathbf{v}_i^{\top} \right)^{-1} .$$

It is a measure of the variance of the experiment parameters (Ahipaşaoğlu, 2015). Our goal is to obtain the “most” information, i.e. we want to maximize some measure of the information matrix. This is equivalent to minimizing over the dispersion matrix (Pukelsheim, 2006), thereby minimizing the variance of the parameters.

The matrix $A^T A$ has full rank, by assumption A has full column rank, and is positive definite<fnref n="1" />. Because of the non-negativity of x, the information matrix $X(x)$ is in the PSD cone. In particular, $X(x)$ is positive definite for $x ∈ ℝ_0^m$ if the non-zero entries of x correspond to at least n linearly independent columns of A. To solve the regression problem (1), we need the chosen experiments to span the parameter space. The information matrix $X(x^*)$ corresponding to the solution $x^*$ of OEDP should wherefore lie in the PD cone.

**Remark.** Experiments can be run only once or be allowed to run multiple times to account for measurement errors. In the latter case, we will suppose non-trivial upper (and lower bounds) on the number of times a given experiment can be run. The sum of the upper bounds significantly exceeds N.

If non-trivial lower bounds l are present, their sum may not exceed N otherwise there is no solution respecting the time and cost constraints. A special case of non-trivial lower bounds is obtained if n linearly independent experiments have non-zero lower bounds. These experiments can be summarized in the matrix $C = A^T \mathrm{diag}(l) A$. Notice that C is positive definite. The information matrix then becomes

$$X_C(\mathbf{x}) = C + A^{\top} \mathrm{diag}(\mathbf{x} - l) A. \quad (3)$$

We will refer to the resulting OEDP as the *Fusion Experiment Design Problem* or short as the *Fusion Problem*. The OEDP with $l = 0$ will be referred to as *Optimal Problem*. These are the two types of problems we are focusing on in this paper.

Let us now answer the question posed earlier: How can we measure information? We need a function $\phi$ receiving a positive definite matrix<fnref n="2" /> as input and returning a number, that is $\phi : S_+^n \to ℝ$. We will

<footnote n="1">1. $z^T A^T A z = \|A z\|_2^2 > 0$ for all $z \in ℝ^m \setminus \{0\}$</footnote>

<footnote n="2">2. As previously stated, the information matrix of the optimal solution $X(x^*)$ has to have full column rank. Thus it suffices to define $\phi$ on the PD cone.</footnote>
lose information by compressing a matrix to a single number. Hence, the suitable choice of $\phi$ depends on the underlying problem. Nevertheless, there are some properties that any $\phi$ has to satisfy to qualify as an information measure.

**Definition 1** (Information Function (Pukelsheim, 2006)). An information function $\phi$ on $S_{++}^n$ is a function $\phi: S_{++}^n \to \mathbb{R}$ that is positively homogeneous, concave, nonnegative, non-constant, upper semi-continuous and respects the Loewner ordering.

**Respecting Loewner ordering** Let $B, D \in S_{+}^n$. We say $D \ge B$ if and only if $D - B \ge 0$ which is equivalent to $D - B \in S_{+}^n$. The order thus imposed on $S_{+}^n$ is called the Loewner Ordering. A map $\phi$ respects the Loewner ordering iff $C \ge B \Rightarrow \phi(C) \ge \phi(B) \forall C, B \in S_{+}^n$. In simple terms, carrying out more experiments should not result in information loss.

**Concavity** The condition for concavity is

$$ \phi(\gamma B + (1 - \gamma)C) \ge \gamma\phi(B) + (1 - \gamma)\phi(C) \quad \forall \gamma \in [0, 1] \forall B, C \in S_{++}^n. $$

The intuition behind this is that we should not be able to achieve the best result by performing two sets of experiments and interpolating the result. There should be a design unifying the two sets achieving a better result.

**Positive homogeneity** For $\gamma > 0$, we have $\phi(\gamma B) = \gamma\phi(B)$, i.e. scaling has no influence on the overall information value. It has added advantage that later in the optimization, we may forgo any factors since they do not interfere with the ordering created by $\phi$.

**Nonnegativity** By convention, we have $\phi(B) \ge 0$ for all $B \in S_{+}^n$.

**Upper semi-continuity** The upper level sets $\{M \in S_{++}^n | \phi(M) \ge \lambda\}$ are closed for all $\lambda \in \mathbb{R}$. This is to ensure "good" behavior at the boundary. The functions considered in this paper are all continuous.

The most frequently used information functions arise from matrix means $\phi_p$ (Pukelsheim (2006), Ahipaşaoğlu (2015)). The matrix means are defined as follows:

**Definition 2** (Matrix mean). Let $C \in S_{++}^n$ and let $\lambda(C)$ denote the eigenvalues of $C$. The matrix mean $\phi_p$ of $C$ is defined as

$$ \phi_p(C) = \begin{cases} \max \lambda(C), & \text{for } p = \infty \\ \left(\frac{1}{n} \text{Tr}(C^p)\right)^{\frac{1}{p}}, & \text{for } p \neq 0, \pm\infty \\ \det(C)^{\frac{1}{n}}, & \text{for } p = 0 \\ \min \lambda(C), & \text{for } p = -\infty. \end{cases} \quad (4) $$

If $C$ is semi-definite with $\text{rank}(C) < n$, the matrix mean is defined as:

$$ \phi_p(C) = \begin{cases} \max \lambda(C), & \text{for } p = \infty \\ \left(\frac{1}{n} \text{Tr}(C^p)\right)^{\frac{1}{p}}, & \text{for } p = (0, \infty) \\ 0, & \text{for } p = [0, -\infty]. \end{cases} \quad (5) $$

Note that the function $\phi_p$ satisfies the requirements of Definition 1 only for $p \le 1$ (Pukelsheim, 2006). The different values of $p$ lead to different so-called criteria. The *Optimal Experiment Design Problem* using a matrix means function is then defined as

$$ \max_{\mathbf{x}} \log(\phi_p(X(\mathbf{x}))) \qquad (\text{OEDP}) $$

$$ \text{s.t.} \quad \sum_{i=1}^{m} x_i = N $$

$$ \mathbf{l} \le \mathbf{x} \le \mathbf{u} $$

$$ \mathbf{x} \in \mathbb{N}_0^m, $$
where **u** and **l** denote the upper and lower bounds, respectively.

**Remark.** Using the logarithm formulation, one can recover Fenchel duality results (Sagnol, 2010, Chapter 3). It can also by beneficial from a information theory point of view. Note, however, that the log does not necessarily preserve concavity.

The resulting problem (OEDP) is an integer optimization problem which, depending on the information function $\phi_p$, can be $N\mathcal{P}$-hard. The two information measures we will focus on lead to $N\mathcal{P}$-hard problems (Welch, 1982; Nikolov et al., 2022; Li, 2025; Li et al., 2024). Thus, these OEDP are hard to solve. Often, therefore, one solves the so-called *Limit Problem* obtained by letting the number of allowed experiments *N* go to infinity. The resulting optimization problem is continuous.

$$ \max_{\mathbf{w}} \log(\phi_p(X(\mathbf{w}))) \qquad (\text{OEDP-Limit}) $$

$$ \text{s.t.} \quad \sum_{i=1}^{m} w_i = 1 \\ \mathbf{w} \in [0, 1]^m $$

The variable vector **w** can be interpreted as a probability distribution. Under suitable assumptions, one can generate a finite experiment design from the solution of the limit problem, see Ahipaşaoğlu (2015), Pukelsheim (2006, Chapter 12). One assumption is that the support of the solution of the Limit Problem (OEDP-Limit) is smaller than the allowed number of experiments *N*. This is often not the case (Pukelsheim, 2006). If an integer solution can be obtained, it is feasible but not necessarily optimal. Optimality can be achieved in some special cases, see Pukelsheim (2006). However, these have very specific requirements that are often not achievable.

## 2.1 The A-, D- and GTI-optimal experiment design problem

For this paper, we focus on two particular criteria arising from the matrix means. The two most commonly used criteria are the D-optimality and A-optimality criterion, $p = 0$ and $p = -1$, respectively.

Many methods for solving MINLP expect minimization formulations. Hence, we will reformulate the problems as minimization problems by flipping the sign of the objective.

**D-Criterion** Choosing $p = 0$ in Definition 2, yields for the objective of (OEDP)

$$ \max_{\mathbf{x} \in \mathbb{N}_0^m} \log \det \left( (X(\mathbf{x}))^{\frac{1}{n}} \right) $$

Note that $\log(\det(X)^{\frac{1}{n}}) = \frac{1}{n} \log \det X$ and thus we can state the *D-Optimal Experiment Design Problem* as:

$$ \begin{array}{ll} \min_{\mathbf{x}} & -\log(\det(X(\mathbf{x}))) \\ \text{s.t.} & \displaystyle\sum_{i=1}^{m} x_i = N \qquad (\text{D-Opt}) \\ & \mathbf{l} \le \mathbf{x} \le \mathbf{u} \\ & \mathbf{x} \in \mathbb{Z} \end{array} $$

Observe that it is equivalent to minimize $\log \det(X(\mathbf{x})^{-1}) = \log \det D(\mathbf{x})$, so the determinant of the dispersion matrix. This is also called *the generalized variance* of the parameter $\theta$ (Pukelsheim, 2006). Thus, a maximal value of $\det X$ corresponds to a maximal volume of standard ellipsoidal confidence region of $\theta$ (Ponte et al., 2025). Additionally, the D-criterion is invariant under reparameterization (Pukelsheim, 2006).

**A-Criterion** For parameters with a physical interpretation, the A-optimality criterion is a good choice (Pukelsheim, 2006) as it amounts to minimizing the average of the variances of $\theta$. Geometrically, the A-criterion amounts to minimizing the diagonal of the bounding box of the ellipsoidal confidence region (Sagnol, 2010). The resulting optimization problem can be stated in two different ways, keeping the log and using the log rules and the positive homogeneity of the information functions.
$$ \min_{\mathbf{x}} \log (\mathrm{Tr}((X(\mathbf{x}))^{-1})) $$

$$ \text{s.t.} \quad \sum_{i=1}^{m} x_i = N $$

$$ \mathbf{l} \leq \mathbf{x} \leq \mathbf{u} $$

$$ \mathbf{x} \in \mathbb{N}_0^m $$

(logA-Opt)

$$ \min_{\mathbf{x}} \mathrm{Tr}((X(\mathbf{x}))^{-1}) $$

$$ \text{s.t.} \quad \sum_{i=1}^{m} x_i = N $$

$$ \mathbf{l} \leq \mathbf{x} \leq \mathbf{u} $$

$$ \mathbf{x} \in \mathbb{N}_0^m $$

(A-Opt)

We test both formulation within the newly proposed framework. Both formulations can be generalized for a real number $p > 0$:

$$ \min_{\mathbf{x}} \log (\mathrm{Tr}((X(\mathbf{x}))^{-p})) $$

$$ \text{s.t.} \quad \sum_{i=1}^{m} x_i = N $$

$$ \mathbf{l} \leq \mathbf{x} \leq \mathbf{u} $$

$$ \mathbf{x} \in \mathbb{N}_0^m $$

(logGTI-Opt)

$$ \min_{\mathbf{x}} \mathrm{Tr}((X(\mathbf{x}))^{-p}) $$

$$ \text{s.t.} \quad \sum_{i=1}^{m} x_i = N $$

$$ \mathbf{l} \leq \mathbf{x} \leq \mathbf{u} $$

$$ \mathbf{x} \in \mathbb{N}_0^m $$

(GTI-Opt)

We call the corresponding problem the *Generalized-Trace-Inverse Optimal Experiment Design Problem*, short *GTI-Optimal Problem*.

**Remark.** We conjecture that OEDP under the GTI-criterion is NPP-hard for any $p > 0$.

Note that the objectives of (D-Opt), (A-Opt), (logA-Opt), (logGTI-Opt) and (GTI-Opt) are only well defined if the information matrix $X(\mathbf{x})$ has full rank.

**Remark.** The Fusion Problems are created by replacing $X(\mathbf{x})$ with $X_C(\mathbf{x})$ in (D-Opt), (A-Opt), (logA-Opt), (logGTI-Opt) and (GTI-Opt), respectively.

For convenience in proofs in the next section, we define

$$ \mathcal{P} := [\mathbf{l}, \mathbf{u}] \cap \{\mathbf{x} \in \mathbb{R}_{\ge 0}^m \mid \sum x_i = N\} \quad (\text{Convex Hull}) $$

as the feasible region of the OEDPs without the integer constraints, i.e. the convex hull of all feasible integer points. Thus, the feasible region with integer constraints will be noted by $\mathcal{P} \cap \mathbb{Z}$.

We denote the domain of the objective functions by

$$ D := \{\mathbf{x} \in \mathbb{R}_{\ge 0}^m \mid X(\mathbf{x}) \in \mathbb{S}_{++}^n\} \quad (\text{Domain}) $$

Throughout the rest of this paper, we denote by

$$ f(X) = -\log \det(X) $$

$$ g(X) = \mathrm{Tr}(X^{-p}) $$

$$ k(X) = \log(\mathrm{Tr}(X^{-p})) $$

where $X \in \mathbb{S}_{++}^n$ and $p > 0$. With abusive of notation, we use the same identifiers for the objectives of the optimization problems.

$$ f(\mathbf{x}) = -\log \det(X(\mathbf{x})) $$

$$ g(\mathbf{x}) = \mathrm{Tr}(X(\mathbf{x})^{-p}) $$

$$ k(\mathbf{x}) = \log(\mathrm{Tr}(X(\mathbf{x})^{-p})) $$
## 3. Properties of the problems and convergence guarantees

To ensure that the newly proposed framework in Hendrych et al. (2025b) is applicable to the previously introduced problems, we have to show that the Frank-Wolfe algorithms used as the subproblem solvers converge on the continuous subproblems. Frank-Wolfe normally requires the objective function to be convex and L-smooth. The convexity part is trivial, for proofs see Appendix A.2. The L-smoothness property only holds for the Fusion Problems on the whole feasible region. For the Optimal Problems, we will show local L-smoothness in Section 3.1 and an alternative property guaranteeing convergence of Frank-Wolfe, namely (generalized) self-concordance, in Section 3.2.

Lastly, we establish sharpness or the Hölder error bound condition of the objective functions, therefore yielding improved convergence rates for Frank-Wolfe methods compared to the standard $O(1/\epsilon)$ rate where $\epsilon$ is the additive error in the primal gap, see Section 3.3.

### 3.1 Lipschitz smoothness

The convergence analysis for Frank-Wolfe algorithms relies on the fact that the objective function values do not grow arbitrarily large. The property guaranteeing this is Lipschitz smoothness, further called L-smoothness.

**Definition 3.** A function $f: \mathbb{R}^n \to \mathbb{R}$ is called L-smooth if its gradient $\nabla f$ is Lipschitz continuous. That is, there exists a finite $L \in \mathbb{R}_{>0}$ with

$$ \|\nabla f(\mathbf{x}) - \nabla f(\mathbf{y})\|_2 \le L \|\mathbf{x} - \mathbf{y}\|_2 $$

Since the functions of interest are in $C^3$, we can use an alternative condition on L-smoothness:

$$ LI \ge \nabla_{xx} f(\mathbf{x}), $$

i.e. the Lipschitz constant $L$ is an upper bound on the maximum eigenvalue of the Hessian.

In Appendix A.3, the reader can find L-smoothness proofs for $f(X)$, $g(X)$ and $k(X)$ over

$$ \{X \in \mathbb{S}_{++}^n \mid \delta \ge \lambda_{\min}(X)\}. $$

The lemmas are not immediately useful for us, in general we cannot bound the minimum eigenvalue of the information matrix. In fact, we will see that we have L-smoothness on the whole convex feasible region $\mathcal{P}$ only for the Fusion Problems. Due to the positive definiteness of the matrix $C$, the information matrix in the Fusion case, $X_C(\mathbf{x})$, is always bounded away from the boundary of the PD cone and we do find a lower bound on the minimum eigenvalue of $X_C(\mathbf{x})$. For Optimal Problems, $X(\mathbf{x})$ can be singular for some $\mathbf{x} \in \mathcal{P}$, i.e. the minimum eigenvalue of $X(\mathbf{x})$ cannot be bounded away from 0 on $\mathcal{P}$. However, we can show L-smoothness in a local region for the Optimal Problems.

We start with the L-smoothness proofs for the objectives of the Fusion Problems.

**Theorem 1.** The functions $f_F(\mathbf{x}) := -\log \det (X_C(\mathbf{x}))$ and $g_F(\mathbf{x}) := \mathrm{Tr}((X_C(\mathbf{x}))^{-p})$ for $p \in \mathbb{R}_{>0}$ are L-smooth on $x \in \mathbb{R}_{\ge 0}$ with Lipschitz constants

$$ L_{f_F} = \left( \max_i (AA^\top)_{ii} \right) \frac{\|A\|_2^2}{\lambda_{\min}(C)^2} $$

and

$$ L_{g_F} = p(p+1) \left( \max_i (AA^\top)_{ii} \right) \frac{\|A\|_2^2}{\lambda_{\min}(C)^{2+p}}, $$

respectively.

*Proof.* For better readability and simplicity, we ignore the dependency of $X$ on $\mathbf{x}$ for now. As stated above, we can prove L-smoothness by showing that the largest eigenvalue of the Hessians is bounded for any $\mathbf{x}$ in the domain. We have

$$ \nabla^2 f_F(\mathbf{x}) = (AA^\top) \circ (AX_C^{-2}A^\top) $$
and

$$ \nabla^2 g_F(\mathbf{x}) = p(p+1) (AA^\top) \circ (AX_C^{-p-2}A^\top). $$

Observe that the Hessian expressions are very similar. Hence, we will only present the proof for $g_F$. The proof of $f_F$ follows the same argumentation. By Horn (1990, page 95) it is known that the maximum eigenvalue of a Hadamard product between two positive semi-definite matrices $N$ and $M$, $\lambda_{\max}(N \circ M)$, is upper bounded by the maximum diagonal entry of $N$ and the largest eigenvalue of $M$, so

$$ \lambda_{\max}(N \circ M) \leq \max_i N_{ii} \lambda_{\max}(M). \qquad (8) $$

In our case, $N = AA^\top$ and $M = AX_C^{-p-2}A^\top$. By Corollary 2 in Appendix A.1, we have that $X_C^{-p-2}$ is positive definite. Thus, both factors are semi-definite and we may use the provided bound.

$$ \lambda_{\max} (\nabla^2 g_F(\mathbf{x})) \leq \max_i (AA^\top)_{ii} \lambda_{\max} (AX_C^{-p-2}A^\top) $$

Note that the first factor is simply

$$ \max_i (AA^\top)_{ii} = \max_i \mathbf{v}_i^\top \mathbf{v}_i. \qquad (9) $$

For the second factor, we can exploit positive semi-definiteness with the spectral norm.

$$ \lambda_{\max} (AX_C^{-p-2}A^\top) = \|AX_C^{-p-2}A^\top\|_2 \\ \leq \|A\|_2^2 \|X_C^{-p-2}\|_2 $$

By Lemma 6, we have $\lambda(A^p) = \lambda(A)^p$.

$$ \begin{aligned} &= \|A\|_2^2 \lambda_{\max}(X_C^{-1})^{2+p} \\ &= \frac{\|A\|_2^2}{\lambda_{\min}(X_C)^{2+p}} \end{aligned} $$

By the definition of $X$ and by Weyl's inequality on the eigenvalues of sums of positive semi-definite matrices Weyl (1912), we have that

$$ \lambda_{\min}(X_C) \geq \lambda_{\min}(C) + \lambda_{\min}(A^\top \mathrm{diag}(x) A) \geq \lambda_{\min}(C). $$

Hence,

$$ \lambda_{\max} (AX_C^{-p-2}A^\top) \leq \frac{\|A\|_2^2}{\lambda_{\min}(C)^{2+p}}. \qquad (10) $$

Combining (8) with (9) and (10) yields

$$ \lambda_{\max} (\nabla^2 g_F(\mathbf{x})) \leq p(p+1) \left( \max_i \mathbf{v}_i^\top \mathbf{v}_i \right) \frac{\|A\|_2^2}{\lambda_{\min}(C)^{2+p}}. \qquad (11) $$

□
For the log variant of the A-criterion, we can also bound the maximum eigenvalue of the hessian $\nabla^2 k_F$.

**Theorem 2.** The function $k_F(\mathbf{x}) := \log \mathrm{Tr}((X_C(\mathbf{x}))^{-p})$ is L-smooth on $\mathcal{P}$ with Lipschitz constant

$$L_{k_F} = \frac{a_C^p}{n} p(p+1) \left( \max_i (AA^\tau)_{ii} \right) \frac{\|A\|_2^2}{\lambda_{\min}(C)^{2+p}}$$

where $a_C$ is the upper bound on the maximum eigenvalue of $X_C(\mathbf{x})$, that is

$$a_C = \lambda_{\max}(C) + \max_{i \in [m]} u_i \max_{j \in [m]} \|v_j\|_2^2$$

with $u_i$ denoting the upper bound of variable $x_i$.

*Proof.* The Hessian of $k_F$ is given by

$$\nabla^2 k_F = p \frac{(p+1) (AA^\tau) \circ (AX_C^{-p-2}A^\tau) \mathrm{Tr}(X_C^{-p}) - p \mathrm{diag}(AX_C^{-p-1}A^\tau) \mathrm{diag}(AX_C^{-p-1}A^\tau)^\top}{\mathrm{Tr}(X_C^{-p})^2}.$$

As before, we omit the dependency on $\mathbf{x}$ for better readability. Note that both parts of the nominator are symmetric matrices. Thus, we can use the upper bound on the eigenvalues of sums of symmetric matrices in Lemma 15. Further, note that for any $\mathbf{z} \in \mathbb{R}^n$ the matrix $\mathbf{z}\mathbf{z}^\top$ is PSD and its maximum eigenvalue is $\langle \mathbf{z}, \mathbf{z} \rangle$.

$$\lambda_{\max}(\nabla^2 k_F) \le \frac{p(p+1)}{\mathrm{Tr}(X_C^{-p})} \lambda_{\max}((AA^\tau) \circ (AX_C^{-p-2}A^\tau))$$

An upper bound on the maximum eigenvalue of $(AA^\tau) \circ (AX_C^{-p-2}A^\tau)$ is already provided by Theorem 1. Observe that

$$\mathrm{Tr}(X_C^{-p}) \ge n\lambda_{\min}(X_C^{-p}) = \frac{n}{\lambda_{\max}(X_C)^p} \ge \frac{n}{a_C}.$$

Assembling everything yields the desired bound.

<figure><img src="image_2.png" /></figure>

As stated before, the proofs of Theorems 1 and 2 work because we can bound the minimum eigenvalue of the Fusion information matrix $X_C$ away from zero thanks to the regular matrix $C$. This is not the case of the information matrices $X(\mathbf{x})$ of the Optimal Problems as they can be singular for some $x \in \mathcal{P}$. Therefore, the objectives of the Optimal Problems are not L-smooth over $\mathcal{P}$. We can show, however, that the objectives are L-smooth on a restricted area of the feasible region.

Remember that $D$ denotes the domain of the objectives, see (Domain). Since the Frank-Wolfe algorithms make monotonic progress, it is helpful to show that given an initial point $\mathbf{x}_0$ in the domain $D$ the minimum eigenvalue is bounded in the region

$$\mathcal{L}_0 = \left\{ \mathbf{x} \in D \cap \sum_{i=1}^{m} x_i = N \mid (*)(\mathbf{x}) \le (*)(\mathbf{x}_0) \right\}$$

where $(*)$ is a placeholder for $f(\mathbf{x})$, $g(\mathbf{x})$ and $k(\mathbf{x})$, respectively. Using the bound provided by Merikoski & Virtanen (1997, Theorem 1) and the fact that the objective value is decreasing, we can bound the minimum eigenvalue by quantities depending on the experiment matrix $A$ and the start point $\mathbf{x}_0$. Let further $X_0 = X(\mathbf{x}_0)$.

**Theorem 3.** The functions $f(\mathbf{x}) := -\log \det(X(\mathbf{x}))$, $g(\mathbf{x}) := \mathrm{Tr}((X(\mathbf{x}))^{-p})$ and $k(\mathbf{x}) := \mathrm{Tr}((X(\mathbf{x}))^{-p})$ for $p > 0$ are L-smooth locally on their respective $\mathcal{L}_0$ for a given initial point $\mathbf{x}_0$ with

$$L_f = \left( \max_i (AA^\tau)_{ii} \right) \frac{\|A\|_2^2 (mN \max_i \|v_i\|_2^2)^{n-1}}{(n-1)^{n-1} \det X_0^2}$$
$$L_g = p(p+1) \left( \max_i (AA^\mathrm{T})_{ii} \right) \|A\|_2^2 \left( \mathrm{Tr} \left( X_0^{-1} \right) \right)^{2+p}$$

and

$$L_k = \frac{a^p}{n} p(p+1) \left( \max_i (AA^\mathrm{T})_{ii} \right) \|A\|_2^2 \left( \mathrm{Tr} \left( X_0^{-1} \right) \right)^{2+p}$$

where $a = \max_{i \in [m]} u_i \max_{j \in [m]} \|v_j\|_2^2$ is a upper bound on the maximum eigenvalue of $X(\mathbf{x})$.

*Proof.* As seen in the previous proofs, we have

$$L_f = \left( \max_i (AA^\mathrm{T})_{ii} \right) \frac{\|A\|_2^2}{\lambda_{\min}(X(\mathbf{x}))^2}$$

$$L_g = p(p+1) \left( \max_i (AA^\mathrm{T})_{ii} \right) \frac{\|A\|_2^2}{\lambda_{\min}(X(\mathbf{x}))^{2+p}}.$$

and

$$L_k = \frac{a^p}{n} p(p+1) \left( \max_i (AA^\mathrm{T})_{ii} \right) \frac{\|A\|_2^2}{\lambda_{\min}(X(\mathbf{x}))^{2+p}}$$

To bound the Lipschitz constant, we need lower bound the minimum eigenvalue of $X(\mathbf{x})$. We start with $L_f$ and find by using the bound provided by Merikoski & Virtanen (1997, Theorem 1)

$$\lambda_{\min}(X) \geq \left( \frac{n-1}{\mathrm{Tr}(X)} \right)^{n-1} \det X.$$

The trace can be upper bounded by $\mathrm{Tr}(X) \leq mN \max_i \|v_i\|_2^2$ and by knowing that $-\log \det(X(\mathbf{x})) \leq -\log \det(X_0)$, we find

$$\lambda_{\min}(X) \geq \left( \frac{n-1}{mN \max_i \|v_i\|_2^2} \right)^{n-1} \det X_0.$$

Thus,

$$L_f = \left( \max_i (AA^\mathrm{T})_{ii} \right) \frac{\|A\|_2^2 \left( mN \max_i \|v_i\|_2^2 \right)^{n-1}}{(n-1)^{n-1} \det X_0^2}.$$

To lowerbound the minimum eigenvalue of $X(\mathbf{x})$ w.r.t. the objectives $g(\mathbf{x})$ and $k(\mathbf{x})$, we first need

$$\mathrm{Tr}(X^{-p-2}) = \sum_{i=1}^{n} \frac{1}{\lambda_i(X)^{p+2}} = \sum_{i=1}^{n} \frac{1}{\lambda_i(X)^2} \frac{1}{\lambda_i(X)^p} \\ \leq \frac{1}{\lambda_{\min}(X)^2} \mathrm{Tr}(X^{-p}).$$

Note that the log is preserving ordering. Hence, we can use the fact that $\mathrm{Tr}(X^{-p}) \leq \mathrm{Tr}(X_0^{-p})$ and we find

$$\leq \frac{1}{\lambda_{\min}(X)^2} \mathrm{Tr}(X_0^{-p}).$$
Exploiting positive definiteness and the spectral norm, we have

$$
\begin{align*}
\lambda_{\min}(X)^{p+2} &= \lambda_{\min}\left(X^{\frac{p+2}{2}}\right)^2 = \frac{1}{\lambda_{\max}\left(X^{-\frac{p+2}{2}}\right)^2} \\
&= \frac{1}{\left\|X^{-\frac{p+2}{2}}\right\|_2^2} \ge \frac{1}{\left\|X^{-\frac{p+2}{2}}\right\|_F^2} = \frac{1}{\operatorname{Tr}(X^{-p-2})}
\end{align*}
$$

$$
\lambda_{\min}(X)^{p+2} \geq \frac{\lambda_{\min}(X)^2}{\operatorname{Tr}(X^{-p})} \geq \frac{\lambda_{\min}(X)^2}{\operatorname{Tr}(X_0^{-p})} \geq \frac{\lambda_{\min}(X)^2}{\operatorname{Tr}(X_0^{-1})^p}.
$$

Ultimately, we find

$$
\lambda_{\min}(X) \geq \frac{1}{\mathrm{Tr}(X_0^{-1})}
$$

and the smooth constants are

$$
L_g = p(p+1) \left( \max_i (AA^\top)_{ii} \right) \|A\|_2^2 \left( \mathrm{Tr}(X_0^{-1}) \right)^{2+p}
$$

and

$$
L_k = \frac{a^p}{n} p(p+1) \left( \max_i (AA^\top)_{ii} \right) \|A\|_2^2 \left( \mathrm{Tr}(X_0^{-1}) \right)^{2+p} .
$$

Thereby, we have local smoothness constants for the objectives f, g and k.

<figure><img src="image_3.png" /></figure>

To summarize, we have shown L-smoothness of the objectives of the Fusion Problems which guarantees convergence of Frank-Wolfe. For the Optimal Problems, we have shown local L-smoothness on a restricted area of the feasible region. This, however, does not suffice to guarantee convergence of Frank-Wolfe. In the next section, we will show that the objectives satisfy an alternative condition that ensures convergence of Frank-Wolfe.

3.2 Generalized self-concordance

By Carderera et al. (2021), the Frank-Wolfe algorithm also converges (with similar convergence rates to the L-smooth case) if the objective is generalized self-concordant.

**Definition 4** (Generalized Self-Concordance Sun & Tran-Dinh (2019)). A three-times differentiable, convex function $f: \mathbb{R}^n \to \mathbb{R}$ is $(M_f, \nu)$-generalized self-concordant with order $\nu > 0$ and constant $M_f \ge 0$, if for all $x \in \text{dom}(f)$ and $\mathbf{u}, \mathbf{v} \in \mathbb{R}^n$, we have

$$
|\langle \nabla^3 f(\mathbf{x}) [\mathbf{u}] \mathbf{v}, \mathbf{v} \rangle| \leq M_f \|\mathbf{u}\|_x^2 \|\mathbf{v}\|_x^{\nu-2} \|\mathbf{v}\|_2^{3-\nu}
$$

where

$$
\|\mathbf{w}\|_x = \langle \nabla^2 f(\mathbf{x})\mathbf{w}, \mathbf{w} \rangle \text{ and } \nabla^3 f(\mathbf{x})[\mathbf{u}] = \lim_{\gamma \to 0} \gamma^{-1} \left( \nabla^2 f(\mathbf{x} + \gamma\mathbf{u}) - \nabla^2 f(\mathbf{x}) \right).
$$

Self-concordance is a special case of generalized self-concordance where $\nu = 3$ and $\mathbf{u} = \mathbf{v}$. This yields the
condition

$$
|\langle \nabla^3 f(\mathbf{x}) [\mathbf{u}] \mathbf{u}, \mathbf{u} \rangle| \leq M_f \|\mathbf{u}\|_x^3.
$$
For a univariate, three times differentiable function $f: \mathbb{R} \to \mathbb{R}$, $(M_f, \nu)$-generalized self-concordance<fnref n="3" />
condition is

$$|f'''(x)| \leq M_f (f''(x))^{\frac{\nu}{2}}.$$

By Sun & Tran-Dinh (2019, Proposition 2), the composition of a generalized self-concordant function with a linear map is still generalized self-concordant. Hence, it suffices that we show that the functions $f(X) = -\log \det(X)$ and $g(X) = \text{Tr}(X^{-p})$ and $k(X) = \log(\text{Tr}(X^{-p}))$, $p > 0$, are generalized self-concordant for $X$ in the PD cone.

Notice that $f$ is the logarithmic barrier for the PSD cone which is known to be self-concordant (Nesterov & Nemirovskii, 1994). Convergence of Frank-Wolfe for the (D-Opt) Problem is therefore guaranteed. For convergence for the (GTI-Opt) Problem and (A-Opt) Problem, we can show that $g$ is self-concordant on a part of the PD cone.

**Theorem 4.** The function $g(X) = \text{Tr}(X^{-p})$, with $p > 0$, is $(3, \frac{(p+2)\sqrt{\alpha^2pn}}{\sqrt{p(p+1)}})$-generalized self concordant on
$\mathcal{D} = \{X \in \mathbb{S}_{++}^n | 0 < X \le \alpha I\}$.

*Proof.* As with the convexity proofs in Appendix A.2, we bring our function back to the univariate case. We define $M(t) = V + tU$ where $V \in D$, $U$ a symmetric matrix and $t \in \mathbb{R}$ such that $V + tU \in \mathcal{D}$. By Lemma 10, the second and third derivatives of $h(t) = \text{Tr}(M(t)^{-p})$ are given by

$$h''(t)|_{t=0} = p(p+1) \text{Tr}(V^{-p}UV^{-1}UV^{-1}) \\ h'''(t)|_{t=0} = -p(p+1)(p+2) \text{Tr}(V^{-p}UV^{-1}UV^{-1}UV^{-1}).$$

Thus, the condition we want to satisfy is

$$|p(p+1)(p+2) \text{Tr}(V^{-p}UV^{-1}UV^{-1}UV^{-1})| \leq M_f p(p+1) \text{Tr}(V^{-p}UV^{-1}UV^{-1})^{\nu/2}.$$

If the LHS is equal to 0, we are done. Otherwise, we divide both sides by the LHS and first try to lower bound the following fraction.

$$\frac{\text{Tr}\left(V^{-\frac{p+1}{2}}UV^{-1}UV^{-\frac{p+1}{2}}\right)^{\nu/2}}{\left|\text{Tr}\left(V^{-\frac{p+1}{2}}UV^{-1}UV^{-1}UV^{-\frac{p+1}{2}}\right)\right|}$$

For that we define $H = V^{-1/2}UV^{-1/2}$ and $L = V^{-p/2}H$.

$$\frac{\text{Tr}\left(V^{-\frac{p+1}{2}}UV^{-1}UV^{-\frac{p+1}{2}}\right)^{\nu/2}}{\left|\text{Tr}\left(V^{-\frac{p+1}{2}}UV^{-1}UV^{-1}UV^{-\frac{p+1}{2}}\right)\right|} = \frac{\text{Tr}(LL^{\tau})^{\nu/2}}{|\text{Tr}(LHL^{\tau})|}$$

<footnote n="3">3. For self-concordance, $\nu = 3$.</footnote>
Using Cauchy-Schwartz, we find

$$
\begin{align*}
|\operatorname{Tr}(LHL^T)| &= |\langle L^T L, H \rangle| \\
&\le \operatorname{Tr}(LL^T) \sqrt{\operatorname{Tr}(H^2)}. \\
\frac{\operatorname{Tr}(LL^T)^{\nu/2}}{|\operatorname{Tr}(LHL^T)|} &\ge \frac{\operatorname{Tr}(LL^T)^{\nu/2}}{\operatorname{Tr}(LL^T) \sqrt{\operatorname{Tr}(H^2)}} \\
\operatorname{Tr}(HH) &= \operatorname{Tr}\left(V^{p/2}V^{-p/2}HHV^{-p/2}V^{p/2}\right) \\
&= \operatorname{Tr}\left(V^{p/2}LL^T V^{p/2}\right) \\
&\le \operatorname{Tr}(LL^T) \sqrt{\operatorname{Tr}(V^{2p})} \\
\frac{\operatorname{Tr}(LL^T)^{\nu/2}}{\operatorname{Tr}(LL^T) \sqrt{\operatorname{Tr}(H^2)}} &\ge \frac{\operatorname{Tr}(LL^T)^{\nu/2}}{\operatorname{Tr}(LL^T) \sqrt{\operatorname{Tr}(LL^T) \operatorname{Tr}(V^{2p})}} \\
&= \operatorname{Tr}(LL^T)^{\nu/2-3/2} \frac{1}{\sqrt{\|V^p\|_F}} \\
&\ge \operatorname{Tr}(LL^T)^{\nu/2-3/2} \frac{1}{\sqrt{\|V^p\|_2}\sqrt{n}}
\end{align*}
$$

By the assumption that V is a feasible point, we have $||V||_2 = \lambda_{\max}(V) \le \alpha$.

$$
\geq \operatorname{Tr}(LL^{\tau})^{\nu/2-3/2} \frac{1}{\sqrt{\alpha^{p}} \sqrt{n}}
$$

Then,

$$
\frac{M_f (p(p+1))^{\nu/2}}{p(p+1)(p+2)} \frac{\operatorname{Tr}(V^{-p}UV^{-1}UV^{-1})^{\nu-2}}{\operatorname{Tr}(V^{-p}UV^{-1}UV^{-1}UV^{-1})} \ge \frac{M_f (p(p+1))^{\nu/2}}{p(p+1)(p+2)} \operatorname{Tr}(LL^{\tau})^{\nu/2-3/2} \frac{1}{\sqrt{\alpha^p} \sqrt{n}}.
$$

We can select $\nu = 3$ and re-express the GSC condition as

$$
1 \le \frac{M_f (p(p+1))^{1/2}}{(p+2)} \frac{1}{\sqrt[4]{\alpha^2 p n}} \\
M_f \ge \frac{(p+2)^{\sqrt[4]{\alpha^2 p n}}}{\sqrt{p(p+1)}}.
$$

Thus, $g$ is $(3, \frac{(p+2)^{\sqrt[4]{\alpha^2 p n}}}{\sqrt{p(p+1)}})$-generalized self concordant. $\square$

**Remark.** We conjecture that there is another value of $\nu$ with a tighter value for the constant $M_f$ satisfying the condition in **Definition 4**.

**Corollary 1.** The function $g(X) = \operatorname{Tr}(X^{-1})$ is $(3, \frac{3\sqrt[4]{\alpha^2 n}}{\sqrt{2}})$-generalized self concordant on $\mathcal{D} = \{X \mid 0 < X \le \alpha I\}$.

Hence, the objectives of the A-Opt and GTI-Opt Problems are generalized self-concordant if we can upperbound the maximum eigenvalue of the information matrix $X(\mathbf{x})$.
**Lemma 1.** Let $x \in \mathcal{P}$. Then,

$$ \lambda_{\max}(X(\mathbf{x})) \leq \max_i u_i \max_j \|\mathbf{v}_j\|_2^2 $$

*Proof.*

$$ \lambda_{\max}(X(\mathbf{x})) = \lambda_{\max}\left(\sum_{i=1}^{m} x_i \mathbf{v}_i \mathbf{v}_i^{\top}\right) $$

By the Courant Fischer Min-Max Theorem, we have

$$ \leq \sum_{i=1}^{m} \lambda_{\max}(x_i \mathbf{v}_i \mathbf{v}_i^{\top}). $$

Using $\mathbf{x} \leq \mathbf{u}$, yields

$$ \leq \max_i u_i \max_j \|\mathbf{v}_j\|_2^2. $$

□

The proof of Theorem 4 does not translate to the log variant of the A-criterion. Our computational experiments strongly suggest that the function $k(X) = \log(\mathrm{Tr}(X^{-p}))$ is generalized self-concordant.

**Conjecture 1.** The function $k(X) = \log(\mathrm{Tr}(X^{-p}))$ is $(\nu, M)$-generalized self concordant for some $\nu \in [2, 3]$ and $M > 0$ on some subset of PD cone.

Thus, we have convergence of Frank-Wolfe for the D-Opt, A-Opt and GTI-Opt Problems. For the logA-Opt and logGTI-Opt Problems, we have strong empirical evidence that convergence holds but the theoretical proof is still open. Lastly, we aim to show that we have improved convergence rates of Frank-Wolfe for our problems of interest.

## 3.3 Sharpness

The classical convergence speed of Frank-Wolfe methods given a convex objective is $\Theta(1/\epsilon)$ where $\epsilon$ is the additive primal error to the true optimum $x^*$, i.e. $f(\mathbf{x}) - f(x^*) \leq \epsilon$. For the objectives of the problems defined in Section 2.1, we can prove a stronger property than convexity, namely sharpness on (a subset of) the feasible region $\mathcal{P}$. This improves the convergence rates of Frank-Wolfe, for the proof see Appendix C and Zhao (2025).

**Definition 5** (Sharpness (Braun et al., 2022, Section 3.1.5)). Let $\mathcal{X}$ be a compact convex set. A convex function $f$ is $(c, \theta)$-sharp (over $\mathcal{X}$) for $0 < M < \infty$, $0 < \theta < 1$ if for all $x \in \mathcal{X}$ and $\mathbf{x}^* \in \Omega_{\mathcal{X}}^*$, we have

$$ M(f(\mathbf{x}) - f(x^*))^{\theta} \geq \min_{\mathbf{y} \in \Omega_{\mathcal{X}}^*} \|\mathbf{x} - \mathbf{y}\| $$

where $\Omega_{\mathcal{X}}^*$ denotes the set of minimizers $\min_{\mathbf{x} \in \mathcal{X}} f(\mathbf{x})$.

**Theorem 5.** The objective functions associated with the Optimal Problem and Fusion Problem

$$ \begin{aligned} f(\mathbf{x}) &= -\log \det(X(\mathbf{x})) & g(\mathbf{x}) &= \mathrm{Tr}(X(\mathbf{x})^{-p}) & k(\mathbf{x}) &= \log(\mathrm{Tr}(X(\mathbf{x})^{-p})) \\ f_F(\mathbf{x}) &= -\log \det(X_C(\mathbf{x})) & g_F(\mathbf{x}) &= \mathrm{Tr}(X_C(\mathbf{x})^{-p}) & k_F(\mathbf{x}) &= \log(\mathrm{Tr}(X_C(\mathbf{x})^{-p})) \end{aligned} $$

with $p > 0$ are $(c, 1/2)$-sharp for some $c > 0$ on $\mathcal{W} := \mathrm{conv}\{x \in \mathcal{P} \cap D \cap \mathbb{N}_0^m\}$.
To prove Theorem 5, we first prove that the functions $f(X) = -\log \det(X)$, $g(X) = \mathrm{Tr}(X^{-p})$ and $k(X) = \log(\mathrm{Tr}(X^{-p}))$ with $p > 0$, are strongly convex on a part of the PD cone.

**Definition 6 (Strong Convexity).** A differentiable function $f: D \to \mathbb{R}$ with $D \subseteq \mathbb{R}^n$ is called $\mu$-strongly convex iff:

$$ \langle \nabla f(\mathbf{x}) - \nabla f(\mathbf{y}), \mathbf{x} - \mathbf{y} \rangle \geq \mu \|\mathbf{x} - \mathbf{y}\|_2^2 \quad \forall \mathbf{x}, \mathbf{y} \in D, $$

with $\mu > 0$. If $f$ is twice differentiable, an equivalent requirement is:

$$ \nabla^2 f(\mathbf{x}) \geq \mu I \quad \forall \mathbf{x} \in D. $$

That is, $\mu$ is a lower bound on the minimum eigenvalue of the Hessian of $f$.

**Lemma 2.** The function $f(X) := -\log \det(X)$ is $\mu$-strongly convex on $\mathcal{D} := \{X \in \mathbb{S}_{++}^n \mid \lambda_{\max}(X) \leq \alpha\}$ with $\mu \leq \frac{1}{a^2}$.

*Proof.* Let $A \in \mathcal{D}$, $B \in \mathbb{S}^n$ and $t \in \mathbb{R}$ such that $A + tB \in \mathcal{D}$. Then we can define $h(t) = -\log \det(A + tB)$. By Lemma 9, $f(X)$ is convex and the second derivative of $h$ is given by

$$ h''(t) = \sum_{i=1}^{n} \frac{\lambda_i (A^{-1/2}BA^{-1/2})^2}{1 + t\lambda_i (A^{-1/2}BA^{-1/2})} $$

It is sufficient to show that $h''(t) \upharpoonright_{t=0} \geq \mu$ to argue strong convexity for $f$.

$$ h''(t) \upharpoonright_{t=0} = \sum_{i=1}^{n} \lambda_i (A^{-1/2}BA^{-1/2})^2 $$

By using a similar idea to Lemma 16, we find

$$ \begin{aligned} & \geq \sum_{i=1}^{n} \lambda_{\min} (A^{-1})^2 \lambda_i (B)^2 \\ &= \lambda_{\min} (A^{-1})^2 \mathrm{Tr}(B^2) \\ &= \lambda_{\min} (A^{-1})^2 \|B\|_F^2 \end{aligned} $$

W.l.o.g. let $\|B\|_F = 1$.

$$ \begin{aligned} &= \frac{1}{\lambda_{\max}(A)^2} \\ &\geq \frac{1}{\alpha^2} \\ &= \mu \end{aligned} $$

Thus, the function is strongly convex at any point $A \in D$.

**Lemma 3.** For $p \in \mathbb{R}_{>0}$, the function $g(X) := \mathrm{Tr}(X^{-p})$ is $\mu$-strongly convex on the domain $\mathcal{D} := \{X \in \mathbb{S}_{++}^n \mid \lambda_{\max}(X) \leq \alpha\}$ with

$$ \mu \leq \frac{p(p+1)}{a^{p+2}}. $$
Proof. Let $A \in \mathcal{D}$ and $B \in \mathbb{S}^n$ and $t \in \mathbb{R}$ such that $A + tB \in \mathcal{D}$. Define $h(t) = \mathrm{Tr}((A + tB)^{-p})$. For the computation of $h''(t)$, see Lemma 10.

$$h''(t)|_{t=0} = p(p+1) \mathrm{Tr}(A^{-p}BA^{-1}BA^{-1}).$$

Since $A^{-p}$ is positive definite by Corollary 2 and the trace is cyclic, we have

$$= p(p+1) \mathrm{Tr}(A^{-\frac{p+2}{2}} BBA^{-\frac{p+2}{2}})$$

Note that $BB$ is positive semi-definite. Thus, we can use the bound in Fang et al. (1994).

$$\begin{align*}
&\geq p(p+1)\lambda_{\min}(A^{-(p+2)}) \mathrm{Tr}(BB) \\
&= p(p+1)\lambda_{\min}(A^{-(p+2)}) \|B\|_F^2
\end{align*}$$

W.l.o.g. let $\|B\|_F = 1$.

$$\begin{align*}
&= \frac{p(p+1)}{\lambda_{\max}(A^{p+2})} \\
&\geq \frac{p(p+1)}{\alpha^{p+2}}
\end{align*}$$

Thus, $h(t)$ is strongly convex with $\mu = \frac{p(p+1)}{\alpha^{p+2}}$. $\square$

**Lemma 4.** For $p \in \mathbb{R}_{>0}$, the function $k(X) = \log(\mathrm{Tr}(X^{-p}))$ is strongly convex on $\mathcal{D} := \{X \in \mathbb{S}_{++}^n \mid \lambda_{\max}(X) \le \alpha, \kappa(X) \le \kappa\}$.

Proof. Let $A \in \mathcal{D}$, $B \in \mathbb{S}^n$ and $t \in \mathbb{R}$ s.t. $A + tB \in \mathcal{D}$. We define $h(t) = k(A + tB) = \log(\mathrm{Tr}((A + tB)^{-p}))$. By Lemma 11, we have

$$h''(t)|_{t=0} = p \frac{(p+1) \mathrm{Tr}(A^{-p-2}BB) \mathrm{Tr}(A^{-p}) - p \mathrm{Tr}(A^{-p-1}B)^2}{\mathrm{Tr}(A^{-p})^2}.$$

Using the Cauchy Schwartz inequality $\mathrm{Tr}(XY^\tau)^2 \le \mathrm{Tr}(XX^\tau) \mathrm{Tr}(YY^\tau)$ and setting $X = A^{-p/2}$ and $Y = A^{-p/2}B$, we have

$$\begin{align*}
&\geq p \frac{(p+1-p) \mathrm{Tr}(A^{-p}) \mathrm{Tr}(A^{-p-2}BB)}{\mathrm{Tr}(A^{-p})^2} \\
&= p \frac{\sum_{i=1}^{n} \lambda_i (A^{-p-2}BB)}{\mathrm{Tr}(A^{-p})}.
\end{align*}$$

Note that the matrix $BB$ is PSD. The proof of Lemma 16 can be adapted for one of matrices being symmetric and the other positive definite.

$$\geq p \frac{\lambda_{\min}(A^{-p-2}) \mathrm{Tr}(BB)}{\mathrm{Tr}(A^{-p})}$$
Observe that $Tr(BB) = \|B\|_F^2$. Without loss of generality, we can assume $\|B\|_F = 1$.

$$ 
\begin{aligned}
&\geq p \frac{\lambda_{\min}(A^{-p-2})}{n\lambda_{\max}(A^{-p})} \\
&= \frac{p}{n\kappa(A)^p \lambda_{\max}(A)^2} \\
&\geq \frac{p}{n\kappa^p a^2} = \mu
\end{aligned}
$$

Thus, $k$ is strongly convex for any $A \in \mathcal{D}$.

□

By Lemma 1, we know that the largest eigenvalue of the information matrix can be bounded. As for the minimum eigenvalue, it can be lower bounded on

$$ \mathcal{W} := \operatorname{conv} \{x \in \mathcal{P} \cap D \cap \mathbb{N}_0^m\} $$

so the convex hull of all domain-feasible integer points, see Figure 1. Any point $Y \in \mathcal{W}$ can be represented as a convex combination of the integer vertices $\{V_i\} \in \mathcal{W}$. By Lemma 15, we have

$$ 
\begin{aligned}
\lambda_{\min}(Y) &= \lambda_{\min}\left(\sum_{i=1}^{n} \gamma_i V_i\right) \\
&\geq \sum_{i=1}^{n} \gamma_i \lambda_{\min}(V_i) \\
&\geq \min_{V \in \mathcal{W}} \lambda_{\min}(V)
\end{aligned}
$$

<figure><img src="image_4.png" /><figcaption>Figure 1: A schematic representation of the feasible region $\mathcal{P}$, the domain of the objective $\mathcal{D}$ and the convex hull of vertices that are both feasible and in the domain denoted as $\mathcal{W}$.</figcaption></figure>

*Proof of Theorem 5.* The functions of interest are compositions of strongly convex functions, see Lemma 2 and Lemma 3, and linear maps. Observe that the linear maps $X(\mathbf{x})$ and $X_C(\mathbf{x})$ are, in general, not injective and hence strong convexity is not preserved.

We can, however, follow the argumentation in Braun et al. (2022, Example 3.28). All of the functions of interest have the form $k(\mathbf{x}) = r(B\mathbf{x})$ where $r$ is a strongly convex function. Notice that $B = A^\top * A^\top$ where * denotes the column-wise Kroenecker product. Observe that

$$ \mathcal{W} := \operatorname{conv} (D \cap \mathcal{P} \cap \mathbb{Z}^m) $$
is the convex hull of the feasible integer points that are also in the domain. This is a polytope and we may use the bound in Braun et al. (2022, Lemma 3.27). Notice that the gradient of $k$ is given by $\nabla k(\mathbf{x}) = B^\top \nabla r(B\mathbf{x})$. As in Definition 5 let $\Omega_W^*$ denote the set of minimizers of $\min_{\mathbf{x} \in W} k(\mathbf{x})$ and let $\mathbf{x}^* \in \Omega_W^*$. Then, we have $\langle \nabla k(\mathbf{x}^*), \mathbf{x} - \mathbf{x}^* \rangle \ge 0$ for $\mathbf{x} \in W$.

$$k(\mathbf{x}) - k(\mathbf{x}^*) = r(B\mathbf{x}) - r(B\mathbf{x}^*)$$

Since $r$ is $\mu$-strongly convex we have

$$\begin{aligned}
& \ge \langle \nabla r(B\mathbf{x}^*), B\mathbf{x} - B\mathbf{x}^* \rangle + \mu \frac{\|B\mathbf{x} - B\mathbf{x}^*\|^2}{2} \\
& = \langle \nabla k(\mathbf{x}), \mathbf{x} - \mathbf{x}^* \rangle + \mu \frac{\|B\mathbf{x} - B\mathbf{x}^*\|_2}{2} \\
& = \mu \frac{\|B\mathbf{x} - B\mathbf{x}^*\|^2}{2}
\end{aligned}$$

Since our region of interest $W$ is a polytope Braun et al. (2022, Lemma 3.27) holds and there exists a constant $c > 0$ such that the distance $\|B\mathbf{x} - B\mathbf{y}\|$ between any two points $\mathbf{x}, \mathbf{y} \in W$ is bounded by

$$\|B\mathbf{x} - B\mathbf{y}\| \ge c \operatorname{dist}(\mathbf{x}, \{\mathbf{w} \in W | B\mathbf{w} = B\mathbf{y}\}).$$

In conclusion, we find

$$k(\mathbf{x}) - k(\mathbf{x}^*) \ge \mu \frac{\|B\mathbf{x} - B\mathbf{x}^*\|^2}{2} \ge \frac{\mu}{2} c^2 \min_{\mathbf{z} \in \Omega_W^*} \|\mathbf{x} - \mathbf{z}\|^2$$

Thus, functions are $(\frac{\sqrt{2}}{c\sqrt{\mu}}, \frac{1}{2})$-sharp. $\square$

Regarding the constant $c$ in the previous proof, we find

$$\begin{aligned}
\|B\mathbf{x} - B\mathbf{y}\|_F &= \|A^\top \operatorname{diag}(\mathbf{x}) A - A^\top \operatorname{diag}(\mathbf{y}) A\|_F \\
&= \|A^\top \operatorname{diag}(\mathbf{x} - \mathbf{y}) A\|_F.
\end{aligned}$$

Let $C = A^\top$ and $B = \operatorname{diag}(\mathbf{x} - \mathbf{y})A$ and let us use the bound in Lemma 17.

$$\begin{aligned}
& \ge \sigma_{\min}(A) \| \operatorname{diag}(\mathbf{x} - \mathbf{y}) A \|_F \\
& \ge \sigma_{\min}(A)^2 \| \operatorname{diag}(\mathbf{x} - \mathbf{y}) \|_F \\
& = \sigma_{\min}(A)^2 \| \mathbf{x} - \mathbf{y} \|_2
\end{aligned}$$

Note that $\|\mathbf{x} - \mathbf{y}\|_2 \ge \operatorname{dist}(\mathbf{x}, \{\mathbf{w} \in W | B\mathbf{w} = B\mathbf{y}\})$ and thus, we have found $c = \sigma_{\min}(A)^2$. Note that since $A$ has full column rank, the minimum singular value is strictly greater than 0.

We have thus established sharpness for all objective functions on $W$. Observe that $W = P$ for the Fusion Problems, thus, linear convergence of Frank-Wolfe is guaranteed on them. In general, however, we have $P \setminus W \cap D \ne \emptyset$, see also Figure 1. That is there exists domain feasible points $\mathbf{y} \in P$ which cannot be expressed as the convex combination of domain feasible integer points in $P$. Hence, we have only linear convergence of Frank-Wolfe on the continuous subproblems if the corresponding continuous solution is in $W$. In this case, we may use Theorem 6 in Appendix C to argue linear convergence. For the Equation (D-Opt) Problem, we could adapt the proof in Zhao (2025) to the Blended Pairwise Conditional Gradient (BPCG) to argue linear convergence on all the subproblems, see Proposition 1 in Appendix C. For the A-criterion and its log variant, we have only linear convergence on nodes where the continuous solution is in $W$. We cannot guarantee that this is the case for all subproblems at the nodes.
<figure><img src="image_5.png" /><figcaption>Figure 2: Trajectory of the dual gap at the root node compared to $1/2t$, $1/t^2$ and $1/e^{ct}$.</figcaption></figure>

From our experiments, we have empirical evidence that we have linear convergence of the dual gap for all Optimal Problems. In Figure 2, we show the trajectory of the dual gap at the root node for the A-criterion, D-criterion and $\log A$-criterion. After a burn-in phase, we see that the trajectory becomes parallel to $1/e^{ct}$ for some constant $c > 0$ which is a representation of the linear convergence.

In summary, we have definitely accelerated convergence rates for the Fusion Problems. In case of the Optimal Problems, it will depend on the position of the continuous solution, so the input experiment data. In our own experiments, we could observe accelerated rates.

<table><caption>Table 1: Convergence of Frank-Wolfe on different objective functions.</caption><thead><tr><th>Objective</th><th>Convergence</th><th>Linear Convergence</th></tr></thead><tbody><tr><td>$f_F(\mathbf{x}) = \log \det(X_C(\mathbf{x}))$</td><td>✓</td><td>✓</td></tr><tr><td>$g_F(\mathbf{x}) = \operatorname{Tr}(X_C(\mathbf{x})^{-p})$</td><td>✓</td><td>✓</td></tr><tr><td>$k_F(\mathbf{x}) = \log (\operatorname{Tr}(X_C(\mathbf{x})^{-p}))$</td><td>✓</td><td>✓</td></tr><tr><td>$f(\mathbf{x}) = -\log \det(X(\mathbf{x}))$</td><td>✓</td><td>✓</td></tr><tr><td>$g(\mathbf{x}) = \operatorname{Tr}(X(\mathbf{x})^{-p})$</td><td>✓</td><td>Not guaranteed</td></tr><tr><td>$k(\mathbf{x}) = \log (\operatorname{Tr}(X(\mathbf{x})^{-p}))$</td><td>Conjecture</td><td>Not guaranteed</td></tr></tbody></table>

## 4. Solution methods

The main goal of this paper is to propose a new solution method for the Optimal and Fusion Problems under the A-criterion and D-criterion based on the novel framework Boscia.jl and assess its performance compared to several other convex MINLP approaches. In the following, we introduce the chosen MINLP solvers and state the necessary conditions and possible reformulations that are needed.

**Branch-and-bound with Frank-Wolfe algorithms (Boscia).** The new framework introduced in Hendrych et al. (2025b) is implemented in the Julia package Boscia.jl. It is a Branch-and-Bound (BnB) framework that utilizes Frank-Wolfe methods to solve the relaxations at the node level. The Frank-Wolfe algorithm (Frank & Wolfe, 1956; Braun et al., 2022), also called Conditional Gradient algorithm (Levitin & Polyak, 1966), and its variants are first-order methods solving problems of the type:

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

where $f$ is a convex, Lipschitz-smooth function and $\mathcal{X}$ is a compact convex set. These methods are especially useful if linear minimization problems over $\mathcal{X}$ can be solved efficiently. The Frank-Wolfe methods used in Boscia.jl are implemented in the Julia package FrankWolfe.jl, see Besançon et al. (2022; 2025).

At each iteration $t$, Frank-Wolfe solves the linear minimization problem over $\mathcal{X}$ taking the current gradient as the linear objective, resulting in a vertex $v_t$ of $\mathcal{X}$. The next iterate $x_{t+1}$ is computed as a convex combination
of the current iterate $x_t$ and the vertex $v_t$. Many Frank-Wolfe variants explicitly store the vertex decomposition of the iterate, henceforth called the active set. We utilize the active set representation to facilitate warm starts in Boscia by splitting the active set when branching.

One novel aspect of Boscia.jl is its use of a *Bounded Mixed-Integer Linear Minimization Oracle (BLMO)* as the *Linear Minimization Oracle (LMO)* in Frank-Wolfe. Typically, the BLMO is a MIP solver but it can also be a combinatorial solver. This leads to more expensive node evaluations but has the benefit that feasible integer points are found from the root node and the feasible region is much tighter than the continuous relaxation for many problems. In addition, Frank-Wolfe methods can be lazified, i.e. calling the LMO at each iteration in the node evaluation can be avoided, see (Braun et al., 2017).

In the case of OEDP, strong lazification is not necessary since the corresponding BLMO is very simple. The feasible region $\mathcal{P}$ is just the scaled probability simplex intersected with integer bounds, which is amenable to efficient linear optimization. Given a linear objective $d$, we first assign $\mathbf{x} = \mathbf{1}$ to ensure that the lower bound constraints are met. Next, we traverse the objective entries in increasing order, adding to the corresponding variable the value of $\max\{u_i - l_i, N - \sum(\mathbf{x})\}$. This way, we ensure that both the upper-bound constraints and the knapsack constraint are satisfied. The LMO over the feasible set can also be cast as a simple network flow problem with $m$ input nodes connected to a single output node, which must receive a flow of $N$ while the edges respect the lower and upper bounds. The scaled probability simplex also allows for a simple heuristic taking a fractional point and outputting an integer feasible point on the probability simplex.

Due to the convexity of the objective, the difference $\langle \nabla f, x_t - v_t \rangle$ is upper bounding the primal gap $f(x_t) - f(x^*)$ at each iteration. We call the quantity the dual gap (or the Frank-Wolfe gap). The dual gap can therefore be used as a stopping criterion. Frank-Wolfe's error adaptiveness can be exploited to a) solve nodes with smaller depth with a coarser precision and b) dynamically stop a node evaluation if the lower bound on the node solution exceeds the incumbent.

Observe that in contrast to the epigraph-based formulation approaches that generate many hyperplanes, this method works with the equivalent of a single supporting hyperplane given by the current gradient and moves this hyperplane until it achieves optimality. It is known that once the optimal solution is found, a single supporting hyperplane can be sufficient to prove optimality (described e.g. for generalized Benders in Sahinidis & Grossmann (1991)). Finding this final hyperplane, however, may require adding many hyperplanes beforehand at suboptimal iterations. In the case of the problems discussed in this paper, the constraint polytope is uni-modular. Adding hyperplanes created from the gradient will not maintain this structure and in consequence, yields a numerically more challenging MIP. Our approach, on the other hand, keeps the polytope and thereby its uni-modularity intact.

A new development during this work was the implementation of a domain oracle in Boscia.jl. As stated earlier, not all points in the feasible region are domain feasible for the objective functions. Thus, we cannot start Boscia (and Frank-Wolfe) at a random point. We therefore added the option of a *domain oracle* and a *domain point function*. The former checks whether a given point is domain feasible, in our case by checking if the associated information matrix is regular. The latter provides a domain feasible point given the feasible region and additional bound constraints from the node. The returned point has to respect the global constraints as well as the node specific constraints. The domain point function is called during branching if the splitting of the active set results in an invalid point. A small projection problem is then solved, also using Frank-Wolfe, to find a new point within the intersection of the feasible region and the domain. Note that we stop the Frank-Wolfe method once we are in the intersection.

For the line search problem within Frank-Wolfe, we utilize the Secant line search which has shown a superior performance for generalized self concordant functions, see Hendrych et al. (2025a).
**Outer approximation (SCIP OA).** Outer Approximation schemes are a popular and well-established way of solving MINLPs (Kronqvist et al., 2019). This approach requires an epigraph formulation of (OEDP):

$$
\begin{array}{ll}
\min_{t, \mathbf{x}} & t \\
\text{s.t.} & t \ge \log (\phi_p(\mathbf{x})) \qquad (\text{E-OEDP}) \\
& \mathbf{x} \in \mathcal{P} \\
& t \in \mathbb{R}, \mathbf{x} \in \mathbb{Z}^m.
\end{array}
$$

This approach approximates the feasible region of (E-OEDP) with linear cuts derived from the gradient of the non-linear constraints, in our case $\nabla f$. Note that this requires the information matrix $X(\mathbf{x})$ at the current iterate $\mathbf{x}$ to be positive definite, otherwise an evaluation of the gradient is not possible or rather it will evaluate to $\infty$. The implementation is done with the Julia wrapper of `SCIP`, (Bestuzheva et al., 2021; 2023). Note that generating cuts that prohibit points leading to singular $X(\mathbf{x})$, we will refer to them as *domain cuts*, is non-trivial. Thus, we are applying this approach to the Fusion Problems only since their information matrix is always positive definite.

**LP/NLP branch-and-bound with direct conic formulation (Direct Conic).** Another Outer Approximation approach, as implemented in Pajarito.jl (Coey et al., 2020), represents the non-linearities as conic constraints. This is particularly convenient in combination with the conic interior point solver Hypatia.jl (Coey et al., 2022b) as it implements the log det cone (the epigraph of the perspective function of log det) directly.

$$
\mathcal{K}_{\log \det} := \operatorname{cl} \left\{ (u, v, W) \in \mathbb{R} \times \mathbb{R}_{>0} \times \mathbb{S}_{++}^n \mid u \le v \log \det(W/v) \right\}
$$

The formulation of (D-Opt) then becomes

$$
\begin{array}{ll}
\max_{t, \mathbf{x}} & t \\
\text{s.t.} & (t, 1, X(\mathbf{x})) \in \mathcal{K}_{\log \det} \\
& \mathbf{x} \in \mathcal{P} \\
& t \in \mathbb{R}, \mathbf{x} \in \mathbb{Z}^m.
\end{array}
$$

For the representation of the trace inverse, we utilize the dual of the separable spectral function cone (Coey et al., 2022a, Section 6):

$$
\mathcal{K}_{\text{sepspec}} := \operatorname{cl} \left\{ (u, v, w) \in \mathbb{R} \times \mathbb{R}_{>0} \times \operatorname{int}(\mathcal{Q}) \mid u \ge v \varphi(w/v) \right\}
$$

For our purposes, $\mathcal{Q}$ is the PSD cone and the spectral function $\varphi$ is the negative square root whose convex conjugate is precisely the trace inverse, see (Coey et al., 2023, Table 1) and (Pilanci et al., 2015, Collary 1)<fnref n="4" />.

$$
\mathcal{K}_{\text{sepspec}}^* := \operatorname{cl} \left\{ (u, v, w) \in \mathbb{R} \times \mathbb{R}_{>0} \times \operatorname{int}(\mathbb{S}_+^n) \mid v \ge u/4 \operatorname{Tr}((w/u)^{-1}) \right\}
$$

The conic formulation of the (A-Opt) is therefore

$$
\begin{array}{ll}
\min_{t, \mathbf{x}} & 4t \\
\text{s.t.} & (1, t, X(\mathbf{x})) \in \mathcal{K}_{\text{sepspec}}^* \\
& \mathbf{x} \in \mathcal{P} \\
& t \in \mathbb{R}, \mathbf{x} \in \mathbb{Z}^m.
\end{array}
$$

Additionally, the conic formulation allows the computation of domain cuts for $\mathbf{x}$. Hence, this solver can be used on all problems. Note that we use HiGHS (Huangfu & Hall, 2018) as a MIP solver within Pajarito.jl.

<footnote n="4">4. For further details, see this discussion Kapelevich (2023).</footnote>
**LP/NLP branch-and-bound with second-order cone formulation (SOCP).** The conic solver from the previous approach was developed fairly recently. A previous conic approach was introduced first in Sagnol (2011) for the continuous case and later extended to the mixed-integer case in Sagnol & Harman (2015). They showed OEDP under the A-criterion and D-criterion can be formulated as a second-order cone program (SOCP). The SOCP model for (D-Opt) is given by

$$ \max_{w,Z,T,J} \prod_{j=1}^{n} (J_{jj})^{\frac{1}{n}} $$

$$ \text{s.t.} \quad \sum_{i=1}^{m} A_i Z_i = J $$

J is a lower triangle matrix

$$ \|Z_i e_j\|^2 \le T_{ij} w_i \quad \forall i \in [m], j \in [n] $$

$$ \sum_{i=1}^{m} T_{ij} \le J_{jj} \quad \forall j \in [n] $$

$$ T_{ij} \ge 0 \quad \forall i \in [m], j \in [n] $$

$$ \sum_{i=1}^{m} w_i = N, \quad w \ge 0 $$

where J is a $n \times n$ matrix, Z and T are $m \times n$ matrices. Observe that the problem size has increased significantly with both the number of variables and number of contraints being $\ge m(2n+1)$.

The SOCP formulation for (A-Opt) is

$$ \min_{w,\mu,Y} \sum_{i=1}^{m} \mu_i $$

$$ \text{s.t.} \quad \sum_{i=1}^{m} A_i Y_i = \sum_{i=1}^{m} \mu_i $$

$$ \|Y_j\|^2 \le \mu_j w_i \quad \forall i \in [m] $$

$$ \mu \ge 0, \quad w \ge 0 $$

$$ \sum_{i=1}^{m} w_i = N $$

where Y is a $m \times n$ matrix and $\mu$ is a $m \times 1$ vector. The problem size does not increase as much, with $m(2+n)$ variables and $3m+2$ constraints.

To solve the SOCP formulation, we again utilize Pajarito.jl with HiGHS as a MIP solver and Hypatia.jl as a conic solver. For the terms involving the norm, we make use of Hypatia.jl's EpiNormEuclCone and EpiPerSquareCone cones which do not require us to deconstruct the norm terms into second order cones.

**A custom branch-and-bound for (OEDP) (Co-BnB).** The most general solver strategy for (OEDP) with matrix means criteria was introduced in Ahipaşaoğlu (2021). Like Boscia.jl, it is a Branch-and-Bound-based approach with a first-order method to solve the node problems. The first-order method in question is a coordinate-descent-like algorithm. As the termination criterion, this method exploits that the objective
function is a matrix mean and shows the connection of the resulting optimization problem

$$
\begin{array}{ll}
\max_{\mathbf{w}} & \log (\phi_p(X(\mathbf{w}))) \\
\text{s.t.} & \sum_{i=1}^{m} w_i = 1 \qquad (\text{M-OEDP}) \\
& \mathbf{w} \ge 0 \\
& w_i N \in \mathbb{Z} \forall i \in [m]
\end{array}
$$

to the generalization of the Minimum Volume Enclosing Ellipsoid Problem (MVEP) (Ahipaşaoğlu, 2021). The variables w can be interpreted as a probability distribution and the number of times the experiments are to be run is wN. Concerning (OEDP), one can say x = wN.

Note first that we have reimplemented the method in Julia and modified it so that we solve the formulation as depicted in (OEDP). Secondly, we have improved and adapted the step size rules within the first-order method, see Appendix B. Note further that the solver was developed for instances with a plethora of experiments and very few parameters. The solver employs the simplest Branch-and-Bound tree, i.e. with the most fractional branching rule and traverses the tree with respect to the minimum lower bound. In the next section, we will see that the method works well in cases where n is small but struggles if the value of n increases.

5. Computational experiments

In this section, we present the computational experiments for the Optimal Problem and Fusion Problem, both under the A- and D-criterion, respectively. The resulting problems will be referred to as the A-Fusion Problem (AF), D-Fusion Problem (DF), A-Optimal Problem (AO), and D-Optimal Problem (DO).

Furthermore, we run the Optimal and Fusion Problems under the GTI-criterion for different values of p using permissible solvers. Lastly, we showcase the performance of Boscia.jl and Co-BnB on problems of large dimension, i.e. number of variables between 300 and 500.

**Experimental setup.** For the instance generation, we choose the number of experiments $m \in \{50, 60, 80, 100, 120\}$, the number of parameters $n \in \lfloor m/4 \rfloor, \lfloor m/10 \rfloor\}$, and the number of allowed experiments $N = \lfloor 1.5n \rfloor$ for the Optimal Problems and $N \in [m/20, m/3]$ for the Fusion Problems. The lower bounds are zero. Note that for the Fusion Problems, the fixed experiments are encoded in a separate matrix. The upper bounds are randomly sampled between 1 and $N/3$ for (A-Opt) and (D-Opt). In the Fusion case, they are sampled between 1 and $m/10$. We generate both independent and correlated experiment data. Also, note that the matrices generated are dense. Seeds used are $[1, 2, 3, 4, 5]$. In total, there are 50 instances for each combination of problem and data set.

Experiments were run on a cluster equipped with Intel Xeon Gold 6338 CPUs running at 2 GHz and a one-hour time limit. The Julia version used is 1.10.2, Boscia.jl v0.1.35, FrankWolfe.jl v0.4.13, HiGHS.jl v1.15.0, Hypatia.jl v0.7.4, Pajarito.jl v0.8.2, SCIP.jl v0.12.3. Note that we use the unregistered package PajaritoExtras.jl to model the dual of the separable spectral function cone. The source code is hosted on GitHub<fnref n="5" />.

**Start solution.** Note that both the objectives (D-Opt) and (A-Opt) are only well defined if the information matrix $X(x)$ has full rank. This is the case for the Fusion Problem, not necessarily for the Optimal Problem. Both Boscia.jl and Co-BnB require a feasible starting point $z_0$. For its construction, we find a set $S \subset [m]$ of $n$ linearly independent experiments, i.e. $n$ linearly independent rows of $A$. Assign those experiments their upper bound. If the sum $\sum z_0$ exceeds $N$, remove 1 from the experiment with the largest entry. If the sum is less than $N$, pick an experiment in $[m]\setminus S$ at random and assign it as many runs as possible. Repeat until the sum is equal to $N$. Note that due to the monotonic progress of both first-order methods, the current iterate will never become domain infeasible, i.e. singular.

<footnote n="5">5. https://github.com/ZIB-IOL/OptimalDesignWithBoscia</footnote>
**Results.** An overview of the results of the computational experiments is given in Table 2 and extensive results can be found in Appendix D. The new framework Boscia.jl shows a superior performance compared to the other methods both in terms of time and number of instances solved to optimality. In comparison to the Outer Approximation methods, for example, it solves nearly twice as many instances.

Co-BnB is the only competitive method. It mostly solves fewer instances than Boscia.jl, the exception being the A-Fusion Problem with both data sets. With independent data, Co-BnB is faster solving the same number of instances. In case of the correlated data set, Co-BnB solves roughly twice as many instances as Boscia.jl. In Table 5, we see that Boscia.jl and Co-BnB have similar magnitudes in number of nodes for both A-Fusion Problems whereas for all other problems Boscia.jl has significantly fewer nodes than Co-BnB. As stated previously, node evaluation in Boscia.jl is more computationally expensive. The fact that the magnitudes of nodes is similar points to the optimal solution being strictly in the interior. Note that in general, Co-BnB fares well for the instances where $n = ⌊m/10⌋$ as it was designed with such problems. It struggles for the instances where $n = ⌊m/4⌋$. In Figure 3, we see that the absolute gap of Co-BnB increasing drastically as the fraction between number of parameters and number experiments grow larger. While Boscia.jl also shows an increase, it is much more moderate. Co-BnB implements no advanced Branch-and-Bound tree specifications like a better traverse strategy or branching strategy. A greater value of $N$ naturally increases the size of the tree and the number of nodes to be processed. Boscia.jl has the advantage here since it finds many integer feasible points while solving the relaxations which have the potential to improve the incumbent. A better incumbent, in turn, lets us prune non-improving nodes early on. Overall, fewer nodes have to be investigated by Boscia.jl.

<figure><img src="image_6.png" /><figcaption>Figure 3: Geometric mean and geometric standard deviation of the absolute gap between the incumbent and lower bound over the conditioning of the problem.</figcaption></figure>

In terms of time, Boscia.jl also shows promising results, especially for instances of larger scale. For small-scale instances, the Outer Approximation approaches are fast, in some cases faster than Boscia.jl. This can be observed in Figures 4 and 5. The plots also highlight that the Outer Approximation Schemes
<figure><img src="image_7.png" /><figcaption>Figure 4: The number of instances solved to optimality over time for the A-Optimal Problem and D-Optimal Problem with both data sets. The upper plots are with the independent data set, the lower ones with correlated data. Note that SCIP+OA is not applicable on the Optimal Problems.</figcaption></figure>

solve fewer instances than the two Branch-and-Bound Approaches. It should be noted that SCIP + OA simply timed out often. On the other hand, the MIP solvers for the conic formulations with *Pajarito.jl* often struggled to solve the resulting MIP problems. SOCP, for example, only solved about a quarter of the instances of the D-Fusion Problem and D-Optimal Problem. In addition, the many solutions provided by SOCP in case of a timeout were not always domain feasible, and thus, the original objective function could not be evaluated at the provided solutions. The superiority of the Branch-and-Bound approaches stems from the fact that the relaxations of both of them keep the simple feasible region intact. Whereas the Outer Approximation schemes add many additional constraints, i.e. cuts, resulting in larger LPs to be solved, see Table 5 for the average number of cuts. Furthermore, these cuts are dense, i.e. have many nonzero entries, leading to an increased difficulty for the LP solvers.

For the (GTI-Opt) Problem, the results are given in Table 3. Note that we used *Boscia.jl* on both the (GTI-Opt) and the (logGTI-Opt), the latter titled as "Boscia Log" in the table. *Boscia.jl* also shows a better performance here than Co-BnB and SCIP + OA. Interestingly, the (logGTI-Opt) objective seems to lead to a better conditioning of the problem. This further motivates an investigation into generalized self-concordance of those objectives.
<figure><img src="image_8.png" /><figcaption>Figure 5: The number of instances solved to optimality over time for the A-Fusion Problem and D-Fusion Problem with both data sets. The upper plots are with the independent data set, the lower ones with correlated data.</figcaption></figure>
In Table 4, we see the relative and absolute gap of Boscia.jl and Co-BnB for instances with sizes from 300 and 500 variables. Boscia.jl showcases better gap values especially for the problems under the D-criterion. Note that almost none of the instances were solved to optimality.

We performed a hyperparameter search for Boscia.jl the results of which can be found in Tables 8 to 10.

Aside from the performance comparison of the solvers, we investigate how the problems themselves compare to each other and if the difficulty of the instances is solver-dependent.

It can be observed in Table 2 that most solvers solve fewer instances under the A-criterion. The notable exception is SOCP on the A-Fusion Problem where it solves more instances to optimality compared to the D-criterion.

Taking a look at some example contour plots shown in Figure 6, we observe that the contour lines for the A-criterion are steeper than those of the D-criterion for both the Optimal Problem and the Fusion Problem, respectively. This points to the conditioning increasing.

<figure><img src="image_9.png" /><figcaption>Figure 6: Example contour plots in two dimensions for objectives of both Optimal Problems with correlated data and both Fusion Problems with independent.</figcaption></figure>

In terms of the data, one could assume that all problems would be easier to solve with independent data. Noticeably, this is not the case, rather, it depends on the problem type. The Fusion Problems are easier to solve with independent data, the Optimal Problems are more often solved with the correlated data. Figures 7a to 7d depict the progress of the incumbent, lower bound, and dual gap within Boscia.jl for selected instances of each combination of problem and data type.

Interestingly, the independent data leads to proof of optimality, i.e. the optimal solution is found early on and the lower bound has to close the gap, regardless of the problem, see Figures 7a and 7c. The difference in problems has, however, an impact on how fast the lower bound can catch up with the incumbent. In the case of the Optimal Problem there is likely a larger region around the optimal solution where the corresponding points/designs x provide roughly the same information. These other candidates have to be checked to ensure the optimality of the incumbent and thus the solving process slows down. Note that Boscia.jl can utilize strong convexity and sharpness of the objective to improve the lower bound. However, the improvement via sharpness is currently only applicable if the optimum is unique which is not the case.

On the other hand, the correlated data leads to solution processes that are very incumbent-driven, i.e. most improvement on the dual gap stems from the improving incumbent, not from the lower bound, as seen in Figures 7b and 7d. Incumbent-driven solution processes can be identified by the dual gap making sudden
jumps and the absence of (a lot of) progress between these jumps. As before, the solution process speed depends on the Problem. In Figure 7b, the dual gap makes big jumps throughout most of the solving process, in contrast to the dual gap Figure 7d. This indicates that the optimal solution of the Fusion Problem is strictly in the interior and thus, will not be found early as a vertex of a relaxation. The key ingredient for improvement in this case will be the incorporation of more sophisticated primal heuristics in Boscia.jl.

Overall, Boscia.jl shows a very promising performance and further research and development will be performed to improve the performance even further.

<table><caption>Table 2: Comparing the performance of Boscia.jl, Pajarito.jl, SCIP, Co-BnB and SOCP on the different problems and the different data sets, i.e. A-Fusion (AF), D-Fusion (DF), A-Optimal (AO) and D-Optimal (DO). One data set contains independent data, the other has correlated data. Shown are the percentage of solved instances and the geometric mean of the solve time (shifted by 1 second) over all instances. Note that there are 50 instances for each problem and data set.
For more extensive results like number of cuts/nodes, see Table 5 in Appendix D.</caption><thead><tr><th rowspan="2">Type</th><th rowspan="2">Corr.</th><th colspan="2">Boscia</th><th colspan="2">Co-BnB</th><th colspan="2">Direct Conic</th><th colspan="2">SOCP</th><th colspan="2">SCIP OA</th></tr><tr><th>% solved</th><th>Time (s)</th><th>% solved</th><th>Time (s)</th><th>% solved</th><th>Time (s)</th><th>% solved</th><th>Time (s)</th><th>% solved</th><th>Time (s)</th></tr></thead><tbody><tr><td>AO</td><td>no</td><td><strong>52 %</strong></td><td><strong>374.74</strong></td><td>48 %</td><td>401.67</td><td>8 %</td><td>2382.52</td><td>20 %</td><td>1578.03</td><td>-</td><td>-</td></tr><tr><td>AO</td><td>yes</td><td><strong>68 %</strong></td><td><strong>227.69</strong></td><td>60 %</td><td>301.8</td><td>20 %</td><td>1515.23</td><td>20 %</td><td>1861.35</td><td>-</td><td>-</td></tr><tr><td>AF</td><td>no</td><td><strong>80 %</strong></td><td>62.83</td><td><strong>80 %</strong></td><td><strong>50.92</strong></td><td>4 %</td><td>2846.5</td><td>26 %</td><td>1686.2</td><td>38 %</td><td>463.65</td></tr><tr><td>AF</td><td>yes</td><td>26 %</td><td>1368.83</td><td><strong>52 %</strong></td><td><strong>311.36</strong></td><td>24 %</td><td>1148.87</td><td>20 %</td><td>2131.81</td><td>14 %</td><td>1480.73</td></tr><tr><td>DO</td><td>no</td><td><strong>68 %</strong></td><td><strong>136.92</strong></td><td>58 %</td><td>216.31</td><td>20 %</td><td>1241.37</td><td>20 %</td><td>2169.4</td><td>-</td><td>-</td></tr><tr><td>DO</td><td>yes</td><td><strong>100 %</strong></td><td><strong>2.56</strong></td><td>70 %</td><td>101.89</td><td>10 %</td><td>1398.01</td><td>10 %</td><td>2526.74</td><td>-</td><td>-</td></tr><tr><td>DF</td><td>no</td><td><strong>94 %</strong></td><td><strong>3.49</strong></td><td>86 %</td><td>22.79</td><td>12 %</td><td>1906.61</td><td>18 %</td><td>2213.03</td><td>50 %</td><td>324.11</td></tr><tr><td>DF</td><td>yes</td><td><strong>60 %</strong></td><td><strong>54.01</strong></td><td>56 %</td><td>153.26</td><td>6 %</td><td>2284.06</td><td>6 %</td><td>2934.61</td><td>28 %</td><td>752.15</td></tr></tbody></table>

## 6. Conclusion

We proposed a new approach for the Optimal Experiment Design Problem based on the Boscia.jl framework and proved convergence of the method on the problems. Our approach exhibits a superior performance compared to other MINLP approaches. In addition, it also outperforms the approach specifically developed for the OEDP, in particular for large-scale instances and a larger number of parameters. This superiority can be explained by the fact that Boscia.jl keeps the structure of the problem intact and that it utilizes a combinatorial solver to find integer feasible points at each node.

## Acknowledgments

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+.
<table><caption>**Table 3:** Comparing the performance of Boscia.jl.SCIAnd Co-BnB on the General-Trace-Inverse (GTI) Optimal Problem and GTI-Fusion (GTIF) Problem for different values of *p* and under independent and correlated data. Note the objective function of Boscia has the form $\phi_p(X(x)) = \text{Tr}(X(x)^{-p})$. The column titled "Boscia Log" shows the runs using log $\phi_p$ as the objective. Shown are the percentage of solved instances and the geometric mean of the solve time (shifted by 1 second) over all instances. Note that there are 30 instances for each problem and data set.
For extensive results, see Tables 6 and 7 in Appendix D.</caption><thead><tr><th rowspan="2">p</th><th rowspan="2">Corr.</th><th colspan="2">Boscia</th><th colspan="2">Boscia Log</th><th colspan="2">Co-BnB</th><th colspan="2">SCIP+OA</th></tr><tr><th>% solved</th><th>Time (s)</th><th>% solved</th><th>Time (s)</th><th>% solved</th><th>Time (s)</th><th>% solved</th><th>Time (s)</th></tr></thead><tbody><tr><td colspan="10"><strong>Optimal Problem</strong></td></tr><tr><td>0.25</td><td>no</td><td>67 %</td><td>162.41</td><td><strong>87 %</strong></td><td><strong>27.13</strong></td><td>50 %</td><td>359.92</td><td>-</td><td>-</td></tr><tr><td>0.25</td><td>yes</td><td>67 %</td><td>110.25</td><td><strong>77 %</strong></td><td><strong>85.83</strong></td><td>60 %</td><td>264.22</td><td>-</td><td>-</td></tr><tr><td>0.5</td><td>no</td><td>53 %</td><td>246.61</td><td><strong>70 %</strong></td><td><strong>85.87</strong></td><td>50 %</td><td>430.08</td><td>-</td><td>-</td></tr><tr><td>0.5</td><td>yes</td><td><strong>60 %</strong></td><td><strong>129.86</strong></td><td>57 %</td><td>245.36</td><td>57 %</td><td>313.7</td><td>-</td><td>-</td></tr><tr><td>0.75</td><td>no</td><td>37 %</td><td>799.73</td><td>43 %</td><td>505.86</td><td><strong>50 %</strong></td><td><strong>471.95</strong></td><td>-</td><td>-</td></tr><tr><td>0.75</td><td>yes</td><td>47 %</td><td>541.67</td><td>43 %</td><td>557.15</td><td><strong>50 %</strong></td><td><strong>357.77</strong></td><td>-</td><td>-</td></tr><tr><td>1.5</td><td>no</td><td>43 %</td><td>659.25</td><td>40 %</td><td><strong>576.51</strong></td><td><strong>50 %</strong></td><td>619.95</td><td>-</td><td>-</td></tr><tr><td>1.5</td><td>yes</td><td>47 %</td><td>418.43</td><td><strong>53 %</strong></td><td><strong>306.7</strong></td><td>47 %</td><td>506.3</td><td>-</td><td>-</td></tr><tr><td>2.0</td><td>no</td><td>43 %</td><td>661.29</td><td><strong>50 %</strong></td><td><strong>562.4</strong></td><td><strong>50 %</strong></td><td>630.18</td><td>-</td><td>-</td></tr><tr><td>2.0</td><td>yes</td><td>43 %</td><td>644.53</td><td><strong>53 %</strong></td><td><strong>297.98</strong></td><td>47 %</td><td>611.8</td><td>-</td><td>-</td></tr><tr><td colspan="10"><strong>Fusion Problem</strong></td></tr><tr><td>0.25</td><td>no</td><td>90 %</td><td>6.57</td><td><strong>100 %</strong></td><td><strong>1.71</strong></td><td>50 %</td><td>725.52</td><td>47 %</td><td>376.08</td></tr><tr><td>0.25</td><td>yes</td><td>53 %</td><td><strong>138.78</strong></td><td><strong>57 %</strong></td><td>184.83</td><td>27 %</td><td>1449.73</td><td>27 %</td><td>927.92</td></tr><tr><td>0.5</td><td>no</td><td>87 %</td><td>9.1</td><td><strong>90 %</strong></td><td><strong>3.63</strong></td><td>47 %</td><td>787.45</td><td>43 %</td><td>349.14</td></tr><tr><td>0.5</td><td>yes</td><td><strong>57 %</strong></td><td><strong>175.85</strong></td><td>53 %</td><td>271.12</td><td>30 %</td><td>1547.49</td><td>20 %</td><td>850.41</td></tr><tr><td>0.75</td><td>no</td><td>70 %</td><td>85.39</td><td><strong>87 %</strong></td><td><strong>42.47</strong></td><td>57 %</td><td>353.3</td><td>43 %</td><td>415.34</td></tr><tr><td>0.75</td><td>yes</td><td>37 %</td><td>741.57</td><td><strong>43 %</strong></td><td><strong>434.78</strong></td><td>27 %</td><td>1639.63</td><td>23 %</td><td>1053.8</td></tr><tr><td>1.5</td><td>no</td><td><strong>77 %</strong></td><td><strong>91.83</strong></td><td>67 %</td><td>129.57</td><td>47 %</td><td>780.56</td><td>40 %</td><td>406.94</td></tr><tr><td>1.5</td><td>yes</td><td>37 %</td><td>715.74</td><td><strong>50 %</strong></td><td><strong>214.97</strong></td><td>30 %</td><td>1415.97</td><td>23 %</td><td>885.83</td></tr><tr><td>2.0</td><td>no</td><td><strong>73 %</strong></td><td><strong>96.28</strong></td><td>70 %</td><td>117.1</td><td>57 %</td><td>797.56</td><td>40 %</td><td>402.28</td></tr><tr><td>2.0</td><td>yes</td><td>33 %</td><td>905.59</td><td><strong>53 %</strong></td><td><strong>202.0</strong></td><td>33 %</td><td>1305.28</td><td>20 %</td><td>923.45</td></tr></tbody></table>

<table><caption>**Table 4:** Comparing Boscia and Co-BnB on large instances. The dimensions are *m* = 300, 400, 500. We showcase only the absolute and relative gap. Note that the majority of the instances were solved to optimality. Boscia solved 3 instances of the D-Fusion Problem with independent data. The relative gap and the absolute gap are computed for the instances on which at least one method did not terminate within the time limit. That means it excludes the instances on which all methods terminated. The "log" prefix indicates that Boscia was used with the log Tr objective.</caption><thead><tr><th rowspan="2">Problem</th><th rowspan="2">Corr.</th><th rowspan="2"># inst.</th><th colspan="2">Boscia</th><th colspan="2">Co-BnB</th></tr><tr><th>relative gap</th><th>absolute gap</th><th>relative gap</th><th>absolute gap</th></tr></thead><tbody><tr><td>A</td><td>no</td><td>12</td><td>188.2483</td><td><strong>3.8117</strong></td><td><strong>2.4036</strong></td><td>5.2537</td></tr><tr><td>A</td><td>yes</td><td>12</td><td>Inf</td><td><strong>0.0024</strong></td><td>Inf</td><td>5.8384</td></tr><tr><td>AF</td><td>no</td><td>12</td><td><strong>0.2243</strong></td><td><strong>0.0019</strong></td><td>0.9264</td><td>1.0258</td></tr><tr><td>AF</td><td>yes</td><td>12</td><td>Inf</td><td><strong>0.0049</strong></td><td>Inf</td><td>5.6742</td></tr><tr><td>log A</td><td>no</td><td>12</td><td>2.4047</td><td>5.2608</td><td>2.4036</td><td><strong>5.2537</strong></td></tr><tr><td>log A</td><td>yes</td><td>12</td><td>Inf</td><td><strong>5.6258</strong></td><td>Inf</td><td>5.8384</td></tr><tr><td>log AF</td><td>no</td><td>12</td><td>1.0491</td><td>2.6105</td><td><strong>0.9264</strong></td><td><strong>1.0258</strong></td></tr><tr><td>log AF</td><td>yes</td><td>12</td><td><strong>0.0955</strong></td><td>6.9323</td><td>Inf</td><td><strong>5.6742</strong></td></tr><tr><td>DF</td><td>no</td><td>12</td><td><strong>0.0169</strong></td><td><strong>0.01</strong></td><td>Inf</td><td>38.0805</td></tr><tr><td>DF</td><td>yes</td><td>12</td><td><strong>0.9819</strong></td><td><strong>0.4054</strong></td><td>Inf</td><td>343.1067</td></tr><tr><td>D</td><td>no</td><td>12</td><td><strong>0.2295</strong></td><td><strong>0.1577</strong></td><td>Inf</td><td>69.0189</td></tr><tr><td>D</td><td>yes</td><td>12</td><td><strong>0.4642</strong></td><td><strong>0.091</strong></td><td>673.4528</td><td>73.5618</td></tr></tbody></table>
<figure><img src="image_10.png" /><figcaption>(a) D-Optimal Problem with independent data and $n = 10$</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>(b) D-Optimal Problem with correlated data and $n = 10$</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>(c) A-Fusion Problem with independent data and $n = 10$</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>(d) A-Fusion Problem with correlated data and $n = 25$</figcaption></figure>

<caption>Figure 7: Progress of the incumbent and the lower bound on the left and progress of the absolute gap on the right. All instances have 100 variables.</caption>
References

Ahipaşaoğlu, S. D. A first-order algorithm for the A-optimal experimental design problem: a mathematical programming approach. *Statistics and Computing*, 25(6):1113–1127, 2015.

Ahipaşaoğlu, S. D. A branch-and-bound algorithm for the exact optimal experimental design problem. *Statistics and Computing*, 31(5):65, 2021.

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., Designolle, S., Halbey, J., Hendrych, D., Kuzinowicz, D., Pokutta, S., Troppens, H., Herrmannsdoerfer, D. V., and Wirth, E. Improved algorithms and novel applications of the frankwolfe. jl library. *arXiv preprint arXiv:2501.14613*, 2025.

Bestuzheva, K., Besançon, M., Chen, W.-K., Chmiela, A., Donkiewicz, T., van Doornmalen, J., Eifler, L., Gaul, O., Gamrath, G., Gleixner, A., Gottwald, L., Graczyk, C., Halbig, K., Hoen, A., Hojny, C., van der Hulst, R., Koch, T., Lübbecke, M., Maher, S. J., Matter, F., Mühmer, E., Müller, B., Pfetsch, M. E., Rehfeldt, D., Schlein, S., Schlösser, F., Serrano, F., Shinano, Y., Sofranac, B., Turner, M., Vigerske, S., Wegscheider, F., Wellner, P., Weninger, D., and Witzig, J. The SCIP Optimization Suite 8.0, 2021.

Bestuzheva, K., Besançon, M., Chen, W.-K., Chmiela, A., Donkiewicz, T., van Doornmalen, J., Eifler, L., Gaul, O., Gamrath, G., Gleixner, A., et al. Enabling research through the SCIP Optimization Suite 8.0. *ACM Transactions on Mathematical Software*, 49(2):1–21, 2023.

Braun, G., Pokutta, S., and Zink, D. Lazifying conditional gradient algorithms. In *International conference on machine learning*, pp. 566–575. PMLR, 2017.

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.

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.

Chen, Z., Fampa, M., and Lee, J. Generalized scaling for the constrained maximum-entropy sampling problem. *Mathematical Programming*, pp. 1–40, 2024.

Coey, C., Lubin, M., and Vielma, J. P. Outer approximation with conic certificates for mixed-integer convex problems. *Mathematical Programming Computation*, 12(2):249–293, 2020.

Coey, C., Kapelevich, L., and Vielma, J. P. Performance enhancements for a generic conic interior point algorithm. *Mathematical Programming Computation*, 2022a. doi: https://doi.org/10.1007/s12532-022-00226-0.

Coey, C., Kapelevich, L., and Vielma, J. P. Solving natural conic formulations with Hypatia.jl. *INFORMS Journal on Computing*, 34(5):2686–2699, 2022b. doi: https://doi.org/10.1287/ijoc.2022.1202.

Coey, C., Kapelevich, L., and Vielma, J. P. Conic optimization with spectral functions on euclidean jordan algebras. *Mathematics of Operations Research*, 48(4):1906–1933, 2023.

de Aguiar, P. F., Bourguignon, B., Khots, M., Massart, D., and Phan-Than-Luu, R. D-optimal designs. *Chemometrics and intelligent laboratory systems*, 30(2):199–210, 1995.

Fampa, M. and Lee, J. *Maximum-Entropy Sampling: Algorithms and Application*. Springer Nature, 2022.

Fang, Y., Loparo, K. A., and Feng, X. Inequalities for the trace of matrix product. *IEEE Transactions on Automatic Control*, 39(12):2489–2490, 1994.
Frank, M. and Wolfe, P. An algorithm for quadratic programming. *Naval research logistics quarterly*, 3(1-2): 95-110, 1956.

Hendrych, D., Besançon, M., Martínez-Rubio, D., and Pokutta, S. Secant line search for frank-wolfe algorithms. *PMLR*, 2025a.

Hendrych, D., Troppens, H., Besançon, M., and Pokutta, S. Convex mixed-integer optimization with Frank-Wolfe methods. *Mathematical Programming Computation*, 2025b.

Horn, R. A. The Hadamard product. In *Proc. Symp. Appl. Math*, volume 40, pp. 87–169, 1990.

Huangfu, Q. and Hall, J. Parallelizing the dual revised simplex method. *Mathematical Programming Computation*, 10(1):119–142, 2018.

Kapelevich, L. How to optimize trace of matrix inverse with JuMP or Convex? https://discourse.julialang.org/t/how-to-optimize-trace-of-matrix-inverse-with-jump-or-convex/94167/6, accessed 4th December 2023, 2023.

Kronqvist, J., Bernal, D. E., Lundell, A., and Grossmann, I. E. A review and comparison of solvers for convex MINLP. *Optimization and Engineering*, 20:397–455, 2019.

Levitin, E. S. and Polyak, B. T. Constrained minimization methods. *USSR Computational mathematics and mathematical physics*, 6(5):1–50, 1966.

Li, Y. Strong formulations and algorithms for regularized a-optimal design. *arXiv preprint arXiv:2505.14957*, 2025.

Li, Y., Fampa, M., Lee, J., Qiu, F., Xie, W., and Yao, R. D-optimal data fusion:: Exact and approximation algorithms. *INFORMS Journal on Computing*, 36(1):97–120, 2024.

Merikoski, J. K. and Virtanen, A. Bounds for eigenvalues using the trace and determinant. *Linear algebra and its applications*, 264:101–108, 1997.

Nesterov, Y. and Nemirovskii, A. *Interior-point polynomial algorithms in convex programming*. SIAM, 1994.

Nikolov, A., Singh, M., and Tantipongpipat, U. Proportional volume sampling and approximation algorithms for A-optimal design. *Mathematics of Operations Research*, 47(2):847–877, 2022.

Pilanci, M., Wainwright, M. J., and El Ghaoui, L. Sparse learning via boolean relaxations. *Mathematical Programming*, 151(1):63–87, 2015.

Ponte, G., Fampa, M., and Lee, J. Computing d-optimal solutions for huge-scale linear and quadratic response-surface models. *arXiv preprint arXiv:2309.04009*, 2023.

Ponte, G., Fampa, M., and Lee, J. Convex relaxation for the generalized maximum-entropy sampling problem. In *22nd International Symposium on Experimental Algorithms*, 2024.

Ponte, G., Fampa, M., and Lee, J. Branch-and-bound for D-optimality with fast local search and variable-bound tightening. *Mathematical Programming*, pp. 1–38, 2025.

Pukelsheim, F. *Optimal design of experiments*. SIAM, 2006.

Sagnol, G. *Optimal design of experiments with application to the inference of traffic matrices in large networks: second order cone programming and submodularity*. PhD thesis, École Nationale Supérieure des Mines de Paris, 2010.

Sagnol, G. Computing optimal designs of multiresponse experiments reduces to second-order cone programming. *Journal of Statistical Planning and Inference*, 141(5):1684–1708, 2011.
Sagnol, G. and Harman, R. Computing exact D-optimal designs by mixed integer second-order cone programming. *The Annals of Statistics*, 43(5):2198–2224, 2015.

Sahinidis, N. and Grossmann, I. E. Convergence properties of generalized benders decomposition. *Computers & Chemical Engineering*, 15(7):481–491, 1991.

Sun, T. and Tran-Dinh, Q. Generalized self-concordant functions: a recipe for Newton-type methods. *Mathematical Programming*, 178(1-2):145–213, 2019.

Tsuji, K., Tanaka, K., and Pokutta, S. Sparser kernel herding with pairwise conditional gradients without swap steps. *arXiv preprint arXiv:2110.12650*, 2021.

Welch, W. J. Branch-and-bound search for experimental designs based on D optimality and other criteria. *Technometrics*, 24(1):41–48, 1982.

Weyl, H. Das asymptotische Verteilungsgesetz der Eigenwerte linearer partieller Differentialgleichungen (mit einer Anwendung auf die Theorie der Hohlraumstrahlung). *Mathematische Annalen*, 71(4):441–479, 1912.

Xu, L. and Liberti, L. Submodular maximization and its generalization through an intersection cut lens. *Mathematical Programming*, pp. 1–37, 2024.

Zhao, R. New analysis of an away-step Frank-Wolfe method for minimizing log-homogeneous barriers. *Mathematics of Operations Research*, 2025.
# Appendix A. Additional proofs and calculations

Note that the following lemmas and the proofs are not new but they are stated here for completeness.

## A.1 General power of a matrix

To start, we present some smaller statements about the power of a matrix. These are used in the consequent proofs.

**Lemma 5.** Let $X \in \mathbb{R}^{n \times n}$ be an invertible, symmetric matrix. Then, the logarithm $\log(X)$ is symmetric.

*Proof.* Let $V$ denote the matrix consisting of eigenvectors of $X$. Observe that $V$ is an orthogonal matrix and w.l.o.g. we assume $V$ is scaled such that it is orthonormal. Next, let $D$ denote the diagonal matrix whose entries are the eigenvalues of $X$. The logarithm of $X$ is then defined as

$$\log(X) = V \log(D) V^{-1}$$

where $\log(D)$ is the diagonal matrix with logarithms of the eigenvalues. In our case, $V$ is orthonormal, so $V^{-1} = V^{\top}$. Hence,

$$\log(X)^{\top} = (V \log(D) V^{\top})^{\top} = V \log(D) V^{\top} = \log(X)$$

□

**Lemma 6.** Let $X \in \mathbb{R}^{n \times n}$ by an invertible matrix and $r \in \mathbb{R}$. Then, the eigenvalues of the power matrix are

$$\lambda_i(X^r) = \lambda_i(X)^r \quad \forall i = [n]$$

and the eigenvectors of the power matrix are the same as those of $X$.

*Proof.* Let $v$ be an eigenvector of $X$ and let $\lambda_v$ denote the corresponding eigenvalue.

$$X^r v = \left( \sum_{k=0}^{\infty} \frac{r^k}{k!} \log(X)^k \right) v = \sum_{k=0}^{\infty} \frac{r^k}{k!} \log(X)^k v$$

For any square matrix $A$ and a natural number $m \in \mathbb{N}$, we have that $A^m v = \lambda_v(A)^m v$. Also, the logarithm of a matrix $A$ has the same eigenvectors as the original and its eigenvalues are $\log(\lambda_i(A))$.

$$\begin{aligned} &= \left( \sum_{k=0}^{\infty} \frac{r^k \log(\lambda_v(X))^k}{k!} \right) v = \exp(r \log(\lambda_v(X)))v \\ &= \lambda_v(X)^r v \end{aligned}$$

This concludes the proof.

□

Combining Lemma 5 and Lemma 6, we get the following corollary.

**Corollary 2.** For $r \in \mathbb{R}$, if $X \in S_{++}^n$, then $X^r \in S_{++}^n$.

**Lemma 7.** Let $r \in \mathbb{R}$ and let the matrix $X$ be diagonalizable. Let $f(X) = \text{Tr}(X^r)$. The gradient of $f$ is then

$$\nabla f(x) = r X^{r-1}$$

*Proof.* We use the definition of $X^r$ to prove the result.

$$\text{Tr}(X^r) = \text{Tr} \left( \sum_{k=0}^{\infty} \frac{r^k}{k!} \log(X)^k \right) = \sum_{k=0}^{\infty} \frac{r^k}{k!} \text{Tr} \left( \log(X)^k \right)$$
Thus, using the sum rule, $(\mathrm{Tr}(X^n))' = nX^{n-1}$ for any positive integer $n$ and $\nabla \mathrm{Tr}(\log(X)) = X^{-1}$, we have

$$
\begin{align*}
\nabla \mathrm{Tr}(X^r) &= \sum_{k=1}^{\infty} \frac{r^k}{k!} k \log(X)^{k-1} X^{-1} \\
&= r X^{-1} \sum_{k=0}^{\infty} \frac{r^k}{k!} \log(X)^k \\
&= r X^{-1} X^r = r X^{r-1}
\end{align*}
$$

This concludes the proof.

**Lemma 8.** For $X \in \mathbb{S}_{++}^n$, we have $X^{-p} = (X^{-1})^p$.

Proof.

$$
\begin{align*}
(X^{-1})^p &= \sum_{k=0}^{\infty} \frac{p^k}{k!} \log (X^{-1})^k \\
\log (X^{-1}) &= V \log(D^{-1}) V^\top = -V \log(D) V^\top = -\log(X) \\
(X^{-1})^p &= \sum_{k=0}^{\infty} \frac{p^k}{k!} (-\log(X))^k \\
&= \sum_{k=0}^{\infty} \frac{(-p)^k}{k!} \log(X)^k \\
&= X^{-p}
\end{align*}
$$

**Remark.** On the contrary, $(X^p)^{-1} \neq X^{-p}$ in general.

## A.2 Convexity of the objectives

In this subsection, we present the convexity proofs for all the considered objectives. Note that concavity of the log det is well known and is stated here for completeness.

**Lemma 9.** The function $f(X) = -\log \det(X)$ is convex for $X \in \mathbb{S}_{++}^n$.

*Proof.* Let $A \in \mathbb{S}_{++}^n$, $B \in \mathbb{S}$ and $t \in \mathbb{R}$ such that $A + tB \in \mathbb{S}_{++}^n$. We define $h(t) = -\log \det (A + tB)$.

$$
\begin{align*}
-\log \det(A + tB) &= -\log \det \left(A^{\frac{1}{2}} A^{\frac{1}{2}} + t A^{\frac{1}{2}} A^{-\frac{1}{2}} B A^{-\frac{1}{2}} A^{\frac{1}{2}}\right) \\
&= -\log \det \left(A^{\frac{1}{2}} \left(I + t A^{-\frac{1}{2}} B A^{-\frac{1}{2}}\right) A^{\frac{1}{2}}\right) \\
&= -\log \det(A) - \log \det \left(I + t A^{-\frac{1}{2}} B A^{-\frac{1}{2}}\right)
\end{align*}
$$

Observe that $I + tA^{-\frac{1}{2}}BA^{-\frac{1}{2}}$ is a positive definite matrix and its eigenvalues are $1 + t\lambda_i$ with $\lambda_i$ being the $i$-th eigenvalue of $A^{-\frac{1}{2}}BA^{-\frac{1}{2}}$. Note that this also means $1 + t\lambda_i > 0$.

$$
\begin{align*}
&= -\log \det(A) - \log \left( \prod_{i=1}^{n} (1 + t\lambda_i) \right) \\
&= -\log \det(A) - \sum_{i=1}^{n} \log (1 + t\lambda_i)
\end{align*}
$$
The first and second derivatives of g are

$$
\begin{align*}
h'(t) &= -\sum_{i=1}^{n} \frac{1}{1 + t\lambda_i}\lambda_i \\
h''(t) &= \sum_{i=1}^{n} \frac{\lambda_i^2}{(1 + t\lambda_i)} \\
&> 0 \quad \forall t
\end{align*}
$$

Thus, f(X) is convex.

**Lemma 10.** The function $g(X) = \mathrm{Tr}(X^{-p})$ is convex for $X \in \mathbb{S}_{++}^n$ and $p > 0$.

Proof. Let $A \in \mathbb{S}_{++}^n$, $B \in \mathbb{S}$ and $t \in \mathbb{R}$ such that $A + tB \in \mathbb{S}_{++}^n$. We define $h(t) = \mathrm{Tr}((A + tB)^{-p})$.

$$
\begin{align*}
h(t) &= \mathrm{Tr}((A + tB)^{-p}) \\
&= \mathrm{Tr}(( (A + tB)^{-1} )^p)
\end{align*}
$$

Using Lemma 7 for the derivative yields

$$
\begin{align*}
h'(t) &= \operatorname{Tr} \left( p \left( (A+tB)^{-1} \right)^{p-1} (-1) (A+tB)^{-1} B(A+tB)^{-1} \right) \\
&= -p \operatorname{Tr} \left( \left( (A+tB)^{-1} \right)^p B(A+tB)^{-1} \right) \\
h''(t) &= -p \operatorname{Tr} \left( p \left( (A+tB)^{-1} \right)^{p-1} (-1) (A+tB)^{-1} B(A+tB)^{-1} B(A+tB)^{-1} \right. \\
&\qquad \left. + \left( (A+tB)^{-1} \right)^p B(-1) (A+tB)^{-1} B(A+tB)^{-1} \right) \\
&= p \operatorname{Tr} \left( (p+1) \left( (A+tB)^{-1} \right)^p B(A+tB)^{-1} B(A+tB)^{-1} \right)
\end{align*}
$$

Restricting $h''$ to $t=0$ yields

$$
h''(t)|_{t=0} = p(p+1) \operatorname{Tr} (A^{-p}BA^{-1}BA^{-1}).
$$

For the third derivative, we have

$$
\begin{align*}
h'''(t) &= p(p+1) \operatorname{Tr} \left( p \left( (A+tB)^{-1} \right)^{p-1} (-1)(A+tB)^{-1} B(A+tB)^{-1} B(A+tB)^{-1} B(A+tB)^{-1} \right. \\
&\qquad \left. + 2 \left( (A+tB)^{-1} \right)^p (-1) B(A+tB)^{-1} B(A+tB)^{-1} B(A+tB)^{-1} \right) \\
h'''(t) &= -p(p+1)(p+2) \operatorname{Tr} \left( (A+tB)^{-p} B(A+tB)^{-1} B(A+tB)^{-1} B(A+tB)^{-1} \right) \\
h'''(t)|_{t=0} &= -p(p+1)(p+2) \operatorname{Tr} \left( A^{-p} B A^{-1} B A^{-1} B A^{-1} \right)
\end{align*}
$$
By Corollary 2, $A^{-p}$ is positive definite and thus, has a unique root $A^{-p/2}$. Using the traces cyclic property, we find

$$ 
\begin{aligned}
h''(t)|_{t=0} &= p(p+1) \operatorname{Tr} \left( A^{-\frac{p+1}{2}} BA^{-1} BA^{-\frac{p+1}{2}} \right) \\
&= p(p+1) \sum_{i=1}^{n} \lambda_i \left( A^{-\frac{p+1}{2}} BA^{-1} BA^{-\frac{p+1}{2}} \right) \\
&\geq 0
\end{aligned}
$$

The last inequality holds because the matrix $A^{-\frac{p+1}{2}} BA^{-1} BA^{-\frac{p+1}{2}}$ is positive definite by positive definiteness of A, B and $A^{-p}$. Thus, $g(X)$ is convex. $\square$

**Lemma 11.** The function $k(X) = \log (\operatorname{Tr}(X^{-p}))$ is convex on $\mathbb{S}_{++}^n$ for $p > 0$.

*Proof.* Let $A \in \mathbb{S}_{++}^n$, $B \in \mathbb{S}^n$ and $t \in \mathbb{R}$ s.t. $A+tB \in \mathbb{S}_{++}^n$. We define $h(t) = k(A+tB) = \log (\operatorname{Tr}((A+tB)^{-p}))$.

$$ 
\begin{aligned}
h(t) &= \log (\operatorname{Tr}((A+tB)^{-p})) \\
h'(t) &= -\frac{p}{\operatorname{Tr}((A+tB)^{-p})} \operatorname{Tr}((A+tB)^{-p-1}B) \\
h''(t) &= p \frac{(p+1) \operatorname{Tr}((A+tB)^{-p-2}BB) \operatorname{Tr}((A+tB)^{-p}) - p \operatorname{Tr}((A+tB)^{-p-1}B)^2}{\operatorname{Tr}((A+tB)^{-p})^2}
\end{aligned}
$$

Restricting us to zero, we get

$$ h''(t)|_{t=0} = p \frac{(p+1) \operatorname{Tr}(A^{-p-2}BB) \operatorname{Tr}(A^{-p}) - p \operatorname{Tr}(A^{-p-1}B)^2}{\operatorname{Tr}(A^{-p})^2} $$

By assumption, $p$ is positive as is the denominator. For the nominator, we use the Cauchy Schwartz inequality $\operatorname{Tr}(XY\tau)^2 \leq \operatorname{Tr}(XX\tau)\operatorname{Tr}(YY\tau)$ and set $X = A^{-p/2}$ and $Y = A^{-\frac{p+2}{2}}B$

$$ h''(t)|_{t=0} \geq 0 $$

Thus, $k(X)$ is convex.

$\square$

## A.3 Additional smoothness proofs

In following, we show that all the considered functions are L-smooth if we can bound the minimum eigenvalue of the input matrix from below.

**Lemma 12.** The function $f(X) := -\log \det(X)$ is L-smooth on $D := \{X \in \mathbb{S}_{++}^n \mid \delta \leq \lambda_{\min}(X)\}$ with $L \geq \frac{1}{\delta^2}$.

*Proof.* Let $A\mathbb{S}_{++}^n$, $B \in \mathbb{S}^n$ and $t \in [0, 1]$. Then we can define $h(t) = -\log \det(A+tB)$. By Lemma 9, $f(X)$ is convex and the second derivative of $h$ is given by

$$ h''(t) = \sum_{i=1}^{n} \frac{\lambda_i (A^{-1/2}BA^{-1/2})^2}{1 + t\lambda_i (A^{-1/2}BA^{-1/2})} $$

It is sufficient to show that $h''(t)|_{t=0} \leq L$ to argue smoothness for $f$.

$$ h''(t)|_{t=0} = \sum_{i=1}^{n} \lambda_i (A^{-1/2}BA^{-1/2})^2 $$
By using a similar idea to Lemma 16, we find

$$
\begin{align*}
&\leq \sum_{i=1}^{n} \lambda_{\max} (A^{-1})^2 \lambda_i (B)^2 \\
&= \lambda_{\max} (A^{-1})^2 \mathrm{Tr}(B^2) \\
&= \lambda_{\max} (A^{-1})^2 \|B\|_F^2
\end{align*}
$$

W.l.o.g. let $\|B\|_F = 1$.

$$
\begin{align*}
&= \frac{1}{\lambda_{\min}(A)^2} \\
&\geq \frac{1}{\delta^2} \\
&= L
\end{align*}
$$

Thus, the function $f$ is smooth at any point $A \in D$.

<figure><img src="image_14.png" /></figure>

**Lemma 13.** For $p \in \mathbb{R}_{>0}$, the function $g(X) := \mathrm{Tr}(X^{-p})$ is $L$-smooth on the domain $D := \{X \in \mathbb{S}_{++}^n \mid \delta \le \lambda_{\min}(X)\}$ with

$$
L \geq \frac{p(p+1)}{\delta^{p+2}}.
$$

Proof. Let $A \in D$ and $B \in \mathbb{S}^n$ and $t \in [0, 1]$. Define $h(t) = \mathrm{Tr}((A + tB)^{-p})$. In Lemma 10 the proof for convexity of $g(X)$ is presented. There one can also find the calculation for $h''(t)|_{t=0}$.

$$
h''(t)|_{t=0} = p(p+1) \mathrm{Tr} \left( A^{-p} B A^{-1} B A^{-1} \right).
$$

Since $A^{-p}$ is positive definite by Corollary 2 and the trace is cyclic, we have

$$
= p(p+1) \mathrm{Tr} \left( A^{-\frac{p+2}{2}} B B A^{-\frac{p+2}{2}} \right)
$$

Note that $BB$ is positive semi-definite. Thus, we can use the bound in Fang et al. (1994).

$$
\begin{align*}
&\leq p(p+1)\lambda_{\max} (A^{-(p+2)}) \mathrm{Tr}(BB) \\
&= p(p+1)\lambda_{\max} (A^{-(p+2)}) \|B\|_F^2
\end{align*}
$$

W.l.o.g. let $\|B\|_F = 1$.

$$
\begin{align*}
&= \frac{p(p+1)}{\lambda_{\min}(A^{p+2})} \\
&\geq \frac{p(p+1)}{\delta^{p+2}}
\end{align*}
$$

Thus, $g$ is smooth with $L = \frac{p(p+1)}{\delta^{p+2}}$.

<figure><img src="image_15.png" /></figure>

**Lemma 14.** The function $k(X) = \log (\mathrm{Tr}(X^{-p}))$ is smooth on $D := \{X \in \mathbb{S}_{++}^n \mid \alpha I \ge X \ge \delta I\}$.
Proof. Let $A \in \mathbb{S}_{++}^n$, $B \in \mathbb{S}^n$ and $t \in \mathbb{R}$ s.t. $A+tB \in \mathbb{S}_{++}^n$. We define $h(t) = k(A+tB) = \log(\mathrm{Tr}((A+tB)^{-p}))$. By Lemma 11, we have

$$
\begin{align*}
h''(t)|_{t=0} &= p \frac{(p+1) \mathrm{Tr}(A^{-p-2}BB) \mathrm{Tr}(A^{-p}) - p \mathrm{Tr}(A^{-p-1}B)^2}{\mathrm{Tr}(A^{-p})^2} \\
&\le p \frac{(p+1) \mathrm{Tr}(A^{-p}) \mathrm{Tr}(A^{-p-2}BB)}{\mathrm{Tr}(A^{-p})^2} \\
&= p(p+1) \frac{\sum_{i=1}^n \lambda_i (A^{-p-2}BB)}{\mathrm{Tr}(A^{-p})}
\end{align*}
$$

Note that *BB* is PSD. The proof of Lemma 16 can be adapted for one of matrices being symmetric and the
other positive definite.

$$
\le p(p+1) \frac{\lambda_{\max} (A^{-p-2}) \mathrm{Tr}(BB)}{\mathrm{Tr}(A^{-p})}
$$

Observe that $\mathrm{Tr}(BB) = \|B\|_F^2$. Without loss of generality, we can assume $\|B\|_F = 1$.

$$
\begin{align*}
&\le p(p+1) \frac{\lambda_{\max} (A^{-p-2})}{n \lambda_{\min} (A^{-p})} \\
&= \frac{p(p+1) \lambda_{\max} (A^p)}{n \lambda_{\min} (A^{p+2})} \\
&\le \frac{p(p+1) \alpha^p}{n \delta^{p+2}} \\
&= L
\end{align*}
$$

□

**Remark.** In our case, the minimum eigenvalue is bounded around the optimum. However, it is not bounded in general for our feasible region unless we can introduce domain cuts. Hence, Lemmas 12 and 14 are not straight away useful to us.

A.4 Results on positive semi-definite matrices

We present two known results on the eigenvalues of the sum and product of positive definite matrices for completeness.

**Lemma 15** (Courant-Fischer min-max Theorem). Let $A, B \in \mathbb{R}^{n \times n}$ symmetric matrices and let $\lambda_1(A) \le \cdots \le \lambda_n(A)$ and $\lambda_1(B) \le \cdots \le \lambda_n(B)$ denote their respective eigenvalues in increasing order. Then, we have the following inequalities concerning the eigenvalues of their sum $A+B$:

$$
\lambda_k(A) + \lambda_l(B) \le \lambda_k(A+B) \le \lambda_k(A) + \lambda_l(B) \quad (12)
$$

Proof. Firstly, we know that

$$
\lambda_1(A) \le \frac{\langle A, \mathbf{x} \rangle}{\langle \mathbf{x}, \mathbf{x} \rangle} \le \lambda_n(A) \quad \forall \mathbf{x} \in \mathbb{R}^n \setminus \{0\}.
$$

By Conrad-Fisher Min-Max Theorem, we have

$$
\begin{align*}
\lambda_k(A+B) &= \min_{\substack{F \subset \mathbb{R}^n \\ \dim F = k}} \left( \max_{\mathbf{x} \in F \setminus \{0\}} \frac{\langle (A+B)\mathbf{x}, \mathbf{x} \rangle}{\langle \mathbf{x}, \mathbf{x} \rangle} \right) \\
&= \min_{\substack{F \subset \mathbb{R}^n \\ \dim F = k}} \left( \max_{\mathbf{x} \in F \setminus \{0\}} \frac{\langle A\mathbf{x}, \mathbf{x} \rangle}{\langle \mathbf{x}, \mathbf{x} \rangle} + \frac{\langle B\mathbf{x}, \mathbf{x} \rangle}{\langle \mathbf{x}, \mathbf{x} \rangle} \right).
\end{align*}
$$
Most likely, there will not be an x attaining the maximum simultaneously for summands. Using the above inequality for the eigenvalues, we get

$$
\begin{align*}
&\geq \lambda_1(B) + \min_{\substack{F \subset \mathbb{R}^n \\ \dim F = k}} \left( \max_{\mathbf{x} \in F \setminus \{0\}} \frac{\langle A\mathbf{x}, \mathbf{x} \rangle}{\langle \mathbf{x}, \mathbf{x} \rangle} \right) \\
&= \lambda_1(B) + \lambda_k(A).
\end{align*}
$$

The proof in the other direction follows analogously.

<figure><img src="image_16.png" /></figure>

**Lemma 16.** Let $A, B \in \mathbb{S}_{++}^n$ and let $\lambda_1(A) \le \dots \le \lambda_n(A)$ and $\lambda_1(B) \le \dots \le \lambda_n(B)$ denote their respective eigenvalues in increasing order. Then, we have the following inequalities concerning the eigenvalues of AB:

$$
\lambda_k(A)\lambda_1(B) \le \lambda_k(AB) \le \lambda_k(A)\lambda_n(B) \quad \forall k \in [n]. \tag{13}
$$

Proof. Since A and B are both positive definite, they both have an invertible root, i.e. there exist matrices $\sqrt{A}$ and $\sqrt{B}$ with $A = \sqrt{A}\sqrt{A}$ and $B = \sqrt{B}\sqrt{B}$. Observe that $\lambda_k(AB) = \lambda_k(\sqrt{B}A\sqrt{B})$ and by definition of eigenvalues, we have

$$
\lambda_1(B) \le \frac{\langle B\mathbf{x}, \mathbf{x} \rangle}{\langle \mathbf{x}, \mathbf{x} \rangle} \le \lambda_n(B) \quad \forall \mathbf{x} \in \mathbb{R}^n \setminus \{0\}
$$

. Thus, we find

$$
\begin{align*}
\lambda_k(AB) &= \lambda_k(\sqrt{BA}\sqrt{B}) \\
&= \min_{\substack{F \subset \mathbb{R}^n \\ \dim F = k}} \left( \max_{\mathbf{x} \in F \setminus \{0\}} \frac{\langle \sqrt{B}A\sqrt{B}\mathbf{x}, \mathbf{x} \rangle}{\langle \mathbf{x}, \mathbf{x} \rangle} \right) \\
&= \min_{\substack{F \subset \mathbb{R}^n \\ \dim F = k}} \left( \max_{\mathbf{x} \in F \setminus \{0\}} \frac{\frac{A\sqrt{B}\mathbf{x}, \sqrt{B}\mathbf{x}}{\langle \sqrt{B}\mathbf{x}, \sqrt{B}\mathbf{x} \rangle} \frac{\langle B\mathbf{x}, \mathbf{x} \rangle}{\langle \mathbf{x}, \mathbf{x} \rangle}}{\langle \sqrt{B}\mathbf{x}, \sqrt{B}\mathbf{x} \rangle} \right)
\end{align*}
$$

Using the above inequality for the eigenvalues of B and the fact that the root of B is invertible, we get

$$
\begin{align*}
&\geq \lambda_1(B) \min_{\substack{F \subset \mathbb{R}^n \\ \dim F = k}} \left( \max_{\mathbf{x} \in F \setminus \{0\}} \frac{\langle A\mathbf{x}, \mathbf{x} \rangle}{\langle \mathbf{x}, \mathbf{x} \rangle} \right) \\
&= \lambda_1(B)\lambda_k(A)
\end{align*}
$$

The other side of the statement follows analogously. Note that we technically only use that B is regular. The
matrix A can be positive semi-definite.
□

<figure><img src="image_17.png" /></figure>

**A.5 Notes on the Frobenius norm**

**Lemma 17.** Let $A \in \mathbb{R}^{m \times n}$ and $B \in \mathbb{R}^{n \times p}$. Then,

$$
\sigma_{\min}(A) \|B\|_F \le \|AB\|_F \le \sigma_{\max} \|B\|_F \quad (14)
$$

*Proof.* By the definition of the Frobenius norm, we have

$$
\begin{align*}
\|AB\|_F^2 &= \operatorname{Tr}((AB)^\top AB) \\
&= \operatorname{Tr}(A^\top AB^\top B).
\end{align*}
$$

Note that both $A^\top A$ and $B^\top B$ are positive semi-definite. Thus, we can use the result in Fang et al. (1994):

$$
\begin{align*}
&\geq \lambda_{\min}(A^{\top}A) \operatorname{Tr}(B^{\top}B) \\
&= \sigma_{\min}(A) \|B\|_{F}^{2}.
\end{align*}
$$
The norm is nonnegative in any case and by definition singular values are also nonnegative. Thus, we can take the root and get

$$ \sigma_{\min}(A) \|B\|_F \le \|AB\|_F. $$

The other direction follows analogously.

<figure><img src="image_18.png" /></figure>

## Appendix B. Custom branch-and-bound with coordinate descent for OEDP

In this section, we showcase the changes we made to the solver set-up in Ahipaşaoğlu (2021). Firstly, we state and solve the problems of interest as minimization problems. Secondly, we forgo the $wN \in \mathbb{Z} \forall i \in [m]$ in favor of directly having the variables $x$ to encode if and how often the experiments should be run. The D-Optimal Problem is then stated as

$$ \begin{array}{ll} \min_{\mathbf{x}} & -\log \det ((X(\mathbf{x}))) \\ \text{s.t.} & \sum_{i=1}^{m} x_i = N \\ & \mathbf{x} \ge 0 \\ & x_i \in \mathbb{Z} \forall i \in [m]. \end{array} $$

The A-Optimal Problem is formulated as

$$ \begin{array}{ll} \min_{\mathbf{x}} & \log (\mathrm{Tr}(X^{-1})) \\ \text{s.t.} & \sum_{i=1}^{m} x_i = N \\ & \mathbf{x} \ge 0 \\ & x_i \in \mathbb{Z} \forall i \in [m]. \end{array} $$

Additionally, we have adapted the step size for the A-Optimal Problem. For the update in the objective, we get

$$ -\log(\mathrm{Tr}(X(\mathbf{x}_+))) = -\log(\mathrm{Tr}(X(\mathbf{x})^{-1})) - \frac{\theta A + \theta^2 B}{1 + \theta C - \theta^2 D} $$

compare Ahipaşaoğlu (2021, Section 4.2). The constant $A$, $B$, $C$ and $D$ are defined as

$$ \begin{align*} A &= \zeta_j - \zeta_k \\ B &= 2\omega_{jk}\zeta_{jk} - \omega_j\zeta_k - \omega_k\zeta_j \\ C &= \omega_j - \omega_k \\ D &= \omega_j\omega_k - \omega_{jk}^2 \end{align*} $$

where $\omega_j = \mathbf{v}_j^\top X(x)^{-1} \mathbf{v}_j$ and $\zeta_j = \mathbf{v}_j^\top X(x)^{-2} \mathbf{v}_j$, and $\omega_{jk} = \mathbf{v}_j^\top X(x)^{-1} \mathbf{v}_k$ and $\zeta_{jk} = \mathbf{v}_j^\top X^{-2} \mathbf{v}_k$. The objective value should be improving.

$$ \begin{align*} -\log \mathrm{Tr}(X(\mathbf{x})^{-1}) &\ge -\log \mathrm{Tr}(X(\mathbf{x}_+)^{-1}) \\ \mathrm{Tr}(X(\mathbf{x})^{-1}) &\le \mathrm{Tr}(X(\mathbf{x}_+)^{-1}) \\ &= \mathrm{Tr}(X(\mathbf{x})^{-1}) - \frac{\theta A + \theta^2 B}{1 + \theta C - \theta^2 D} \end{align*} $$
Hence, we want to maximise the function $q(\theta) = \frac{\theta A + \theta^2 B}{1 + \theta C - \theta^2 D}$. Let $\Delta = AD + BC$. By computing the first and second derivatives, it is easy to verify that we have

$$ \theta^* = - \frac{B + \sqrt{B^2 - A\Delta}}{\Delta} $$

if $\Delta \neq 0$. If $\Delta = 0$ but $B$ is not, then we have

$$ \theta^* = -\frac{A}{2B}. $$

If both $B$ and $\Delta$ are zero, then we choose $\theta$ as big as possible given the bound constraints.

$$ \theta = \begin{cases} \min \left\{ -\frac{B+\sqrt{B^2-A\Delta}}{\Delta}, u_j - x_j, x_k - l_k \right\} & \text{if } \Delta \neq 0 \\ \min \left\{ -\frac{A}{2B}, u_j - x_j, x_k - l_k \right\} & \text{if } \Delta = 0 \text{ and } B \neq 0 \\ \min \{u_j - x_j, x_k - l_k\} & \text{if } \Delta = B = 0 \text{ and } A > 0 \end{cases} $$

## Appendix C. BPCG convergence under sharpness conditions

In this appendix, we prove linear convergence of BPCG on polytopes when the objective function is sharp or presents a Hölderian error bound. For the definition of sharpness, see Definition 5. The following proofs rely on a geometric constant of a polytope $\mathcal{P}$.

**Definition 7** (Pyramidal Witdh Braun et al. (2022)). The pyramidal width of a polytope $\mathcal{P} \subset \mathbb{R}^n$ is the largest number $\delta$ such that for any set $S$ of some vertices of $\mathcal{P}$, we have

$$ \langle \mathbf{w}, \mathbf{v}^A - \mathbf{v}^{FW} \rangle \geq \delta \frac{\langle \mathbf{w}, \mathbf{x} - \mathbf{y} \rangle}{\| \mathbf{x} - \mathbf{y} \|} \quad \forall \mathbf{x} \in \text{conv}(S) \quad \forall \mathbf{y} \in \mathcal{P} \quad \forall \mathbf{w} \in \mathbb{R}^n $$

where $\mathbf{v}^A := \text{argmax}_{\mathbf{v} \in S} \langle \mathbf{w}, \mathbf{v} \rangle$ and $\mathbf{v}^{FW} := \text{argmin}_{\mathbf{v} \in S} \langle \mathbf{w}, \mathbf{v} \rangle$.

**Theorem 6** (Linear convergence of BPCG). Let $P$ be a polytope of pyramidal width $\delta$ and diameter $D$, and let $f$ be an $L$-smooth and $(M, \theta)$-sharp function over $P$. Noting $f^* = \min_{\mathbf{x} \in P} f(\mathbf{x})$ and $\{\mathbf{x}_t\}_{t=0}^T$ the iterations of the BPCG algorithm, then it holds that:

$$ f(\mathbf{x}_t) - f^* \le \begin{cases} c_0(1-c_1)^{2t-1} & \text{if } 1 \le t \le \frac{t_0}{2} \\ \frac{(c_1/c_2)^{1/\alpha}}{(1+c_1\alpha(2t-t_0))^{1/\alpha}} & \text{if } t \ge \frac{t_0}{2}. \end{cases} $$

with parameters:

$$ \begin{aligned} c_1 &= \frac{1}{2} \\ \alpha &= 2 - 2\theta \\ c_2 &= \frac{\delta^2}{8LD^2M^2} \\ t_0 &= \max \left\{ \left\lfloor \log_{1-c_1} \left( \frac{(c_1/c_2)^{1/\alpha}}{c_0} \right) \right\rfloor + 2, 1 \right\}. \end{aligned} $$

*Proof.* We will denote $h_t = f(\mathbf{x}_t) - f^*$. The proof adapts that of Tsuji et al. (2021, Theorem 3.2) to the case of a sharp objective. Tsuji et al. (2021, Lemma 3.5) establishes that at any step $t$, the following holds:

$$ 2 \langle \nabla f(\mathbf{x}_t), \mathbf{d}_t \rangle \ge \langle \nabla f(\mathbf{x}_t), \mathbf{v}_t^A - \mathbf{v}_t^{FW} \rangle. \quad (15) $$
Let us first assume that $t$ is not a drop step.

If $t$ follows Case (a) of Lemma 19, then

$$h_t - h_{t+1} \ge \frac{\langle \nabla f(\mathbf{x}_t), \mathbf{d}_t \rangle^2}{2LD^2} \qquad \text{by (17)}$$

$$\ge \frac{\langle \nabla f(\mathbf{x}_t), \mathbf{v}_t^A - \mathbf{v}_t^{FW} \rangle^2}{8LD^2} \qquad \text{by (15)}$$

$$\ge h_t^{2-2\theta} \frac{\delta^2}{8LD^2 M^2} \qquad \text{by (16).}$$

If $t$ follows Case (b) of Lemma 19, then:

$$h_t - h_{t+1} \ge \frac{1}{2} \langle \nabla f(\mathbf{x}_t), \mathbf{d}_t \rangle \ge \frac{1}{2} h_t,$$

where the second inequality comes from $d_t$ being a FW step and from the FW gap being an upper bound on the primal gap.

Denoting with $\mathcal{T}_{\text{drop}} \subseteq [T]$ the set of drop steps, we can already observe that the sequence $\{h_t\}_{t \in [T]} \setminus \mathcal{T}_{\text{drop}}$ follows the hypotheses of Lemma 20, with parameters $c_1, c_2, \alpha$ defined in the statement of the theorem.

We can then observe that the number of drop steps is bounded by the number of FW steps on the sequence. This implies in the worst case that in $2t, t > 1$ iterations, we can reach the primal gap of $t$ FW and pairwise steps combined. Let us denote $\tau$ the number of steps that were not drop steps up to iteration $t$, then:

$$h_t \le \begin{cases} \frac{c_0(1-c_1)^{\tau-1}}{(c_1/c_2)^{1/\alpha}} & 1 \le \tau \le t_0 \\ \frac{(1+c_1\alpha(\tau-t_0))^{1/\alpha}}{c_0(1-c_1)^{2t-1}} & \tau \ge t_0, \end{cases} \\ \le \begin{cases} \frac{c_0(1-c_1)^{2t-1}}{(c_1/c_2)^{1/\alpha}} & 1 \le t \le \frac{t_0}{2} \\ \frac{(1+c_1\alpha(2t-t_0))^{1/\alpha}}{c_0(1-c_1)^{2t-1}} & t \ge \frac{t_0}{2}. \end{cases}$$

with $t_0$ as defined in (19).

□

**Lemma 18** (Geometric sharpness Braun et al. (2022), Lemma 3.32). Let $P$ be a polytope with pyramidal width $\delta$ and let $f$ be $(M, \theta)$-sharp over $P$. Given $S \subseteq \text{Vert}(P)$ such that $\mathbf{x} \in \text{conv}(S)$ and:

$$\mathbf{v}^{FW} \in \underset{\mathbf{v} \in P}{\operatorname{argmin}} \langle \nabla f(\mathbf{x}), \mathbf{v} \rangle$$

$$\mathbf{v}^A \in \underset{\mathbf{v} \in P}{\operatorname{argmax}} \langle \nabla f(\mathbf{x}), \mathbf{v} \rangle.$$

Then:

$$\frac{\delta}{M} (f(\mathbf{x}) - f^*)^{(1-\theta)} \le \langle \nabla f(\mathbf{x}), \mathbf{v}^A - \mathbf{v}^{FW} \rangle. \qquad (16)$$

**Lemma 19** (Minimum decrease Tsuji et al. (2021), Lemma 3.4). Suppose that $t$ is not a drop step, and let $\alpha_t^* = \frac{\langle \nabla f(\mathbf{x}_t), \mathbf{d}_t \rangle}{L \|\mathbf{d}_t\|^2}$.

(a) If step $t$ is either a FW step with $\alpha_t^* < 1$ or a pairwise step, then:

$$f(\mathbf{x}_t) - f(\mathbf{x}_{t+1}) \ge \frac{\langle \nabla f(\mathbf{x}_t), \mathbf{d}_t \rangle^2}{2LD^2}. \qquad (17)$$
(b) If step t is a FW step with $\alpha_t > 1$, we have:

$$f(\mathbf{x}_t) - f(\mathbf{x}_{t+1}) \geq \frac{1}{2} \langle \nabla f(\mathbf{x}_t), \mathbf{d}_t \rangle. \quad (18)$$

**Lemma 20** (Convergence rates from contraction inequalities, Braun et al. (2022), Lemma 2.21). Let {$h_t$}$_{t \ge 1}$ be a sequence of positive numbers and $c_0, c_1, c_2, \alpha$ such that:

$$\begin{cases} c_1 < 1 \\ h_1 \le c_0 \\ h_t - h_{t+1} \ge h_t \min\{c_1, c_2 h_t^\alpha\} \quad \forall t \ge 1, \end{cases}$$

then,

$$h_t \le \begin{cases} c_0(1-c_1)^{t-1} & 1 \le t \le t_0 \\ \frac{(c_1/c_2)^{1/\alpha}}{(1+c_1\alpha(t-t_0))^{1/\alpha}} & t \ge t_0, \end{cases}$$

where

$$t_0 = \max \left\{ \left\lceil \log_{1-c_1} \left( \frac{(c_1/c_2)^{1/\alpha}}{c_0} \right) \right\rceil + 2, 1 \right\}. \quad (19)$$

Finally, we can exploit the recent results of Zhao (2025) on AFW for log-homogeneous self-concordant barrier functions to show that on D-Opt Problem, BPCG converges at a linear rate in primal and FW gaps.

**Proposition 1** (Linear convergence of BPCG on D-Opt (Zhao, 2025)). The blended pairwise conditional gradient contracts the primal gap $h_t$ at a linear rate $h_t \le h_0 \exp(-ct)$ with $h_0$ the primal gap of the initial domain-feasible solution and c a constant depending on the design matrix and polytope.

*Proof.* The core observation required to extend Zhao (2025, Theorem 4.1) is that the gap produced by BPCG upper-bounds the one produced by AFW. Let $\mathbf{d}^{\text{BPCG}}$, $\mathbf{d}^{\text{AFW}}$ be the search directions produced by BPCG, AFW respectively. A drop step can occur in both algorithms in at most half of the iterations, since each drop step reduces the size of the active set by one. We can focus on “effective” steps in which no vertex is dropped. BPCG either takes a local pairwise step with direction:

$$\begin{align*} \mathbf{d}^{\text{BPCG}} &= \mathbf{a} - \mathbf{s} \\ \text{with } \mathbf{a} &= \underset{v \in S_t}{\operatorname{argmax}} \langle \nabla f(\mathbf{x}), \mathbf{v} \rangle \\ \mathbf{s} &= \underset{v \in S_t}{\operatorname{argmin}} \langle \nabla f(\mathbf{x}), \mathbf{v} \rangle, \end{align*}$$

and $S_t$ the local active set. Using the same notation, $\mathbf{d}^{\text{AFW}} = \mathbf{a} - \mathbf{x}$. The quantity determining whether a local pairwise step is selected is $\langle \nabla f(\mathbf{x}), \mathbf{d}^{\text{BPCG}} \rangle$, which needs to be greater than the FW gap $\langle \nabla f(\mathbf{x}), \mathbf{x} - \mathbf{v} \rangle$ at the current point. Regardless of the direction taken by BPCG, Tsuji et al. (2021, Lemma 3.5) provides:

$$\langle \nabla f(\mathbf{x}), \mathbf{d} \rangle \ge 1/2 \langle \nabla f(\mathbf{x}), \mathbf{a} - \mathbf{v} \rangle$$

which is precisely the only inequality required from effective AFW steps. The rest of the proofs from Zhao (2025, Theorem 4.1, Theorem 4.2) follow without relying on the AFW descent direction specifically. □

**Proposition 1** unfortunately relies on the fact that the D-Opt objective is a log-barrier in addition to being self-concordant. Since this is not the case for the trace inverse function, we cannot transpose this result to the A-Opt Problem.
## Appendix D. Computational experiments

In this appendix section, we present additional computational experiments. Table 5 show an extended comparison of the performance between the different solution approaches on the A-Optimal Problem, D-Optimal Problem, A-Fusion Problem and D-Fusion Problem. In Tables 6 and 7, the results of the computations on the GTI-Optimal and GTI-Fusion Problem are shown. The Tables 8 to 10 compare the performance of Boscia using different settings.
<caption>Table 5: Comparing Boscia, SCIP, Co-BnB and the direct conic formulation and second-order formulation using Pajarito on the different problems and the different data sets, i.e. A-Fusion (AF), D-Fusion (DF), A-Optimal (AO) and D-Optimal (DO). One data set contains independent data, the other has correlated data.</caption>

The instances for each problem are split into increasingly smaller subsets depending on their minimum solve time, i.e. the minimum time any of the solvers took to solve it. The cut-offs are at 0 seconds (all problems), took at least 10 seconds to solve, 100 s, 1000 s and lastly 2000 s. Note that if none of the solvers terminates on any instance of a subset, the corresponding row is omitted from the table.

The average of the relative gap does not include instances that were solved by all methods. The average of number nodes/cuts is only taken for the instances solved in that group. The average time is taken using the geometric mean shifted by 1 second. Also note that this is the average time over all instances in that group, i.e. it includes the time outs.

<table><thead><tr><th rowspan="2">Type</th><th rowspan="2">Corr.</th><th colspan="2">Boscia</th><th colspan="2">Co-BnB</th><th colspan="2">Direct Conic</th><th colspan="2">SOCP</th><th colspan="2">SCIPOA</th></tr><tr><th>Solved after (s)</th><th>% solved</th><th>Time (s)</th><th>relative gap</th><th># nodes</th><th>% solved</th><th>Time (s)</th><th>relative gap</th><th># cuts solved</th><th>% solved</th><th>% cuts solved</th><th>Time (s)</th><th>relative gap</th><th># cuts solved</th><th>Time (s)</th><th>relative gap</th><th># cuts</th></tr></thead><tbody><tr><td rowspan="5">AO</td><td rowspan="5">no</td><td>0</td><td>52 %</td><td><b>374.74</b></td><td><b>0.0851</b></td><td><b>7340</b></td><td>48 %</td><td>401.67</td><td>22211</td><td>8 %</td><td>2382.52</td><td>2.4436</td><td>112</td><td>20 %</td><td>1578.03</td><td>Inf</td><td>2842</td><td>-</td><td>-</td><td>-</td></tr><tr><td>10</td><td>40 %</td><td><b>1230.45</b></td><td><b>0.0964</b></td><td><b>11775</b></td><td>35 %</td><td>1309.24</td><td>56.5936</td><td>37906</td><td>0 %</td><td>3600.09</td><td>3.3563</td><td>-</td><td>0 %</td><td>3600.02</td><td>Inf</td><td>-</td><td>-</td><td>-</td></tr><tr><td>100</td><td>25 %</td><td>2974.04</td><td><b>0.118</b></td><td><b>22241</b></td><td>19 %</td><td><b>2922.12</b></td><td>66.0235</td><td>81489</td><td>0 %</td><td>3600.11</td><td>0.6943</td><td>-</td><td>0 %</td><td>3600.01</td><td>Inf</td><td>-</td><td>-</td><td>-</td></tr><tr><td>1000</td><td>17 %</td><td><b>3164.43</b></td><td><b>0.1291</b></td><td><b>19766</b></td><td>10 %</td><td>3360.8</td><td>71.1272</td><td>86515</td><td>0 %</td><td>3600.12</td><td>0.7501</td><td>-</td><td>0 %</td><td>3600.01</td><td>Inf</td><td>-</td><td>-</td><td>-</td></tr><tr><td>2000</td><td>4 %</td><td><b>3583.85</b></td><td><b>0.1482</b></td><td><b>22096</b></td><td>0 %</td><td>3602.18</td><td>74.692</td><td>-</td><td>0 %</td><td>3600.09</td><td>0.8378</td><td>-</td><td>0 %</td><td>3600.01</td><td>Inf</td><td>-</td><td>-</td><td>-</td></tr><tr><td rowspan="5">AO</td><td rowspan="5">yes</td><td>0</td><td>68 %</td><td><b>227.69</b></td><td><b>0.0336</b></td><td><b>7814</b></td><td>60 %</td><td>301.8</td><td>22379</td><td>20 %</td><td>1515.23</td><td>30.3669</td><td>188</td><td>20 %</td><td>1861.35</td><td>Inf</td><td>3623</td><td>-</td><td>-</td><td>-</td></tr><tr><td>10</td><td>60 %</td><td><b>481.42</b></td><td><b>0.0348</b></td><td><b>10181</b></td><td>50 %</td><td>864.83</td><td>2058.4159</td><td>30.35</td><td>10648</td><td>4 %</td><td>2846.5</td><td>0.0371</td><td>26 %</td><td>1666.2</td><td>Inf</td><td>5634</td><td>38 %</td><td>463.65</td><td>0.0302</td><td>801</td></tr><tr><td>100</td><td>45 %</td><td><b>1421.72</b></td><td><b>0.0434</b></td><td><b>16675</b></td><td>31 %</td><td>2476.41</td><td>2058.4159</td><td>33031</td><td>2 %</td><td>3149.17</td><td>34.3286</td><td>206</td><td>5 %</td><td>3366.07</td><td>Inf</td><td>5752</td><td>-</td><td>-</td><td>-</td><td>-</td><td>1930</td></tr><tr><td>1000</td><td>16 %</td><td><b>3544.51</b></td><td><b>0.061</b></td><td><b>49147</b></td><td>5 %</td><td>3583.18</td><td>2107.5216</td><td>59473</td><td>0 %</td><td>3600.05</td><td>0.4903</td><td>-</td><td>0 %</td><td>3600.01</td><td>Inf</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>1000</td><td>16 %</td><td><b>3544.51</b></td><td><b>0.061</b></td><td><b>49147</b></td><td>5 %</td><td>3583.18</td><td>2107.5216</td><td>89805</td><td>0 %</td><td>3600.05</td><td>1.2972</td><td>-</td><td>0 %</td><td>3600.01</td><td>Inf</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td rowspan="5">AF</td><td rowspan="5">no</td><td>0</td><td>80 %</td><td>62.83</td><td><b>0.0168</b></td><td><b>11634</b></td><td><b>80 %</b></td><td><b>50.92</b></td><td>30.35</td><td>10648</td><td>4 %</td><td>2846.5</td><td>0.0374</td><td>58</td><td>26 %</td><td>1666.2</td><td>Inf</td><td>5634</td><td>7 %</td><td>3172.81</td><td>0.0379</td><td>801</td></tr><tr><td>10</td><td>66 %</td><td>460.44</td><td><b>0.0213</b></td><td><b>22887</b></td><td><b>66 %</b></td><td><b>409.38</b></td><td>37.6051</td><td>21718</td><td>0 %</td><td>3600.03</td><td>0.0548</td><td>-</td><td>0 %</td><td>3600.09</td><td>Inf</td><td>-</td><td>0 %</td><td>3600.1</td><td>0.0485</td><td>1930</td></tr><tr><td>100</td><td>47 %</td><td>1644.98</td><td><b>0.0272</b></td><td><b>41058</b></td><td><b>47 %</b></td><td><b>1374.15</b></td><td>42.7763</td><td>33254</td><td>0 %</td><td>3600.04</td><td>0.074</td><td>-</td><td>0 %</td><td>3600.14</td><td>Inf</td><td>-</td><td>0 %</td><td>3600.15</td><td>0.0646</td><td>-</td></tr><tr><td>1000</td><td>25 %</td><td><b>3087.98</b></td><td><b>0.0372</b></td><td><b>67544</b></td><td>17 %</td><td>3125.27</td><td>48.0929</td><td>67087</td><td>0 %</td><td>3600.06</td><td>0.0967</td><td>-</td><td>0 %</td><td>3600.17</td><td>Inf</td><td>-</td><td>0 %</td><td>3600.19</td><td>0.071</td><td>-</td></tr><tr><td>2000</td><td>11 %</td><td><b>3416.18</b></td><td><b>0.0461</b></td><td><b>70407</b></td><td>0 %</td><td>3601.84</td><td>51.6913</td><td>-</td><td>0 %</td><td>3600.06</td><td>0.1108</td><td>-</td><td>0 %</td><td>3600.22</td><td>Inf</td><td>-</td><td>0 %</td><td>3600.19</td><td>0.071</td><td>-</td></tr><tr><td rowspan="5">AF</td><td rowspan="5">yes</td><td>0</td><td>26 %</td><td>1368.83</td><td><b>2.1573</b></td><td><b>28578</b></td><td><b>52 %</b></td><td><b>311.36</b></td><td>1407.4062</td><td>30449</td><td>24 %</td><td>1148.87</td><td>9.0208</td><td>318</td><td>20 %</td><td>2131.81</td><td>Inf</td><td>4539</td><td>14 %</td><td>1480.73</td><td>3.4254</td><td>552</td></tr><tr><td>10</td><td>11 %</td><td>3030.17</td><td><b>2.5452</b></td><td><b>51328</b></td><td><b>37 %</b></td><td><b>1336.22</b></td><td>1468.0559</td><td>56106</td><td>3 %</td><td>3418.49</td><td>10.6718</td><td>1086</td><td>0 %</td><td>3603.12</td><td>Inf</td><td>-</td><td>0 %</td><td>3600.04</td><td>3.6558</td><td>-</td></tr><tr><td>100</td><td>6 %</td><td>3315.04</td><td><b>2.8901</b></td><td><b>58354</b></td><td><b>27 %</b></td><td><b>2303.15</b></td><td>1468.0559</td><td>84247</td><td>0 %</td><td>3600.08</td><td>12.2264</td><td>-</td><td>0 %</td><td>3603.59</td><td>Inf</td><td>-</td><td>0 %</td><td>3600.05</td><td>3.9173</td><td>-</td></tr><tr><td>1000</td><td>0 %</td><td>3600.06</td><td><b>3.2127</b></td><td><b>17 %</b></td><td><b>3079.19</b></td><td><b>17 %</b></td><td><b>3079.19</b></td><td>1468.0559</td><td>128319</td><td>0 %</td><td>3600.09</td><td>13.8081</td><td>-</td><td>0 %</td><td>3604.08</td><td>Inf</td><td>-</td><td>0 %</td><td>3600.05</td><td>4.2154</td><td>-</td></tr><tr><td>2000</td><td>0 %</td><td>3600.07</td><td><b>3.6098</b></td><td><b>4 %</b></td><td><b>3595.22</b></td><td><b>1533.847</b></td><td>154005</td><td>0 %</td><td>3600.09</td><td>13.7875</td><td>-</td><td>0 %</td><td>3604.73</td><td>Inf</td><td>-</td><td>0 %</td><td>3600.06</td><td>4.5519</td><td>-</td></tr><tr><td rowspan="5">DF</td><td rowspan="5">no</td><td>0</td><td>94 %</td><td>3.49</td><td><b>0.0102</b></td><td><b>301</b></td><td>86 %</td><td>22.79</td><td>0.0382</td><td>6782</td><td>12 %</td><td>1906.61</td><td>0.0126</td><td>433</td><td>18 %</td><td>2213.03</td><td>Inf</td><td>4787</td><td>50 %</td><td>324.11</td><td>0.0133</td><td>1155</td></tr><tr><td>10</td><td>50 %</td><td>727.47</td><td><b>0.0128</b></td><td><b>1424</b></td><td>17 %</td><td>2540.85</td><td>0.1531</td><td>32841</td><td>0 %</td><td>3879.62</td><td>0.0201</td><td>-</td><td>0 %</td><td>3600.0</td><td>Inf</td><td>-</td><td>0 %</td><td>3600.17</td><td>0.0163</td><td>-</td></tr><tr><td>100</td><td>40 %</td><td><b>1176.39</b></td><td><b>0.0133</b></td><td><b>94</b></td><td>0 %</td><td>3602.41</td><td>0.1825</td><td>-</td><td>0 %</td><td>3936.34</td><td>0.0213</td><td>-</td><td>0 %</td><td>3600.0</td><td>Inf</td><td>-</td><td>0 %</td><td>3600.2</td><td>0.0176</td><td>-</td></tr><tr><td>100</td><td>40 %</td><td><b>1176.39</b></td><td><b>0.0133</b></td><td><b>94</b></td><td>0 %</td><td>3602.41</td><td>0.1825</td><td>-</td><td>0 %</td><td>3936.34</td><td>0.0213</td><td>-</td><td>0 %</td><td>3600.0</td><td>Inf</td><td>-</td><td>0 %</td><td>3600.05</td><td>0.185</td><td>-</td></tr><tr><td>100</td><td>5 %</td><td><b>3535.72</b></td><td><b>0.1761</b></td><td><b>40687</b></td><td>0 %</td><td>3599.62</td><td>1.0588</td><td>-</td><td>0 %</td><td>3604.36</td><td>0.2811</td><td>-</td><td>0 %</td><td>3600.0</td><td>Inf</td><td>-</td><td>0 %</td><td>3600.05</td><td>0.1711</td><td>-</td></tr><tr><td rowspan="5">DO</td><td rowspan="5">no</td><td>0</td><td>68 %</td><td><b>136.92</b></td><td><b>0.0208</b></td><td><b>3578</b></td><td>58 %</td><td>216.31</td><td>2.7678</td><td>9559</td><td>20 %</td><td>1241.37</td><td>0.676</td><td>1077</td><td>20 %</td><td>2169.4</td><td>Inf</td><td>4514</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>10</td><td>56 %</td><td><b>618.39</b></td><td><b>0.0226</b></td><td><b>5916</b></td><td>42 %</td><td>991.36</td><td>3.3814</td><td>17925</td><td>3 %</td><td>2355.99</td><td>0.8846</td><td>3056</td><td>0 %</td><td>3600.0</td><td>Inf</td><td>-</td><td>0 %</td><td>3600.05</td><td>0.1679</td><td>-</td></tr><tr><td>100</td><td>45 %</td><td><b>1330.76</b></td><td><b>0.0257</b></td><td><b>8559</b></td><td>28 %</td><td>1978.6</td><td>4.5636</td><td>27449</td><td>3 %</td><td>2126.78</td><td>1.3081</td><td>3056</td><td>0 %</td><td>3600.0</td><td>Inf</td><td>-</td><td>0 %</td><td>3600.05</td><td>0.1711</td><td>-</td></tr><tr><td>1000</td><td>17 %</td><td><b>3261.11</b></td><td><b>0.0358</b></td><td><b>18628</b></td><td>0 %</td><td>3602.01</td><td>7.4215</td><td>-</td><td>0 %</td><td>2741.23</td><td>4.4622</td><td>-</td><td>0 %</td><td>3600.01</td><td>Inf</td><td>-</td><td>0 %</td><td>3600.05</td><td>0.185</td><td>-</td></tr><tr><td>2000</td><td>12 %</td><td><b>3515.21</b></td><td><b>0.0294</b></td><td><b>30726</b></td><td>0 %</td><td>3601.85</td><td>3.4692</td><td>-</td><td>0 %</td><td>3614.18</td><td>4.4622</td><td>-</td><td>0 %</td><td>3600.0</td><td>Inf</td><td>-</td><td>0 %</td><td>3600.05</td><td>0.185</td><td>-</td></tr><tr><td rowspan="5">DO</td><td rowspan="5">yes</td><td>0</td><td>100 %</td><td>2.56</td><td><b>0.0094</b></td><td><b>108</b></td><td>70 %</td><td>101.89</td><td>0.0809</td><td>7973</td><td>10 %</td><td>1398.01</td><td>0.0206</td><td>309</td><td>10 %</td><td>2526.74</td><td>Inf</td><td>2871</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>10</td><td>100 %</td><td>65.51</td><td><b>0.0099</b></td><td><b>439</b></td><td>0 %</td><td>3599.94</td><td>0.2101</td><td>-</td><td>0 %</td><td>1347.23</td><td>Inf</td><td>-</td><td>0 %</td><td>3600.01</td><td>Inf</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>100</td><td>100 %</td><td><b>195.36</b></td><td><b>0.0099</b></td><td><b>828</b></td><td>0 %</td><td>3600.17</td><td>0.1967</td><td>-</td><td>0 %</td><td>1204.26</td><td>Inf</td><td>-</td><td>0 %</td><td>3600.02</td><td>Inf</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr><tr><td>100</td><td>100 %</td><td><b>195.36</b></td><td><b>0.0099</b></td><td><b>828</b></td><td>0 %</td><td>3600.17</td><td>0.1967</td><td>-</td><td>0 %</td><td>1204.26</td><td>Inf</td><td>-</td><td>0 %</td><td>3600.02</td><td>Inf</td><td>-</td><td>-</td><td>-</td><td>-</td><td>-</td></tr></tbody></table>
<caption>Table 6: Comparing Boscia and Co-BnB on the General-Trace-Inverse (GTI) Optimal Problem for different values of *p* and under independent and correlated data. Note the objective function has the form $\phi_p(X(x)) = -1/p \log(\mathrm{Tr}(X(x)^p))$. The instances for each problem are split into increasingly smaller subsets depending on their minimum solve time, i.e. the minimum time any of the solvers took to solve it. The cut-offs are at 0 seconds (all problems), took at least 10 seconds to solve, 100 s, 1000 s and lastly 2000 s. Note that if none of the solvers terminates on any instance of a subset, the corresponding row is omitted from the table.</caption>

The relative gap is computed for the instances on which at least one method did not terminate within the time limit. That means it excludes the instances on which all methods terminated. The average time is taken using the geometric mean shifted by 1 second. Also note that this is the average time over all instances in that group, i.e. it includes the time outs.

<table><thead><tr><th rowspan="2">p</th><th rowspan="2">Corr.</th><th rowspan="2">Solved after (s)</th><th rowspan="2"># inst.</th><th colspan="2">Boscia</th><th colspan="2">Boscia Log</th><th colspan="2">Co-BnB</th></tr><tr><th>% solved</th><th>Time (s)</th><th>% solved</th><th>Time (s)</th><th>% solved</th><th>Time (s)</th></tr></thead><tbody><tr><td>GTI_25</td><td>no</td><td>0</td><td>30</td><td>67 %</td><td>162.41</td><td><strong>87 %</strong></td><td><strong>27.13</strong></td><td>50 %</td><td>359.92</td></tr><tr><td>GTI_25</td><td>no</td><td>10</td><td>16</td><td>38 %</td><td>1880.31</td><td><strong>75 %</strong></td><td><strong>200.69</strong></td><td>12 %</td><td>2864.51</td></tr><tr><td>GTI_25</td><td>no</td><td>100</td><td>9</td><td>11 %</td><td>3437.77</td><td><strong>56 %</strong></td><td><strong>930.74</strong></td><td>0 %</td><td>3622.39</td></tr><tr><td>GTI_25</td><td>no</td><td>1000</td><td>5</td><td>0 %</td><td>3606.39</td><td><strong>20 %</strong></td><td><strong>3222.96</strong></td><td>0 %</td><td>3640.97</td></tr><tr><td>GTI_25</td><td>yes</td><td>0</td><td>30</td><td>67 %</td><td>110.25</td><td><strong>77 %</strong></td><td><strong>85.83</strong></td><td>60 %</td><td>264.22</td></tr><tr><td>GTI_25</td><td>yes</td><td>10</td><td>16</td><td>38 %</td><td>1461.4</td><td><strong>56 %</strong></td><td><strong>896.41</strong></td><td>25 %</td><td>2614.2</td></tr><tr><td>GTI_25</td><td>yes</td><td>100</td><td>14</td><td>29 %</td><td>2309.53</td><td><strong>50 %</strong></td><td><strong>1437.34</strong></td><td>14 %</td><td>3307.62</td></tr><tr><td>GTI_25</td><td>yes</td><td>1000</td><td>7</td><td>0 %</td><td>3600.83</td><td>0 %</td><td>3600.9</td><td>0 %</td><td>3599.3</td></tr><tr><td>GTI_50</td><td>no</td><td>0</td><td>30</td><td>53 %</td><td>246.61</td><td><strong>70 %</strong></td><td><strong>85.87</strong></td><td>50 %</td><td>430.08</td></tr><tr><td>GTI_50</td><td>no</td><td>10</td><td>17</td><td>18 %</td><td>3139.96</td><td><strong>47 %</strong></td><td><strong>1197.73</strong></td><td>12 %</td><td>3456.55</td></tr><tr><td>GTI_50</td><td>no</td><td>100</td><td>14</td><td>0 %</td><td>3601.04</td><td><strong>36 %</strong></td><td><strong>2242.33</strong></td><td>0 %</td><td>3611.02</td></tr><tr><td>GTI_50</td><td>no</td><td>1000</td><td>10</td><td>0 %</td><td>3601.45</td><td><strong>10 %</strong></td><td><strong>3581.72</strong></td><td>0 %</td><td>3615.73</td></tr><tr><td>GTI_50</td><td>yes</td><td>0</td><td>30</td><td><strong>60 %</strong></td><td><strong>129.86</strong></td><td>57 %</td><td>245.36</td><td>57 %</td><td>313.7</td></tr><tr><td>GTI_50</td><td>yes</td><td>10</td><td>21</td><td><strong>43 %</strong></td><td><strong>675.52</strong></td><td>38 %</td><td>1340.71</td><td>38 %</td><td>1326.2</td></tr><tr><td>GTI_50</td><td>yes</td><td>100</td><td>16</td><td><strong>25 %</strong></td><td><strong>2105.9</strong></td><td>19 %</td><td>3238.0</td><td>19 %</td><td>3193.81</td></tr><tr><td>GTI_75</td><td>no</td><td>0</td><td>30</td><td>37 %</td><td>799.73</td><td>43 %</td><td>505.86</td><td><strong>50 %</strong></td><td><strong>471.95</strong></td></tr><tr><td>GTI_75</td><td>no</td><td>10</td><td>25</td><td>24 %</td><td>2171.71</td><td>32 %</td><td>1308.01</td><td><strong>40 %</strong></td><td><strong>1228.42</strong></td></tr><tr><td>GTI_75</td><td>no</td><td>100</td><td>21</td><td>10 %</td><td>3011.64</td><td>19 %</td><td>2210.64</td><td><strong>29 %</strong></td><td><strong>2093.83</strong></td></tr><tr><td>GTI_75</td><td>no</td><td>1000</td><td>17</td><td>0 %</td><td>3601.73</td><td>0 %</td><td>3602.06</td><td><strong>12 %</strong></td><td><strong>3518.93</strong></td></tr><tr><td>GTI_75</td><td>yes</td><td>0</td><td>30</td><td>47 %</td><td>541.67</td><td>43 %</td><td>557.15</td><td><strong>50 %</strong></td><td><strong>357.77</strong></td></tr><tr><td>GTI_75</td><td>yes</td><td>10</td><td>25</td><td>36 %</td><td>1514.11</td><td>32 %</td><td>1626.43</td><td><strong>40 %</strong></td><td><strong>904.04</strong></td></tr><tr><td>GTI_75</td><td>yes</td><td>100</td><td>21</td><td>24 %</td><td>2446.72</td><td>19 %</td><td>2739.52</td><td><strong>29 %</strong></td><td><strong>1608.59</strong></td></tr><tr><td>GTI_75</td><td>yes</td><td>1000</td><td>16</td><td>0 %</td><td>3600.46</td><td>0 %</td><td>3600.45</td><td><strong>6 %</strong></td><td><strong>3440.58</strong></td></tr><tr><td>GTI_75</td><td>yes</td><td>2000</td><td>15</td><td>0 %</td><td>3600.48</td><td>0 %</td><td>3600.48</td><td>0 %</td><td>3599.49</td></tr><tr><td>GTI_150</td><td>no</td><td>0</td><td>30</td><td>43 %</td><td>659.25</td><td>40 %</td><td><strong>576.51</strong></td><td><strong>50 %</strong></td><td><strong>619.95</strong></td></tr><tr><td>GTI_150</td><td>no</td><td>10</td><td>25</td><td>32 %</td><td>1908.22</td><td>28 %</td><td>1673.37</td><td><strong>40 %</strong></td><td><strong>1669.28</strong></td></tr><tr><td>GTI_150</td><td>no</td><td>1000</td><td>17</td><td>0 %</td><td>3600.54</td><td>0 %</td><td>3601.19</td><td><strong>12 %</strong></td><td><strong>3571.66</strong></td></tr><tr><td>GTI_150</td><td>yes</td><td>0</td><td>30</td><td>47 %</td><td>418.43</td><td><strong>53 %</strong></td><td><strong>306.7</strong></td><td>47 %</td><td>506.3</td></tr><tr><td>GTI_150</td><td>yes</td><td>10</td><td>24</td><td>33 %</td><td>1413.27</td><td><strong>42 %</strong></td><td><strong>1076.7</strong></td><td>33 %</td><td>1539.25</td></tr><tr><td>GTI_150</td><td>yes</td><td>100</td><td>19</td><td>16 %</td><td>2602.93</td><td><strong>26 %</strong></td><td><strong>2474.23</strong></td><td>16 %</td><td>2546.07</td></tr><tr><td>GTI_150</td><td>yes</td><td>1000</td><td>16</td><td>0 %</td><td>3600.04</td><td><strong>12 %</strong></td><td><strong>3520.88</strong></td><td>0 %</td><td>3599.27</td></tr><tr><td>GTI_200</td><td>no</td><td>0</td><td>30</td><td>43 %</td><td>661.29</td><td><strong>50 %</strong></td><td><strong>562.4</strong></td><td><strong>50 %</strong></td><td>630.18</td></tr><tr><td>GTI_200</td><td>no</td><td>10</td><td>25</td><td>32 %</td><td>1880.56</td><td><strong>40 %</strong></td><td><strong>1601.07</strong></td><td><strong>40 %</strong></td><td>1642.44</td></tr><tr><td>GTI_200</td><td>no</td><td>100</td><td>25</td><td>32 %</td><td>1880.56</td><td><strong>40 %</strong></td><td><strong>1601.07</strong></td><td><strong>40 %</strong></td><td>1642.44</td></tr><tr><td>GTI_200</td><td>no</td><td>1000</td><td>18</td><td>6 %</td><td>3510.95</td><td><strong>17 %</strong></td><td>3342.37</td><td><strong>17 %</strong></td><td><strong>3207.77</strong></td></tr><tr><td>GTI_200</td><td>no</td><td>2000</td><td>16</td><td>0 %</td><td>3601.01</td><td><strong>6 %</strong></td><td>3590.35</td><td><strong>6 %</strong></td><td><strong>3521.64</strong></td></tr><tr><td>GTI_200</td><td>yes</td><td>0</td><td>30</td><td>43 %</td><td>644.53</td><td><strong>53 %</strong></td><td><strong>297.98</strong></td><td>47 %</td><td>611.8</td></tr><tr><td>GTI_200</td><td>yes</td><td>10</td><td>24</td><td>29 %</td><td>2068.4</td><td><strong>42 %</strong></td><td><strong>1062.97</strong></td><td>33 %</td><td>1851.58</td></tr><tr><td>GTI_200</td><td>yes</td><td>100</td><td>20</td><td>20 %</td><td>2632.63</td><td><strong>30 %</strong></td><td><strong>2026.91</strong></td><td>20 %</td><td>2734.27</td></tr><tr><td>GTI_200</td><td>yes</td><td>1000</td><td>16</td><td>0 %</td><td>3600.06</td><td><strong>12 %</strong></td><td><strong>3547.5</strong></td><td>0 %</td><td>3599.23</td></tr></tbody></table>
<caption>Table 7: Comparing Boscia, Co-BnB and SCIP on the General-Trace-Inverse (GTI) Fusion Problem for different values of *p* and under independent and correlated data. Note the objective function has the form $\phi_p(X(x)) = -1/p \log(\mathrm{Tr}(C + X(x)^p))$. The instances for each problem are split into increasingly smaller subsets depending on their minimum solve time, i.e. the minimum time any of the solvers took to solve it. The cut-offs are at 0 seconds (all problems), took at least 10 seconds to solve, 100 s, 1000 s and lastly 2000 s. Note that if none of the solvers terminates on any instance of a subset, the corresponding row is omitted from the table.</caption>

The relative gap is computed for the instances on which at least one method did not terminate within the time limit. That means it excludes the instances on which all methods terminated. The average time is taken using the geometric mean shifted by 1 second. Also note that this is the average time over all instances in that group, i.e. it includes the time outs.

<table><thead><tr><th rowspan="2">p</th><th rowspan="2">Corr.</th><th rowspan="2">Solved after (s)</th><th rowspan="2"># inst.</th><th colspan="3">Boscia</th><th colspan="3">Boscia Log</th><th colspan="3">Co-BnB</th><th colspan="3">SCIP OA</th></tr><tr><th>% solved</th><th>Time (s)</th><th>% solved</th><th>Time (s)</th><th>% solved</th><th>Time (s)</th><th>% solved</th><th>Time (s)</th><th>% solved</th><th>Time (s)</th></tr></thead><tbody><tr><td>GTIF_25</td><td>no</td><td>0</td><td>30</td><td>90 %</td><td>6.57</td><td><strong>100 %</strong></td><td><strong>1.71</strong></td><td>50 %</td><td>725.52</td><td>47 %</td><td>376.08</td><td></td><td></td><td></td></tr><tr><td>GTIF_25</td><td>no</td><td>10</td><td>3</td><td>67 %</td><td>470.21</td><td><strong>100 %</strong></td><td><strong>56.43</strong></td><td>0 %</td><td>3755.69</td><td>0 %</td><td>3600.18</td><td></td><td></td><td></td></tr><tr><td>GTIF_25</td><td>no</td><td>100</td><td>1</td><td>0 %</td><td>3602.77</td><td><strong>100 %</strong></td><td><strong>137.03</strong></td><td>0 %</td><td>3834.75</td><td>0 %</td><td>3600.01</td><td></td><td></td><td></td></tr><tr><td>GTIF_25</td><td>yes</td><td>0</td><td>30</td><td>53 %</td><td><strong>138.78</strong></td><td><strong>57 %</strong></td><td>184.83</td><td>27 %</td><td>1449.73</td><td>27 %</td><td>927.92</td><td></td><td></td><td></td></tr><tr><td>GTIF_25</td><td>yes</td><td>10</td><td>19</td><td>26 %</td><td>1299.73</td><td><strong>32 %</strong></td><td><strong>1260.16</strong></td><td>0 %</td><td>3601.55</td><td>0 %</td><td>3600.03</td><td></td><td></td><td></td></tr><tr><td>GTIF_25</td><td>yes</td><td>100</td><td>16</td><td>12 %</td><td>2722.54</td><td><strong>19 %</strong></td><td><strong>2572.48</strong></td><td>0 %</td><td>3601.84</td><td>0 %</td><td>3600.04</td><td></td><td></td><td></td></tr><tr><td>GTIF_25</td><td>yes</td><td>1000</td><td>14</td><td>0 %</td><td>3600.55</td><td><strong>7 %</strong></td><td><strong>3566.88</strong></td><td>0 %</td><td>3602.03</td><td>0 %</td><td>3600.04</td><td></td><td></td><td></td></tr><tr><td>GTIF_50</td><td>no</td><td>0</td><td>30</td><td>87 %</td><td>9.1</td><td><strong>90 %</strong></td><td><strong>3.63</strong></td><td>47 %</td><td>787.45</td><td>43 %</td><td>349.14</td><td></td><td></td><td></td></tr><tr><td>GTIF_50</td><td>no</td><td>10</td><td>6</td><td>33 %</td><td>1865.24</td><td><strong>50 %</strong></td><td><strong>310.51</strong></td><td>0 %</td><td>3885.14</td><td>0 %</td><td>3600.18</td><td></td><td></td><td></td></tr><tr><td>GTIF_50</td><td>yes</td><td>0</td><td>30</td><td><strong>57 %</strong></td><td><strong>175.85</strong></td><td>53 %</td><td>271.12</td><td>30 %</td><td>1547.49</td><td>20 %</td><td>850.41</td><td></td><td></td><td></td></tr><tr><td>GTIF_50</td><td>yes</td><td>10</td><td>21</td><td><strong>38 %</strong></td><td><strong>1010.86</strong></td><td>33 %</td><td>1617.58</td><td>0 %</td><td>3601.95</td><td>0 %</td><td>3600.03</td><td></td><td></td><td></td></tr><tr><td>GTIF_50</td><td>yes</td><td>100</td><td>16</td><td><strong>19 %</strong></td><td><strong>2753.86</strong></td><td>12 %</td><td>3261.97</td><td>0 %</td><td>3602.31</td><td>0 %</td><td>3600.04</td><td></td><td></td><td></td></tr><tr><td>GTIF_50</td><td>yes</td><td>1000</td><td>14</td><td><strong>7 %</strong></td><td><strong>3489.55</strong></td><td>7 %</td><td>3569.66</td><td>0 %</td><td>3602.47</td><td>0 %</td><td>3600.04</td><td></td><td></td><td></td></tr><tr><td>GTIF_75</td><td>no</td><td>0</td><td>30</td><td>70 %</td><td>85.39</td><td><strong>87 %</strong></td><td><strong>42.47</strong></td><td>57 %</td><td>353.3</td><td>43 %</td><td>415.34</td><td></td><td></td><td></td></tr><tr><td>GTIF_75</td><td>no</td><td>10</td><td>15</td><td>60 %</td><td>362.32</td><td><strong>73 %</strong></td><td><strong>144.1</strong></td><td>33 %</td><td>1347.24</td><td>27 %</td><td>1927.57</td><td></td><td></td><td></td></tr><tr><td>GTIF_75</td><td>no</td><td>100</td><td>6</td><td>17 %</td><td>2549.51</td><td><strong>33 %</strong></td><td><strong>2006.07</strong></td><td>0 %</td><td>3832.95</td><td>0 %</td><td>3600.04</td><td></td><td></td><td></td></tr><tr><td>GTIF_75</td><td>no</td><td>1000</td><td>5</td><td>0 %</td><td>3603.61</td><td><strong>20 %</strong></td><td><strong>3333.88</strong></td><td>0 %</td><td>3881.18</td><td>0 %</td><td>3600.03</td><td></td><td></td><td></td></tr><tr><td>GTIF_75</td><td>yes</td><td>0</td><td>30</td><td>37 %</td><td>741.57</td><td><strong>43 %</strong></td><td><strong>434.78</strong></td><td>27 %</td><td>1639.63</td><td>23 %</td><td>1053.8</td><td></td><td></td><td></td></tr><tr><td>GTIF_75</td><td>yes</td><td>10</td><td>24</td><td>21 %</td><td>2351.14</td><td><strong>29 %</strong></td><td><strong>1512.43</strong></td><td>12 %</td><td>3038.52</td><td>8 %</td><td>2837.69</td><td></td><td></td><td></td></tr><tr><td>GTIF_75</td><td>yes</td><td>100</td><td>20</td><td>10 %</td><td>3212.49</td><td><strong>15 %</strong></td><td><strong>2855.63</strong></td><td>0 %</td><td>3602.37</td><td>0 %</td><td>3600.05</td><td></td><td></td><td></td></tr><tr><td>GTIF_75</td><td>yes</td><td>1000</td><td>18</td><td>6 %</td><td>3567.81</td><td><strong>6 %</strong></td><td><strong>3373.72</strong></td><td>0 %</td><td>3602.86</td><td>0 %</td><td>3600.06</td><td></td><td></td><td></td></tr><tr><td>GTIF_150</td><td>no</td><td>0</td><td>30</td><td><strong>77 %</strong></td><td><strong>91.83</strong></td><td>67 %</td><td>129.57</td><td>47 %</td><td>780.56</td><td>40 %</td><td>406.94</td><td></td><td></td><td></td></tr><tr><td>GTIF_150</td><td>no</td><td>10</td><td>19</td><td><strong>63 %</strong></td><td><strong>629.52</strong></td><td>47 %</td><td>821.17</td><td>21 %</td><td>2030.26</td><td>11 %</td><td>2732.57</td><td></td><td></td><td></td></tr><tr><td>GTIF_150</td><td>no</td><td>100</td><td>14</td><td><strong>50 %</strong></td><td><strong>1556.16</strong></td><td>36 %</td><td>1922.49</td><td>0 %</td><td>3712.95</td><td>0 %</td><td>3600.09</td><td></td><td></td><td></td></tr><tr><td>GTIF_150</td><td>no</td><td>1000</td><td>9</td><td><strong>22 %</strong></td><td><strong>3112.4</strong></td><td>11 %</td><td>3171.4</td><td>0 %</td><td>3776.35</td><td>0 %</td><td>3600.13</td><td></td><td></td><td></td></tr><tr><td>GTIF_150</td><td>no</td><td>2000</td><td>8</td><td><strong>12 %</strong></td><td><strong>3488.09</strong></td><td>0 %</td><td>3601.58</td><td>0 %</td><td>3798.53</td><td>0 %</td><td>3600.14</td><td></td><td></td><td></td></tr><tr><td>GTIF_150</td><td>yes</td><td>0</td><td>30</td><td>37 %</td><td>715.74</td><td><strong>50 %</strong></td><td><strong>214.97</strong></td><td>30 %</td><td>1415.97</td><td>23 %</td><td>885.83</td><td></td><td></td><td></td></tr><tr><td>GTIF_150</td><td>yes</td><td>10</td><td>20</td><td>15 %</td><td>2749.79</td><td><strong>25 %</strong></td><td><strong>1837.42</strong></td><td>5 %</td><td>2727.35</td><td>0 %</td><td>3600.04</td><td></td><td></td><td></td></tr><tr><td>GTIF_150</td><td>yes</td><td>100</td><td>17</td><td>18 %</td><td>2622.1</td><td><strong>18 %</strong></td><td><strong>2813.97</strong></td><td>0 %</td><td>3603.41</td><td>0 %</td><td>3600.04</td><td></td><td></td><td></td></tr><tr><td>GTIF_150</td><td>yes</td><td>1000</td><td>15</td><td>7 %</td><td>3379.09</td><td><strong>7 %</strong></td><td><strong>3515.28</strong></td><td>0 %</td><td>3603.8</td><td>0 %</td><td>3600.05</td><td></td><td></td><td></td></tr><tr><td>GTIF_200</td><td>no</td><td>0</td><td>30</td><td><strong>73 %</strong></td><td><strong>96.28</strong></td><td>70 %</td><td>117.1</td><td>57 %</td><td>797.56</td><td>40 %</td><td>402.28</td><td></td><td></td><td></td></tr><tr><td>GTIF_200</td><td>no</td><td>10</td><td>20</td><td><strong>60 %</strong></td><td><strong>554.66</strong></td><td>55 %</td><td>677.02</td><td>35 %</td><td>2413.83</td><td>10 %</td><td>2710.21</td><td></td><td></td><td></td></tr><tr><td>GTIF_200</td><td>no</td><td>100</td><td>15</td><td><strong>47 %</strong></td><td><strong>1536.15</strong></td><td>40 %</td><td>1840.11</td><td>13 %</td><td>3313.81</td><td>0 %</td><td>3600.06</td><td></td><td></td><td></td></tr><tr><td>GTIF_200</td><td>no</td><td>1000</td><td>9</td><td><strong>11 %</strong></td><td><strong>3319.15</strong></td><td>0 %</td><td>3601.02</td><td>0 %</td><td>3762.3</td><td>0 %</td><td>3600.09</td><td></td><td></td><td></td></tr><tr><td>GTIF_200</td><td>yes</td><td>0</td><td>30</td><td>33 %</td><td>905.59</td><td><strong>53 %</strong></td><td><strong>202.0</strong></td><td>33 %</td><td>1305.28</td><td>20 %</td><td>923.45</td><td></td><td></td><td></td></tr><tr><td>GTIF_200</td><td>yes</td><td>10</td><td>19</td><td>21 %</td><td>2561.54</td><td><strong>32 %</strong></td><td><strong>1658.86</strong></td><td>5 %</td><td>3586.45</td><td>0 %</td><td>3600.05</td><td></td><td></td><td></td></tr><tr><td>GTIF_200</td><td>yes</td><td>100</td><td>18</td><td>22 %</td><td>2513.56</td><td><strong>28 %</strong></td><td><strong>2167.04</strong></td><td>6 %</td><td>3585.71</td><td>0 %</td><td>3600.06</td><td></td><td></td><td></td></tr><tr><td>GTIF_200</td><td>yes</td><td>1000</td><td>14</td><td>7 %</td><td>3471.17</td><td><strong>7 %</strong></td><td><strong>3513.18</strong></td><td>0 %</td><td>3600.85</td><td>0 %</td><td>3600.07</td><td></td><td></td><td></td></tr></tbody></table>
<caption>Table 8: Comparing the different Boscia settings on the different problems and the different data sets, i.e. A-Fusion (AF), D-Fusion (DF), A-Optimal (AO) and D-Optimal (DO). One data set contains independent data, the other has correlated data.</caption>

The settings displayed here are the default, so all options are off, using heuristics, using SCIP to model the constraints and tightening the lazifaction for the BPCG algorithm solving the nodes.

The instances for each problem are split into increasingly smaller subsets depending on their minimum solve time, i.e. the minimum time any of the solvers took to solve it. The cut-offs are at 0 seconds (all problems), took at least 10 seconds to solve, 100 s, 1000 s and lastly 2000 s. Note that if none of the solvers terminates on any instance of a subset, the corresponding row is omitted from the table. A line will also be omitted if nothing changes compared to the previous one.

The relative gap only includes the instances on which at least one run didn't terminate within the time limit. That means it does not include the instances that were solved by all.

The average time is taken using the geometric mean shifted by 1 econd. Also note that this is the average time over all instances in that group, i.e. it includes the time outs.

<table><thead><tr><th rowspan="2">Type</th><th rowspan="2">Corr.</th><th colspan="3">Default</th><th colspan="3">Heuristics</th><th colspan="3">Shadow Set</th><th colspan="3">MIP</th></tr><tr><th>Solved after (s)</th><th># inst.</th><th>% solved</th><th>Time (s)</th><th>relative gap</th><th># nodes solved</th><th>% solved</th><th>Time (s)</th><th>relative gap</th><th># nodes</th><th>% solved</th><th>Time (s)</th><th>relative gap</th></tr></thead><tbody><tr><td rowspan="3">AO</td><td rowspan="3">no</td><td>0</td><td>18</td><td><strong>50</strong> %</td><td>358.32</td><td>7.5254</td><td>7775</td><td><strong>50</strong> %</td><td>363.71</td><td>0.1521</td><td>8291</td><td><strong>50</strong> %</td><td>365.61</td><td>5.2159</td><td>8257</td><td>44 %</td><td>560.05</td><td>5.2295</td><td>2368</td></tr><tr><td>10</td><td>13</td><td><strong>31</strong> %</td><td>1410.24</td><td>10.4161</td><td>14871</td><td><strong>31</strong> %</td><td>1450.37</td><td>0.2069</td><td>16194</td><td><strong>31</strong> %</td><td>1450.66</td><td>7.2184</td><td>16044</td><td>23 %</td><td>1820.8</td><td>7.2372</td><td>2970</td></tr><tr><td>100</td><td>10</td><td><strong>10</strong> %</td><td>3554.77</td><td>13.5379</td><td>50135</td><td><strong>10</strong> %</td><td>3587.62</td><td>0.266</td><td>55115</td><td><strong>10</strong> %</td><td>3594.98</td><td>9.3809</td><td>54589</td><td>0 %</td><td>3600.25</td><td>9.4054</td><td>-</td></tr><tr><td rowspan="3">AO</td><td rowspan="3">yes</td><td>0</td><td>18</td><td><strong>44</strong> %</td><td>831.95</td><td>0.1441</td><td>39425</td><td><strong>44</strong> %</td><td>778.14</td><td>0.2456</td><td>33389</td><td><strong>44</strong> %</td><td>823.4</td><td>0.2557</td><td>35199</td><td><strong>44</strong> %</td><td>1434.99</td><td>0.3364</td><td>34942</td></tr><tr><td>10</td><td>12</td><td><strong>17</strong> %</td><td>3066.58</td><td>0.2783</td><td>93409</td><td><strong>17</strong> %</td><td>2994.35</td><td>0.3634</td><td>84460</td><td><strong>17</strong> %</td><td>2944.02</td><td>0.3785</td><td>71701</td><td><strong>17</strong> %</td><td>3452.15</td><td>0.4996</td><td>79349</td></tr><tr><td>1000</td><td>4</td><td><strong>25</strong> %</td><td>3097.25</td><td>0.0537</td><td>64107</td><td><strong>25</strong> %</td><td>2905.95</td><td>0.0463</td><td>59519</td><td><strong>25</strong> %</td><td>3012.72</td><td>0.0418</td><td>62081</td><td>0 %</td><td>3600.69</td><td>0.0639</td><td>-</td></tr><tr><td rowspan="3">AF</td><td rowspan="3">yes</td><td>0</td><td>18</td><td><strong>28</strong> %</td><td>1330.47</td><td>2.1036</td><td>31537</td><td><strong>28</strong> %</td><td>1386.95</td><td>2.1095</td><td>32697</td><td><strong>28</strong> %</td><td>1369.5</td><td>2.0899</td><td>32533</td><td><strong>28</strong> %</td><td>1919.67</td><td>2.3779</td><td>27555</td></tr><tr><td>10</td><td>17</td><td><strong>24</strong> %</td><td><strong>1847.36</strong></td><td>2.2267</td><td>39036</td><td><strong>24</strong> %</td><td>1933.2</td><td>2.233</td><td>40487</td><td><strong>24</strong> %</td><td>1902.13</td><td>2.2122</td><td>40282</td><td><strong>24</strong> %</td><td>2481.32</td><td>2.5172</td><td>34050</td></tr><tr><td>1000</td><td>15</td><td><strong>13</strong> %</td><td>3107.54</td><td>2.5223</td><td>63405</td><td><strong>13</strong> %</td><td>3059.65</td><td>2.5294</td><td>58879</td><td><strong>13</strong> %</td><td>3060.47</td><td>2.5059</td><td>60458</td><td><strong>13</strong> %</td><td>3431.17</td><td>2.8515</td><td>51914</td></tr><tr><td rowspan="3">AF</td><td rowspan="3">yes</td><td>0</td><td>18</td><td><strong>28</strong> %</td><td>1330.47</td><td>2.1036</td><td>31537</td><td><strong>28</strong> %</td><td>1386.95</td><td>2.1095</td><td>32697</td><td><strong>28</strong> %</td><td>1369.5</td><td>2.0899</td><td>32533</td><td><strong>28</strong> %</td><td>1919.67</td><td>2.3779</td><td>27555</td></tr><tr><td>10</td><td>17</td><td><strong>24</strong> %</td><td><strong>1847.36</strong></td><td>2.2267</td><td>39036</td><td><strong>24</strong> %</td><td>1933.2</td><td>2.233</td><td>40487</td><td><strong>24</strong> %</td><td>1902.13</td><td>2.2122</td><td>40282</td><td><strong>24</strong> %</td><td>2481.32</td><td>2.5172</td><td>34050</td></tr><tr><td>1000</td><td>15</td><td><strong>13</strong> %</td><td>3107.54</td><td>2.5223</td><td>63405</td><td><strong>13</strong> %</td><td>3059.65</td><td>2.5294</td><td>58879</td><td><strong>13</strong> %</td><td>3060.47</td><td>2.5059</td><td>60458</td><td><strong>13</strong> %</td><td>3431.17</td><td>2.8515</td><td>51914</td></tr><tr><td rowspan="3">DF</td><td rowspan="3">no</td><td>0</td><td>18</td><td><strong>94</strong> %</td><td>4.76</td><td>0.0101</td><td>219</td><td><strong>94</strong> %</td><td>4.54</td><td>0.0098</td><td>217</td><td><strong>94</strong> %</td><td><strong>4.43</strong></td><td>0.0102</td><td>232</td><td><strong>94</strong> %</td><td>11.15</td><td>0.0103</td><td>252</td></tr><tr><td>10</td><td>3</td><td><strong>67</strong> %</td><td>575.13</td><td>0.0135</td><td>125</td><td><strong>67</strong> %</td><td>419.91</td><td>0.0119</td><td>97</td><td><strong>67</strong> %</td><td><strong>356.85</strong></td><td>0.013</td><td>89</td><td><strong>67</strong> %</td><td>778.56</td><td>0.0151</td><td>118</td></tr><tr><td>1000</td><td>4</td><td><strong>7</strong> %</td><td>3441.35</td><td>2.7017</td><td>87165</td><td><strong>7</strong> %</td><td>3370.08</td><td>2.7094</td><td>75443</td><td><strong>7</strong> %</td><td>3399.93</td><td>2.6842</td><td>80221</td><td><strong>7</strong> %</td><td>3593.22</td><td>3.0545</td><td>69063</td></tr><tr><td rowspan="3">DF</td><td rowspan="3">yes</td><td>0</td><td>18</td><td><strong>61</strong> %</td><td>77.57</td><td>0.097</td><td>18067</td><td><strong>61</strong> %</td><td>78.71</td><td>0.097</td><td>18990</td><td><strong>61</strong> %</td><td>79.39</td><td>0.0968</td><td>18161</td><td>50 %</td><td>105.04</td><td>0.1012</td><td>169</td></tr><tr><td>10</td><td>10</td><td><strong>30</strong> %</td><td>1942.63</td><td>0.1673</td><td>66153</td><td><strong>30</strong> %</td><td>2001.29</td><td>0.1671</td><td>69540</td><td><strong>30</strong> %</td><td>1940.96</td><td>0.1669</td><td>66478</td><td>10 %</td><td>2372.28</td><td>0.1749</td><td>9819</td></tr><tr><td>1000</td><td>8</td><td><strong>25</strong> %</td><td>3389.76</td><td>0.0418</td><td>48615</td><td><strong>25</strong> %</td><td>3309.23</td><td>0.0413</td><td>48268</td><td><strong>25</strong> %</td><td>3447.06</td><td>0.0428</td><td>48411</td><td>0 %</td><td>3600.31</td><td>0.0431</td><td>-</td></tr><tr><td rowspan="3">DO</td><td rowspan="3">no</td><td>0</td><td>18</td><td><strong>67</strong> %</td><td>195.53</td><td>0.024</td><td>11231</td><td><strong>67</strong> %</td><td>187.77</td><td>0.0238</td><td>11117</td><td><strong>67</strong> %</td><td>188.2</td><td>0.0245</td><td>11062</td><td>56 %</td><td>400.29</td><td>0.0246</td><td>3751</td></tr><tr><td>10</td><td>11</td><td><strong>45</strong> %</td><td>1468.68</td><td>0.0331</td><td>25307</td><td><strong>45</strong> %</td><td>1394.14</td><td>0.0327</td><td>25024</td><td><strong>45</strong> %</td><td>1449.27</td><td>0.0338</td><td>24941</td><td>27 %</td><td>2057.64</td><td>0.0341</td><td>9819</td></tr><tr><td>1000</td><td>8</td><td><strong>25</strong> %</td><td>3389.76</td><td>0.0418</td><td>48615</td><td><strong>25</strong> %</td><td>3309.23</td><td>0.0413</td><td>48268</td><td><strong>25</strong> %</td><td>3447.06</td><td>0.0428</td><td>48411</td><td>0 %</td><td>3600.31</td><td>0.0431</td><td>-</td></tr><tr><td rowspan="3">DO</td><td rowspan="3">yes</td><td>0</td><td>18</td><td><strong>100</strong> %</td><td>5.47</td><td>0.0095</td><td>494</td><td><strong>100</strong> %</td><td>5.05</td><td>0.0095</td><td>563</td><td><strong>100</strong> %</td><td>4.83</td><td>0.0094</td><td>385</td><td><strong>100</strong> %</td><td>9.75</td><td>0.0095</td><td>436</td></tr><tr><td>10</td><td>4</td><td><strong>100</strong> %</td><td>230.32</td><td>0.01</td><td>1980</td><td><strong>100</strong> %</td><td>170.88</td><td>0.0098</td><td>2232</td><td><strong>100</strong> %</td><td>149.39</td><td>0.01</td><td>1502</td><td><strong>100</strong> %</td><td>333.38</td><td>0.0099</td><td>1720</td></tr><tr><td>1000</td><td>5</td><td><strong>20</strong> %</td><td>3539.8</td><td>0.0552</td><td>54787</td><td><strong>20</strong> %</td><td>3444.68</td><td>0.0539</td><td>54409</td><td><strong>20</strong> %</td><td>3597.01</td><td>0.0567</td><td>55215</td><td>0 %</td><td>3600.47</td><td>0.0564</td><td>-</td></tr></tbody></table>
<caption>Table 9: Comparing the different Boscia settings on the different problems and the different data sets, i.e. A-Fusion (AF), D-Fusion (DF), A-Optimal (AO) and D-Optimal (DO). One data set contains independent data, the other has correlated data.</caption>

The settings displayed here are using tightening of the bounds, enabling the shadow set within BPCG and using Strong Branching instead of the most fractional branching rule.

The instances for each problem are split into increasingly smaller subsets depending on their minimum solve time, i.e. the minimum time any of the solvers took to solve it. The cut-offs are at 0 seconds (all problems), took at least 10 seconds to solve, 100 s, 1000 s and lastly 2000 s. Note that if none of the solvers terminates on any instance of a subset, the corresponding row is omitted from the table. A line will also be omitted if nothing changes compared to the previous one.

The relative gap only includes the instances on which at least one run didn't terminate within the time limit. That means it does not include the instances that were solved by all.

The average time is taken using the geometric mean shifted by 1 second. Also note that this is the average time over all instances in that group, i.e. it includes the time outs.

<table><thead><tr><th rowspan="2">Type</th><th rowspan="2">Corr.</th><th rowspan="2">Solved after (s)</th><th rowspan="2"># inst.</th><th rowspan="2">% solved</th><th rowspan="2">Time (s)</th><th rowspan="2">relative gap</th><th rowspan="2"># nodes</th><th colspan="2">Strong Branching</th><th colspan="2">Tightening</th><th colspan="2">Tighten Lazification</th><th colspan="2">Secant</th><th colspan="2">Blended Conditional Gradient</th></tr><tr><th>% solved</th><th>Time (s)</th><th>relative gap</th><th># nodes</th><th>% solved</th><th>Time (s)</th><th>relative gap</th><th># nodes</th><th>% solved</th><th>Time (s)</th><th>relative gap</th><th># nodes</th><th>% solved</th><th>Time (s)</th><th>relative gap</th></tr></thead><tbody><tr><td rowspan="3">AO</td><td rowspan="3">no</td><td>0</td><td>18</td><td>44%</td><td>509.39</td><td>7.7803</td><td>2170</td><td>50%</td><td>7.5423</td><td>7847</td><td>50%</td><td>335.12</td><td>7.562</td><td>8113</td><td>44%</td><td>395.39</td><td>7.5383</td><td>2369</td><td>50%</td><td>288.11</td><td>0.7865</td><td>8233</td></tr><tr><td>10</td><td>13</td><td>23%</td><td>1785.5</td><td>10.7691</td><td>2848</td><td>31%</td><td>10.4396</td><td>15068</td><td>31%</td><td>1327.05</td><td>10.4668</td><td>15506</td><td>23%</td><td>1498.71</td><td>10.434</td><td>2891</td><td>31%</td><td>1156.73</td><td>1.0854</td><td>15548</td></tr><tr><td>100</td><td>10</td><td>0%</td><td>3635.44</td><td>13.9969</td><td>-</td><td>10%</td><td>13.5685</td><td>51487</td><td>10%</td><td>3469.34</td><td>13.6038</td><td>52459</td><td>0%</td><td>3600.14</td><td>13.5612</td><td>-</td><td>10%</td><td>3226.67</td><td>1.408</td><td>51685</td></tr><tr><td rowspan="3">AO</td><td rowspan="3">yes</td><td>0</td><td>18</td><td>33%</td><td>1411.93</td><td>0.5182</td><td>26947</td><td>44%</td><td>895.28</td><td>0.2547</td><td>35056</td><td>44%</td><td>1032.46</td><td>0.3766</td><td>52251</td><td>44%</td><td>780.03</td><td>0.255</td><td>44423</td><td>39%</td><td>1056.59</td><td>0.2829</td><td>50528</td></tr><tr><td>10</td><td>12</td><td>8%</td><td>3482.79</td><td>0.9416</td><td>69567</td><td>17%</td><td>2859.77</td><td>0.377</td><td>66564</td><td>17%</td><td>3262.57</td><td>0.5599</td><td>109156</td><td>17%</td><td>3106.83</td><td>0.3776</td><td>98795</td><td>8%</td><td>3475.97</td><td>0.5559</td><td>135093</td></tr><tr><td>100</td><td>8</td><td>38%</td><td>2711.25</td><td>0.0781</td><td>13742</td><td>62%</td><td>1281.81</td><td>0.0291</td><td>41038</td><td>62%</td><td>1540.09</td><td>0.0317</td><td>49409</td><td>50%</td><td>1805.8</td><td>0.0322</td><td>37498</td><td>62%</td><td>1471.05</td><td>0.0305</td><td>63486</td></tr><tr><td rowspan="3">AF</td><td rowspan="3">no</td><td>0</td><td>18</td><td>72%</td><td>224.3</td><td>0.0402</td><td>4937</td><td>83%</td><td>69.05</td><td>0.0184</td><td>15279</td><td>78%</td><td>77.05</td><td>0.0196</td><td>16534</td><td>78%</td><td>88.49</td><td>0.0198</td><td>12429</td><td>83%</td><td>74.95</td><td>0.0191</td><td>23414</td></tr><tr><td>10</td><td>11</td><td>55%</td><td>1382.75</td><td>0.0595</td><td>9816</td><td>73%</td><td>471.19</td><td>0.0239</td><td>27754</td><td>64%</td><td>563.16</td><td>0.0258</td><td>31716</td><td>64%</td><td>673.09</td><td>0.0261</td><td>23944</td><td>73%</td><td>513.29</td><td>0.0249</td><td>42680</td></tr><tr><td>100</td><td>8</td><td>38%</td><td>2711.25</td><td>0.0781</td><td>13742</td><td>62%</td><td>1281.81</td><td>0.0291</td><td>41038</td><td>62%</td><td>1540.09</td><td>0.0317</td><td>49409</td><td>50%</td><td>1805.8</td><td>0.0322</td><td>37498</td><td>62%</td><td>1471.05</td><td>0.0305</td><td>63486</td></tr><tr><td rowspan="3">AF</td><td rowspan="3">yes</td><td>0</td><td>18</td><td>28%</td><td>1658.47</td><td>3.2623</td><td>30096</td><td>28%</td><td>1325.29</td><td>2.1184</td><td>28058</td><td>28%</td><td>1461.5</td><td>2.4675</td><td>36446</td><td>28%</td><td>1296.61</td><td>2.1909</td><td>30838</td><td>28%</td><td>1378.94</td><td>2.1662</td><td>35027</td></tr><tr><td>10</td><td>17</td><td>24%</td><td>2198.67</td><td>3.4656</td><td>37295</td><td>24%</td><td>1824.24</td><td>2.2424</td><td>34688</td><td>24%</td><td>2016.49</td><td>2.6121</td><td>45073</td><td>24%</td><td>1855.8</td><td>2.3194</td><td>38217</td><td>24%</td><td>1899.87</td><td>2.3009</td><td>43212</td></tr><tr><td>100</td><td>15</td><td>13%</td><td>3420.23</td><td>3.9592</td><td>65163</td><td>13%</td><td>3000.06</td><td>2.54</td><td>55034</td><td>13%</td><td>3138.87</td><td>2.9591</td><td>68958</td><td>13%</td><td>3062.15</td><td>2.6273</td><td>56098</td><td>13%</td><td>2985.76</td><td>2.6282</td><td>62897</td></tr><tr><td rowspan="3">DF</td><td rowspan="3">no</td><td>0</td><td>18</td><td>89%</td><td>25.69</td><td>0.0125</td><td>272</td><td>94%</td><td>4.94</td><td>0.0104</td><td>227</td><td>94%</td><td>5.24</td><td>0.0102</td><td>333</td><td>94%</td><td>5.27</td><td>0.0105</td><td>209</td><td>94%</td><td>5.61</td><td>0.0103</td><td>331</td></tr><tr><td>10</td><td>3</td><td>33%</td><td>3300.66</td><td>0.0281</td><td>79</td><td>67%</td><td>447.07</td><td>0.0152</td><td>101</td><td>67%</td><td>614.7</td><td>0.0138</td><td>233</td><td>67%</td><td>451.16</td><td>0.0142</td><td>99</td><td>67%</td><td>739.18</td><td>0.0126</td><td>232</td></tr><tr><td>1000</td><td>8</td><td>7%</td><td>3499.51</td><td>4.263</td><td>75549</td><td>7%</td><td>3370.29</td><td>2.7208</td><td>73985</td><td>7%</td><td>3434.08</td><td>3.1697</td><td>87381</td><td>7%</td><td>3412.79</td><td>2.8142</td><td>79157</td><td>7%</td><td>3332.5</td><td>2.8296</td><td>78621</td></tr><tr><td rowspan="3">DF</td><td rowspan="3">yes</td><td>0</td><td>18</td><td>56%</td><td>133.22</td><td>0.1285</td><td>16635</td><td>61%</td><td>77.67</td><td>0.0967</td><td>18104</td><td>61%</td><td>76.96</td><td>0.0962</td><td>18141</td><td>56%</td><td>85.74</td><td>0.0987</td><td>16260</td><td>61%</td><td>72.59</td><td>0.0938</td><td>17502</td></tr><tr><td>10</td><td>10</td><td>20%</td><td>2517.61</td><td>0.2244</td><td>83020</td><td>30%</td><td>1935.53</td><td>0.1668</td><td>66290</td><td>30%</td><td>1838.5</td><td>0.1656</td><td>66376</td><td>20%</td><td>2133.82</td><td>0.1703</td><td>81149</td><td>30%</td><td>1648.16</td><td>0.1615</td><td>64030</td></tr><tr><td>100</td><td>9</td><td>11%</td><td>3493.0</td><td>0.2482</td><td>163999</td><td>22%</td><td>3323.78</td><td>0.1842</td><td>98814</td><td>22%</td><td>3215.14</td><td>0.1829</td><td>98904</td><td>11%</td><td>3495.7</td><td>0.1882</td><td>161073</td><td>22%</td><td>2884.32</td><td>0.1784</td><td>95276</td></tr><tr><td rowspan="3">DO</td><td rowspan="3">no</td><td>0</td><td>18</td><td>56%</td><td>354.36</td><td>0.1266</td><td>3254</td><td>61%</td><td>196.4</td><td>0.0243</td><td>7423</td><td>67%</td><td>191.89</td><td>0.0248</td><td>13438</td><td>61%</td><td>227.48</td><td>0.0252</td><td>7050</td><td>67%</td><td>158.11</td><td>0.0221</td><td>14300</td></tr><tr><td>10</td><td>11</td><td>27%</td><td>2133.07</td><td>0.2009</td><td>8332</td><td>36%</td><td>1503.71</td><td>0.0336</td><td>18386</td><td>45%</td><td>1429.48</td><td>0.0343</td><td>30310</td><td>36%</td><td>1652.29</td><td>0.0354</td><td>17358</td><td>45%</td><td>1156.8</td><td>0.03</td><td>32303</td></tr><tr><td>100</td><td>8</td><td>0%</td><td>3659.93</td><td>0.2725</td><td>-</td><td>12%</td><td>3473.32</td><td>0.0425</td><td>43491</td><td>25%</td><td>3393.4</td><td>0.0434</td><td>58562</td><td>12%</td><td>3577.58</td><td>0.045</td><td>42633</td><td>25%</td><td>3006.11</td><td>0.0375</td><td>63716</td></tr><tr><td rowspan="3">DO</td><td rowspan="3">yes</td><td>0</td><td>10</td><td>6%</td><td>3679.97</td><td>0.3538</td><td>-</td><td>0%</td><td>3601.58</td><td>0.0499</td><td>-</td><td>65771</td><td>0%</td><td>3600.1</td><td>0.0535</td><td>-</td><td>17%</td><td>3315.64</td><td>0.0442</td><td>74469</td><td></td><td></td><td></td></tr><tr><td>1000</td><td>6</td><td>0%</td><td>3696.16</td><td>0.4197</td><td>-</td><td>0%</td><td>3601.9</td><td>0.0561</td><td>-</td><td>65771</td><td>0%</td><td>3600.12</td><td>0.0599</td><td>-</td><td>20%</td><td>3261.52</td><td>0.0499</td><td>74469</td><td></td><td></td><td></td></tr><tr><td>2000</td><td>5</td><td>0%</td><td>3696.16</td><td>0.4197</td><td>-</td><td>0%</td><td>3601.9</td><td>0.0561</td><td>-</td><td>65771</td><td>0%</td><td>3600.12</td><td>0.0599</td><td>-</td><td>20%</td><td>3261.52</td><td>0.0499</td><td>74469</td><td></td><td></td><td></td></tr><tr><td rowspan="3">DO</td><td rowspan="3">yes</td><td>0</td><td>18</td><td>94%</td><td>18.54</td><td>0.0094</td><td>281</td><td>100%</td><td>5.63</td><td>0.0093</td><td>378</td><td>100%</td><td>5.5</td><td>0.0097</td><td>638</td><td>100%</td><td>5.67</td><td>0.0094</td><td>392</td><td>94%</td><td>4.76</td><td>0.0095</td><td>280</td></tr><tr><td>10</td><td>4</td><td>75%</td><td>1385.8</td><td>0.0104</td><td>1206</td><td>100%</td><td>205.16</td><td>0.0098</td><td>1456</td><td>100%</td><td>204.36</td><td>0.01</td><td>2491</td><td>100%</td><td>221.99</td><td>0.0098</td><td>1470</td><td>75%</td><td>134.78</td><td>0.0098</td><td>1108</td></tr></tbody></table>
<caption>Table 10: Comparing performance between A-criterion with and without log. For Tr(X⁻¹), we use both the Secant linesearch as well as the Adaptive linesearch wrapped in a MonotonicGeneric linesearch. For log Tr(X⁻¹), we just consider the Secant linesearch since it is numerically better.</caption>

The instances for each problem are split into increasingly smaller subsets depending on their minimum solve time, i.e. the minimum time any of the solvers took to solve it. The cut-offs are at 0 seconds (all problems), took at least 10 seconds to solve, 100 s, 1000 s and lastly 2000 s. Note that if none of the solvers terminates on any instance of a subset, the corresponding row is omitted from the table.

The relative gap is computed for the instances on which at least one method did not terminate within the time limit. That means it excludes the instances on which all methods terminated. The average number of nodes is taken over all solved instances for that solver. The average time is taken using the geometric mean shifted by 1 second. Also note that this is the average time over all instances in that group, i.e. it includes the time outs.

<table><thead><tr><th rowspan="2">Type</th><th rowspan="2">Corr.</th><th colspan="3">Tr (X<sup>-1</sup>)</th><th colspan="3">Tr (X<sup>-1</sup>)</th><th colspan="3">log Tr (X<sup>-1</sup>)</th></tr><tr><th>Solved<br>after<br>(s)</th><th>#<br>inst.</th><th>%<br>solved</th><th>Time (s)</th><th>relative<br>gap</th><th># nodes</th><th>%<br>solved</th><th>Time (s)</th><th>relative<br>gap</th><th># nodes</th><th>%<br>solved</th><th>Time (s)</th><th>relative<br>gap</th><th># nodes</th></tr></thead><tbody><tr><td rowspan="4">AO</td><td rowspan="4">no</td><td>0</td><td>18</td><td><strong>50</strong> %</td><td>358.32</td><td>7.5254</td><td>7775</td><td>44 %</td><td>395.39</td><td>7.5383</td><td>2369</td><td><strong>50</strong> %</td><td><strong>279.53</strong></td><td>0.3128</td><td>3116</td></tr><tr><td>10</td><td>15</td><td><strong>40</strong> %</td><td>996.8</td><td>9.0286</td><td>11600</td><td>33 %</td><td>1078.18</td><td>9.0442</td><td>3712</td><td><strong>40</strong> %</td><td><strong>733.37</strong></td><td>0.3736</td><td>4637</td></tr><tr><td>100</td><td>10</td><td><strong>10</strong> %</td><td>3554.77</td><td>13.5379</td><td>50135</td><td>0 %</td><td>3600.14</td><td>13.5612</td><td>-</td><td><strong>10</strong> %</td><td><strong>3259.84</strong></td><td>0.5553</td><td>21991</td></tr><tr><td>yes</td><td>0</td><td>18</td><td>44 %</td><td>831.95</td><td>0.1441</td><td>39425</td><td>44 %</td><td>780.03</td><td>0.255</td><td>44423</td><td><strong>61</strong> %</td><td><strong>206.45</strong></td><td>0.0262</td><td>6508</td></tr><tr><td rowspan="4">AF</td><td rowspan="4">yes</td><td>0</td><td>18</td><td>28 %</td><td>1330.47</td><td>2.1036</td><td>31537</td><td>28 %</td><td>1296.61</td><td>2.1909</td><td>30838</td><td><strong>50</strong> %</td><td><strong>270.53</strong></td><td>5.1204</td><td>7754</td></tr><tr><td>10</td><td>13</td><td>15 %</td><td>3037.99</td><td>2.8795</td><td>63405</td><td>15 %</td><td>2986.85</td><td>2.9945</td><td>56098</td><td><strong>31</strong> %</td><td><strong>1837.4</strong></td><td>7.9606</td><td>17411</td></tr><tr><td>100</td><td>12</td><td>17 %</td><td>2995.32</td><td>2.9574</td><td>63405</td><td>17 %</td><td>2940.73</td><td>3.0822</td><td>56098</td><td><strong>25</strong> %</td><td><strong>2761.53</strong></td><td>8.9546</td><td>23174</td></tr><tr><td>1000</td><td>11</td><td>9 %</td><td>3399.3</td><td>3.2253</td><td>87165</td><td>9 %</td><td>3363.42</td><td>3.3615</td><td>79157</td><td><strong>18</strong> %</td><td><strong>3015.56</strong></td><td>10.2324</td><td>23230</td></tr></tbody></table>