Rectification

Rectification{N, S<:LazySet{N}}

Type that represents the rectification of a set.

Fields

• X – set
• cache – storage of information computed before

Notes

Given a vector $v = (v_1, …, v_n)$, its rectification is defined as $\text{rectify}(v) = (v_1', …, v_n')$ such that $v_i' = \max(v_i, 0)$ for each $i = 1, …, n$.

The extension to a set $X$ is defined elementwise:

\[ \text{rectify}(X) = \{\text{rectify}(x) \mid x ∈ X\}\]

The rectification of a convex set $X$ is not necessarily convex. It can be expressed exactly as the union of the intersection of $X$ with the nonnegative orthant and the projection of the intersection of $X$ with each other orthant. This can be seen as follows.

First we observe that rectification distributes with union.

\[ \text{rectify}(X_1 ∪ … ∪ X_m) = ⋃_j \text{rectify}(X_j)\]

Next we express $X$ as the union of the intersection of $X$ with each orthant $O$.

\[ X = ⋃_j (X ∩ O_j)\]

Thus we have

\[ \text{rectify}(X) = \text{rectify}((X ∩ O_1) ∪ … ∪ (X ∩ O_m)) = ⋃_j \text{rectify}(X ∩ O_j).\]

Clearly, $\text{rectify}(X ∩ O_j) = X$ if $O_j$ is the nonnegative orthant.

For example, consider a two-dimensional case and call the orthants $O_1, …, O_4$ in clockwise fashion, starting with the nonnegative orthant. We conclude that

\[ \text{rectify}(X) = (X ∩ O_1) ∪ \text{rectify}(X ∩ O_2) ∪ \text{rectify}(X ∩ O_3) ∪ \text{rectify}(X ∩ O_4).\]

The rectification of the intersection in the nonpositive orthant, $\text{rectify}(X ∩ O_3)$, is either the empty set or the singleton containing the origin. The rectification of $X ∩ O_2$ and $X ∩ O_4$ both result in flat $1$-dimensional line segments on the corresponding hyperplane of $O_1$.

set(r::Rectification)

Return the original set of a rectification.

Input

• r – rectification

Output

The original set of the rectification.

dim(r::Rectification)

Return the dimension of a rectification.

Input

• r – rectification

Output

The ambient dimension of the rectification.

σ(d::AbstractVector, r::Rectification)

Return the support vector of a rectification.

Input

• d – direction
• r – rectification

Output

The support vector in the given direction. If the direction has norm zero, the result depends on the wrapped set.

σ(d::AbstractVector, r::Rectification{N, <:AbstractHyperrectangle{N}}) where {N}

Return the support vector of the rectification of a hyperrectangular set.

Input

• d – direction
• r – rectification of a hyperrectangular set

Output

The support vector in the given direction.

Algorithm

Let $r(·)$ be the rectification of a vector respectively a set, and let $H$ be a hyperrectangle. Then $σ_{r(H)}(d) = r(σ_{H}(d))$.

σ(d::AbstractVector, r::Rectification{N, <:CartesianProduct{N}}) where {N}

Return the support vector of the rectification of a Cartesian product of two sets.

Input

• d – direction
• r – rectification of a Cartesian product of two sets

Output

The support vector in the given direction.

Algorithm

Rectification distributes with the Cartesian product. Let $r(·)$ be the rectification of a set. We can just query the support vector for $r(X)$ and $r(Y)$ recursively: $σ_{r(X × Y)}(d) = σ_{r(X)}(d_X) × σ_{r(Y)}(d_Y)$, where $x × y$ concatenates vectors $x$ and $y$.

σ(d::AbstractVector, r::Rectification{N, <:CartesianProductArray{N}}) where {N}

Return the support vector of the rectification of a Cartesian product of a finite number of sets.

Input

• d – direction
• r – rectification of a Cartesian product of a finite number of sets

Output

The support vector in the given direction.

Algorithm

Rectification distributes with the Cartesian product. Let $r(·)$ be the rectification of a set. We can just query the support vector for each subspace recursively: $σ_{r(X_1 × ⋯ × X_m)}(d) = σ_{r(X_1)}(d_{X_1}) × ⋯ × σ_{r(X_m)}(d_{X_m})$, where $x × y$ concatenates vectors $x$ and $y$.

ρ(d::AbstractVector, r::Rectification)

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

Input

• d – direction
• r – rectification of a set

Output

