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.LinearMinimizationOracleType

Supertype 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_pointFunction
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.CachedLinearMinimizationOracleType
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.ProductLMOType
ProductLMO(lmos)

Linear minimization oracle over the Cartesian product of multiple LMOs.

FrankWolfe.SingleLastCachedLMOType
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.MultiCacheLMOType
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.VectorCacheLMOType
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.EllipsoidLMOType
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.KNormBallLMOType
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 L1-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.LpNormLMOType
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.NuclearNormLMOType
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.SpectraplexLMOType
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.UnitSpectrahedronLMOType
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.compute_dual_solutionMethod

Dual 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_solutionMethod

Dual 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_pointMethod

LMO 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_pointMethod

LMO 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.BirkhoffPolytopeLMOType
BirkhoffPolytopeLMO

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

FrankWolfe.ConvexHullOracleType
ConvexHullOracle{AT,VT}

Convex hull of a finite number of vertices of type AT, stored in a vector of type VT.

FrankWolfe.KSparseLMOType
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.ScaledBoundL1NormBallType
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.ScaledBoundLInfNormBallType
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.MathOptLMOType
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 incompute_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_mathoptFunction
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.

Index