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 ∈ \mathbb{R}^n : ‖ x - c ‖_∞ ≤ r \},\]

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

Examples

Create 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,Array{Float64,1}}([0.0, 0.0], 1.0)

julia> dim(B)
2

julia> ρ([1., 1.], 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.

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 radius 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, which is the same in every dimension.

Input

• B – ball in the infinity norm

Output

The box radius of the ball in the infinity norm.

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.

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 when applied to the radius of the ball. Hence, this function depends on the absolute zero tolerance ABSZTOL.

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.

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

Return the support vector of a ball in the infinity norm in a 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 vertex with biggest values is returned.

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

Evaluate the support function of a ball in the infinity norm in a 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, taylored 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.

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

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

Input

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

Output

A translated ball in the infinity norm.

Algorithm

We add the vector to the center of the ball.