Hyperrectangles (AbstractHyperrectangle)

AbstractHyperrectangle{N} <: AbstractZonotope{N}

Abstract type for hyperrectangular sets.

Notes

See Hyperrectangle for a standard implementation of this interface.

Every concrete AbstractHyperrectangle must define the following functions:

• radius_hyperrectangle(::AbstractHyperrectangle) – return the hyperrectangle's radius, which is a full-dimensional vector

• radius_hyperrectangle(::AbstractHyperrectangle, i::Int) – return the hyperrectangle's radius in the i-th dimension

• isflat(::AbstractHyperrectangle) – check whether the hyperrectangle's radius is zero in some dimension

Every hyperrectangular set is also a zonotopic set; see AbstractZonotope.

The subtypes of AbstractHyperrectangle (including abstract interfaces):

julia> subtypes(AbstractHyperrectangle)
5-element Vector{Any}:
 AbstractSingleton
 BallInf
 Hyperrectangle
 Interval
 SymmetricIntervalHull

□(c, r)

Convenience constructor of Hyperrectangles or BallInfs depending on the type of r.

Input

• c – center
• r – radius (either a vector for Hyperrectangle or a number for BallInf)

Output

A Hyperrectangles or BallInfs depending on the type of r.

Notes

The function symbol can be typed via \square<tab>.

norm(H::AbstractHyperrectangle, [p]::Real=Inf)

Return the norm of a hyperrectangular set.

The norm of a hyperrectangular set is defined as the norm of the enclosing ball of the given $p$-norm, of minimal volume, that is centered in the origin.

Input

• H – hyperrectangular set
• p – (optional, default: Inf) norm

Output

A real number representing the norm.

Algorithm

Recall that the norm is defined as

\[‖ X ‖ = \max_{x ∈ X} ‖ x ‖_p = max_{x ∈ \text{vertices}(X)} ‖ x ‖_p.\]

The last equality holds because the optimum of a convex function over a polytope is attained at one of its vertices.

This implementation uses the fact that the maximum is attained in the vertex $c + \text{diag}(\text{sign}(c)) r$ for any $p$-norm. Hence it suffices to take the $p$-norm of this particular vertex. This statement is proved below. Note that, in particular, there is no need to compute the $p$-norm for each vertex, which can be very expensive.

If $X$ is a hyperrectangle and the $n$-dimensional vectors center and radius of the hyperrectangle are denoted $c$ and $r$ respectively, then reasoning on the $2^n$ vertices we have that:

\[\max_{x ∈ \text{vertices}(X)} ‖ x ‖_p = \max_{α_1, …, α_n ∈ \{-1, 1\}} (|c_1 + α_1 r_1|^p + ... + |c_n + α_n r_n|^p)^{1/p}.\]

The function $x ↦ x^p$, $p > 0$, is monotonically increasing and thus the maximum of each term $|c_i + α_i r_i|^p$ is given by $|c_i + \text{sign}(c_i) r_i|^p$ for each $i$. Hence, $x^* := \text{argmax}_{x ∈ X} ‖ x ‖_p$ is the vertex $c + \text{diag}(\text{sign}(c)) r$.

radius(H::AbstractHyperrectangle, [p]::Real=Inf)

Return the radius of a hyperrectangular set.

Input

• H – hyperrectangular set
• p – (optional, default: Inf) norm

Output

A real number representing the radius.

Notes

The radius is defined as the radius of the enclosing ball of the given $p$-norm of minimal volume with the same center. It is the same for all corners of a hyperrectangular set.

σ(d::AbstractVector, H::AbstractHyperrectangle)

Return a support vector of a hyperrectangular set in a given direction.

Input

• d – direction
• H – hyperrectangular set

Output

A support vector in the given direction.

If the direction vector is zero in dimension $i$, the result will have the center's coordinate in that dimension. For instance, for the two-dimensional infinity-norm ball, if the direction points to the right, the result is the vector [1, 0] in the middle of the right-hand facet.

If the direction has norm zero, the result can be any point in H. The default implementation returns the center of H.

ρ(d::AbstractVector, H::AbstractHyperrectangle)

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

Input

• d – direction
• H – hyperrectangular set

Output

The evaluation of the support function in the given direction.

∈(x::AbstractVector, H::AbstractHyperrectangle)

Check whether a given point is contained in a hyperrectangular set.

Input

• x – point/vector
• H – hyperrectangular set

Output

true iff $x ∈ H$.

Algorithm

Let $H$ be an $n$-dimensional hyperrectangular set, $c_i$ and $r_i$ be the center and radius, and $x_i$ be the vector $x$ in dimension $i$, respectively. Then $x ∈ H$ iff $|c_i - x_i| ≤ r_i$ for all $i=1,…,n$.

vertices_list(H::AbstractHyperrectangle; kwargs...)

Return the list of vertices of a hyperrectangular set.

Input

• H – hyperrectangular set

Output

A list of vertices. Zeros in the radius are correctly handled, i.e., the result does not contain any duplicate vertices.

Algorithm

First we identify the dimensions where H is flat, i.e., its radius is zero. We also compute the number of vertices that we have to create.

