Exponential map

Exponential map (ExponentialMap)

LazySets.ExponentialMapType
ExponentialMap{N, S<:ConvexSet{N}} <: AbstractAffineMap{N, S}

Type that represents the action of an exponential map on a set.

Fields

  • spmexp – sparse matrix exponential
  • X – set

Notes

The exponential map preserves convexity: if X is convex, then any exponential map of X is convex as well.

Examples

The ExponentialMap type is overloaded to the usual times * operator when the linear map is a lazy matrix exponential. For instance,

julia> using SparseArrays

julia> A = sprandn(100, 100, 0.1);

julia> E = SparseMatrixExp(A);

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

julia> M = E * B; # represents the image set: exp(A) * B

julia> M isa ExponentialMap
true

julia> dim(M)
100

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

julia> E * ZeroSet(100)
ZeroSet{Float64}(100)

julia> E * EmptySet(2)
∅(2)
source
LazySets.dimMethod
dim(em::ExponentialMap)

Return the dimension of an exponential map.

Input

  • em – an ExponentialMap

Output

The ambient dimension of the exponential map.

source
LazySets.ρMethod
ρ(d::AbstractVector, em::ExponentialMap; [backend]=get_exponential_backend())

Return the support function of the exponential map.

Input

  • d – direction
  • em – exponential map
  • backend – (optional; default: get_exponential_backend()) exponentiation backend

Output

The support function in the given direction.

Notes

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

source
LazySets.σMethod
σ(d::AbstractVector, em::ExponentialMap; [backend]=get_exponential_backend())

Return the support vector of the exponential map.

Input

  • d – direction
  • em – exponential map
  • backend – (optional; default: get_exponential_backend()) exponentiation backend

Output

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

Notes

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

source
Base.:∈Method
∈(x::AbstractVector, em::ExponentialMap; [backend]=get_exponential_backend())

Check whether a given point is contained in an exponential map of a set.

Input

  • x – point/vector
  • em – exponential map of a set
  • backend – (optional; default: get_exponential_backend()) exponentiation backend

Output

true iff $x ∈ em$.

Algorithm

This implementation exploits that $x ∈ \exp(M)⋅S$ iff $\exp(-M)⋅x ∈ S$. This follows from $\exp(-M)⋅\exp(M) = I$ for any $M$.

Examples

julia> using SparseArrays

julia> em = ExponentialMap(
        SparseMatrixExp(sparse([1, 2], [1, 2], [2.0, 1.0], 2, 2)),
        BallInf([1., 1.], 1.));

julia> [-1.0, 1.0] ∈ em
false
julia> [1.0, 1.0] ∈ em
true
source
LazySets.isboundedMethod
isbounded(em::ExponentialMap)

Determine whether an exponential map is bounded.

Input

  • em – exponential map

Output

true iff the exponential map is bounded.

source
LazySets.vertices_listMethod
vertices_list(P::AbstractHPolygon{N};
              apply_convex_hull::Bool=true,
              check_feasibility::Bool=true) where {N}

Return the list of vertices of a polygon in constraint representation.

Input

  • P – polygon in constraint representation
  • apply_convex_hull – (optional, default: true) flag to post-process the intersection of constraints with a convex hull
  • check_feasibility – (optional, default: true) flag to check whether the polygon was empty (required for correctness in case of empty polygons)

Output

List of vertices.

Algorithm

We compute each vertex as the intersection of consecutive lines defined by the half-spaces. If check_feasibility is active, we then check if the constraints of the polygon were actually feasible (i.e., they pointed in the right direction). For this we compute the average of all vertices and check membership in each constraint.

source
vertices_list(B::Ball1{N, VN}) where {N, VN<:AbstractVector}

Return the list of vertices of a ball in the 1-norm.

Input

  • B – ball in the 1-norm

Output

A list containing the vertices of the ball in the 1-norm.

source
vertices_list(∅::EmptySet{N}) where {N}

Return the list of vertices of an empty set.

Input

  • – empty set

Output

The empty list of vertices, as the empty set does not contain any vertices.

source
vertices_list(P::HPolytope{N};
              [backend]=nothing, [prune]::Bool=true) where {N}

Return the list of vertices of a polytope in constraint representation.

Input

  • P – polytope in constraint representation
  • backend – (optional, default: nothing) the polyhedral computations backend
  • prune – (optional, default: true) flag to remove redundant vertices

Output

List of vertices.

Algorithm

If the polytope is two-dimensional, the polytope is converted to a polygon in H-representation and then its vertices_list function is used. This ensures that, by default, the optimized two-dimensional methods are used.

It is possible to use the Polyhedra backend in two-dimensions as well by passing, e.g. backend=CDDLib.Library().

If the polytope is not two-dimensional, the concrete polyhedra manipulation library Polyhedra is used. The actual computation is performed by a given backend; for the default backend used in LazySets see default_polyhedra_backend(P). For further information on the supported backends see Polyhedra's documentation.

source
vertices_list(cp::CartesianProduct{N}) where {N}

Return the list of vertices of a (polytopic) Cartesian product.

Input

  • cp – Cartesian product

Output

A list of vertices.

Algorithm

We assume that the underlying sets are polytopic. Then the high-dimensional set of vertices is just the Cartesian product of the low-dimensional sets of vertices.

