Infinity-norm ball (BallInf)

BallInf{N, VN<:AbstractVector{N}} <: AbstractHyperrectangle{N}

Type that represents a ball in the infinity norm.

Fields

• center – center of the ball as a real vector
• radius – radius of the ball as a real scalar ($≥ 0$)

Notes

Mathematically, a ball in the infinity norm is defined as the set

\[\mathcal{B}_∞^n(c, r) = \{ x ∈ ℝ^n : ‖ x - c ‖_∞ ≤ r \},\]

where $c ∈ ℝ^n$ is its center and $r ∈ ℝ_+$ its radius. Here $‖ ⋅ ‖_∞$ denotes the infinity norm, defined as $‖ x ‖_∞ = \max\limits_{i=1,…,n} \vert x_i \vert$ for any $x ∈ ℝ^n$.

Examples

Construct the two-dimensional unit ball and compute its support function along the positive $x=y$ direction:

julia> B = BallInf(zeros(2), 1.0)
BallInf{Float64, Vector{Float64}}([0.0, 0.0], 1.0)

julia> dim(B)
2

julia> ρ([1.0, 1.0], B)
2.0

center(B::BallInf)

Return the center of a ball in the infinity norm.

Input

• B – ball in the infinity norm

Output

The center of the ball in the infinity norm.

isflat(B::BallInf)

Determine whether a ball in the infinity norm is flat, i.e., whether its radius is zero.

Input

• B – ball in the infinity norm

Output

true iff the ball is flat.

Notes

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

ngens(B::BallInf)

Return the number of generators of a ball in the infinity norm.

Input

• B – ball in the infinity norm

Output

The number of generators.

Algorithm

A ball in the infinity norm has either one generator for each dimension, or zero generators if it is a degenerated ball of radius zero.

radius(B::BallInf, [p]::Real=Inf)

Return the radius of a ball in the infinity norm.

Input

• B – ball in the infinity norm
• p – (optional, default: Inf) norm

Output

A real number representing the radius.

Notes

The result is defined as the radius of the enclosing ball of the given $p$-norm of minimal volume with the same center.

radius_hyperrectangle(B::BallInf)

Return the box radius of a ball in the infinity norm.

Input

• B – ball in the infinity norm

Output

The box radius of the ball in the infinity norm, which is the same in every dimension.

radius_hyperrectangle(B::BallInf, i::Int)

Return the box radius of a ball in the infinity norm in a given dimension.

Input

• B – ball in the infinity norm
• i – dimension of interest

Output

The box radius of the ball in the infinity norm in the given dimension.

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

Create a random ball in the infinity norm.

Input

• BallInf – 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 ball in the infinity norm.

Algorithm

All numbers are normally distributed with mean 0 and standard deviation 1. Additionally, the radius is nonnegative.

reflect(B::BallInf)

Concrete reflection of a ball in the infinity norm B, resulting in the reflected set -B.

Input

• B – ball in the infinity norm

Output

The BallInf representing -B.

Algorithm

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

volume(B::BallInf)

Return the volume of a ball in the infinity norm.

Input

• B – ball in the infinity norm

Output

The volume of $B$.

Algorithm

We compute the volume by iterative multiplication of the radius.

For floating-point inputs we use this implementation for balls of dimension less than $50$. For balls of higher dimension we instead compute $exp(n * log(2r))$, where $r$ is the radius of the ball.

ρ(d::AbstractVector, B::BallInf)

Evaluate the support function of a ball in the infinity norm in the given direction.

Input

• d – direction
• B – ball in the infinity norm

Output

Evaluation of the support function in the given direction.

Algorithm

Let $B$ be a ball in the infinity norm with center $c$ and radius $r$ and let $d$ be the direction of interest. For balls with dimensions less than $30$ we use the implementation for AbstractHyperrectangle, tailored to a BallInf, which computes

\[ ∑_{i=1}^n d_i (c_i + \textrm{sgn}(d_i) · r)\]

where $\textrm{sgn}(α) = 1$ if $α ≥ 0$ and $\textrm{sgn}(α) = -1$ if $α < 0$.

For balls of higher dimension we instead exploit that for a support vector $v = σ(d, B) = c + \textrm{sgn}(d) · (r, …, r)ᵀ$ we have

\[ ρ(d, B) = ⟨d, v⟩ = ⟨d, c⟩ + ⟨d, \textrm{sgn}(d) · (r, …, r)ᵀ⟩ = ⟨d, c⟩ + r · ∑_{i=1}^n |d_i|\]

where $⟨·, ·⟩$ denotes the dot product.

σ(d::AbstractVector, B::BallInf)

Return the support vector of a ball in the infinity norm in the given direction.

Input

• d – direction
• B – ball in the infinity norm

Output

The support vector in the given direction. If the direction has norm zero, the center of the ball is returned.

translate!(B::BallInf, v::AbstractVector)

Translate (i.e., shift) a ball in the infinity norm by a given vector, in-place.

Input

• B – ball in the infinity norm
• v – translation vector

Output

The ball B translated by v.

Algorithm

We add the vector to the center of the ball.

Notes

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