🔢 mathematics

Immunity to Increasing Condition Numbers of Linear Superiorization versus Linear Programming

This paper experimentally investigates and compares the sensitivity of classical Linear Programming (LP) and Linear Superiorization (LinSup) algorithms to increasing condition numbers in linear constraint systems, specifically evaluating their respective abilities to handle ill-posed problems and error propagation.

Original authors: Jan Schröder, Yair Censor, Philipp Süss, Karl-Heinz Küfer

Published 2026-07-10

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jan Schröder, Yair Censor, Philipp Süss, Karl-Heinz Küfer

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the perfect spot in a giant, crowded maze to set up a lemonade stand. You have two goals: first, you must stay inside the maze walls (the constraints), and second, you want to be in the spot where you can sell the most lemonade (the objective function).

In the world of math and computers, this is called a Linear Programming (LP) problem. Usually, people use powerful, high-tech "Simplex" or "Interior Point" algorithms to find the absolute best spot. But there's a new, scrappier method called Linear Superiorization (LinSup). Instead of hunting for the perfect, golden spot, LinSup just wants to find a good spot inside the walls that sells more lemonade than a random spot would. It's like aiming for "satisficing"—getting a result that is good enough, rather than wasting time and energy chasing perfection.

The Big Problem: The "Wobbly" Maze

The paper investigates what happens when the maze itself is "wobbly." In math, this is called a high condition number. Imagine the maze walls are so close together and slightly crooked that if you nudge your starting point by a tiny bit, you might end up crashing into a wall or getting lost. This is an "ill-posed" problem.

The researchers wanted to see: Who handles a wobbly maze better? The high-tech perfection hunters (LP solvers) or the scrappy "good enough" hunters (LinSup)?

The Experiment: A Race Against Time

The team built thousands of digital mazes of different sizes (from small 80x100 grids to massive 4000x5000 grids) and made them wobbly to different degrees. They set a rule: Stop the race as soon as a runner gets close enough to the walls without crashing (a specific "infeasibility" threshold of $10^{-8}$ ). They didn't wait for anyone to find the perfect spot; they just wanted to see who could get close enough to the walls fastest and with the best lemonade sales.

They tested:

LinSup: The scrappy runner who takes small steps, checks the walls, and nudges itself toward better sales.
Scipy Simplex: A classic runner that moves from corner to corner.
Gurobi Simplex: A super-fast commercial runner.
Interior Point: A runner that tries to cut through the middle of the maze.

The Results: The Scrappy Runner Wins the Wobbly Maze

1. When the maze gets huge:
In small mazes, the high-tech runners (Simplex) are fast. But as the maze grew to massive sizes (like 4000x5000), the high-tech runners started to stumble. They took much longer to even get close to the walls. In the biggest mazes, LinSup finished the race before the Gurobi runner even finished its own run. The paper shows that for these large, difficult problems, LinSup is much more robust and finishes the task of getting "close enough" to feasibility much faster.

2. When the maze gets wobbly (High Condition Numbers):
This is where the paper's main discovery shines. As the mazes became more "ill-conditioned" (wobblier):

The Simplex runners (especially the free Scipy ones) started to panic. They realized the maze was too tricky, gave up, and stopped with terrible lemonade sales. They were fast at quitting, but they failed to find a good spot.
The Interior Point runner seemed fast at first, but it had a secret flaw: it kept ending up outside the walls. Even though it found a good sales number, it was technically in the wrong place (high infeasibility). In the most wobbly mazes, it ended up with infeasibility values as high as $100$ to $10^1$ , meaning it was completely lost.
LinSup, however, stayed steady. No matter how wobbly the maze got, LinSup consistently found a spot that was exactly at the required distance from the walls. It didn't care how "wobbly" the math was; it just kept taking its small, careful steps.

Why Does LinSup Win?

The authors suggest that LinSup wins because it doesn't try to look at the entire wobbly maze at once. Instead, it looks at one wall at a time, checks if it's touching, and nudges itself. This "bounded perturbation" approach seems to absorb the errors that usually mess up other algorithms.

The Bottom Line

The paper doesn't claim LinSup finds the perfect mathematical solution. It explicitly states that LinSup is not an LP solver. It doesn't aim for the absolute minimum.

