certlin.linear_inequality_systems¶

Linear inequality systems¶

This module provides classes for linear inequality systems with methods to find solutions or to certify their nonexistence.

Classes

`HomogeneousSystem`(matrix_strict, ...)	A class for homogeneous linear inequality systems.
`InhomogeneousSystem`(matrix_strict, ...)	A class for inhomogeneous linear inequality systems.
`LinearInequalitySystem`(matrix[, intervals])	A class for linear inequality systems given by a matrix and intervals.

Exceptions

`MaxIterationsReachedError`	Raised when the maximum number of iterations is reached.
`ProcessStoppedError`	Raised when the process was stopped by another process.

class certlin.linear_inequality_systems.HomogeneousSystem(matrix_strict: matrix, matrix_nonstrict: matrix, matrix_zero: matrix)¶

A class for homogeneous linear inequality systems.

A homogeneous linear inequality system is of the form

\[A x > 0, \quad B x \geq 0, \quad C x = 0.\]

EXAMPLES:

sage: from certlin import *
sage: A = matrix([[1, 2], [0, 1]])
sage: B = matrix([[2, 3]])
sage: C = matrix([[-1, 0]])
sage: S = HomogeneousSystem(A, B, C)
sage: S
[ 1  2]  x >  0
[ 0  1]  x >  0
[ 2  3]  x >= 0
[-1  0]  x =  0

We certify whether a solution exists:

sage: S.certify()
(True, (0, 1))
sage: S.certify(random=True)
(True, (0, 1))

Therefore, there is indeed a solution:

sage: S.find_solution()
(0, 1)
sage: S.find_solution_random() # random
(0, 1)

The dual system can be computed as well:

sage: S.dual()
[ 1  1  0  0]  x >  0
[ 1  0  0  0]  x >= 0
[ 0  1  0  0]  x >= 0
[ 0  0  1  0]  x >= 0
[ 1  0  2 -1]  x =  0
[ 2  1  3  0]  x =  0
sage: S.dual().certify()
(False, (-1, -1, 0, -3, 0, 1))

TESTS:

sage: from certlin import *
sage: A = matrix([[0, 1], [0, 1], [0, 1]])
sage: B = zero_matrix(0, 2)
sage: C = matrix([[1, 1], [0, 0]])
sage: S = HomogeneousSystem(A, B, C)
sage: S.certify()
(True, (-1, 1))

dual() → HomogeneousSystem¶: Return the dual linear inequality system.

to_homogeneous() → HomogeneousSystem¶: Return the equivalent homogeneous system.

class certlin.linear_inequality_systems.InhomogeneousSystem(matrix_strict: matrix, matrix_nonstrict: matrix, vector_strict: vector, vector_nonstrict: vector)¶

A class for inhomogeneous linear inequality systems.

An inhomogeneous linear inequality system is of the form

\[A x < a, \quad B x \leq b.\]

EXAMPLES:

sage: from certlin import *
sage: A = matrix([[-1, -1]])
sage: B = matrix([[1, 0], [1, 1]])
sage: a = vector([0])
sage: b = vector([1, 0])
sage: S = InhomogeneousSystem(A, B, a, b)
sage: S
[-1 -1]  x <  0
[ 1  0]  x <= 1
[ 1  1]  x <= 0

This system has no solution which we certify:

sage: S.certify()
(False, (1, 0, 1))
sage: S.certify(random=True)
(False, (1, 0, 1))
sage: S.certify_nonexistence()
(1, 0, 1)
sage: S.certify_nonexistence_random() # random
(1, 0, 1)

Therefore, we cannot find a solution:

sage: S.find_solution()
Traceback (most recent call last):
...
ValueError: No solution exists.
sage: S.find_solution_random()
Traceback (most recent call last):
...
MaxIterationsReachedError: Maximum number of iterations reached. A solution may not exist.

We compute the dual system and write it in homogeneous form:

sage: S.dual()
[ 0  0  1  1]  x >  0
[ 1  0  0  0]  x >= 0
[ 0  1  0  0]  x >= 0
[ 0  0  1  0]  x >= 0
[ 0  0  0  1]  x >= 0
[ 1  1 -1  0]  x =  0
[ 0  1 -1  0]  x =  0
[-1  0  0 -1]  x =  0
sage: S.dual().certify()
(True, (0, 1, 1, 0))

dual() → HomogeneousSystem¶: Return the dual linear inequality system.

to_homogeneous() → HomogeneousSystem¶: Return the equivalent homogeneous system.

to_inhomogeneous() → InhomogeneousSystem¶: Return the equivalent inhomogeneous system.

class certlin.linear_inequality_systems.LinearInequalitySystem(matrix: matrix, intervals: Intervals | None = None)¶

A class for linear inequality systems given by a matrix and intervals.

Every linear inequality system can be written using a matrix \(M\) and a Cartesian product of intervals \(I\) as

\[M x \in I.\]

EXAMPLES:

sage: from certlin 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: I # Cartesian product of intervals
[2, 5) x [5, +oo) x (0, 8) x (-oo, 5]
sage: S = LinearInequalitySystem(M, I)
sage: S
[1 0]  x in [2, 5)
[0 1]  x in [5, +oo)
[1 1]  x in (0, 8)
[0 1]  x in (-oo, 5]

We check for solvability:

sage: S.certify()
(True, (5/2, 5))
sage: S.find_solution()
(5/2, 5)
sage: S.find_solution_random() # random
(5/2, 5)
sage: S.certify_nonexistence()
Traceback (most recent call last):
...
ValueError: A solution exists.
sage: S.certify_nonexistence_random()
Traceback (most recent call last):
...
MaxIterationsReachedError: Maximum number of iterations reached. A solution might exist.

We rewrite the system as a homogeneous and an inhomogeneous system:

sage: S.to_homogeneous()
[ 1  0 -5]  x >  0
[-1 -1  0]  x >  0
[ 1  1 -8]  x >  0
[ 0  0 -1]  x >  0
[-1  0  2]  x >= 0
[ 0 -1  5]  x >= 0
[ 0  1 -5]  x >= 0
sage: S.to_inhomogeneous()
[ 1  0]  x <   5
[-1 -1]  x <   0
[ 1  1]  x <   8
[-1  0]  x <= -2
[ 0 -1]  x <= -5
[ 0  1]  x <=  5

The dual system can be computed as well:

sage: S.dual()
[ 0  0  0  1  1  1  1]  x >  0
[ 1  0  0  0  0  0  0]  x >= 0
[ 0  1  0  0  0  0  0]  x >= 0
[ 0  0  1  0  0  0  0]  x >= 0
[ 0  0  0  1  0  0  0]  x >= 0
[ 0  0  0  0  1  0  0]  x >= 0
[ 0  0  0  0  0  1  0]  x >= 0
[ 0  0  0  0  0  0  1]  x >= 0
[-1  0  0  1 -1  1  0]  x =  0
[ 0 -1  1  0 -1  1  0]  x =  0
[ 2  5 -5 -5  0 -8 -1]  x =  0

certify(random: bool = False, iteration_limit: int = -1) → tuple[bool, vector]¶

Return a boolean and a certificate for solvability.

Both existence and nonexistence are checked in parallel.

INPUT:

random – if true, elementary vectors are generated randomly
iteration_limit – maximum number of iterations for each process (by default unlimited)

OUTPUT: A tuple (exists, certificate) where exists is a boolean indicating whether a solution exists, and certificate is either a solution (if exists is true) or a vector certifying nonexistence (if exists is false).

See also

certify_nonexistence()
certify_nonexistence_random()
find_solution()
find_solution_random()

certify_nonexistence(iteration_limit: int = -1) → vector¶

Certify nonexistence of a solution if no solution exists.

INPUT:

iteration_limit – maximum number of iterations (by default unlimited).

OUTPUT: A vector certifying that no solution exists.

Note

If the iteration limit is reached, a MaxIterationsReachedError is raised.
If a solution exists, a ValueError is raised.

See also

certify()
certify_nonexistence_random()

certify_nonexistence_random(iteration_limit: int = 10000) → vector¶

Certify nonexistence of a solution using random elementary vectors.

INPUT:

iteration_limit – maximum number of iterations (by default 10000). If -1, unlimited.

OUTPUT: A vector certifying that no solution exists.

Note

If the iteration limit is reached, a MaxIterationsReachedError is raised.
If a solution exists, a ValueError is raised.
If a solution exists and the iteration limit is -1, you get an endless loop.

See also

certify()
certify_nonexistence()

dual() → LinearInequalitySystem¶: Return the dual linear inequality system.

find_solution(iteration_limit: int = -1) → vector¶

Compute a solution if existent.

INPUT:

iteration_limit – maximum number of iterations (by default unlimited).

OUTPUT: A vector (as a sum of elementary vectors) solving the system.

Note

If the iteration limit is reached, a MaxIterationsReachedError is raised.
If no solution exists, a ValueError is raised.

See also

certify()
find_solution_random()

find_solution_random(iteration_limit: int = 10000) → vector¶

Compute a solution using random elementary vectors.

INPUT:

iteration_limit – maximum number of iterations (by default 10000). If -1, unlimited.

OUTPUT: A vector (as a sum of elementary vectors) solving the system.

Note

If the iteration limit is reached, a MaxIterationsReachedError is raised.
If no solution exists, a ValueError is raised.
If no solution exists and the iteration limit is -1, you get an endless loop.

See also

certify()
find_solution()

property intervals: Intervals¶: Return the corresponding intervals.

property matrix: matrix¶: Return the corresponding matrix.

to_homogeneous() → HomogeneousSystem¶: Return the equivalent homogeneous system.

to_inhomogeneous() → InhomogeneousSystem¶: Return the equivalent inhomogeneous system.

with_intervals(intervals: Intervals) → LinearInequalitySystem¶

Return a copy of this system with different intervals.

TESTS:

sage: from certlin 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: S = LinearInequalitySystem(M, I)
sage: S.certify()
(True, (5/2, 5))
sage: S.with_intervals(I).certify()
(True, (5/2, 5))
sage: S.with_intervals(Intervals.from_bounds([2, 6, 0, -oo], [5, oo, 8, 5])).certify()
(False, (0, 1, 0, -1))
sage: S.with_intervals(Intervals.from_bounds([2, 5, 0, -oo], [5, 5, 8, 5])).certify()
(True, (2, 5))

exception certlin.linear_inequality_systems.MaxIterationsReachedError¶: Raised when the maximum number of iterations is reached.

exception certlin.linear_inequality_systems.ProcessStoppedError¶: Raised when the process was stopped by another process.