-
Notifications
You must be signed in to change notification settings - Fork 32
/
Bloating.jl
259 lines (175 loc) · 5.41 KB
/
Bloating.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
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
export Bloating
"""
Bloating{N, S<:LazySet{N}} <: LazySet{N}
Type that represents a uniform expansion of a set in a given norm (also
known as *bloating*).
### Fields
- `X` -- set
- `ε` -- (usually positive) bloating factor
- `p` -- ``p``-norm (should be ``≥ 1``; default: ``2``)
### Notes
The `Bloating` operation preserves convexity: if `X` is convex, then any
bloating of `X` is convex as well.
If `ε` is positive, then `Bloating(X, ε, p)` is equivalent to the Minkowski sum
of `X` and a ball in the `p`-norm of radius `ε` centered in the origin `O`
(i.e., `X ⊕ Ballp(p, O, ε)`).
Some operations require, or silently assume, that `ε` is positive. Check the
documentation for further information.
"""
struct Bloating{N,S<:LazySet{N}} <: LazySet{N}
X::S
ε::N
p::N
function Bloating(X::S, ε::N, p::N=N(2)) where {N,S<:LazySet{N}}
@assert p >= one(N) "bloating requires a norm >= 1, but $p was given"
return new{N,S}(X, ε, p)
end
end
isoperationtype(::Type{<:Bloating}) = true
isconvextype(::Type{Bloating{N,S}}) where {N,S} = isconvextype(S)
"""
dim(B::Bloating)
Return the dimension of a bloated set.
### Input
- `B` -- bloated set
### Output
The ambient dimension of the bloated set.
"""
function dim(B::Bloating)
return dim(B.X)
end
# helper function to compute the bloating ball
function _bloating_ball(B::Bloating{N}) where {N}
return _bloating_ball(B.ε, B.p, dim(B))
end
function _bloating_ball(ε::N, p::N, n::Int) where {N}
@assert ε >= zero(N) "cannot compute the ball for a negative bloating"
return Ballp(p, zeros(N, n), ε)
end
"""
σ(d::AbstractVector, B::Bloating)
Return the support vector of a bloated set in a given direction.
### Input
- `d` -- direction
- `B` -- bloated set
### Output
The support vector of the bloated set in the given direction.
"""
function σ(d::AbstractVector, B::Bloating)
@assert !iszero(d) "the support vector in the zero direction is undefined"
@assert B.ε >= 0 || B.p > 1 "the support vector for negative bloating " *
"in the 1-norm is not implemented"
return σ(d, B.X) +
sign_cadlag(B.ε) * σ(d, _bloating_ball(abs(B.ε), B.p, dim(B)))
end
"""
ρ(d::AbstractVector, B::Bloating)
Return the support function of a bloated set in a given direction.
### Input
- `d` -- direction
- `B` -- bloated set
### Output
The support function of the bloated set in the given direction.
"""
function ρ(d::AbstractVector, B::Bloating)
@assert !iszero(d) "the support function in the zero direction is undefined"
return ρ(d, B.X) +
sign_cadlag(B.ε) * ρ(d, _bloating_ball(abs(B.ε), B.p, dim(B)))
end
"""
isbounded(B::Bloating)
Determine whether a bloated set is bounded.
### Input
- `B` -- bloated set
### Output
`true` iff the wrapped set is bounded.
"""
function isbounded(B::Bloating)
return isbounded(B.X)
end
function isboundedtype(::Type{<:Bloating{N,S}}) where {N,S}
return isboundedtype(S)
end
"""
isempty(B::Bloating)
Determine whether a bloated set is empty.
### Input
- `B` -- bloated set
### Output
`true` iff the wrapped set is empty.
### Notes
This implementation disregards negative bloating, which could potentially turn a
non-empty set into an empty set.
"""
function isempty(B::Bloating)
return isempty(B.X)
end
"""
an_element(B::Bloating)
Return some element of a bloated set.
### Input
- `B` -- bloated set
### Output
An element in the bloated set.
### Algorithm
This implementation disregards negative bloating and returns the result of
`an_element` for the wrapped set.
"""
function an_element(B::Bloating)
return an_element(B.X)
end
"""
constraints_list(B::Bloating)
Return the list of constraints of a bloated set.
### Input
- `B` -- bloated set
### Output
The list of constraints of the bloated set.
### Notes
The constraints list is only available for non-negative bloating in the `p`-norm
for ``p = 1`` or ``p = ∞`` and if `constraints_list` is available for the
unbloated set.
### Algorithm
We call `constraints_list` on the lazy Minkowski sum with the bloating ball.
"""
function constraints_list(B::Bloating)
@assert is_polyhedral(B) "the constraints list is only available for " *
"polyhedral bloating (which requires a polyhedral base set and the " *
"1-norm or the infinity norm)"
if B.ε < 0
throw(ArgumentError("computing the constraints list of a negatively " *
"bloated set is not supported"))
end
return constraints_list(MinkowskiSum(B.X, _bloating_ball(B)))
end
"""
center(B::Bloating)
Return the center of a bloated set.
### Input
- `B` -- bloated set
### Output
The center of the wrapped set.
### Notes
This implementation disregards negative bloating, which could potentially remove
the center from the set.
"""
function center(B::Bloating)
return center(B.X)
end
"""
is_polyhedral(B::Bloating)
Check whether a bloated set is polyhedral.
### Input
- `B` -- bloated set
### Output
`true` if the set is polyhedral.
### Algorithm
We check the sufficient condition that the base set is polyhedral and that the
norm for bloating is either 1-norm or the infinity norm.
"""
function is_polyhedral(B::Bloating)
return (B.p == 1 || B.p == Inf) && is_polyhedral(B.X)
end
function translate(B::Bloating, x::AbstractVector)
return Bloating(translate(B.X, x), B.ε, B.p)
end