# Linear Minimization Oracles

The Linear Minimization Oracle (LMO) is a key component called at each iteration of the FW algorithm. Given $d\in \mathcal{X}$, it returns a vertex of the feasible set:

\[v\in \argmin_{x\in \mathcal{C}} \langle d,x \rangle.\]

See Combettes, Pokutta 2021 for references on most LMOs implemented in the package and their comparison with projection operators.

## Interface and wrappers

`FrankWolfe.LinearMinimizationOracle`

— TypeSupertype for linear minimization oracles.

All LMOs must implement `compute_extreme_point(lmo::LMO, direction)`

and return a vector `v`

of the appropriate type.

All of them are subtypes of `FrankWolfe.LinearMinimizationOracle`

and implement the following method:

`FrankWolfe.compute_extreme_point`

— Function`compute_extreme_point(lmo::LinearMinimizationOracle, direction; kwargs...)`

Computes the point `argmin_{v ∈ C} v ⋅ direction`

with `C`

the set represented by the LMO. Most LMOs feature `v`

as a keyword argument that allows for an in-place computation whenever `v`

is dense. All LMOs should accept keyword arguments that they can ignore.

We also provide some meta-LMOs wrapping another one with extended behavior:

`FrankWolfe.CachedLinearMinimizationOracle`

— Type`CachedLinearMinimizationOracle{LMO}`

Oracle wrapping another one of type lmo. Subtypes of `CachedLinearMinimizationOracle`

contain a cache of previous solutions.

By convention, the inner oracle is named `inner`

. Cached optimizers are expected to implement `Base.empty!`

and `Base.length`

.

`FrankWolfe.ProductLMO`

— Type`ProductLMO(lmos)`

Linear minimization oracle over the Cartesian product of multiple LMOs.

`FrankWolfe.SingleLastCachedLMO`

— Type`SingleLastCachedLMO{LMO, VT}`

Caches only the last result from an LMO and stores it in `last_vertex`

. Vertices of `LMO`

have to be of type `VT`

if provided.

`FrankWolfe.MultiCacheLMO`

— Type`MultiCacheLMO{N, LMO, A}`

Cache for a LMO storing up to `N`

vertices in the cache, removed in FIFO style. `oldest_idx`

keeps track of the oldest index in the tuple, i.e. to replace next. `VT`

, if provided, must be the type of vertices returned by `LMO`

`FrankWolfe.VectorCacheLMO`

— Type`VectorCacheLMO{LMO, VT}`

Cache for a LMO storing an unbounded number of vertices of type `VT`

in the cache. `VT`

, if provided, must be the type of vertices returned by `LMO`

## Norm balls

`FrankWolfe.EllipsoidLMO`

— Type`EllipsoidLMO(A, c, r)`

Linear minimization over an ellipsoid centered at `c`

of radius `r`

:

`x: (x - c)^T A (x - c) ≤ r`

The LMO stores the factorization `F`

of A that is used to solve linear systems `A⁻¹ x`

. The result of the linear system solve is stored in `buffer`

. The ellipsoid is assumed to be full-dimensional -> A is positive definite.

`FrankWolfe.KNormBallLMO`

— Type`KNormBallLMO{T}(K::Int, right_hand_side::T)`

LMO with feasible set being the K-norm ball in the sense of 2010.07243, i.e., the convex hull over the union of an L*1-ball with radius τ and an L*∞-ball with radius τ/K:

`C_{K,τ} = conv { B_1(τ) ∪ B_∞(τ / K) }`

with `τ`

the `right_hand_side`

parameter. The K-norm is defined as the sum of the largest `K`

absolute entries in a vector.

`FrankWolfe.LpNormLMO`

— Type`LpNormLMO{T, p}(right_hand_side)`

LMO with feasible set being an L-p norm ball:

`C = {x ∈ R^n, norm(x, p) ≤ right_hand_side}`

`FrankWolfe.NuclearNormLMO`

— Type`NuclearNormLMO{T}(radius)`

LMO over matrices that have a nuclear norm less than `radius`

. The LMO returns the best rank-one approximation matrix with singular value `radius`

, computed with Arpack.

`FrankWolfe.OrderWeightNormLMO`

— Type`OrderWeightNormLMO(weights,radius)`

LMO with feasible set being the atomic ordered weighted l1 norm: https://arxiv.org/pdf/1409.4271

`C = {x ∈ R^n, Ω_w(x) ≤ R} `

The weights are assumed to be positive.

`FrankWolfe.SpectraplexLMO`

— Type`SpectraplexLMO{T,M}(radius::T,gradient_container::M,ensure_symmetry::Bool=true)`

Feasible set

`{X ∈ 𝕊_n^+, trace(X) == radius}`

`gradient_container`

is used to store the symmetrized negative direction. `ensure_symmetry`

indicates whether the linear function is made symmetric before computing the eigenvector.

`FrankWolfe.UnitSpectrahedronLMO`

— Type`UnitSpectrahedronLMO{T,M}(radius::T, gradient_container::M)`

Feasible set of PSD matrices with bounded trace:

