REVIEW 1 major objections 4 minor 37 references
Synthesis of safety certificates for discrete-time uncertain systems via convex optimization
T0 review · 1 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash
Pith's one-line read This paper proves that a quadratic control barrier function and a linear feedback controller for a discrete-time linear system with additive disturbances can be co-designed by solving a single convex semidefinite program, guaranteeing…
desk verdict The deterministic co-design SDP is solid, but the finite-horizon theorem has a real trace-term LMI gap plus an initial-condition margin problem that invalidate the bound as stated for n>1. 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 central object is the quadratic control barrier function $b(x)=1-x^\top\Omega^{-1}x$ paired with the linear feedback gain $u(x)=Y\Omega^{-1}x$, where $\Omega\succ 0$ and $Y$ are the decision variables. The key identity is that the robust invariance condition $b(Ax+Bu(x)+Dw) \ge (1-\beta)b(x)$ for all $w^\top w \le 1$ can be rewritten as a linear matrix inequality in $(\Omega,Y)$ via the S-lemma, yielding constraint (8c). For the stochastic case, the expected-increase condition in (10) is encoded by the covariance LMI (14d) together with (14e)-(14f), and a shifted and scaled supermartingale $\zeta_t$ (constructed in Lemma 3.5) converts the one-step drift bound into a joint-in-time exit probability bound using Ville's inequality.
What would settle it
Run a scalar system $x_{t+1}=0.5x_t+u_t+w_t$ with a chosen safe set and initial ellipsoid, solve SDP (14), and draw $w_t$ from a zero-mean heavy-tailed distribution (e.g., a t-distribution with three degrees of freedom) scaled to have the same covariance $\Sigma$ as assumed. If the measured exit probability over $T=100$ steps exceeds the $\alpha$ predicted by Theorem 3.7 for a feasible SDP, the sub-Gaussian assumption is violated and the certificate fails. For the bounded-support case, set $w_t=1$ deterministically at every step starting from a boundary point of $B$; if the state exits $B$ in one step despite SDP (8) being feasible, the invariance certificate is refuted.
Extended reading notes
Core claim
The central claim is that the co-design of a CBF and a controller, which is generally nonconvex because the CBF appears inside the composition $b(Ax+Bu(x)+Dw)$, becomes convex when the CBF is quadratic and the controller is linear, after a change of variables that lifts the matrix inequalities. Specifically, Problem (8) is a convex SDP whose feasibility implies existence of a quadratic CBF and a linear feedback that render $B$ invariant for all disturbances $w^\top w \le 1$, with $I\subseteq B\subseteq S$ and $B$ being the largest-volume ellipsoid in this family achieving those properties. For the stochastic case, Problem (14) uses the same parametrization and adds a covariance LMI to enforce the expected-increase condition $\mathbb{E}[b(x_{t+1})\mid F_t] \ge (1-\beta)b(x_t)+\delta$; the paper proves that if it is feasible, then $\Pr(x_t\in S \text{ for all } t\in\{0,\ldots,T\}) \ge 1-\alpha$, with $\alpha$ given by an explicit formula depending on the horizon $T$, the initial ellipsoid parameter $\sigma$, and the chosen $\beta,\delta$. This gives a parameter-free derivation chain from the SDP to a rigorous safety certificate rather than a heuristic one.
Load-bearing premise
The certificates rest on the disturbance being i.i.d., zero-mean, sub-Gaussian with exactly the covariance $\Sigma$ used in the SDP, and on the initial state lying in a known ellipsoid; if the true noise violates these assumptions, the stated safety bounds are not certified.
Editorial extensions
If this is right
- The SDP replaces the standard alternating SOS co-design; no feasible initial CBF guess is required and the problem is convex, so a global solution is certified.
- The largest-volume invariant ellipsoid property (Theorem 3.3) gives a direct way to optimize the size of the safety set in one shot, without solving a reachability problem.
- For the stochastic case, the method returns an explicit joint-in-time exit probability bound that scales with the horizon $T$ and risk tolerance $\alpha$, letting designers trade off horizon versus safety in closed form.
- Input constraints, both polytopic and norm-bounded, can be added as extra LMIs without destroying convexity, and the same certificate can be used to build a safety filter solved in real time.
- Distributionally robust safety certificates can be obtained by replacing the covariance LMI with a Gelbrich-distance ambiguity set (Proposition 4.3), making the bound robust to misspecified covariances within a given radius.
Reading between the lines
- Because the parametrization is identical to the usual quadratic Lyapunov/controller pair, the same SDP could be recycled for performance objectives such as H2 or H-infinity control by adding LMIs, giving a combined safety-and-performance design.
- The martingale bound is a discrete-time analogue of continuous-time supermartingale exit estimates; one could adapt it to time-varying $\beta_t$ or position-dependent noise, at the cost of a more complex LMI.
- The explicit threshold $\alpha$ in Theorem 3.7 suggests a natural experiment: compare the predicted exit probability against Monte-Carlo counts in high-dimensional systems; the gap between bound and empirical frequency measures the conservatism of the quadratic CBF, not just the martingale step.
- For partially observed systems, one could combine the construction with a state estimator and use the same CBF on the estimated state; the paper does not treat output feedback, and the covariance LMI would need a correction term for estimation error.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes convex semidefinite programs for the joint synthesis of a quadratic control barrier function b(x)=1-x^T Omega^{-1}x and a linear feedback u=Y Omega^{-1}x for discrete-time linear systems with additive disturbances. Problem (8) is intended to certify infinite-horizon, worst-case safety under bounded disturbances, while Problem (14) is intended to certify finite-horizon, joint-in-time (1-alpha)-safety under i.i.d. sub-Gaussian noise using a martingale argument based on Ville's inequality. The paper also discusses input constraints, distributional ambiguity, safety filters, and SOS-based extensions to general semialgebraic safe sets. The main claims are Theorems 3.3 and 3.7, with the finite-horizon result being the principal contribution for unbounded noise.
Significance. If the stated results were correct, the paper would be a useful contribution: it offers an explicit convex SDP for co-designing a CBF and a feedback law, avoiding the usual bilinearities and alternating SOS schemes, and it provides a reasonably detailed derivation of the infinite-horizon invariance conditions. The distributionally robust extension and the safety-filter formulation are also natural and potentially valuable. However, the finite-horizon result is the advertised headline for unbounded disturbances, and that result is false as stated. The error is internal to the SDP encoding: Problem (14) does not enforce the scalar trace condition needed in the expected-increase inequality, and Theorem 3.7 is contradicted by a small feasible instance. Because the numerical example in Section 5 rests on this SDP, the central contribution cannot stand without a substantial redesign.
major comments (1)
- [Section 4.4, Algorithm 1] Algorithm 1 is described as having guaranteed convergence to a feasible CBF and controller, but no convergence proof or termination argument is provided. The initialization step (27) may not produce B subset of S, and the alternating iterations (28)--(29) are not shown to preserve feasibility or to converge. This does not affect the main theorems, but if the extension is to be claimed with a guarantee, the proof is missing.
minor comments (4)
- [Section 3.2, Theorem 3.7 statement] The statement of Theorem 3.7 should explicitly restate the hypotheses on the safe set S and the initial set I from Assumption 3.1, including the role of the vectors a_j and the scalar sigma; as written, the theorem refers to S and I without defining them in its own statement.
- [Section 4.3, Lemma 4.4] The proof of Lemma 4.4 is omitted with the comment that it follows directly from the definition of convexity; for a journal submission, the short proof should be included or a precise citation given.
- [Example 1, Eq. (11) and surrounding display] The formulas for a(t), kappa, and the cases delta<0 and delta>=0 are hard to follow because some symbols in the displayed derivation are garbled, and the relationship between the formulas for alpha_1 and alpha_2 and the later simplified bounds is not shown step by step. Please rewrite this part with consistent notation.
- [Notation] The symbol R is used both for a given matrix defining the initial ellipsoid and for the real numbers, and the appearance R^n in the same context can be confusing. This should be clarified in the notation subsection.
Circularity Check
No load-bearing circularity: the safety theorems are re-derived in the paper from the stated disturbance and set assumptions, and the only self-citation is not load-bearing.
full rationale
The derivation chain is self-contained. Problem (8) is shown in Appendix 6.1 to render the ellipsoid B invariant under bounded w directly from LMI (8c), with I⊆B⊆S enforced by (8d)-(8e); no target safety property is fed back into the constraints. Problem (14) is obtained by transcribing the expected-increase condition (10) into LMIs, and the finite-horizon bound in Theorem 3.7 follows from Ville's inequality via Lemma 3.5 and Proposition 3.6, using only the stated sub-Gaussian and covariance assumptions. No fitted parameter is later relabeled as a prediction, and no uniqueness or equivalence theorem is imported from the authors' prior work to force the choice of Ω and Y. The citation to the authors' own [34] supplies only the quadratic parameterization (5) and motivation; the containment and invariance proofs are carried out in the paper, so the self-citation is not load-bearing. A soundness concern exists in the proof of Theorem 3.7—the Schur complement of (14d) bounds Tr(Ω^{-1}Σ) only by nλ rather than λ, so (14e) may not enforce β−δ−Tr(Ω^{-1}Σ)≥0—but this is an internal LMI gap, not a circular reduction of the theorem to its inputs.
Assumptions & free parameters
free parameters (5)
- beta =
user-specified in (0,1)
- delta =
user-specified in (beta-1, beta]
- lambda =
user-specified in [0,1]
- sigma =
user-specified in (0,1)
- eta =
optimized analytically
assumptions (7)
- standard math S-Lemma (Lemma 1.3) and its use for quadratic and affine constraints
- standard math Ville's inequality (Lemma 1.2) for non-negative supermartingales
- standard math Schur complement and congruent transformations
- domain assumption Assumption 2.1: disturbances are i.i.d., zero-mean, sub-Gaussian with known covariance Sigma
- domain assumption Assumption 3.2: bounded support W = {w : w^T w <= 1}
- domain assumption Assumption 3.1: safe set is an intersection of half-planes a_j^T x + 1 >= 0 and initial set is an ellipsoid
- ad hoc to paper Quadratic CBF parametrization (5): b(x)=1-x^T Omega^{-1} x, u(x)=Y Omega^{-1} x
Cite this review
Pith. "Pith review of Synthesis of safety certificates for discrete-time uncertain systems via convex optimization." pith.science (2026). https://pith.science/paper/HPMMBWL4
@misc{pith2026250508559,
author = {Pith},
title = {Pith review of: Synthesis of safety certificates for discrete-time uncertain systems via convex optimization},
year = {2026},
howpublished = {\url{https://pith.science/paper/HPMMBWL4}},
note = {Machine review of arXiv:2505.08559}
}
read the original abstract
We study the problem of co-designing control barrier functions and linear state feedback controllers for discrete-time linear systems affected by additive disturbances. For disturbances of bounded magnitude, we provide a semi-definite program whose feasibility implies the existence of a control law and a certificate ensuring safety in the infinite horizon with respect to the worst-case disturbance realization in the uncertainty set. For disturbances with unbounded support, we rely on martingale theory to derive a second semi-definite program whose feasibility provides probabilistic safety guarantees holding joint-in-time over a finite time horizon. We examine several extensions, including (i) encoding of different types of input constraints, (ii) robustification against distributional ambiguity around the true distribution, (iii) design of safety filters, and (iv) extension to general safety specifications such as obstacle avoidance.
Figures
Reference graph
Works this paper leans on
-
[1]
Control barrier function based quadratic programs with applicatio n to adaptive cruise control
Aaron D Ames, Jessy W Grizzle, and Paulo Tabuada. Control barrier function based quadratic programs with applicatio n to adaptive cruise control. In 53rd IEEE Conference on Decision and Control , pages 6271–6278. IEEE, 2014
work page 2014
-
[2]
Infinite time reachability of state- space regions by using feedback control
Dimitri Bertsekas. Infinite time reachability of state- space regions by using feedback control. IEEE Transactions on Automatic Control, 17(5):604–613, 1972
work page 1972
-
[3]
End to end learning for self-driving c ars
Mariusz Bojarski. End to end learning for self-driving c ars. arXiv preprint arXiv:1604.07316 , 2016
arXiv 2016
-
[4]
A semi-algebraic framework for verificati on and synthesis of control barrier functions
Andrew Clark. A semi-algebraic framework for verificati on and synthesis of control barrier functions. arXiv preprint arXiv:2209.00081, 2022
arXiv 2022
-
[5]
Robust safety under stochastic uncertainty with discrete-time control barrier functions
Ryan K Cosner, Preston Culbertson, Andrew J Taylor, and Aaron D Ames. Robust safety under stochastic uncertainty with discrete-time control barrier functions. arXiv preprint arXiv:2302.07469, 2023
arXiv 2023
-
[6]
Charles Dawson, Sicun Gao, and Chuchu Fan. Safe control with learned certificates: A survey of neural lyapunov, barr ier, and contraction methods for robotics and control. IEEE Transactions on Robotics, 39(3):1749–1767, 2023
work page 2023
-
[7]
Penlab: A matlab solver for nonlinear semidefinite optimization
Jan Fiala, Michal Kočvara, and Michael Stingl. Penlab: A matlab solver for nonlinear semidefinite optimization. arXiv preprint arXiv:1311.5240, 2013
arXiv 2013
-
[8]
Formal synthesis of stochastic systems via control barrier certificates
Pushpak Jagtap, Sadegh Soudjani, and Majid Zamani. Formal synthesis of stochastic systems via control barrier certificates. IEEE Transactions on Automatic Control , 66(7):3097–3110, 2020
work page 2020
Show all 37 references
-
[9]
Fast and certifiable trajectory optimization
Shucheng Kang, Xiaoyang Xu, Jay Sarva, Ling Liang, and Heng Yang. Fast and certifiable trajectory optimization. arXiv preprint arXiv:2406.05846 , 2024
2024 arXiv
-
[10]
Convex computation of the maximum controlled invariant set for polynomial control systems
Milan Korda, Didier Henrion, and Colin N Jones. Convex computation of the maximum controlled invariant set for polynomial control systems. SIAM Journal on Control and Optimization, 52(5):2944–2969, 2014
2014
-
[11]
Stochastic stability and contr ol
Harold Joseph Kushner. Stochastic stability and contr ol. 1967
1967
-
[12]
Distributionally robust policy and lyapunov-certificate learning
Kehan Long, Jorge Cortes, and Nikolay Atanasov. Distributionally robust policy and lyapunov-certificate learning. arXiv preprint arXiv:2404.03017 , 2024
2024 arXiv
-
[13]
Hamilton–jacobi formulation for reach–avoid differential games
Kostas Margellos and John Lygeros. Hamilton–jacobi formulation for reach–avoid differential games. IEEE Transactions on automatic control , 56(8):1849–1861, 2011
2011
-
[14]
Procrustes metrics on covariance operators and optimal transportation of gaussian processes
Valentina Masarotto, Victor M Panaretos, and Yoav Zeme l. Procrustes metrics on covariance operators and optimal transportation of gaussian processes. Sankhya A, 81:172–213, 2019
2019
-
[15]
Safe value functions
Pierre-François Massiani, Steve Heim, Friedrich Solo wjow, and Sebastian Trimpe. Safe value functions. IEEE Transactions on Automatic Control , 68(5):2743–2757, 2022
2022
-
[16]
A time-dependent hamilton-jacobi formulation of reachabl e sets for continuous dynamic games
Ian M Mitchell, Alexandre M Bayen, and Claire J Tomlin. A time-dependent hamilton-jacobi formulation of reachabl e sets for continuous dynamic games. IEEE Transactions on automatic control, 50(7):947–957, 2005
2005
-
[17]
Mean-covariance robust risk measurement
Viet Anh Nguyen, Soroosh Shafiee, Damir Filipović, and Daniel Kuhn. Mean-covariance robust risk measurement. arXiv preprint arXiv:2112.09959 , 2021
2021
-
[18]
Semidefinite programming relaxations for semialgebraic problems
Pablo A Parrilo. Semidefinite programming relaxations for semialgebraic problems. Mathematical programming, 96:293– 320, 2003
2003
-
[19]
Barrier certificates for nonlinear mod el validation
Stephen Prajna. Barrier certificates for nonlinear mod el validation. Automatica, 42(1):117–126, 2006
2006
-
[20]
A framework for worst-case and stochastic safety verificatio n using barrier certificates
Stephen Prajna, Ali Jadbabaie, and George J Pappas. A framework for worst-case and stochastic safety verificatio n using barrier certificates. IEEE Transactions on Automatic Control, 52(8):1415–1428, 2007
2007
-
[21]
Application of reachab ility analysis for stochastic hybrid systems to aircraft conflict prediction
Maria Prandini and Jianghai Hu. Application of reachab ility analysis for stochastic hybrid systems to aircraft conflict prediction. In 2008 47th IEEE conference on decision and control, pages 4036–4041. IEEE, 2008
2008
-
[22]
Dynamic walking: Toward agile and efficient bipedal robots
Jenna Reher and Aaron D Ames. Dynamic walking: Toward agile and efficient bipedal robots. Annual Review of Control, Robotics, and Autonomous Systems , 4:535–572, 2021
2021
-
[23]
Learning control barrier functions from expert demonstrations
Alexander Robey, Haimin Hu, Lars Lindemann, Hanwen Zhang, Dimos V Dimarogonas, Stephen Tu, and Nikolai Matni. Learning control barrier functions from expert demonstrations. In 2020 59th IEEE Conference on Decision and Control (CDC) , pages 3717–3724. IEEE, 2020
2020
-
[24]
Variational analysis, volume 317
R Tyrrell Rockafellar and Roger J-B W ets. Variational analysis, volume 317. Springer Science & Business Media, 2009
2009
-
[25]
Advanced safety filter based on sos control barrier and lyapunov functions
Michael Schneeberger, Silvia Mastellone, and Florian Dörfler. Advanced safety filter based on sos control barrier and lyapunov functions. arXiv preprint arXiv:2401.06901 , 2024. 12
2024
-
[26]
Safe control for nonlinear systems with stochastic uncertainty via risk control barrier functions
Andrew Singletary, Mohamadreza Ahmadi, and Aaron D Ames. Safe control for nonlinear systems with stochastic uncertainty via risk control barrier functions. IEEE Control Systems Letters , 7:349–354, 2022
2022
-
[27]
Synthesis of control barrier functions usi ng a supervised machine learning approach
Mohit Srinivasan, Amogh Dabholkar, Samuel Coogan, and Patricio A Vela. Synthesis of control barrier functions usi ng a supervised machine learning approach. In 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 7139–7145. IEEE, 2020
2020
-
[28]
Searching for control lyapunov functions using sums of squares programming
W eehong Tan and Andrew Packard. Searching for control lyapunov functions using sums of squares programming. sibi, 1(1), 2004
2004
-
[29]
Safety of sampled- data systems with control barrier functions via approximat e discrete time models
Andrew J Taylor, Victor D Dorobantu, Ryan K Cosner, Yisong Yue, and Aaron D Ames. Safety of sampled- data systems with control barrier functions via approximat e discrete time models. In 2022 IEEE 61st Conference on Decision and Control (CDC) , pages 7127–7134. IEEE, 2022
2022
-
[30]
Etude critique de la notion de collectif
Jean Ville. Etude critique de la notion de collectif . Gauthier- Villars Paris, 1939
1939
-
[31]
Predictive con trol barrier functions: Enhanced safety mechanisms for learnin g- based control
Kim P W abersich and Melanie N Zeilinger. Predictive con trol barrier functions: Enhanced safety mechanisms for learnin g- based control. IEEE Transactions on Automatic Control , 68(5):2638–2651, 2022
2022
-
[32]
Assessing safety for contr ol systems using sum-of-squares programming, 2023
Han W ang, Kostas Margellos, and Antonis Papachristodoulou. Assessing safety for contr ol systems using sum-of-squares programming, 2023
2023
-
[33]
Safety verification and controller synthesis for systems with inpu t constraints
Han W ang, Kostas Margellos, and Antonis Papachristodoulou. Safety verification and controller synthesis for systems with inpu t constraints. IF AC-PapersOnLine, 56(2):1698–1703, 2023
2023
-
[34]
Convex co-design of control barrier function and safe feedback controller under input constrai nts
Han W ang, Kostas Margellos, Antonis Papachristodoulo u, and Claudio De Persis. Convex co-design of control barrier function and safe feedback controller under input constrai nts. arXiv preprint arXiv:2403.11763 , 2024
2024 arXiv
-
[35]
Simultaneous synthesis and verification of neural control barrier functions through branch-and-bound verification-in-the-loop training
Xinyu W ang, Luzia Knoedler, Frederik Baymler Mathiese n, and Javier Alonso-Mora. Simultaneous synthesis and verification of neural control barrier functions through branch-and-bound verification-in-the-loop training. In 2024 European Control Conference (ECC) , pages 571–578. IEEE, 2024
2024
-
[36]
Synthesizing control barrier functions with feasible region iteration for safe reinforcement learning
Yujie Yang, Yuhang Zhang, W enjun Zou, Jianyu Chen, Yuming Yin, and Shengbo Eben Li. Synthesizing control barrier functions with feasible region iteration for safe reinforcement learning. IEEE Transactions on Automatic Control, 2023
2023
-
[37]
Convex synthesis of control barrier functions under input constraints
Pan Zhao, Reza Ghabcheloo, Yikun Cheng, Hossein Abdi, and Naira Hovakimyan. Convex synthesis of control barrier functions under input constraints. IEEE Control Systems Letters, 2023. Appendix A: Proofs of Section 3 6.1 Proof of Theorem 3.3 We first prove that (8c) is sufficient f...
2023
Reviewed August 15, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.