Feasibility seeking algorithms#

While individual linear constraints \(C_i = \{x \in \mathbb{R}^n | a_i x \leq b_i\}\) can be projected onto using the dedicated HalfspaceProjection class, this becomes cumbersome for the intersection of many linear constraints. For linear feasibility problems SupPy provides several implementations of feasibility seeking algorithms that take advante of matrix operations in the

These cover the following problems:

  • Hyperplane \(Ax = b\)

  • Halfspace \(Ax \leq b\)

  • Hyperslab/Bands \(lb \leq Ax \leq ub\)

For all three implementations the AMS algorithm/Kaczmarz’s method are available (sequentially and simultaenously). Furthermore the ART3+ (Algebraic reconstruction technique) and ARM (Automatic relaxation method) algorithms are available for the hyperslab/bands problems. Once a class is initialized a single step of the algorithm can be performed using the project() method, while a full run can be done using the solve() method.

Initialization of Halfspace and Hyperplane problems are identical, while the hyperslab/bands problem requires a lower and an upper bound (instead of a single bound). A simple sequential model for \(lb \leq Ax \leq ub\) can bet set up and solved using:

import numpy as np
from suppy.feasibility import SequentialAMSHyperslab

A = np.array([[1, 1], [-1, 1], [1, 0], [0, 1]])
lb = np.array([-2, -2, -3 / 2, -3 / 2])
ub = -1 * lb
seq_model = SequentialAMSHyperslab(A, lb, ub)
x_0 = np.array([10,2])
x_sol = seq_model.solve(x_0,3000)

In the following variables for the different classes are explained.

Sequential implementations#

Sequential implementations can be passed a control sequence cs that determines the order in which the constraints are processed. If no sequence is passed the constraints are evaluated in order of the rows.

Simultaneous implementations#

Simultaneous implementations can be passed a weights option that determines how much an individual constraint \(\langle A,x \rangle \leq b\) is weighted in the individual projection step. To ensure that weights add up to 1, the passed weights are divided by their sum. If no weights are passed uniform weights are applied.

Hyperslab/Bands#

Halfspace#

  • SequentialAMSHalfspace

  • SimultaneousAMSHalfspace

  • BlockIterativeAMSHalfspace

  • StringAveragedAMSHalfspace

Hyperplane#

  • KaczmarzMethod

  • SimultaneousKaczmarzMethod

  • BlockIterativeKaczmarz

  • StringAveragedKaczmarz