Immunity to Increasing Condition Numbers of Linear Superiorization versus Linear Programming

Given a family of linear constraints and a linear objective function one can consider whether to apply a Linear Programming (LP) algorithm or use a Linear Superiorization (LinSup) algorithm on this data.

In the LP methodology one aims at finding an optimal point, i.e., a point that fulfills the constraints and has the minimal value of the objective function over these constraints.

The Linear Superiorization approach considers the same data as in linear programming problems but instead of attempting to solve with linear programming methods it employs perturbation resilient feasibility-seeking algorithms that steer the iterations toward a feasible point with reduced (not necessarily minimal) objective function value.

This aim of the superiorization method (SM) is less demanding than aiming to reach full-fledged constrained optimality and it places more importance on reaching feasibility than on reaching optimality.

Previous studies (e.g., [1]) compared LP and LinSup in terms of their respective outputs and the resources they use.

Here, we investigate classical LP approaches and LinSup in terms of their sensitivity to condition numbers of the system of linear constraints.

Condition numbers are a measure for the impact of deviations in the input data on the output of a problem and, in particular, they describe the factor of error propagation when given wrong or erroneous data.

Therefore, the ability of LP and LinSup to cope with increased condition numbers, thus with illposed problems, is an important matter to consider which was not studied until now.

We investigate experimentally the advantages and disadvantages of both LP and LinSup on exemplary sets of data of problems of linear programming with multiple condition numbers and different problem dimensions.