`{X ∈ 𝕊_n^+, trace(X) ≤ radius}`

`gradient_container`

is used to store the symmetrized negative direction. `ensure_symmetry`

indicates whether the linear function is made symmetric before computing the eigenvector.

## Simplex

`FrankWolfe.HyperSimplexOracle`

— Type`HyperSimplexOracle(radius)`

Represents the scaled hypersimplex of radius τ, the convex hull of vectors `v`

such that:

- v_i ∈ {0, τ}
- ||v||_0 = k

Equivalently, this is the convex hull of the vertices of the K-sparse polytope lying in the nonnegative orthant.

`FrankWolfe.ProbabilitySimplexOracle`

— Type`ProbabilitySimplexOracle(right_side)`

Represents the scaled probability simplex:

`C = {x ∈ R^n_+, ∑x = right_side}`

`FrankWolfe.UnitHyperSimplexOracle`

— Type`UnitHyperSimplexOracle(radius)`

Represents the scaled unit hypersimplex of radius τ, the convex hull of vectors `v`

such that:

- v_i ∈ {0, τ}
- ||v||_0 ≤ k

Equivalently, this is the intersection of the K-sparse polytope and the nonnegative orthant.

`FrankWolfe.UnitSimplexOracle`

— Type`UnitSimplexOracle(right_side)`

Represents the scaled unit simplex:

`C = {x ∈ R^n_+, ∑x ≤ right_side}`

`FrankWolfe.compute_dual_solution`

— MethodDual costs for a given primal solution to form a primal dual pair for scaled probability simplex. Returns two vectors. The first one is the dual costs associated with the constraints and the second is the reduced costs for the variables.

`FrankWolfe.compute_dual_solution`

— MethodDual costs for a given primal solution to form a primal dual pair for scaled unit simplex. Returns two vectors. The first one is the dual costs associated with the constraints and the second is the reduced costs for the variables.

`FrankWolfe.compute_extreme_point`

— MethodLMO for scaled probability simplex. Returns a vector with one active value equal to RHS in the most improving (or least degrading) direction.

`FrankWolfe.compute_extreme_point`

— MethodLMO for scaled unit simplex: `∑ x_i = τ`

Returns either vector of zeros or vector with one active value equal to RHS if there exists an improving direction.

## Polytope

`FrankWolfe.BirkhoffPolytopeLMO`

— Type`BirkhoffPolytopeLMO`

The Birkhoff polytope encodes doubly stochastic matrices. Its extreme vertices are all permutation matrices of side-dimension `dimension`

.

`FrankWolfe.ConvexHullOracle`

— Type`ConvexHullOracle{AT,VT}`

Convex hull of a finite number of vertices of type `AT`

, stored in a vector of type `VT`

.

`FrankWolfe.KSparseLMO`

— Type`KSparseLMO{T}(K::Int, right_hand_side::T)`

LMO for the K-sparse polytope:

`C = B_1(τK) ∩ B_∞(τ)`

with `τ`

the `right_hand_side`

parameter. The LMO results in a vector with the K largest absolute values of direction, taking values `-τ sign(x_i)`

.

`FrankWolfe.ScaledBoundL1NormBall`

— Type`ScaledBoundL1NormBall(lower_bounds, upper_bounds)`

Polytope similar to a L1-ball with shifted bounds. It is the convex hull of two scaled and shifted unit vectors for each axis (shifted to the center of the polytope, i.e., the elementwise midpoint of the bounds). Lower and upper bounds are passed on as abstract vectors, possibly of different types. For the standard L1-ball, all lower and upper bounds would be -1 and 1.

`FrankWolfe.ScaledBoundLInfNormBall`

— Type`ScaledBoundLInfNormBall(lower_bounds, upper_bounds)`

Polytope similar to a L-inf-ball with shifted bounds or general box constraints. Lower- and upper-bounds are passed on as abstract vectors, possibly of different types. For the standard L-inf ball, all lower- and upper-bounds would be -1 and 1.

## MathOptInterface

`FrankWolfe.MathOptLMO`

— Type`MathOptLMO{OT <: MOI.Optimizer} <: LinearMinimizationOracle`

Linear minimization oracle with feasible space defined through a MathOptInterface.Optimizer. The oracle call sets the direction and reruns the optimizer.

The `direction`

vector has to be set in the same order of variables as the `MOI.ListOfVariableIndices()`

getter.

The Boolean `use_modify`

determines if the objective in`compute_extreme_point`

is updated with `MOI.modify(o, ::MOI.ObjectiveFunction, ::MOI.ScalarCoefficientChange)`

or with `MOI.set(o, ::MOI.ObjectiveFunction, f)`

. `use_modify = true`

decreases the runtime and memory allocation for models created as an optimizer object and defined directly with MathOptInterface. `use_modify = false`

should be used for CachingOptimizers.

`FrankWolfe.convert_mathopt`

— Function`convert_mathopt(lmo::LMO, optimizer::OT; kwargs...) -> MathOptLMO{OT}`

Converts the given LMO to its equivalent MathOptInterface representation using `optimizer`

. Must be implemented by LMOs.