vectors_in_intervals.existence¶
Existence of vectors with components in intervals
Functions
|
Check whether an orthogonal vector exists with components in given intervals. |
|
Check whether the system |
- vectors_in_intervals.existence.exists_orthogonal_vector(v, intervals: list[sage.sets.real_set.RealSet]) bool ¶
Check whether an orthogonal vector exists with components in given intervals.
INPUT:
v
– a vector of lengthn
intervals
– a list ofn
intervals
OUTPUT:
Return whether there exists an orthogonal vector to
v
such that the components of this vector lie inintervals
.EXAMPLES:
We define several lists of intervals and vectors and apply the function:
sage: from vectors_in_intervals import * sage: I = intervals_from_bounds([0, 1, -1], [1, 2, -1]) sage: I [[0, 1], [1, 2], {-1}] sage: v = vector([1, 1, 1]) sage: exists_orthogonal_vector(v, I) True sage: v = vector([1, 1, -1]) sage: exists_orthogonal_vector(v, I) False
Next, we consider open intervals:
sage: I = intervals_from_bounds([0, 1, -1], [1, 2, 1], False, [True, True, False]) sage: I [(0, 1], (1, 2], (-1, 1)] sage: v = vector([1, 0, 1]) sage: exists_orthogonal_vector(v, I) True
We can also work with unbounded intervals:
sage: I = intervals_from_bounds([0, 1, -oo], [oo, 2, -2], False, [True, True, False]) sage: I [(0, +oo), (1, 2], (-oo, -2)] sage: v = vector([-1, 1, -1]) sage: exists_orthogonal_vector(v, I) True
TESTS:
sage: I = intervals_from_bounds([-oo, 0], [oo, 0], False, False) sage: I [(-oo, +oo), {}] sage: v = vector([1, 0]) sage: exists_orthogonal_vector(v, I) False sage: v = vector([1]) sage: exists_orthogonal_vector(v, I) Traceback (most recent call last): ... ValueError: Lengths of vector and intervals do not match.
- vectors_in_intervals.existence.exists_vector(data, intervals: list[sage.sets.real_set.RealSet], certify: bool = False) bool ¶
Check whether the system
M x in I
has a solution.INPUT:
data
– either a matrixM
withm
rows or a list ofelementary vectors (in the kernel of
M
) of lengthm
intervals
– a list ofm
intervalsI
certify
– a boolean (default:False
)
OUTPUT:
If
data
is a matrix, check if a vector in the row space lies in the intervals.If
data
is a list of elementary vectors, check if a vector exists orthogonal to those.If
certify
is true and no vector exists, an elementary vector is returned as certificate.
ALGORITHM:
The underlying algorithm is based on Minty’s Lemma. (see [Min74])
- Min74
Minty, G. J.: “A ‘from scratch’ proof of a theorem of Rockafellar and Fulkerson”. In: Mathematical Programming 7 (1974), pp. 368-375.
EXAMPLES:
sage: from vectors_in_intervals import * sage: M = matrix([[1], [1], [0]]) sage: lower_bounds = [2, 5, -1] sage: upper_bounds = [5, 6, 1]
First, we consider closed intervals:
sage: I = intervals_from_bounds(lower_bounds, upper_bounds) sage: I [[2, 5], [5, 6], [-1, 1]] sage: exists_vector(M, I) True
Next, we take open intervals:
sage: I = intervals_from_bounds(lower_bounds, upper_bounds, False, False) sage: I [(2, 5), (5, 6), (-1, 1)] sage: exists_vector(M, I) False
Since no vector exists, there is an elementary vector certifying this. To find one, we pass
certify=True
:sage: exists_vector(M, I, certify=True) (1, -1, 0)
Mixed intervals are also possible:
sage: lower_bounds_closed = [True, True, False] sage: upper_bounds_closed = [False, True, True] sage: I = intervals_from_bounds(lower_bounds, upper_bounds, lower_bounds_closed, upper_bounds_closed) sage: I [[2, 5), [5, 6], (-1, 1]] sage: exists_vector(M, I) False
Finally, we consider unbounded intervals:
sage: M = matrix([[1, 0], [0, 1], [1, 1], [0, 1]]) sage: lower_bounds = [2, 5, 0, -oo] sage: upper_bounds = [5, oo, 8, 5] sage: lower_bounds_closed = [True, True, False, False] sage: upper_bounds_closed = [False, False, False, True] sage: I = intervals_from_bounds(lower_bounds, upper_bounds, lower_bounds_closed, upper_bounds_closed) sage: I [[2, 5), [5, +oo), (0, 8), (-oo, 5]] sage: exists_vector(M, I) True
TESTS:
sage: I = intervals_from_bounds([0, 0], [1, 0], False) sage: I [(0, 1], {}] sage: exists_vector([], I) False sage: M = random_matrix(QQ, 2, 0) sage: exists_vector(M, I) False sage: M = random_matrix(QQ, 1, 0) sage: exists_vector(M, I) Traceback (most recent call last): ... ValueError: Number of rows of matrix ``data`` and length of ``intervals`` do not match.