Next we create the vertices. We do this by enumerating all vectors v of length n (the dimension of H) with entries -1/0/1 and construct the corresponding vertex as follows:

\[ \text{vertex}(v)(i) = \begin{cases} c(i) + r(i) & v(i) = 1 \\ c(i) & v(i) = 0 \\ c(i) - r(i) & v(i) = -1. \end{cases}\]

For enumerating the vectors v, we modify the current v from left to right by changing entries -1 to 1, skipping entries 0, and stopping at the first entry 1 (but changing it to -1). This way we only need to change the vertex in those dimensions where v has changed, which usually is a smaller number than n.

constraints_list(H::AbstractHyperrectangle{N}) where {N}

Return the list of constraints of a hyperrectangular set.

Input

• H – hyperrectangular set

Output

A list of $2n$ linear constraints, where $n$ is the dimension of H.

constraints_list(U::Universe{N}) where {N}

Return the list of constraints defining a universe.

Input

• U – universe

Output

The empty list of constraints, as the universe is unconstrained.

high(H::AbstractHyperrectangle)

Return the higher coordinates of a hyperrectangular set.

Input

• H – hyperrectangular set

Output

A vector with the higher coordinates of the hyperrectangular set.

high(H::AbstractHyperrectangle, i::Int)

Return the higher coordinate of a hyperrectangular set in a given dimension.

Input

• H – hyperrectangular set
• i – dimension of interest

Output

The higher coordinate of the hyperrectangular set in the given dimension.

low(H::AbstractHyperrectangle)

Return the lower coordinates of a hyperrectangular set.

Input

• H – hyperrectangular set

Output

A vector with the lower coordinates of the hyperrectangular set.

low(H::AbstractHyperrectangle, i::Int)

Return the lower coordinate of a hyperrectangular set in a given dimension.

Input

• H – hyperrectangular set
• i – dimension of interest

Output

The lower coordinate of the hyperrectangular set in the given dimension.

extrema(H::AbstractHyperrectangle)

Return the lower and higher coordinates of a hyperrectangular set.

Input

• H – hyperrectangular set

Output

The lower and higher coordinates of the set.

Notes

The result is equivalent to (low(H), high(H)).

extrema(H::AbstractHyperrectangle, i::Int)

Return the lower and higher coordinate of a hyperrectangular set in a given dimension.

Input

• H – hyperrectangular set
• i – dimension of interest

Output

The lower and higher coordinate of the set in the given dimension.

Notes

The result is equivalent to (low(H, i), high(H, i)).

isflat(H::AbstractHyperrectangle)

Check whether a hyperrectangular set is flat, i.e., whether its radius is zero in some dimension.

Input

• H – hyperrectangular set

Output

true iff the hyperrectangular set is flat.

Notes

For robustness with respect to floating-point inputs, this function relies on the result of isapproxzero when applied to the radius in some dimension. Hence this function depends on the absolute zero tolerance ABSZTOL.

split(H::AbstractHyperrectangle{N},
      num_blocks::AbstractVector{Int}) where {N}

Partition a hyperrectangular set into uniform sub-hyperrectangles.

Input

• H – hyperrectangular set
• num_blocks – number of blocks in the partition for each dimension

Output

A list of Hyperrectangles.

generators(H::AbstractHyperrectangle)

Return an iterator over the generators of a hyperrectangular set.

Input

• H – hyperrectangular set

Output

An iterator over the generators of H.

genmat(H::AbstractHyperrectangle)

Return the generator matrix of a hyperrectangular set.

Input

• H – hyperrectangular set

Output

A matrix where each column represents one generator of H.

ngens(H::AbstractHyperrectangle{N}) where {N}

Return the number of generators of a hyperrectangular set.

Input

• H – hyperrectangular set

Output

The number of generators.

Algorithm

A hyperrectangular set has one generator for each non-flat dimension.

rectify(H::AbstractHyperrectangle)

Concrete rectification of a hyperrectangular set.

Input

• H – hyperrectangular set

Output

The Hyperrectangle that corresponds to the rectification of H.

volume(H::AbstractHyperrectangle)

Return the volume of a hyperrectangular set.

Input

• H – hyperrectangular set

Output

The volume of $H$.

Algorithm

The volume of the $n$-dimensional hyperrectangle $H$ with radius vector $r$ is $2ⁿ ∏ᵢ rᵢ$ where $rᵢ$ denotes the $i$-th component of $r$.

distance(x::AbstractVector, H::AbstractHyperrectangle{N};
         [p]::Real=N(2)) where {N}

Compute the distance between a point x and a hyperrectangular set H with respect to the given p-norm.

Input

• x – point/vector
• H – hyperrectangular set

Output

A scalar representing the distance between point x and hyperrectangle H.

reflect(H::AbstractHyperrectangle)

Concrete reflection of a hyperrectangular set H, resulting in the reflected set -H.

Input

• H – hyperrectangular set

Output

A Hyperrectangle representing -H.

Algorithm

If $H$ has center $c$ and radius $r$, then $-H$ has center $-c$ and radius $r$.