vectors_in_intervals.certifying_inequalities

Certifying solvability of linear inequality systems using elementary vectors

Given is a system of linear inequalities. We are interested whether the system has a solution. Further, we want to certify the result using an elementary vector (support-minimal vector).

Many of the results are derived from theorems in [Ben00].

Ben00

A. Ben-Israel. Motzkin’s transposition theorem, and the related theorems of Farkas, Gordan and Stiemke. 2000.

Homogeneous systems

There is also a homogeneous version of Motzkin’s transposition theorem. Here, we have three matrices \(A\), \(B\) and \(C\) and deals with the system \(A x > 0, B x \geq 0, C x = 0\):

sage: from vectors_in_intervals import *
sage: A = matrix([[1, 2], [0, 1]])
sage: B = matrix([[2, 3]])
sage: C = matrix([[-1, 0]])
sage: S = AlternativesHomogeneous(A, B, C)
sage: S.one.matrix
[ 1  2]
[ 0  1]
[-----]
[ 2  3]
[-----]
[-1  0]
sage: S.one.get_intervals()
[(0, +oo), (0, +oo), [0, +oo), {0}]
sage: exists_vector(S.one.matrix, S.one.get_intervals())
True

The certify the result, we consider the alternative system which consists of a single matrix and intervals:

sage: S.two.matrix
[ 1  1  0  0]
[-----------]
[ 1  0  0  0]
[ 0  1  0  0]
[ 0  0  1  0]
[-----------]
[ 1  0  2 -1]
[ 2  1  3  0]
sage: S.two.get_intervals()
[(0, +oo), [0, +oo), [0, +oo), [0, +oo), {0}, {0}]
sage: exists_vector(S.two.matrix, S.two.get_intervals())
False
sage: exists_vector(S.two.matrix, S.two.get_intervals(), certify=True)
(-1, -1, 0, -3, 0, 1)

There is a single command for certification:

sage: S.certify()
(True, (-1, -1, 0, -3, 0, 1), 2)

We can also use elementary vectors to construct a solution:

sage: S.one.solve()
(0, 1)

We consider another example:

sage: A = matrix([[1, 0], [0, 1]])
sage: B = matrix([[2, -3]])
sage: C = matrix([[-1, -1]])
sage: S = AlternativesHomogeneous(A, B, C)
sage: S.certify()
(False, (0, -5, -1, -2), 1)
sage: S.one.certify()
(False, (1, 1, 0, 1))

In some cases, it is faster to randomly generate elementary vectors to certify:

sage: S.certify(random=True) # random
(False, (0, -5, -1, -2), 2)

Parallel computation is also supported:

sage: S.certify(number_parallel=4) # random
(False, (0, -5, -1, -2), 2)

A solution for the second system is:

sage: S.two.solve()
(1, 1, 0, 1)

Inhomogeneous systems

We deal with linear inequality systems given in the form \(A x \leq b, B x < c\) with matrices \(A\), \(B\) and vectors \(b\), \(c\). We are interested whether the system has a solution \(x\). This can be checked using vectors_in_intervals.existence.exists_vector(). If no solution exists, this function can be used to certify the result.

To demonstrate this, consider the following example:

sage: from vectors_in_intervals import *
sage: A = matrix([[1, 2], [0, 1]])
sage: B = matrix([[2, 3]])
sage: b = vector([1, -1])
sage: c = vector([2])
sage: S = AlternativesInhomogeneous(A, B, b, c)
sage: S.one.matrix
[1 2]
[0 1]
[---]
[2 3]
sage: S.one.get_intervals()
[(-oo, 1], (-oo, -1], (-oo, 2)]
sage: exists_vector(S.one.matrix, S.one.get_intervals())
True

However, to certify existence of a solution, we need to consider the alternative system. This system can be described by two matrices and two lists of intervals:

sage: S.two.matrix
[ 0  0  1  1]
[-----------]
[ 1  0  0  0]
[ 0  1  0  0]
[ 0  0  1  0]
[ 0  0  0  1]
[-----------]
[ 1  0  2  0]
[ 2  1  3  0]
[-1  1 -2 -1]
sage: S.two.get_intervals()
[(0, +oo), [0, +oo), [0, +oo), [0, +oo), [0, +oo), {0}, {0}, {0}]
sage: exists_vector(S.two.matrix, S.two.get_intervals())
False
sage: exists_vector(S.two.matrix, S.two.get_intervals(), certify=True)
(1, 3, 0, 4, 0, 0, -1, 1)

The package offers a single function that certifies existence of a solution:

sage: S.certify()
(True, (2, 2, 0, 0, 0, 4, -2, 2), 12)

The alternatives for the inhomogeneous case can be formulated using two systems. The resulting systems yield different certificates:

sage: S = AlternativesInhomogeneous(A, B, b, c, two_double_system=True)
sage: S.certify()
(True, [(-2, 0, -1, 0, 0, 1, 0), (-2, -1, 0, 0, -5, 2)], 5)

A solution is:

sage: S.one.solve()
(2, -1)

We consider another example:

sage: A = matrix([[1, 0], [1, 1]])
sage: B = matrix([[-1, -1]])
sage: b = vector([1, 0])
sage: c = vector([0])
sage: S = AlternativesInhomogeneous(A, B, b, c)
sage: S.certify()
(False, (0, 1, 1), 1)

We can homogenized the first alternative yielding a different system:

sage: S = AlternativesInhomogeneous(A, B, b, c, one_homogenized=True)
sage: S.certify()
(False, (0, 1, 0, 1), 1)

A solution is:

sage: S.two.solve()
(0, 1, 1, 0)

General systems

By translating systems of the form M x in I into inhomogeneous systems, we can certify general systems:

