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 ∈ \mathbb{R}^n : (x-c)^T Q^{-1} (x-c) ≤ 1 \right\},\]

where $c \in \mathbb{R}^n$ is its center and $Q \in \mathbb{R}^{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

center(E::Ellipsoid)

Return the center of the ellipsoid.

Input

• E – ellipsoid

Output

The center of the ellipsoid.

shape_matrix(E::Ellipsoid)

Return the shape matrix of the ellipsoid.

Input

• E – ellipsoid

Output

The shape matrix of the ellipsoid.

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

Return the support function of an ellipsoid in a given direction.

Input

• d – direction
• E – ellipsoid

Output

The support function of the ellipsoid in the given direction.

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, E::Ellipsoid)

Return the support vector of an ellipsoid in a given direction.

Input

• d – direction
• E – ellipsoid

Output

The support vector in the given direction.

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}}.\]

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

Check whether a given point is contained in an ellipsoid.

Input

• x – point/vector
• E – ellipsoid

Output

true iff x ∈ E.

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.\]

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

Create a random ellipsoid.

Input

• Ellipsoid – type for dispatch
• 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 ellipsoid.

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 \times n$ random matrix whose coefficients are uniformly distributed in the interval $[-1, 1]$.

translate(E::Ellipsoid, v::AbstractVector)

Translate (i.e., shift) an ellipsoid by a given vector.

Input

• E – ellipsoid
• v – translation vector

Output

A translated ellipsoid.

Notes

See also translate!(::Ellipsoid, ::AbstractVector) for the in-place version.

translate!(E::Ellipsoid, v::AbstractVector)

Translate (i.e., shift) an ellipsoid by a given vector, in-place.

Input

• E – ellipsoid
• v – translation vector

Output

The ellipsoid E translated by v.

Notes

See also translate(::Ellipsoid, ::AbstractVector) for the out-of-place version.

Algorithm

We add the vector to the center of the ellipsoid.

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

Concrete linear map of an ellipsoid.

Input

• M – matrix
• x – ellipsoid

Output

An ellipsoid.

Algorithm

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