Oracles

AbstractOracle

Abstract supertype for Frank-Wolfe linear minimization oracles.

Every concrete oracle lmo <: AbstractOracle is a callable struct invoked as lmo(v, g), writing the solution of

\[\min_{v \in C} \langle g, v \rangle\]

into v in-place.

Plain functions (v, g) -> v are auto-wrapped as FunctionOracle by solve. Non-function callable structs should subtype AbstractOracle directly or be wrapped explicitly with FunctionOracle for specialized dispatch (e.g. active_set, sparse vertex protocol).

FunctionOracle{F} <: AbstractOracle

Wraps a plain function fn(v, g) -> v as an AbstractOracle.

lmo = FunctionOracle(my_lmo_function)
solve(f, lmo, x0; grad=∇f!)

Simplex{T, Equality}(r)

Oracle for simplex constraints. The type parameter Equality controls whether the budget constraint is $\le$ or $=$.

• Simplex(r) / Simplex(; r=1.0): capped simplex $\{x \ge 0,\; \sum x_i \le r\}$
• ProbSimplex(r) / ProbabilitySimplex(r): probability simplex $\{x \ge 0,\; \sum x_i = r\}$

Capped (Equality=false): Vertices are $\{0, r e_1, \ldots, r e_n\}$. Selects $r e_{i^*}$ where $i^* = \arg\min_i g_i$ when $g_{i^*} < 0$, otherwise the origin. Complexity: $O(n)$.

Probability (Equality=true): Vertices are $\{r e_1, \ldots, r e_n\}$. Always selects $r e_{i^*}$ where

\[i^* = \arg\min_i g_i\]

Complexity: $O(n)$.

ProbSimplex(r=1.0)

Convenience constructor for Simplex{T, true}(r) – the probability simplex $\{x \ge 0,\; \sum x_i = r\}$.

ProbabilitySimplex(r=1.0)

Alias for ProbSimplex.

Knapsack(budget, m)

Oracle for the knapsack polytope

\[C = \{x \in [0,1]^m : \sum x_i \le \text{budget}\}\]

Selects up to budget indices with most negative gradient and sets them to 1; only indices with strictly negative gradient are selected. Complexity: $O(m \cdot k)$ where $k = \text{budget}$, via zero-allocation insertion sort. For large budgets ($k \approx m$), consider using a full sort or a Box oracle instead.

MaskedKnapsack(budget, masked, m)

Oracle for the knapsack polytope with masked indices fixed to 1:

\[C = \{x \in [0,1]^m : \sum x_i \le \text{budget},\; x_e = 1 \;\forall\; e \in \text{masked}\}\]

Fixes masked entries to 1, then selects up to $k = \text{budget} - |\text{masked}|$ non-masked indices with most negative gradient; only indices with strictly negative gradient are selected. Complexity: $O(m \cdot k)$ via zero-allocation insertion sort.

Box(lb, ub)

Oracle for the box constraint set

\[C = \{x : l_i \le x_i \le u_i\}\]

Each coordinate is solved independently: select $l_i$ when $g_i \ge 0$, $u_i$ when $g_i < 0$:

\[v_i = \begin{cases} l_i & g_i \ge 0 \\ u_i & g_i < 0 \end{cases}\]

Complexity: $O(n)$.

ScalarBox{T}(lb, ub)

Oracle for a box constraint with uniform scalar bounds:

\[C = \{x : l \le x_i \le u \;\forall i\}\]

Memory-efficient alternative to Box when all bounds are identical. Convenience constructor: Box(lb::Real, ub::Real).

Complexity: $O(n)$.

WeightedSimplex(α, β, lb)

Oracle for the weighted simplex

\[C = \{x \ge l : \langle \alpha, x \rangle \le \beta\}\]

Shifts $u = x - l$, adjusted budget $\beta_{\mathrm{bar}} = \beta - \langle \alpha, l \rangle$. Then

\[u^* = \frac{\bar\beta}{\alpha_{i^*}}\, e_{i^*}, \quad i^* = \arg\min_i \left\{\frac{g_i}{\alpha_i} : g_i < 0\right\}\]

Returns $v = u^* + l$.

When all $g_i \ge 0$, returns the lower bound $l$.

Complexity: $O(m)$.

Spectraplex{T}(n, r)

Oracle for the spectraplex (spectrahedron with trace constraint)

\[C = \{X \in \mathbb{S}_+^n : \operatorname{tr}(X) = r\}\]

The solver operates on vec(X) (length $n^2$). Given gradient $g$ (as a vector), reshapes to $G \in \mathbb{R}^{n \times n}$, symmetrizes, and computes the minimum eigenvector $v_{\min}$ of $\frac{1}{2}(G + G^\top)$. The vertex is the rank-1 matrix $r \, v_{\min} v_{\min}^\top$, written column major into the output buffer.

Convenience: Spectraplex(n) gives the unit spectraplex ($r = 1$).

Complexity: $O(n^3)$ (dense eigendecomposition).

ActiveConstraints{T}

Active constraint identification at a solution $x^*$.

Fields

• bound_indices::Vector{Int} – indices pinned to bounds
• bound_values::Vector{T} – their bound values
• bound_is_lower::BitVector – true if bound is a lower bound, false if upper
• free_indices::Vector{Int} – unconstrained variable indices
• eq_normals – vector-like collection of equality constraint normals (in full space)
• eq_rhs – equality constraint RHS values

active_set(lmo, x; tol=1e-8) -> ActiveConstraints

Identify active constraints at solution x for the given oracle.

Returns an ActiveConstraints with bound-pinned indices, free indices, and equality constraint normals/RHS.