Linear Minimization Oracles

LinearMinimizationOracle

Supertype for linear minimization oracles.

All LMOs must implement compute_extreme_point(lmo::LMO, direction) and return a vector v of the appropriate type.

See also: compute_extreme_point.

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.

CachedLMO{LMO}

Oracle wrapping another one of type lmo. Subtypes of CachedLMO 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.

ProductLMO(lmos)

Linear minimization oracle over the Cartesian product of multiple LMOs.

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.

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

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

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.

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.

LpNormBallLMO{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}

OrderWeightNormBallLMO(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.

HyperSimplexLMO(K, 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.

ProbabilitySimplexLMO(right_side)

Represents the scaled probability simplex:

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

UnitHyperSimplexLMO(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.

UnitSimplexLMO(right_side)

Represents the scaled unit simplex:

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

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.

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.

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

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.

BirkhoffPolytopeLMO

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

BoxLMO(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.

ConvexHullLMO{AT,VT}

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

DiamondLMO(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.

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

ZeroOneHypercubeLMO

{0,1} hypercube polytope.

FantopeLMO(k::Int)

Spectrahedron defined on square symmetric matrices as: F_k = {X : 0 ≼ X ≼ I_n, tr(X) = k} or equivalently as: F_k = conv{VVᵀ, VᵀV = I_k}

Source: V.Q. Vu, J. Cho, J. Lei, K. Rohe Dattorro, Convex optimization & euclidean distance geometry, 2.3.2.

NuclearNormBallLMO{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.

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.

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.

MathOptLMO{OT <: MOI.AbstractOptimizer} <: 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.

Copy and modify the constriants if necesssary for computing in-face vertex.

function barrier for performance

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.

Fast way to compute gammamax. Check every constraint and compute the corresponding gammaupper_bound.