Linear map (LinearMap)

LinearMap{N<:Real, S<:LazySet{N}, NM, MAT<:AbstractMatrix{NM}} <: LazySet{N}

Type that represents a linear transformation $M⋅S$ of a convex set $S$.

Fields

• M – matrix/linear map
• X – convex set

Notes

This type is parametric in the elements of the linear map, NM, which is independent of the numeric type of the wrapped set (N). Typically NM = N, but there may be exceptions, e.g., if NM is an interval that holds numbers of type N, where N is a floating point number type such as Float64.

Examples

For the examples we create a $3×2$ matrix and two unit squares, one of them being two-dimensional and the other one being one-dimensional.

julia> A = [1 2; 1 3; 1 4]; X = BallInf([0, 0], 1); Y = BallInf([0], 1);

The function $*$ can be used as an alias to construct a LinearMap object.

julia> lm = LinearMap(A, X)
LinearMap{Int64,BallInf{Int64},Int64,Array{Int64,2}}([1 2; 1 3; 1 4], BallInf{Int64}([0, 0], 1))

julia> lm2 = A * X
LinearMap{Int64,BallInf{Int64},Int64,Array{Int64,2}}([1 2; 1 3; 1 4], BallInf{Int64}([0, 0], 1))

julia> lm == lm2
true

For convenience, A does not need to be a matrix but we also allow to use vectors (interpreted as an $n×1$ matrix) and UniformScalings resp. scalars (interpreted as a scaling, i.e., a scaled identity matrix). Scaling by $1$ is ignored.

julia> using LinearAlgebra: I

julia> [2, 3] * Y
LinearMap{Int64,BallInf{Int64},Int64,Array{Int64,2}}([2; 3], BallInf{Int64}([0], 1))

julia> lm3 = 2 * X
LinearMap{Int64,BallInf{Int64},Int64,SparseArrays.SparseMatrixCSC{Int64,Int64}}(
  [1, 1]  =  2
  [2, 2]  =  2, BallInf{Int64}([0, 0], 1))

julia> 2I * X == lm3
true

julia> 1I * X == X
true

Applying a linear map to a LinearMap object combines the two maps into a single LinearMap instance. Again we can make use of the conversion for convenience.

julia> B = transpose(A); B * lm
LinearMap{Int64,BallInf{Int64},Int64,Array{Int64,2}}([3 9; 9 29], BallInf{Int64}([0, 0], 1))

julia> B = [3, 4, 5]; B * lm
LinearMap{Int64,BallInf{Int64},Int64,Array{Int64,2}}([12 38], BallInf{Int64}([0, 0], 1))

julia> B = 2; B * lm
LinearMap{Int64,BallInf{Int64},Int64,Array{Int64,2}}([2 4; 2 6; 2 8], BallInf{Int64}([0, 0], 1))

The application of a LinearMap to a ZeroSet or an EmptySet is simplified automatically.

julia> A * ZeroSet{Int}(2)
ZeroSet{Int64}(3)

julia> A * EmptySet{Int}()
EmptySet{Int64}()

    *(map::Union{AbstractMatrix, UniformScaling, AbstractVector, Real}, X::LazySet)

Alias to create a LinearMap object.

Input

• map – linear map
• X – convex set

Output

A lazy linear map, i.e., a LinearMap instance.

dim(lm::LinearMap)

Return the dimension of a linear map.

Input

• lm – linear map

Output

The ambient dimension of the linear map.

ρ(d::AbstractVector{N}, lm::LinearMap{N}; kwargs...) where {N<:Real}

Return the support function of the linear map.

Input

• d – direction
• lm – linear map
• kwargs – additional arguments that are passed to the support function algorithm

Output

The support function in the given direction. If the direction has norm zero, the result depends on the wrapped set.

Notes

If $L = M⋅S$, where $M$ is a matrix and $S$ is a convex set, it follows that $ρ(d, L) = ρ(M^T d, S)$ for any direction $d$.

σ(d::AbstractVector{N}, lm::LinearMap{N}) where {N<:Real}

Return the support vector of the linear map.

Input

• d – direction
• lm – linear map

Output

The support vector in the given direction. If the direction has norm zero, the result depends on the wrapped set.

Notes

If $L = M⋅S$, where $M$ is a matrix and $S$ is a convex set, it follows that $σ(d, L) = M⋅σ(M^T d, S)$ for any direction $d$.

∈(x::AbstractVector{N}, lm::LinearMap{N}) where {N<:Real}

Check whether a given point is contained in a linear map of a convex set.

Input

• x – point/vector
• lm – linear map of a convex set

Output

true iff $x ∈ lm$.

Algorithm

Note that $x ∈ M⋅S$ iff $M^{-1}⋅x ∈ S$. This implementation does not explicitly invert the matrix, which is why it also works for non-square matrices.

Examples

julia> lm = LinearMap([2.0 0.0; 0.0 1.0], BallInf([1., 1.], 1.));

julia> [5.0, 1.0] ∈ lm
false
julia> [3.0, 1.0] ∈ lm
true

An example with non-square matrix:

julia> B = BallInf(zeros(4), 1.);

julia> M = [1. 0 0 0; 0 1 0 0]/2;

julia> [0.5, 0.5] ∈ M*B
true

an_element(lm::LinearMap{N})::Vector{N} where {N<:Real}

Return some element of a linear map.

Input

• lm – linear map

Output

An element in the linear map. It relies on the an_element function of the wrapped set.

isbounded(lm::LinearMap; cond_tol::Number=DEFAULT_COND_TOL)

Determine whether a linear map is bounded.

Input

• lm – linear map
• cond_tol – (optional) tolerance of matrix condition (used to check whether the matrix is invertible)

Output

true iff the linear map is bounded.

Algorithm

We first check if the matrix is zero or the wrapped set is bounded. If not, we perform a sufficient check whether the matrix is invertible. If the matrix is invertible, then the map being bounded is equivalent to the wrapped set being bounded, and hence the map is unbounded. Otherwise, we check boundedness via isbounded_unit_dimensions.

isempty(lm::LinearMap)

Return if a linear map is empty or not.

Input

• lm – linear map

Output

true iff the wrapped set is empty.

vertices_list(lm::LinearMap{N}; prune::Bool=true)::Vector{Vector{N}} where {N<:Real}

Return the list of vertices of a (polyhedral) linear map.

Input

• lm – linear map
• prune – (optional, default: true) if true removes redundant vertices

Output

A list of vertices.

Algorithm

We assume that the underlying set X is polyhedral. Then the result is just the linear map applied to the vertices of X.

constraints_list(lm::LinearMap{N}) where {N<:Real}

Return the list of constraints of a (polyhedral) linear map.

Input

• lm – linear map

Output

The list of constraints of the linear map.

Notes

We assume that the underlying set X is polyhedral, i.e., offers a method constraints_list(X).

Algorithm

We fall back to a concrete set representation and apply linear_map.

linear_map(M::AbstractMatrix{N}, lm::LinearMap{N}) where {N<:Real}

Return the linear map of a lazy linear map.

Input

• M – matrix
• lm – linear map

Output

The polytope representing the linear map of the lazy linear map of a set.