The support value of the rectification of a set in the given direction.

Algorithm

We use different procedures for different types of input sets. If the wrapped set has a suitable structure for which we can efficiently compute the support vector, we fall back to the evaluation of the support function by means of the support vector. Otherwise we compute the union of projections to obtain a precise result (see to_union_of_projections), and then compute the support function for this union. (The union is cached internally, so subsequent queries are more efficient.)

an_element(r::Rectification)

Return some element of a rectification.

Input

• r – rectification

Output

An element in the rectification. The implementation relies on the an_element function of the wrapped set.

∈(x::AbstractVector, r::Rectification)

Check whether a given point is contained in a rectification.

Input

• x – point/vector
• r – rectification

Output

true iff $x ∈ r$.

Algorithm

We first scan for negative entries in the vector. If there are any, the vector is not contained in the rectification.

Next we ask a membership query in the wrapped set. If the answer is positive, the vector is contained in the rectification.

Otherwise, we scan for zero entries in the vector. If there are none, membership reduces to membership in the wrapped set, and so the answer is negative.

Finally, if there are zero entries in the vector and the vector is not contained in the wrapped set, we give up and throw an error.

isempty(r::Rectification)

Check whether a rectification is empty or not.

Input

• r – rectification

Output

true iff the wrapped set is empty.

isbounded(P::AbstractPolyhedron{N}; [solver]=default_lp_solver(N)) where {N}

Determine whether a polyhedron is bounded.

Input

• P – polyhedron
• solver – (optional, default: default_lp_solver(N)) the backend used to solve the linear program

Output

true iff the polyhedron is bounded

Algorithm

We first check if the polyhedron has more than max(dim(P), 1) constraints, which is a necessary condition for boundedness.

If so, we check boundedness via _isbounded_stiemke.

isbounded(r::Rectification{N}) where {N}

Determine whether a rectification is bounded.

Input

• r – rectification

Output

true iff the rectification is bounded.

Algorithm

Let $X$ be the set wrapped by rectification $r$. We first check whether $X$ is bounded (because then $r$ is bounded). Otherwise, we check unboundedness of $X$ in direction $(1, 1, …, 1)$, which is sufficient for unboundedness of $r$; this step is not necessary but rather a heuristics. Otherwise, we check boundedness of $X$ in every positive unit direction, which is sufficient and necessary for boundedness of $r$.

to_union_of_projections(r::Rectification{N},
                        concrete_intersection::Bool=false
                       ) where {N}

Compute an equivalent union of projections from a rectification of a set.

Input

• r – rectification of a set
• concrete_intersection – (optional, default: false) option to compute all intersections concretely or lazily

Algorithm

Let $X$ be the set wrapped by the rectification $r$. We compute a union of sets that represents the rectification of $X$ precisely. The sets are lazy projections, potentially of intersections.

We first identify those dimensions where $X$ is negative, using one support-function query per dimension, and collect the dimensions in the index set $I_\text{neg}$. For each element in $I_\text{neg}$ we will later apply a projection to zero.

Next we identify those dimensions from $I_\text{neg}$ where $X$ is also positive, using another support-function query in each dimension, and collect the dimensions in the index set $I_\text{mix}$. Let us call the remaining dimensions ($I_\text{neg} \setminus I_\text{mix}$) $I_\text{nonpos}$. For each dimension in $j ∈ I_\text{mix}$ we will apply an intersection with axis-aligned polyhedra. In particular, we distinguish two cases using half-spaces $x_j ≤ 0$ and $x_j ≥ 0$, and then compute all possible combinations to intersect, using one half-space per dimension $j ∈ I_\text{mix}$.

Next we project the intersections in all dimensions from $i ∈ I_\text{mix}$ such that we used the half-space $x_i ≤ 0$ in their computation, and in all dimensions $j ∈ I_\text{nonpos}$ irrespective of the half-space used.

Finally, we take the union of the resulting sets.

Output

The result can be one of three cases depending on the wrapped set $X$, namely

• the set $X$ if $X$ is contained in the positive quadrant,
• a LinearMap (projection) of $X$ if for each dimension, $X$ is only either positive or negative, or
• a UnionSetArray of LinearMaps (projections) otherwise.

RectificationCache{N}

Struct that is used as a cache for Rectifications.

Fields

• set – set represented by the rectification (can be nothing if not computed yet)
• use_support_vector – flag indicating whether to use support-vector computations for the cached set