User guide#

SupPy is a library for projection based feasibility seeking and superiorization algorithms.

Feasibility seeking algorithms have the goal of finding a point in a constrained set given by the intersection of individual constraints \(C_i\)

\[\begin{equation} \text{find } x \in C=\bigcap_{i} C_i \end{equation}\]

One way to achieve this is by means of projecting onto the individual sets \(P_{C_i}(x)\).

Individual projections#

Individual constraints in SupPy are represented by Projection objects that each have a method project() that calculates the projection of a given point x onto the set. Furthermore a relaxed projection can be calculated by setting up a relaxation parameter when constructing the object. project() then calculates a relaxed projection based on the parameter. For indication on whether to use the GPU for calculations a use_gpu parameter is used. This is either set automatically if the required input allows to determine it, or is set manually when constructing the object.

For simple objects like hyperplanes or balls analytical formulations based on the metric projection can be found. A list and explanation of these simple projections can be found in the Projections section.

Should the constraint be formulated as a level set of a function (i.e. \(C_i = \{x \in \mathbb{R}^n | f_i(x) \leq \alpha_i\}\)) the projection can be calculated by means of the subgradient projection method:

\[\begin{split}P_{C_i}(x) = \begin{cases} x - \frac{(f_i(x)-\alpha_i)_+}{||g_i(x)||^2} g_i(x) & \text{if } g_i(x) \neq 0 \\ x & \text{otherwise} \end{cases}\end{split}\]

How these constraints can be implemented is found in the Subgradient projections section.

Projection onto the intersection of sets#

To project onto the intersection of general sets, combinations of the individual projections are used. The simplest ideas are SequentialProjection and SimultaneousProjection methods that project onto the individual sets sequentially or simultaenously, respectively. Furthermore combinations of the two approaches can be used in the form of StringAveragedProjection and BlockIterativeProjection. For a full readup on how these are implemented in SupPy please refer to the Projection methods section.

Linear feasibility problems#

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. To speed up the computation and setup for projections onto linear constraints, SupPy provides several matrix based formulations in the feasibility module. These include AMS, ARM and ART3+ algorithms. For a full readup on these algorithms please refer to the Feasibility seeking algorithms section.

Superiorization#

The idea of superiorization can be best explained by comparing it to constrained optimization. A general constrained optimization problem can be formulated as:

\[\begin{split}\begin{aligned} & \underset{x}{\text{minimize}} & & f(x) \\ & \text{subject to} & & x \in C=\bigcap_{i} C_i \end{aligned}\end{split}\]

The goal of constrained optimization is to fully minimize the objective function while meeting all of the constraints. Superiorization meanwhile aims to find a point in the feasible set and only reducing the objective function value - not necessarily minimizing it. This is done by using a feasibility seeking algorithm and perturbing it with respect to the objective function \(f\) to reduce its value.

In SupPy superiorization algorithms are class based and can be found in the superiorization module. For set up an underlying feasibility seeking algorithm as well as perturbation scheme is needed. An explanation on how this is done can be found in the Superiorization section.

User guide: