vectors_in_intervals.existence

Existence of vectors with components in intervals

Functions

exists_orthogonal_vector(v, intervals)

Check whether an orthogonal vector exists with components in given intervals.

exists_vector(data, intervals[, certify])

Check whether the system M x in I has a solution.
vectors_in_intervals.existence.exists_orthogonal_vector(v, intervals: vectors_in_intervals.intervals.Intervals) → bool

Check whether an orthogonal vector exists with components in given intervals.

INPUT:

  • v – a vector of length n

  • intervals – a list of n intervals

OUTPUT:

Return whether there exists an orthogonal vector to v such that the components of this vector lie in intervals.

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] x [1, 2] x {-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] x (1, 2] x (-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) x (1, 2] x (-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) x {}
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: vectors_in_intervals.intervals.Intervals, certify: bool = False) → bool

Check whether the system M x in I has a solution.

INPUT:

  • data – either a matrix M with m rows or a list of

    elementary vectors (in the kernel of M) of length m

  • intervals – a list of m intervals I

  • 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] x [5, 6] x [-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) x (5, 6) x (-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) x [5, 6] x (-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) x [5, +oo) x (0, 8) x (-oo, 5]
sage: exists_vector(M, I)
True

TESTS:

sage: I = Intervals.from_bounds([0, 0], [1, 0], False)
sage: I
(0, 1] x {}
sage: exists_vector([], I)
False
sage: M = random_matrix(QQ, 2, 0)
sage: exists_vector(M, I)
False