Balls in the p-norm (AbstractBallp)

AbstractBallp{N} <: AbstractCentrallySymmetric{N}

Abstract type for p-norm balls.

Notes

See Ballp for a standard implementation of this interface.

Every concrete AbstractBallp must define the following methods:

• ball_norm(::AbstractBallp) – return the characteristic norm
• radius_ball(::AbstractBallp) – return the ball radius

The subtypes of AbstractBallp:

julia> subtypes(AbstractBallp)
2-element Vector{Any}:
 Ball2
 Ballp

There are two further set types implementing the AbstractBallp interface, but they also implement other interfaces and hence cannot be subtypes: Ball1 and BallInf.

ball_norm(B::AbstractBallp)

Determine the norm (p) of a p-norm ball.

Input

• B – p-norm ball

Output

A number representing the norm.

radius_ball(B::AbstractBallp)

Compute the radius of a p-norm ball.

Input

• B – p-norm ball

Output

A number representing the radius.

∈(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, B::AbstractBallp)

Notes

This implementation is worst-case optimized, i.e., it is optimistic and first computes (see below) the whole sum before comparing to the radius. In applications where the point is typically far away from the ball, a fail-fast implementation with interleaved comparisons could be more efficient.

Algorithm

Let $B$ be an $n$-dimensional ball in the p-norm with radius $r$ and let $c_i$ and $x_i$ be the ball's center and the vector $x$ in dimension $i$, respectively. Then $x ∈ B$ iff $\left( ∑_{i=1}^n |c_i - x_i|^p \right)^{1/p} ≤ r$.

Examples

julia> B = Ballp(1.5, [1.0, 1.0], 1.)
Ballp{Float64, Vector{Float64}}(1.5, [1.0, 1.0], 1.0)

julia> [0.5, -0.5] ∈ B
false

julia> [0.5, 1.5] ∈ B
true

ρ(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, B::AbstractBallp)

Algorithm

Let $c$ and $r$ be the center and radius of the ball $B$ in the p-norm, respectively, and let $q = \frac{p}{p-1}$. Then:

\[ρ(d, B) = ⟨d, c⟩ + r ‖d‖_q.\]

σ(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, B::AbstractBallp)

Algorithm

The support vector of the unit ball in the $p$-norm along direction $d$ is:

\[σ(d, \mathcal{B}_p^n(0, 1)) = \dfrac{\tilde{v}}{‖\tilde{v}‖_q},\]

where $\tilde{v}_i = \frac{|d_i|^q}{d_i}$ if $d_i ≠ 0$ and $\tilde{v}_i = 0$ otherwise, for all $i=1,…,n$, and $q$ is the conjugate number of $p$. By the affine transformation $x = r\tilde{x} + c$, one obtains that the support vector of $\mathcal{B}_p^n(c, r)$ is

\[σ(d, \mathcal{B}_p^n(c, r)) = \dfrac{v}{‖v‖_q},\]

where $v_i = c_i + r\frac{|d_i|^q}{d_i}$ if $d_i ≠ 0$ and $v_i = 0$ otherwise, for all $i = 1, …, n$.

If the direction has norm zero, the center of the ball is returned.