Ellipsoid

Ellipsoid{N<:AbstractFloat, VN<:AbstractVector{N},
          MN<:AbstractMatrix{N}} <: AbstractCentrallySymmetric{N}

Type that represents an ellipsoid.

It is defined as the set

\[E = \left\{ x ∈ ℝ^n : (x-c)^T Q^{-1} (x-c) ≤ 1 \right\},\]

where $c ∈ ℝ^n$ is its center and $Q ∈ ℝ^{n×n}$ its shape matrix, which should be a positive definite matrix. An ellipsoid can also be characterized as the image of a Euclidean ball by an invertible linear transformation. It is the higher-dimensional generalization of an ellipse.

Fields

• center – center of the ellipsoid
• shape_matrix – real positive definite matrix, i.e., it is equal to its transpose and $x^\mathrm{T}Qx > 0$ for all nonzero $x$

Notes

By default, the inner constructor checks that the given shape matrix is positive definite. Use the flag check_posdef=false to disable this check.

Examples

We create a two-dimensional ellipsoid with center [1, 1]:

julia> using LinearAlgebra

julia> E = Ellipsoid(ones(2), Diagonal([2.0, 0.5]))
Ellipsoid{Float64, Vector{Float64}, Diagonal{Float64, Vector{Float64}}}([1.0, 1.0], [2.0 0.0; 0.0 0.5])

If the center is not specified, it is assumed that it is the origin. For instance, a three-dimensional ellipsoid centered in the origin with the shape matrix being the identity can be created as follows:

julia> E = Ellipsoid(Matrix(1.0I, 3, 3))
Ellipsoid{Float64, Vector{Float64}, Matrix{Float64}}([0.0, 0.0, 0.0], [1.0 0.0 0.0; 0.0 1.0 0.0; 0.0 0.0 1.0])

julia> dim(E)
3

The center and shape matrix of the ellipsoid can be retrieved with the functions center and shape_matrix, respectively:

julia> center(E)
3-element Vector{Float64}:
 0.0
 0.0
 0.0

julia> shape_matrix(E)
3×3 Matrix{Float64}:
 1.0  0.0  0.0
 0.0  1.0  0.0
 0.0  0.0  1.0

The function an_element returns some element of the ellipsoid:

julia> an_element(E)
3-element Vector{Float64}:
 0.0
 0.0
 0.0

julia> an_element(E) ∈ E
true

We can evaluate the support vector in a given direction, say [1, 1, 1]:

julia> σ(ones(3), E)
3-element Vector{Float64}:
 0.5773502691896258
 0.5773502691896258
 0.5773502691896258

rand(T::Type{<:LazySet}; [N]::Type{<:Real}=Float64, [dim]::Int=2,
     [rng]::AbstractRNG=GLOBAL_RNG, [seed]::Union{Int, Nothing}=nothing
    )

Create a random set of the given set type.

Input

• T – set type
• N – (optional, default: Float64) numeric type
• dim – (optional, default: 2) dimension
• rng – (optional, default: GLOBAL_RNG) random number generator
• seed – (optional, default: nothing) seed for reseeding

Output

A random set of the given set type.

Extended help

rand(::Type{Ellipsoid}; [N]::Type{<:AbstractFloat}=Float64, [dim]::Int=2,
     [rng]::AbstractRNG=GLOBAL_RNG, [seed]::Union{Int, Nothing}=nothing)

Algorithm

The center is a normally distributed vector with entries of mean 0 and standard deviation 1.

The idea for the shape matrix comes from here. The matrix is symmetric positive definite, but also diagonally dominant.

\[Q = \frac{1}{2}(S + S^T) + nI,\]

where $n$ = dim and $S$ is a $n × n$ random matrix whose coefficients are uniformly distributed in the interval $[-1, 1]$.

shape_matrix(E::Ellipsoid)

Return the shape matrix of the ellipsoid.

Input

• E – ellipsoid

Output

The shape matrix of the ellipsoid.

∈(x::AbstractVector, X::LazySet)

Check whether a point lies in a set.

Input

• x – point/vector
• X – set

Output

true iff $x ∈ X$.

Extended help

∈(x::AbstractVector, E::Ellipsoid)

Algorithm

The point $x$ belongs to the ellipsoid of center $c$ and shape matrix $Q$ if and only if

\[(x-c)^\mathrm{T} Q^{-1} (x-c) ≤ 1.\]

ρ(d::AbstractVector, X::LazySet)

Evaluate the support function of a set in a given direction.

Input

• d – direction
• X – set

Output

The evaluation of the support function of X in direction d.

Notes

A convenience alias support_function is also available.

We have the following identity based on the support vector $σ$:

\[ ρ(d, X) = d ⋅ σ(d, X)\]

Extended help

ρ(d::AbstractVector, E::Ellipsoid)

Algorithm

The support value is $cᵀ d + ‖Bᵀ d‖₂$, where $c$ is the center and $Q = B Bᵀ$ is the shape matrix of E.

σ(d::AbstractVector, X::LazySet)

Compute a support vector of a set in a given direction.

Input

• d – direction
• X – set

Output

A support vector of X in direction d.

Notes

A convenience alias support_vector is also available.

Extended help

σ(d::AbstractVector, E::Ellipsoid)

Algorithm

Let $E$ be an ellipsoid of center $c$ and shape matrix $Q = BB^\mathrm{T}$. Its support vector along direction $d$ can be deduced from that of the unit Euclidean ball $\mathcal{B}_2$ using the algebraic relations for the support vector,

\[σ_{B\mathcal{B}_2 ⊕ c}(d) = c + Bσ_{\mathcal{B}_2} (B^\mathrm{T} d) = c + \dfrac{Qd}{\sqrt{d^\mathrm{T}Q d}}.\]

linear_map(M::AbstractMatrix, X::LazySet)

Compute the linear map $M · X$.

Input

• M – matrix
• X – set

Output

A set representing the linear map $M · X$.

Extended help

linear_map(M::AbstractMatrix, E::Ellipsoid)

Algorithm

Given an ellipsoid $⟨c, Q⟩$ and a matrix $M$, the linear map yields the ellipsoid $⟨M c, M Q Mᵀ⟩$.