Underapproximation

underapproximate(X::S, dirs::AbstractDirections;
                [apply_convex_hull]::Bool=false) where {N, S<:LazySet{N}}

Compute the underapproximation of a convex set by sampling support vectors.

Input

• X – convex set
• dirs – directions
• apply_convex_hull – (optional, default: false) if true, post-process the support vectors with a convex hull operation

Output

The VPolytope obtained by taking the convex hull of support vectors of X along the directions determined by dirs.

Notes

Since the support vectors are not always unique, this algorithm may return a strict underapproximation even if the set can be exactly approximated using the given template.

underapproximate(X::LazySet, ::Type{<:Hyperrectangle};
                 solver=nothing) where {N}

Underapproximate a convex polygon with a hyperrectangle of maximal area.

Input

• X – convex polygon
• Hyperrectangle – type for dispatch
• solver – (optional; default: nothing) nonlinear solver; if nothing, default_nln_solver(N) will be used

Output

A hyperrectangle underapproximation with maximal area.

Notes

The implementation only works for 2D sets, but the algorithm can be generalized.

Due to numerical issues, the result may be slightly outside the set.

Algorithm

The algorithm is taken from [1, Theorem 17] and solves a convex program (in fact a linear program with nonlinear objective). (The objective is modified to an equivalent version due to solver issues.)

[1] Mehdi Behroozi - Largest inscribed rectangles in geometric convex sets. arXiv:1905.13246.

underapproximate(X::LazySet, ::Type{<:Ball2})

Compute the largest inscribed Euclidean ball in a set X.

Input

• X – set
• Ball2 – target type

Output

A largest Ball2 contained in X.

Algorithm

We use chebyshev_center_radius(X).

underapproximate(P::AbstractPolyhedron{N}, ::Type{Ellipsoid};
                 backend=default_sdp_solver(),
                 interior_point::AbstractVector{N}=chebyshev_center_radius(P)[1]
                ) where {N<:Real}

Underapproximate a polyhedral set by the maximum-volume ellipsoid.

Input

• P – polyhedral set
• Ellipsoid – type for dispatch
• backend – (optional, default: default_sdp_solver()) backend to solve the semi-definite program
• interior_point – (optional, default: chebyshev_center_radius(P)[1]) an interior point of the ellipsoid (needed for the algorithm: see below for details)

Output

An ellipsoid $E$ such that $E ⊆ P$. $E$ has maximal volume if P is bounded (no such guarantee is given in directions where P is unbounded).

Notes

The maximum-volume ellipsoid is also called Löwner-John ellipsoid.

The algorithm requires to specify a point in the interior of the ellipsoid which can be specified with the argument interior_point. If no such point is known (i.e., interior_point == nothing), the implementation will compute the Chebyshev center (see chebyshev_center_radius).

Note that the Chebyshev center will be computed using the default LP solver and not the passed SDP solver backend (because it is not guaranteed that backend supports LPs). If a custom LP solver should be used, the Chebyshev center needs to be computed and passed manually.

Algorithm

We use the package SetProg.jl to encode the problem directly.

An algorithm is described here.