sage: from vectors_in_intervals import *
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: exists_vector(M, I) # no certificate
True
sage: S = AlternativesGeneral(M, I)
sage: S.one.matrix
[1 0]
[0 1]
[1 1]
[0 1]
sage: S.one.get_intervals()
[[2, 5), [5, +oo), (0, 8), (-oo, 5]]
sage: S.two.matrix
[ 0  0  0  1  1  1  1]
[--------------------]
[ 1  0  0  0  0  0  0]
[ 0  1  0  0  0  0  0]
[ 0  0  1  0  0  0  0]
[ 0  0  0  1  0  0  0]
[ 0  0  0  0  1  0  0]
[ 0  0  0  0  0  1  0]
[ 0  0  0  0  0  0  1]
[--------------------]
[-1  0  0  1 -1  1  0]
[ 0 -1  1  0 -1  1  0]
[ 2  5 -5 -5  0 -8 -1]
sage: S.two.get_intervals()
[(0, +oo), [0, +oo), [0, +oo), [0, +oo), [0, +oo), [0, +oo), [0, +oo), [0, +oo), {0}, {0}, {0}]
sage: S.certify()
(True, (1, 0, 0, 0, 2, 6, 0, 0, 2, 5, 1), 3)

We compute a solution using elementary vectors:

sage: S.one.solve()
(2, 5)

Functions

inhomogeneous_alternative1(system)

A standard inhomogeneous linear inequality system.

inhomogeneous_alternative1_homogenized(system)

Homogenization of a standard inhomogeneous linear inequality system.

inhomogeneous_alternative2(system)

Alternative of a standard inhomogeneous linear inequality system.

inhomogeneous_alternative2_system1(system)

Alternative of a standard inhomogeneous linear inequality system given by two systems.

inhomogeneous_alternative2_system2(system)

Alternative of a standard inhomogeneous linear inequality system given by two systems.

Classes

Alternatives

An abstract class for certifying linear inequality systems.

AlternativesGeneral(M, I)

Alternatives for a general system M x in I.

AlternativesHomogeneous(A, B, C)

A class for certifying homogeneous linear inequality systems.

AlternativesInhomogeneous(A, B, b, c[, ...])

A class for certifying inhomogeneous linear inequality systems.
class vectors_in_intervals.certifying_inequalities.Alternatives

An abstract class for certifying linear inequality systems.

certify(reverse: bool = True, random: bool = False, number_parallel: int = 1) → tuple

Certify whether the first alternative has a solution.

  • reverse – reverses the order of elementary vectors

  • random – randomizes computed elementary vectors (repetition possible)

  • number_parallel – number of parallel computations

OUTPUT: A boolean, a vector certifying the result, and the number of needed iterations.

class vectors_in_intervals.certifying_inequalities.AlternativesGeneral(M, I)

Alternatives for a general system M x in I.

class vectors_in_intervals.certifying_inequalities.AlternativesHomogeneous(A, B, C)

A class for certifying homogeneous linear inequality systems.

A x > 0, B x >= 0, C x = 0

class vectors_in_intervals.certifying_inequalities.AlternativesInhomogeneous(A, B, b, c, one_homogenized=False, two_double_system=False)

A class for certifying inhomogeneous linear inequality systems.

A x <= b, B x < c

INPUT:

  • To use a homogenized representation of the first alternative, pass one_homogenized=True.

  • To use two systems for the second alternative instead of a homogenized system, pass two_double_system=True.

TESTS:

sage: from vectors_in_intervals import *
sage: A = matrix([[1]])
sage: B = matrix(0, 1)
sage: b = vector([1])
sage: c = vector([])
sage: S = AlternativesInhomogeneous(A, B, b, c)
sage: S.certify()
(True, (-1, 0, 0, -1, -1), 2)
sage: S.certify(random=True)[0]
True
certify(reverse: bool = True, random: bool = False, number_parallel: int = 1) → tuple

Certify whether the first alternative has a solution.

OUTPUT: A boolean, vectors certifying the result, and the number of needed iterations.

vectors_in_intervals.certifying_inequalities.inhomogeneous_alternative1(system: vectors_in_intervals.linear_inequality_systems.InhomogeneousSystem) → vectors_in_intervals.linear_inequality_systems.InhomogeneousSystem

A standard inhomogeneous linear inequality system.

A x <= b, B x < c

vectors_in_intervals.certifying_inequalities.inhomogeneous_alternative1_homogenized(system: vectors_in_intervals.linear_inequality_systems.InhomogeneousSystem) → vectors_in_intervals.linear_inequality_systems.HomogeneousSystem

Homogenization of a standard inhomogeneous linear inequality system.

The system has this form:

[A -b]
[B -c] x in [0, oo)^p x (0, oo)^(q + 1)
[0 -1]
vectors_in_intervals.certifying_inequalities.inhomogeneous_alternative2(system: vectors_in_intervals.linear_inequality_systems.InhomogeneousSystem) → vectors_in_intervals.linear_inequality_systems.HomogeneousSystem

Alternative of a standard inhomogeneous linear inequality system.

vectors_in_intervals.certifying_inequalities.inhomogeneous_alternative2_system1(system: vectors_in_intervals.linear_inequality_systems.InhomogeneousSystem) → vectors_in_intervals.linear_inequality_systems.HomogeneousSystem

Alternative of a standard inhomogeneous linear inequality system given by two systems.

vectors_in_intervals.certifying_inequalities.inhomogeneous_alternative2_system2(system: vectors_in_intervals.linear_inequality_systems.InhomogeneousSystem) → vectors_in_intervals.linear_inequality_systems.HomogeneousSystem

Alternative of a standard inhomogeneous linear inequality system given by two systems.