Paperlane

no. 16 · Tuesday 17 November 2026

Finite-Step Algorithms for Input-Constrained Control Barrier Function-Based Safety Filters

Johannes Autenrieb, Mark Spiller and Mayank S. Jha

math.OC · via eess.SY · 8 pp

Abstract

Control barrier function (CBF) safety filters commonly rely on quadratic programs (QPs) to modify nominal control inputs while satisfying safety constraints. For safety-critical applications, however, the solution must be computed reliably under actuator limitations and with predictable computational effort. General-purpose QP solvers typically rely on numerical convergence criteria, which do not directly provide finite bounds on algorithmic steps or distinguish solver failure from mathematical infeasibility. This paper considers CBF-QPs with a single affine safety constraint, componentwise input bounds, and diagonal quadratic weights. Exploiting the established scalar dual structure of continuous quadratic knapsack problems, we obtain a necessary and sufficient pointwise feasibility condition and an exact breakpoint-based solution procedure. The algorithm requires at most 2n positive breakpoint events for n inputs, reducing to at most n events when the nominal input is admissible. In the latter case, an exact saturation–redistribution algorithm computes the optimal solution in at most n passes. We further describe how the structured solution can be combined with verified floating-point constraint evaluation to distinguish certified feasible commands, certified infeasibility, and unresolved numerical cases. The resulting framework provides an exact and computationally predictable solution procedure for a practically relevant class of input-constrained CBF safety filters.

comments
8 pages, 3 figures
fields
Optimization and Control
pdf ↗ page arXiv:2611.21075 ↗