/
box_approximations.jl
189 lines (146 loc) · 4.61 KB
/
box_approximations.jl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
# ===================================
# Approximations in the infinity norm
# ===================================
"""
box_approximation(S::LazySet{N})::Union{Hyperrectangle{N}, EmptySet{N}}
where {N<:Real}
Overapproximate a convex set by a tight hyperrectangle.
### Input
- `S` -- convex set
### Output
A tight hyperrectangle.
### Algorithm
The center of the hyperrectangle is obtained by averaging the support function
of the given set in the canonical directions, and the lengths of the sides can
be recovered from the distance among support functions in the same directions.
"""
function box_approximation(S::LazySet{N}
)::Union{Hyperrectangle{N}, EmptySet{N}} where {N<:Real}
(c, r) = box_approximation_helper(S)
if r[1] < 0
return EmptySet{N}()
end
return Hyperrectangle(c, r)
end
# special case: Hyperrectangle
box_approximation(S::Hyperrectangle) = S
# special case: other rectangle
box_approximation(S::AbstractHyperrectangle) =
Hyperrectangle(center(S), radius_hyperrectangle(S))
# special case: empty set
box_approximation(∅::EmptySet) = ∅
"""
interval_hull
Alias for `box_approximation`.
"""
interval_hull = box_approximation
"""
box_approximation_symmetric(S::LazySet{N}
)::Union{Hyperrectangle{N}, EmptySet{N}}
where {N<:Real}
Overapproximate a convex set by a tight hyperrectangle centered in the origin.
### Input
- `S` -- convex set
### Output
A tight hyperrectangle centered in the origin.
### Algorithm
The center of the box is the origin, and the radius is obtained by computing the
maximum value of the support function evaluated at the canonical directions.
"""
function box_approximation_symmetric(S::LazySet{N};
)::Union{Hyperrectangle{N},
EmptySet{N}} where {N<:Real}
(c, r) = box_approximation_helper(S)
if r[1] < 0
return EmptySet{N}()
end
return Hyperrectangle(zeros(N, length(c)), abs.(c) .+ r)
end
# special case: empty set
box_approximation_symmetric(∅::EmptySet) = ∅
"""
symmetric_interval_hull
Alias for `box_approximation_symmetric`.
"""
symmetric_interval_hull = box_approximation_symmetric
"""
box_approximation_helper(S::LazySet{N};
) where {N<:Real}
Common code of `box_approximation` and `box_approximation_symmetric`.
### Input
- `S` -- convex set
### Output
A tuple containing the data that is needed to construct a tightly
overapproximating hyperrectangle.
- `c` -- center
- `r` -- radius
### Algorithm
The center of the hyperrectangle is obtained by averaging the support function
of the given convex set in the canonical directions.
The lengths of the sides can be recovered from the distance among support
functions in the same directions.
"""
@inline function box_approximation_helper(S::LazySet{N};
) where {N<:Real}
zero_N = zero(N)
one_N = one(N)
n = dim(S)
c = Vector{N}(undef, n)
r = Vector{N}(undef, n)
d = zeros(N, n)
@inbounds for i in 1:n
d[i] = one_N
htop = ρ(d, S)
d[i] = -one_N
hbottom = -ρ(d, S)
d[i] = zero_N
c[i] = (htop + hbottom) / 2
r[i] = (htop - hbottom) / 2
if r[i] < 0
# contradicting bounds => set is empty
# terminate with first radius entry being negative
r[1] = r[i]
break
end
end
return c, r
end
"""
ballinf_approximation(S::LazySet{N};
)::BallInf{N} where {N<:Real}
Overapproximate a convex set by a tight ball in the infinity norm.
### Input
- `S` -- convex set
### Output
A tight ball in the infinity norm.
### Algorithm
The center and radius of the box are obtained by evaluating the support function
of the given convex set along the canonical directions.
"""
function ballinf_approximation(S::LazySet{N};
)::Union{BallInf{N}, EmptySet{N}} where {N<:Real}
zero_N = zero(N)
one_N = one(N)
n = dim(S)
c = Vector{N}(undef, n)
r = zero_N
d = zeros(N, n)
@inbounds for i in 1:n
d[i] = one_N
htop = ρ(d, S)
d[i] = -one_N
hbottom = -ρ(d, S)
d[i] = zero_N
c[i] = (htop + hbottom) / 2
rcur = (htop - hbottom) / 2
if (rcur > r)
r = rcur
elseif rcur < 0
# contradicting bounds => set is empty
return EmptySet{N}()
end
end
return BallInf(c, r)
end
# special case: empty set
ballinf_approximation(∅::EmptySet) = ∅