However, for the specific task of finding a feasible spot (one that doesn't break the rules) that is better than a random spot, LinSup proved to be more immune to "wobbly" math problems than the standard tools.

In these simulations, when the problems got big and messy, the "good enough" approach was faster and more reliable than the "perfect" approach. The authors suspect this is because LinSup is less sensitive to the errors that high condition numbers create. While they are confident in these results for the sizes they tested, they note that this is an experimental finding, and they hope to see if this trend holds for even larger problems in the future.

So, if you have a messy, huge, and wobbly problem, you might not need the fancy, expensive perfection machine. Sometimes, the scrappy, "good enough" runner is the one who actually gets the job done.

Technical Summary: Immunity to Increasing Condition Numbers of Linear Superiorization Versus Linear Programming

Problem Statement
The paper addresses the comparative performance of Linear Programming (LP) algorithms and the Linear Superiorization (LinSup) methodology when applied to linear programming problems characterized by increasing condition numbers. While classical LP aims to find an optimal point (minimizing the objective function subject to constraints), LinSup aims to find a feasible point with a "superior" (reduced, though not necessarily minimal) objective function value. The central problem investigated is the sensitivity of both approaches to ill-posedness, specifically how increasing condition numbers of the constraint matrix affect the runtime, feasibility attainment, and objective function reduction of these algorithms.

Methodology
The authors conducted a controlled experimental study comparing LinSup against established LP solvers.

Problem Generation: The researchers constructed linear programming problems of the form $\min \langle c, x \rangle$ subject to $Ax \le b$ and $\ell \le x \le u$ . To ensure structural similarity across different condition numbers, they utilized Singular Value Decomposition (SVD). They generated random semi-orthogonal matrices $U$ and $V$ and constructed diagonal matrices $\Sigma_\kappa$ with singular values distributed to achieve specific condition numbers $\kappa$ (ranging from well-conditioned to highly ill-conditioned). Matrix sizes ranged from $80 \times 100$ to $4000 \times 5000$ .
Algorithms Tested:
- LinSup: Implemented using the Agmon-Motzkin-Schönberg (AMS) projection method as the base feasibility-seeking algorithm. Perturbations were introduced using the normalized negative gradient of the objective function. The algorithm employed bounded perturbations and cyclic projections with specific step-size schedules and restart mechanisms.
- LP Solvers: The study compared LinSup against scipy.simplex, scipy.revised simplex, scipy.interior-point, and gurobi.primal simplex.
Experimental Protocol: To ensure a fair comparison, the authors imposed a unified stopping criterion based on a fixed infeasibility threshold ( $\varepsilon = 10^{-8}$ $ε = 1 0^{- 8}$ ).
- LinSup was run until it reached this threshold.
- LP solvers were run under the same threshold. If an LP solver failed to reach the threshold within the time $T_{sup}$ (the time LinSup took to terminate), it was stopped at $T_{sup}$ , and its current iterate was recorded.
- Metrics recorded included runtime, objective function values, and maximal constraint violations (infeasibility) at termination and throughout the iterations.

Key Contributions and Results
The study provides empirical evidence regarding the robustness of LinSup compared to classical LP solvers under varying problem difficulties:

Performance on Increasing Dimensions (Fixed $\kappa$ ):
- For small dimensions, simplex-based solvers were faster.
- As problem dimensions increased (up to $4000 \times 5000$ ), the runtime of simplex implementations (including Gurobi) increased significantly. In high dimensions, LinSup terminated faster than the simplex solvers.
- Notably, in the largest dimensions tested, LinSup reached the feasibility threshold before the simplex algorithms even attained feasibility.
Immunity to Increasing Condition Numbers (Fixed Dimensions):
- Simplex Methods: As the condition number increased, the scipy simplex implementations exhibited severe degradation. They often terminated early with sub-optimal objective values, effectively "surrendering" due to the difficulty of the problem.
- Interior Point Method: While this method appeared to find low objective values quickly, it struggled to attain the required level of feasibility for high condition numbers, resulting in high infeasibility values (up to $10^1$ ).
- LinSup: The superiorization method demonstrated remarkable stability. Its runtime remained relatively consistent regardless of the condition number, and it consistently achieved the target feasibility level ( $\varepsilon = 10^{-8}$ ) across all tested condition numbers.
- Objective Function: LinSup consistently produced better (lower) objective function values at the point of termination compared to the simplex methods in ill-conditioned scenarios.
Proximity-Target Analysis:
- Plots of infeasibility versus objective function value (proximity-target curves) confirmed that LinSup maintained a steady path toward feasibility while reducing the objective. In contrast, the interior-point method showed a disconnect between finding a low objective value and satisfying constraints in ill-conditioned settings.

Significance and Claims
The paper claims that Linear Superiorization offers a distinct advantage over classical LP solvers when dealing with ill-conditioned linear systems, particularly in large-scale scenarios.

Robustness: The authors conclude that LinSup is less affected by high condition numbers than the tested LP solvers. They attribute this to the nature of the algorithm: LinSup performs individual projections onto half-spaces rather than solving the full system simultaneously, and the "bounded perturbation resilience" of the base algorithm may help absorb computational errors that would otherwise be amplified by ill-conditioning.
Practical Utility: The study suggests that for applications where finding a feasible point with a reduced objective value is sufficient (a "satisficing" approach rather than strict optimality), LinSup is a more reliable and efficient tool for ill-posed problems.
Modest Scope: The authors explicitly state that their results are based on specific experimental setups and problem sizes. They express confidence that the observed trends will hold for larger instances but do not claim LinSup replaces LP solvers for all optimization tasks. They note that LinSup is not an LP solver and does not aim for constrained optimality, but rather for a "superior" feasible point.
Future Work: The paper suggests that the observed robustness of LinSup in linear settings warrants investigation in nonlinear settings, particularly where interior-point methods are known to struggle with ill-conditioning (e.g., intensity-modulated radiotherapy).