source

vertices_list(cpa::CartesianProductArray{N}) where {N}

Return the list of vertices of a (polytopic) Cartesian product of a finite number of sets.

Input

  • cpa – Cartesian product array

Output

A list of vertices.

Algorithm

We assume that the underlying sets are polytopic. Then the high-dimensional set of vertices is just the Cartesian product of the low-dimensional sets of vertices.

source
vertices_list(em::ExponentialMap{N};
              [backend]=get_exponential_backend()) where {N}

Return the list of vertices of a (polytopic) exponential map.

Input

  • em – exponential map
  • backend – (optional; default: get_exponential_backend()) exponentiation backend

Output

A list of vertices.

Algorithm

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

source

Inherited from AbstractAffineMap:

Inherited from ConvexSet:

Sparse matrix exponential

LazySets.SparseMatrixExpType
SparseMatrixExp{N}

Type that represents the matrix exponential, $\exp(M)$, of a sparse matrix.

Fields

  • M – sparse matrix; it should be square

Examples

Take for example a random sparse matrix of dimensions $100 × 100$ and with occupation probability $0.1$:

julia> using SparseArrays

julia> A = sprandn(100, 100, 0.1);

julia> using ExponentialUtilities

julia> E = SparseMatrixExp(A);

julia> size(E)
(100, 100)

Here E is a lazy representation of $\exp(A)$. To compute with E, use get_row and get_column resp. get_rows and get_columns. These functions return row and column vectors (or matrices). For example:

julia> get_row(E, 10); # compute E[10, :]

julia> get_column(E, 10); # compute E[:, 10]

julia> get_rows(E, [10]); # same as get_row(E, 10) but a 1x100 matrix is returned

julia> get_columns(E, [10]); # same as get_column(E, 10) but a 100x1 matrix is returned

Notes

This type is provided for use with very large and very sparse matrices. The evaluation of the exponential matrix action over vectors relies on external packages such as ExponentialUtilities or Expokit. Hence, you will have to install and load such an optional dependency to have access to the functionality of SparseMatrixExp.

source
Base.:*Method
    *(spmexp::SparseMatrixExp, X::ConvexSet)

Return the exponential map of a set from a sparse matrix exponential.

Input

  • spmexp – sparse matrix exponential
  • X – set

Output

The exponential map of the set.

source
LazySets.get_rowMethod
get_row(spmexp::SparseMatrixExp{N}, i::Int;
        [backend]=get_exponential_backend()) where {N}

Return a single row of a sparse matrix exponential.

Input

  • spmexp – sparse matrix exponential
  • i – row index
  • backend – (optional; default: get_exponential_backend()) exponentiation backend

Output

A row vector corresponding to the ith row of the matrix exponential.

Notes

This function uses Julia's transpose function to create the result. The result is of type Transpose; in Julia versions older than v0.7, the result was of type RowVector.

source

Exponential projection map (ExponentialProjectionMap)

LazySets.ExponentialProjectionMapType
ExponentialProjectionMap{N, S<:ConvexSet{N}} <: AbstractAffineMap{N, S}

Type that represents the application of a projection of a sparse matrix exponential to a set.

Fields

  • spmexp – projection of a sparse matrix exponential
  • X – set

Notes

The exponential projection preserves convexity: if X is convex, then any exponential projection of X is convex as well.

source
LazySets.dimMethod
dim(eprojmap::ExponentialProjectionMap)

Return the dimension of a projection of an exponential map.

Input

  • eprojmap – projection of an exponential map

Output

The ambient dimension of the projection of an exponential map.

source
LazySets.σMethod
σ(d::AbstractVector, eprojmap::ExponentialProjectionMap;
  [backend]=get_exponential_backend())

Return the support vector of a projection of an exponential map.

Input

  • d – direction
  • eprojmap – projection of an exponential map
  • backend – (optional; default: get_exponential_backend()) exponentiation backend

Output

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

Notes

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

source
LazySets.isboundedMethod
isbounded(eprojmap::ExponentialProjectionMap)

Determine whether an exponential projection map is bounded.

Input

  • eprojmap – exponential projection map

Output

true iff the exponential projection map is bounded.

Algorithm

We first check if the left or right projection matrix is zero or the wrapped set is bounded. Otherwise, we check boundedness via LazySets._isbounded_unit_dimensions.

source

Inherited from AbstractAffineMap:

Inherited from ConvexSet:

Projection of a sparse matrix exponential

LazySets.ProjectionSparseMatrixExpType
ProjectionSparseMatrixExp{N, MN1<:AbstractSparseMatrix{N},
                             MN2<:AbstractSparseMatrix{N},
                             MN3<:AbstractSparseMatrix{N}}

Type that represents the projection of a sparse matrix exponential, i.e., $L⋅\exp(M)⋅R$ for a given sparse matrix $M$.

Fields

  • L – left multiplication matrix
  • E – sparse matrix exponential
  • R – right multiplication matrix
source
Base.:*Method
    *(projspmexp::ProjectionSparseMatrixExp, X::ConvexSet)

Return the application of a projection of a sparse matrix exponential to a set.

Input

  • projspmexp – projection of a sparse matrix exponential
  • X – set

Output

The application of the projection of a sparse matrix exponential to the set.

source