REVIEW 3 major objections 4 minor 31 references
Synthesis of Discrete-time Control Barrier Functions for Polynomial Systems Based on Sum-of-Squares Programming
T0 review · 3 major / 4 minor · reviewed 2026-08-16 · deepseek-v4-flash
Pith's one-line read The paper claims an alternating-descent SOS algorithm can synthesize quadratic and higher-degree DTCBFs with polynomial control policies for discrete-time control-affine polynomial systems, and that the procedure is lossless once it starts.
desk verdict A genuinely new quadratic DTCBF synthesis scheme, but the central claim is narrower than stated because Step 1 silently forces policy components to vanish at zeros of the cross coefficients, and the higher-degree extension is only sketched. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The engine of the method is a replacement rule for the problematic term h^(k-1)(f(x)+g(x)pi(x)). Because h is quadratic, once h^(k-1) is fixed this term expands as a sum of coefficient polynomials a_{i,j}(x) times pi_i(x)pi_j(x). The paper replaces each product pi_i(x)pi_j(x) with a fresh polynomial e_pi_{i,j}(x), then imposes SOS constraints, built from 2 by 2 positive-semidefinite matrix inequalities and the generalized S-procedure, that guarantee a_{i,j}(x)(pi_i(x)pi_j(x) - e_pi_{i,j}(x)) >= 0 on the current zero-superlevel set C^(k-1). This makes the true next-step barrier value no smaller than the tractable substitute, so an SOS certificate for the substitute implies the DTCBF inequality for the real system. All decision variables enter linearly, so each substep is a semidefinite program.
What would settle it
Run the first Step-1 feasibility problem (35) on the scalar control-affine system x+ = x + u with U = [-1,1], safe set S = {x : $x^{2}$ <= 1}, and initial barrier h^(0)(x) = 1 - $x^{2}$, where the known triple (h^(0), gamma(r)=r, pi(x)=0) satisfies the DTCBF inequality and input admissibility. If (35) is infeasible for this data, the auxiliary conditions are strictly conservative; conversely, a successful run that later returns a triple violating the barrier inequality or input admissibility on a sampled grid would refute the losslessness claim.
Extended reading notes
Core claim
On its own terms, the paper's central claim is Theorem 3: the proposed three-step algorithm is lossless. Starting from an initial quadratic DTCBF h^(0), allowed to be very conservative, Step 1 fixes h^(k-1) and searches for gamma^(k) and a polynomial policy pi^(k), together with auxiliary multipliers that remove bilinearities. Step 2 fixes the policy and gamma, finds an SOS multiplier, and solves a feasibility problem for a new h^(k) with C^(k-1) strictly inside C^(k) and C^(k) inside the safe set S. Theorem 3 states that if Step 1 succeeds at the first iteration, then at every later iteration before termination the triple (h^(l), gamma^(l), pi^(l)) is a genuine DTCBF-triple satisfying the barrier inequality and input admissibility on C^(l), and the only possible halt is condition (37e), which encodes that the zero-superlevel set can no longer be enlarged. The paper further claims that higher-degree polynomial DTCBFs can be synthesized in two ways: applying the product-replacement propositions repeatedly on a shifted nonnegative input, or first building a quadratic barrier and then running only the barrier-update step with the policy fixed.
Load-bearing premise
The whole procedure presupposes that the very first search for a control policy succeeds for the chosen initial barrier function; the paper states this success is not guaranteed, so the algorithm can fail to start even when a valid barrier exists.
Editorial extensions
If this is right
- Once the algorithm starts, it never needs to re-check safety: every intermediate pair (h^(l), pi^(l)) is certified, so the method can be stopped early and still yield a valid safety guarantee.
- The certified safe region grows monotonically from the initial conservative set, so the user can trade computation time against conservatism by choosing when to stop.
- Because each subproblem is an SOS feasibility program with linear decision variables, the overall method is a sequence of convex semidefinite programs and can be implemented with standard SOS toolboxes.
- Higher-degree barriers can be produced from a quadratic start without solving the hard bilinear problem again, by keeping the control policy fixed.
- A successful synthesis yields a DTCBF-triple that guarantees controlled invariance of its zero-superlevel set and safety for every initial state inside that set, so the barrier can serve directly as a safety filter or as a terminal ingredient in model predictive control.
Reading between the lines
- The admitted first-step feasibility gap points to the real design bottleneck: the method needs a valid starting barrier, and a natural extension is a preliminary SOS routine that searches for h^(0) as a small ellipsoidal Lyapunov-like set, or adaptively scales one from a stabilizing policy.
- Because the replacement technique only uses the quadratic structure of h and the polynomial structure of f and g, the same mechanism should transfer to discrete-time control Lyapunov functions and to non-polyhedral controlled invariant sets for polynomial systems, a problem the paper itself calls open.
- A sharper test of the method's conservatism would compare, on the cart-pole example, the terminal zero-superlevel set against the true maximal controlled invariant subset of the safe set; the paper only compares with a maximal polyhedral invariant set from a linear analysis.
- The fixed-policy higher-degree route suggests a cheap two-stage design: first enlarge with a quadratic barrier under tight input limits, then re-fit a higher-degree barrier for the same fixed policy; if the input set is tight this is likely to enlarge the safe set less aggressively than the full repeated-proposition route.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper addresses the synthesis of discrete-time control barrier functions (DTCBFs) and associated polynomial control policies for control-affine polynomial systems with polyhedral input constraints and semi-algebraic safe sets. The authors propose an alternating-descent SOS scheme for quadratic DTCBFs: after initializing a valid quadratic DTCBF, Step 1 fixes the barrier candidate and searches for a polynomial policy and γ via SOS constraints, introducing auxiliary polynomials eπ_{i,j} to replace bilinear products π_iπ_j, while Step 2 fixes the policy and enlarges the zero-superlevel set. Theorem 2 assembles sufficient SOS conditions from Propositions 1–3; Theorem 3 claims the iteration is lossless once the first Step 1 is feasible. Two extensions to higher-degree polynomial barrier functions are sketched, and numerical results are given for a linearized cart-pole system and a two-dimensional nonlinear system.
Significance. If correct, the proposed method would be a valuable contribution to DTCBF synthesis: it offers a computationally tractable SOS formulation that handles the bilinear term h(f(x)+g(x)π(x)) without restricting to affine barrier functions or set-valued policies, provides complete proofs for the quadratic case, and validates the approach against an independent maximal invariant set computation (MPT3) in the linear example. The losslessness argument in Theorem 3 is a useful feature, conditional on initial feasibility. However, the higher-degree extension is only sketched, and the hidden algebraic restrictions in Propositions 2–3 substantially weaken the claim that the relaxation is non-conservative and may cause Step 1 infeasibility in cases not exercised by the numerical examples.
major comments (3)
- [§5.1, Eqs. (24)–(31) and Eq. (19)] Propositions 2 and 3 together impose an unstated vanishing condition on the policy components. At any x in C^{(k-1)} with h^{(k-1)}(x)>0 and a^{(k-1)}_{i,j}(x)=0, constraints (24)–(27) imply 2 eπ_{i,j}(x) ≥ π_i(x)^2 + π_j(x)^2 plus nonnegative multiplier terms, while constraints (28)–(31) imply 2 eπ_{i,j}(x) ≤ -π_i(x)^2 - π_j(x)^2 minus nonnegative multiplier terms. Hence every feasible solution must satisfy π_i(x)=π_j(x)=0 at such x. Consequently, whenever a coefficient a_{i,j} changes sign on C^{(k-1)}, Step 1 (35) forces each pair of policy components to vanish on the algebraic set {x in C^{(k-1)} : a_{i,j}(x)=0}; the same phenomenon appears for the diagonal terms via Proposition 1 at zeros of a_{i,i}. This is a genuine algebraic restriction that is not stated in Theorem 2 or Remark 6. It also contradicts the sentence after (19) that condition (19) 'does not introduce conservatism since eπ_{i,j}(x) can be equal to π_i(x)π_j(x)': at a zero of a_{i,j}, even the exact choice eπ_{i,j}=π_iπ_j cannot satisfy the conjunction of (24)–(27) and (28)–(31) unless π_i and π_j vanish (or at least until (π_i−π_j)^2=0 and all multiplier terms vanish). Since for nonlinear systems with state-dependent g the coefficients a_{i,j}(x) generically change sign inside a nontrivial controlled invariant set, this hidden condition can make (35) infeasible even when a valid DTCBF-triple exists, providing a concrete mechanism behind the admitted non-guarantee in Remark 6. Please characterize this condition explicitly and assess its impact on the central synthesis claim.
- [§6.1] The extension to higher-degree polynomial DTCBFs is not proved. The text treats only the monomial µ_i^3 and states that 'all other bilinear terms can be handled in a similar manner,' but no general recursion is specified and no proof is given that the recursively introduced auxiliary polynomials eµ_{i,i}, eµ_{i,i,i}, ... preserve linearity of the SOS programs and maintain the required sign conditions for mixed monomials such as µ_i^2 µ_j. Since the abstract and Problem 1 explicitly claim higher-degree DTCBF synthesis, and Theorem 3's guarantee depends on the Step 1 formulation being correct at every degree, this is a load-bearing gap. The numerical example in Section 7.1 uses a degree-four barrier function, but the manuscript does not state whether Section 6.1 or Section 6.2 was used, nor how the quartic terms were encoded, so the demonstration does not fill the gap. Please provide a complete treatment for the general monomial case or clearly restrict the main claims to quadratic DTCBFs.
- [§5.2, Step 0 and Remark 6] The algorithm cannot start without a valid initial quadratic DTCBF h^{(0)}, and Remark 6 concedes that feasibility of (35) at k=1 is not guaranteed. The paper does not give a systematic procedure for constructing h^{(0)} or for certifying that Step 1 will be feasible. As a result, for a general polynomial system the proposed method is an iterative enlargement procedure from a user-supplied feasible certificate rather than a synthesis method in the sense of Problem 1. This limitation should be stated clearly at the outset, together with a concrete initialization strategy (for example, small ellipsoidal estimates around a stable equilibrium) and a discussion of when such a strategy can be certified.
minor comments (4)
- [§5.2, after Eq. (35)] The word 'admissibe' is a typo for 'admissible'; the manuscript should be proofread for similar mechanical errors.
- [Appendix B heading] The heading reads 'Apendix B' instead of 'Appendix B'.
- [Remark 4 and Eq. (37)] In the displayed feasibility problem (37), it is not immediately clear which variables are decision variables and which are fixed from the previous Step 1 solution; Remark 4 explains this verbally, but the display should list the fixed variables explicitly to avoid ambiguity.
- [Step 2 and termination] The termination condition says the algorithm stops when (37) is infeasible 'due to violation of (37e)', but the behavior for infeasibility caused by other constraints is not specified; please clarify whether such infeasibility is treated as failure or as another stopping criterion.
Circularity Check
No significant circularity: the DTCBF synthesis is a constructive SOS optimization procedure whose only input premise is an honestly admitted initial-feasibility assumption.
full rationale
The derivation chain is self-contained. The synthesized DTCBF triple (h, gamma, pi) is the decision-variable output of the SOS feasibility problems (35)-(37), not a quantity fitted to a target, and the algorithm's validity is established by imposing the DTCBF conditions as explicit constraints rather than by assuming the conclusion. The algorithm-specific premise is the existence of a valid initial DTCBF h^(0); the paper explicitly flags this in Remark 6: 'the feasibility of (35) at the first iteration (k = 1) is not generally guaranteed due to the conservatism introduced both by the supplementary conditions used to handle the bilinear terms and by the use of the generalized S-procedure lemma.' This is an honest initialization assumption, not a circular reduction. Theorem 3's monotone-enlargement claim is proved directly from the constraints (37b)-(37e) imposed in Step 2, so the enlargement C^(l-1) subset C^(l) is a constructed consequence, not a restatement of the input. The higher-degree extensions in Section 6 use the same propositions and do not import any uniqueness theorem or hidden ansatz from the authors' prior work; citation [21] is contextual (the conference version without proofs), and [15]/[22] are not load-bearing. The numerical section checks the result against the externally computed MPT3 maximal polyhedral controlled invariant set, giving an independent benchmark. The skeptical concern about zeros of a_{i,j} making (35) infeasible is a conservatism/feasibility critique of the sufficient SOS conditions, not a case of a conclusion being identical to its inputs; it is consistent with the paper's own admitted non-guarantee in Remark 6. I therefore find no circular step.
Assumptions & free parameters
free parameters (4)
- Initial DTCBF h^(0) (center and radius) =
-theta^2-omega^2+0.04 in cart-pole; -x1^2-x2^2+0.1 in nonlinear example
- Relaxation constants epsilon and delta =
chosen sufficiently small, not numerically specified
- Control shift c for higher-degree approach in Section 6.1 =
not specified; must be sufficiently large
- Polynomial degrees and SOS multiplier degrees =
h degree 4 and pi degree 3 in cart-pole; quadratic h and pi in nonlinear example; multiplier degrees not reported
assumptions (6)
- standard math Generalized S-procedure with SOS multipliers is valid (Lemma 1).
- domain assumption The system mappings f, g and the safe set mapping s are polynomials (Assumption 1).
- domain assumption The control admissible set U is polyhedral (Assumption 2), and for Section 6.1 additionally bounded.
- domain assumption A valid initial quadratic DTCBF h^(0) is available.
- standard math SOS constraints are used only in the sufficient direction.
- standard math The 2x2 matrix PSD characterization in Lemma 2 is applied pointwise and is preserved by the SOS matrix constraint.
Cite this review
Pith. "Pith review of Synthesis of Discrete-time Control Barrier Functions for Polynomial Systems Based on Sum-of-Squares Programming." pith.science (2026). https://pith.science/paper/4GF5TMAW
@misc{pith2026250419330,
author = {Pith},
title = {Pith review of: Synthesis of Discrete-time Control Barrier Functions for Polynomial Systems Based on Sum-of-Squares Programming},
year = {2026},
howpublished = {\url{https://pith.science/paper/4GF5TMAW}},
note = {Machine review of arXiv:2504.19330}
}
read the original abstract
Discrete-time Control Barrier Functions (DTCBFs) are commonly utilized in the literature as a powerful tool for synthesizing control policies that guarantee safety of discrete-time dynamical systems. However, the systematic synthesis of DTCBFs in a computationally efficient way is at present an important open problem. This article first proposes a novel alternating-descent approach based on Sum-of-Squares programming to synthesize quadratic DTCBFs and corresponding polynomial control policies for discrete-time control-affine polynomial systems with input constraints and semi-algebraic safe sets. Subsequently, two distinct approaches are introduced to extend the proposed method to the synthesis of higher-degree polynomial DTCBFs. To demonstrate its efficacy, we apply the proposed method to numerical case studies.
Figures
Reference graph
Works this paper leans on
-
[1]
A. Agrawal and K. Sreenath. Discrete control barrier functions for safety-critical control of discrete systems with application to bipedal robot navigation. In Robotics: Science and Systems , pages 1–10, 2017
work page 2017
-
[2]
A. D. Ames, S. Coogan, M. Egerstedt, G. Notomista, K. Sreenath, and P. Tabuada. Control barrier functions: Theory and applications. In 18th European Control Conference (ECC), pages 3420–3431, 2019
work page 2019
-
[3]
A. D. Ames, J. W. Grizzle, and P. Tabuada. Control barrier function based quadratic programs with application to adaptive cruise control. In 53rd IEEE Conference on Decision and Control (CDC) , pages 6271–6278, 2014
work page 2014
-
[4]
Y. Chen, M. Jankovic, M. Santillo, and A. D. Ames. Backup control barrier functions: Formulation and comparative study. In 60th IEEE Conference on Decision and Control (CDC), pages 6835–6841, 2021
work page 2021
-
[5]
A. Clark. A semi-algebraic framework for verification and synthesis of control barrier functions, 2022. arXiv preprint arXiv:2209.00081
arXiv 2022
-
[6]
R. W. Cottle, J.-S. Pang, and R. E. Stone. The Linear Complementarity Problem . Philadelphia: Society for Industrial and Applied Mathematics, 2009
work page 2009
- [7]
-
[8]
G. Delimpaltadakis, J. Cort´ es, and W.P.M.H. Heemels. Continuous approximations of projected dynamical systems via control barrier functions. IEEE Transactions on Automatic Control, 70(1):681–688, 2025
work page 2025
Show all 31 references
-
[9]
Freire and M
V. Freire and M. M. Nicotra. Systematic Design of Discrete- Time Control Barrier Functions Using Maximal Output Admissible Sets. IEEE Control Systems Letters, 7:1891–1896, 2023
2023
-
[10]
Freire and M
V. Freire and M. M. Nicotra. Building robust control barrier functions from robust maximal output admissible sets. In 63rd IEEE Conference on Decision and Control (CDC) , pages 8171–8177, 2024
2024
-
[11]
Gurriet, M
T. Gurriet, M. Mote, A. Singletary, P. Nilsson, E. Feron, and A. D. Ames. A scalable safety critical control framework for nonlinear systems. IEEE Access, 8:187249–187275, 2020
2020
-
[12]
Herceg, M
M. Herceg, M. Kvasnica, C.N. Jones, and M. Morari. Multi- parametric toolbox 3.0. In European Control Conference (ECC), pages 502–510, 2013
2013
-
[13]
Jagtap, S
P. Jagtap, S. Soudjani, and M. Zamani. Formal synthesis of stochastic systems via control barrier certificates. IEEE Transactions on Automatic Control , 66(7):3097–3110, 2021
2021
-
[14]
S. Kang, Y. Chen, H. Yang, and M. Pavone. Verification and synthesis of robust control barrier functions: Multilevel polynomial optimization and semidefinite relaxation. In 62nd IEEE Conference on Decision and Control (CDC) , pages 8215–8222, 2023
2023
-
[15]
Katriniok, E
A. Katriniok, E. Shakhesi, and W.P.M.H. Heemels. Discrete- time control barrier functions for guaranteed recursive feasibility in nonlinear MPC: An application to lane merging. In 62nd IEEE Conference on Decision and Control (CDC) , pages 3776–3783, 2023
2023
-
[16]
Lindemann, A
L. Lindemann, A. Robey, L. Jiang, S. Das, S. Tu, and N. Matni. Learning robust output control barrier functions from safe expert demonstrations. IEEE Open Journal of Control Systems, 3:158–172, 2024
2024
-
[17]
Papachristodoulou, J
A. Papachristodoulou, J. Anderson, G. Valmorbida, S. Prajna, P. Seiler, P. A. Parrilo, M. M. Peet, and D. Jagt. SOSTOOLS: Sum of squares optimization toolbox for MATLAB, 2021. arXiv preprint arXiv:1310.4716
2021 arXiv
-
[18]
Papachristodoulou and S
A. Papachristodoulou and S. Prajna. A tutorial on sum of squares techniques for systems analysis. In Proceedings of the American Control Conference, pages 2686–2700 vol. 4, 2005
2005
-
[19]
M. Putinar. Positive polynomials on compact semi-algebraic sets. Indiana University Mathematics Journal , 42(3):969– 984, 1993
1993
-
[20]
B. Reznick. Some concrete aspects of Hilbert’s 17th problem. Contemporary Mathematics, American Mathematical Society, 253:251–272, 2000
2000
-
[21]
Shakhesi, W.P.M.H
E. Shakhesi, W.P.M.H. Heemels, and A. Katriniok. Synthesis of quadratic discrete-time control barrier functions for polynomial systems based on sum-of-squares programming. Accepted in 13th IFAC Symposium on Nonlinear Control Systems. https://heemels.tue.nl/ assets/content/pape...
-
[22]
Shakhesi, W.P.M.H
E. Shakhesi, W.P.M.H. Heemels, and A. Katriniok. Optimization-based verification of discrete-time control barrier functions: A branch-and-bound approach. In 63rd IEEE Conference on Decision and Control (CDC) , pages 3632–3637, 2024
2024
-
[23]
H. Wang, K. Margellos, and A. Papachristodoulou. Assessing Safety for Control Systems Using Sum-of-Squares Programming, pages 207–234. Springer Nature Switzerland, Cham, 2023
2023
-
[24]
H. Wang, K. Margellos, and A. Papachristodoulou. Safety verification and controller synthesis for systems with input constraints. IF AC-PapersOnLine, 56(2):1698–1703, 2023. 22nd IFAC World Congress
2023
-
[25]
H. Wang, K. Margellos, A. Papachristodoulou, and C. De Persis. Convex co-design of control barrier function and safe feedback controller under input constraints, 2024. arXiv preprint arXiv:2403.11763
2024 arXiv
-
[26]
T. Wei, S. Kang, W. Zhao, and C. Liu. Persistently feasible robust safe control by safety index synthesis and convex semi- infinite programming. IEEE Control Systems Letters, 7:1213– 1218, 2023
2023
-
[27]
J. Wu, A. Clark, Y. Kantaros, and Y. Vorobeychik. Neural Lyapunov control for discrete-time systems. In Advances in Neural Information Processing Systems , volume 36, pages 2939–2955. Curran Associates, Inc., 2023
2023
-
[28]
Y. Yang, Y. Zhang, W. Zou, J. Chen, Y. Yin, and S. E. Li. Synthesizing control barrier functions with feasible region iteration for safe reinforcement learning. IEEE Transactions on Automatic Control , 69(4):2713–2720, 2024
2024
-
[29]
J. Zeng, Z. Li, and K. Sreenath. Enhancing feasibility and safety of nonlinear model predictive control with discrete- time control barrier functions. In 60th IEEE Conference on Decision and Control (CDC) , pages 6137–6144, 2021. 11
2021
-
[30]
J. Zeng, B. Zhang, and K. Sreenath. Safety-critical model predictive control with discrete-time control barrier function. In American Control Conference (ACC) , pages 3882–3889, 2021
2021
-
[31]
Zhang, Z
H. Zhang, Z. Li, H. Dai, and A. Clark. Efficient sum of squares-based verification and construction of control barrier functions by sampling on algebraic varieties. In 62nd IEEE Conference on Decision and Control (CDC) , pages 5384– 5391, 2023. A Proof of Proposition 1 By Lemm...
2023
Reviewed August 16, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.