REVIEW 1 major objections 5 minor 48 references
Robust Optimal Control of Arbitrarily Switched Systems: A Path-Complete Framework
T0 review · 1 major / 5 minor · reviewed 2026-08-02 · deepseek-v4-flash
Pith's one-line read Graph-based Bellman inequalities over path-complete graphs produce certified worst-case cost bounds and policies for arbitrarily switched systems.
desk verdict Theorem 1 is sound and the reachability-graph min–max construction is a real extension, but the general-graph synthesis story is conditional on an initialization heuristic with no proven feasibility or convergence conditions. 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 load-bearing construction is a path-complete graph G=(S,E), a directed labeled graph in which every finite mode sequence is realized as a path, together with one of its reachability graphs H=(S_H,E_H), whose nodes are subsets of S and which is complete for every mode. Local quadratic functions V_alpha and linear policies pi_A are required to satisfy graph-based Bellman inequalities along edges; the reachability property ensures that whatever node set A is active, every mode i has an outgoing edge to some B whose every element is reachable from some element of A. The min-max combination V(x)=min_A max_{alpha in A} V_alpha(x), with policy pi_{A*(x)}, turns these local inequalities into the
What would settle it
On a small two-mode switched linear system with quadratic cost, compute the certificate from equation (5) by solving the matrix inequalities (13) for a complete path-complete graph of order 2, then simulate the resulting piecewise-linear policy under all mode sequences up to 20 steps from a fixed x0. If the finite-horizon empirical worst-case cost ever exceeds V(x0), the graph-based Bellman inequalities cannot have been satisfied and the certification claim would be refuted.
Extended reading notes
Core claim
The paper proves that if functions on the nodes of a path-complete graph and policies on the nodes of a reachability graph satisfy graph-based Bellman inequalities, then the pointwise min-max function V(x)=min_A max_{alpha in A} V_alpha(x), together with the policy phi(x)=pi_{A*(x)}(x), satisfies the robust Bellman inequality. Consequently V is a certified upper bound on the closed-loop value function of phi and hence also on the optimal value function J*. In the LQR setting these conditions become matrix inequalities; complete graphs give a single semidefinite program, while general path-complete graphs are handled by alternating optimization. Numerical results on a building temperature reg
Load-bearing premise
The practical pipeline assumes an initial stabilizing controller with a contraction factor below one can be found; for switched systems where no such stabilizing controller exists, the alternating optimization cannot be initialized.
Editorial extensions
If this is right
- If the graph-based inequalities are feasible, the theorem delivers both a policy and a certified upper bound on its worst-case cost, so no separate verification step is needed.
- For complete graphs the whole synthesis reduces to one semidefinite program; for general path-complete graphs, alternating optimization over the matrices P and the feedback gains K provides a tractable route.
- Because the certified function satisfies the robust Bellman inequality, it can be appended as a terminal cost in robust MPC; in the reported benchmark this lowered the horizon-5 MPC average cost from about 1487 to 1197.
- Co-complete graph structures can outperform complete ones on the same benchmark, showing that moving beyond complete graphs is practically relevant, not just a theoretical generalization.
- The construction recovers earlier complete- and co-complete-graph results as special cases and extends them to controlled switched systems with inputs.
Reading between the lines
- Extension: the gap between the certified V(x0) and the best empirical closed-loop cost can be read as a measure of how much information the graph's memory encodes about adversarial mode sequences; larger graphs should shrink it, and the paper's future-work note points in the same direction.
- Extension: since V is pointwise evaluable and non-differentiable only at switching boundaries, it could serve as a candidate for safety-barrier or control-Lyapunov reuse, not just as a cost certificate.
- Extension: the same graph-based relaxation idea should transfer to continuous-state robust Markov decision processes, replacing the expectation operator with the robust worst-case operator; a natural test is a continuous-state inventory or queueing problem with adversarial demand.
- Extension: a practical refinement is to warm-start Algorithm 1 with a certificate from a coarser graph and then progressively refine the graph structure, which could cut the offline synthesis times reported at higher graph orders.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper develops a path-complete graph framework for joint synthesis of feedback policies and certified upper bounds on the infinite-horizon worst-case value function for arbitrarily switched systems. Functions attached to graph nodes and policies attached to nodes of a reachability graph are constrained by graph-based Bellman inequalities (3). The main theorem (Theorem 1) asserts that the pointwise min-max combination V(x)=min_A max_{α∈A} V_α(x) is a certified upper bound on the closed-loop value function of the policy φ(x)=π_{A*(x)}(x), and hence on the optimal value function. Complete and co-complete graphs are recovered as corollaries. For linear switched systems with quadratic stage costs, the inequalities become matrix inequalities; complete graphs yield a single SDP (17)-(18), while general path-complete graphs are treated by alternating optimization (Algorithm 1) initialized by a stabilization heuristic (Appendix A). Numerical experiments compare the proposed controllers with robust MPC on a synthetic example and a three-zone building temperature regulation benchmark, including the use of the certified bound as an MPC terminal cost.
Significance. The theoretical result is significant and, as far as I can verify, correct. Theorem 1 provides a genuine extension of path-complete Lyapunov methods to certified performance bounds with explicit policy synthesis, and the reachability-graph construction is elegant. The LMI formulation for complete graphs is useful, and the terminal-cost application to robust MPC is a nice demonstration. The paper also releases code for reproduction. The main weakness is computational: Algorithm 1's initialization is a heuristic without proven feasibility or convergence, so the claim that general path-complete graphs are 'handled' is conditional. This is fixable and does not undermine the core theory.
major comments (1)
- [§5.1/Appendix A (Algorithm 1, line 2; Eq. (19))] Algorithm 1 requires an initial feasible solution to (13). Appendix A proposes to find one by alternating optimization on (19) seeking a contraction factor γ<1, but it gives no conditions under which such a solution exists, no guidance for choosing the starting positive definite matrices, and no convergence guarantee for the alternation. For a switched linear system that is not switched-stabilizable, or for a graph G that admits no stabilizing assignment of the prescribed form, no such γ<1 exists and the procedure cannot initialize; for stabilizable systems the heuristic can still fail on a given graph. Thus the paper does not delimit the class of systems/graphs for which the general path-complete synthesis in Algorithm 1 is guaranteed to run. The authors should either prove sufficient conditions for the existence of the initial feasible point (e.g., existence of a stabilizing path-compl
minor comments (5)
- [Definition 5 / Theorem 1] The nodes of a reachability graph are subsets of S, but nonemptiness is not stated. If an empty set were allowed, the expressions max_{α∈A}V_α(x), argmin, and the proof would be undefined. Please add an explicit nonemptiness requirement for all A∈S_H.
- [Proof of Theorem 1] After applying (3) to (α*, β*, i), the proof jumps from V(x) ≥ c(x,π_A(x)) + max_{β∈B}V_β(f_i(x,π_A(x))) to V(x) ≥ c(x,φ(x)) + V(f_i(x,φ(x))). The missing intermediate step is V(f_i(x,φ(x))) ≤ max_{β∈B}V_β(f_i(x,φ(x))), which follows from (5) because B is one of the sets in the min. Adding this sentence would make the proof fully explicit.
- [Section 6, Table 1] The empirical costs J^avg_T are averages over 50 Monte Carlo runs, but no standard deviations, confidence intervals, or per-trial spread are reported. Since the qualitative claims (e.g., 'nearly identical costs', 'improved performance') rely on these averages, please add error bars or a variance measure.
- [Remark 1] The statement that any graph admitting a reachability graph is path-complete is asserted with the proof omitted. This is not used later, so it is not load-bearing, but in a journal version the proof should be supplied or a reference given.
- [Section 6, building benchmark] The building model matrices are delegated to [44] rather than stated. For reproducibility, include the numerical A_i,B_i matrices (or an appendix) or make clear that they are fully specified in the accompanying code repository.
Circularity Check
No significant circularity: Theorem 1's certification argument is self-contained; only minor non-load-bearing self-citations to the authors' prior work appear.
full rationale
The central derivation is not circular. Theorem 1 assumes graph-based Bellman inequalities (3) and constructs V and phi from the same V_alpha and pi_A; the proof then shows, using only the completeness of the reachability graph and condition (ii) of Definition 5, that (2) holds at every x. Proposition 2, which converts (2) into the bound V >= J^phi, is proved in the paper by a telescoping-sum argument and does not presuppose the theorem's conclusion. No parameter is fitted to observed costs or to J^phi; the synthesis minimizes trace(P) or gamma on the bound itself, and the reported V(x0) is a certified upper bound, not a prediction fitted to data. Self-citations to [33] occur only for Proposition 2 (whose proof is included) and for the standard Schur-complement LMI reformulation (17), and [3,17] are cited as prior constructions rather than as the load-bearing justification of Theorem 1. No uniqueness theorem is imported from the authors' own work, and no ansatz is smuggled via citation: the quadratic template and piecewise-linear policies are explicit modeling choices. The initialization feasibility concern in Appendix A is a real algorithmic gap but is a correctness/completeness issue, not a circularity: it does not make the certified bound equivalent to its inputs. Overall, the paper's main claim has independent content and is not forced by definition or by a self-citation chain.
Assumptions & free parameters
assumptions (4)
- domain assumption The stage cost c is nonnegative (c: R^n x R^m -> R_{\ge0})
- domain assumption The switching signal is fully adversarial: value function is the supremum over all mode sequences
- standard math Schur complement equivalences for LMI reformulations
- domain assumption Existence of an initial feasible solution to (13) in Algorithm 1
Cite this review
Pith. "Pith review of Robust Optimal Control of Arbitrarily Switched Systems: A Path-Complete Framework." pith.science (2026). https://pith.science/paper/E2TJAUKH
@misc{pith2026260715055,
author = {Pith},
title = {Pith review of: Robust Optimal Control of Arbitrarily Switched Systems: A Path-Complete Framework},
year = {2026},
howpublished = {\url{https://pith.science/paper/E2TJAUKH}},
note = {Machine review of arXiv:2607.15055}
}
read the original abstract
This paper addresses the robust control of switched systems under arbitrary switching with performance guarantees. We propose a framework that jointly synthesizes a feedback policy and a certified upper bound on its corresponding infinite-horizon closed-loop value function. The proposed upper bound not only certifies the performance of the synthesized policy, but can also be optimized during controller synthesis. More precisely, our approach associates functions with the nodes of a path-complete graph and enforces graph-based Bellman inequalities along its edges. Exploiting a newly introduced notion of reachability graph, these functions are combined into both a feedback policy and a certified upper bound on its corresponding closed-loop value function, expressed as a pointwise min-max combination of the graph-indexed functions. For linear switched systems with quadratic stage costs, the proposed framework admits tractable computational formulations based on semidefinite programming and alternating optimization. Numerical experiments, including a building temperature regulation benchmark, demonstrate the practical usefulness of the proposed approach both for direct feedback control using the synthesized policy and for model predictive control using the certified upper bound as a terminal cost.
Figures
Figures from the paper (5 more)
Reference graph
Works this paper leans on
-
[44]
Z. Wang, G. O. Berger, and R. M. Jungers. Data-driven control of unknown switched linear systems using scenario optimization.IEEE Transactions on Automatic Control, 69(11):7310–7325, 2024
2024
-
[33]
Ninite, A
L. Ninite, A. Banse, G. O. Berger, and R. M. Jungers. A path-complete approach for optimal control of switched systems. InProceedings of the 29th International Conference on Hybrid Systems: Computation and Control, 2026
2026
-
[1]
Jointspectralradiusandpath-complete graph lyapunov functions.SIAM Journal on Control and Optimization, 52(1):687–717, 2014
A.A.Ahmadi, R.M.Jungers, P.A.Parrilo, andM.Roozbehani. Jointspectralradiusandpath-complete graph lyapunov functions.SIAM Journal on Control and Optimization, 52(1):687–717, 2014
2014
-
[2]
M. Alamir. Learning against uncertainty in control engineering.Annual Reviews in Control, 53:19–29, 2022
2022
-
[3]
Angeli, N
D. Angeli, N. Athanasopoulos, R. M. Jungers, and M. Philippe. Path-complete graphs and common lya- punov functions. InProceedings of the 20th International Conference on Hybrid Systems: Computation and Control, HSCC ’17, page 81–90, New York, NY, USA, 2017. Association for Computing Machinery
2017
-
[4]
Baier and J.-P
C. Baier and J.-P. Katoen.Principles Of Model Checking. MIT Press, 2008
2008
-
[5]
Baier, P
R. Baier, P. Braun, L. Grüne, and C. M. Kellett. Numerical calculation of nonsmooth control lyapunov functions via piecewise affine approximation∗∗p. braun, l. grüne and c. m. kellett are supported by the australian research council (grant number: Arc-dp160102138).IFAC-PapersOnLine, 52(16):370–375,
-
[6]
Belta, B
C. Belta, B. Yordanov, and E. A. Gol.Formal Methods for Discrete-Time Dynamical Systems, volume 89 ofStudies in Systems, Decision and Control. Springer
Show all 48 references
-
[7]
Bemporad and M
A. Bemporad and M. Morari. Robust model predictive control: A survey. In A. Garulli and A. Tesi, editors,Robustness in identification and control, pages 207–226, London, 1999. Springer London
1999
-
[8]
G. O. Berger. On the differentiability of the value function of switched linear systems under arbitrary and controlled switching.arXiv preprint arXiv:2511.20037, 2025
2025 arXiv
-
[9]
Bertsekas.Dynamic programming and optimal control: Volume I, volume 4
D. Bertsekas.Dynamic programming and optimal control: Volume I, volume 4. Athena scientific, 2012
2012
-
[10]
Blanchini
F. Blanchini. Nonquadratic lyapunov functions for robust control.Automatica, 31(3):451–461, 1995
1995
-
[11]
Blanchini, D
F. Blanchini, D. Casagrande, P. Gardonio, and S. Miani. Constant and switching gains in semi-active damping of vibrating structures.International Journal of Control, 85(12):1886–1897, 2012
2012
-
[12]
Blanchini, S
F. Blanchini, S. Miani, et al.Set-theoretic methods in control, volume 78. Springer, 2008
2008
-
[13]
Calbert, B
J. Calbert, B. Legat, L. N. Egidio, and R. Jungers. Alternating simulation on hierarchical abstractions. In2021 60th IEEE Conference on Decision and Control (CDC), pages 593–598, 2021
2021
-
[14]
Chang, N
Y.-C. Chang, N. Roohi, and S. Gao. Neural lyapunov control. In H. Wallach, H. Larochelle, A. Beygelz- imer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors,Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019
2019
-
[15]
N. G. De Bruijn and P. Erdös. On a combinatorial problem.Proceedings of the Section of Sciences of the Koninklijke Nederlandse Akademie van Wetenschappen te Amsterdam, 51(10):1277–1279, 1948
1948
-
[16]
de Oliveira, J
M. de Oliveira, J. Bernussou, and J. Geromel. A new discrete-time robust stability condition.Systems & Control Letters, 37(4):261–265, 1999
1999
-
[17]
Della Rossa, T
M. Della Rossa, T. Alves Lima, M. Jungers, and R. M. Jungers. Graph-based conditions for feedback stabilization of switched and lpv systems.Automatica, 160:111427, 2024
2024
-
[18]
Della Rossa and R
M. Della Rossa and R. M. Jungers. Multiple lyapunov functions and memory: A symbolic dynamics approach to systems and control.SIAM Journal on Control and Optimization, 62(5):2695–2722, 2024
2024
-
[19]
Donkers, W
M. Donkers, W. M. H. Heemels, N. Van de Wouw, and L. Hetel. Stability analysis of networked control systems using a switched linear systems approach.IEEE Transactions on Automatic control, 56(9):2101–2115, 2011. 18
2011
-
[20]
Fujita, T
T. Fujita, T. Ueno, and S. Iwamoto. A nondeterministic dynamic programming model. InInternational Conference on Knowledge-Based and Intelligent Information and Engineering Systems, pages1208–1214. Springer, 2004
2004
-
[21]
Görges, M
D. Görges, M. Izák, and S. Liu. Optimal control and scheduling of switched systems.IEEE Transactions on Automatic Control, 56(1):135–140, 2011
2011
-
[22]
E. A. Hernandez-Vargas, R. H. Middleton, and P. Colaneri. Optimal and mpc switching strategies for mitigating viral mutation and escape.IFAC Proceedings Volumes, 44(1):14857–14862, 2011
2011
-
[23]
G. N. Iyengar. Robust dynamic programming.Mathematics of Operations Research, 30(2):257–280, 2005
2005
-
[24]
Jungers.The joint spectral radius: theory and applications, volume 385
R. Jungers.The joint spectral radius: theory and applications, volume 385. Springer Science & Business Media, 2009
2009
-
[25]
E. A. Lee and S. A. Seshia.Introduction to Embedded Systems A Cyber-Physical Systems Approach. MIT Press, 2016
2016
-
[26]
Liberzon.Switching in systems and control, volume 190
D. Liberzon.Switching in systems and control, volume 190. Springer, 2003
2003
-
[27]
T. A. Lima, M. Della Rossa, and A. Girard. Feedback stabilization of switched systems under arbitrary switching: A convex characterization.arXiv preprint arXiv:2506.03759, 2025
2025 arXiv
-
[28]
Lincoln and A
B. Lincoln and A. Rantzer. Relaxing dynamic programming.IEEE Transactions on Automatic Control, 51(8):1249–1260, 2006
2006
-
[29]
F. Lu, P. G. Mehta, S. P. Meyn, and G. Neu. Convex q-learning. In2021 American Control Conference (ACC), pages 4749–4756. IEEE, 2021
2021
-
[30]
V. L. Mehrmann.The autonomous linear quadratic control problem: theory and numerical solution. Springer, 1991
1991
-
[31]
Mitra.Verifying Cyber-Physical Systems: A Path to Safe Autonomy
S. Mitra.Verifying Cyber-Physical Systems: A Path to Safe Autonomy. MIT Press, 2021
2021
-
[32]
Nilim and L
A. Nilim and L. E. Ghaoui. Robust control of markov decision processes with uncertain transition matrices.Operations Research, 53(5):780–798, 2005
2005
-
[34]
Pairet, J
E. Pairet, J. D. Hernandez, M. Carreras, Y. Petillot, and M. Lahijanian. Online mapping and mo- tion planning under uncertainty for safe navigation in unknown environments.IEEE Transactions on Automation Science and Engineering, 19(4):3356–3378, Oct. 2022
2022
-
[35]
P. A. Parrilo. Semidefinite programming relaxations for semialgebraic problems.Mathematical Pro- gramming, Series B, 96, 2003
2003
-
[36]
Prajna and A
S. Prajna and A. Jadbabaie. Safety verification of hybrid systems using barrier certificates. In R. Alur and G. J. Pappas, editors,Hybrid Systems: Computation and Control, pages 477–492, Berlin, Heidel- berg, 2004. Springer Berlin Heidelberg
2004
-
[37]
Prajna, A
S. Prajna, A. Jadbabaie, and G. J. Pappas. A framework for worst-case and stochastic safety verification using barrier certificates.IEEE Transactions on Automatic Control, 52(8):1415–1428, 2007
2007
-
[38]
A. Rantzer. On approximate dynamic programming in switching systems. InProceedings of the 44th IEEE Conference on Decision and Control, pages 1391–1396. IEEE, 2005. 19
2005
-
[39]
J. B. Rawlings, D. Q. Mayne, and M. M. Diehl.Model Predictive Control Theory, Computation, and Design, 2nd Edition. Nob Hill Publishing, LLC
-
[40]
C. A. Sanchez, G. Garcia, S. Hadjeras, W. M. H. Heemels, and L. Zaccarian. Practical stabiliza- tion of switched affine systems with dwell-time guarantees.IEEE Transactions on Automatic Control, 64(11):4811–4817, 2019
2019
-
[41]
Suilen, T
M. Suilen, T. Badings, E. M. Bovy, D. Parker, and N. Jansen. Robust markov decision processes: A place where ai and formal methods meet. InPrinciples of Verification: Cycling the Probabilistic Landscape: Essays Dedicated to Joost-Pieter Katoen on the Occasion of His 60th Birth...
2024
-
[42]
Sun and S
Z. Sun and S. S. Ge. Stability theory of switched dynamical systems. 2011
2011
-
[43]
Tabuada.Verification and Control of Hybrid Systems: A Symbolic Approach
P. Tabuada.Verification and Control of Hybrid Systems: A Symbolic Approach. Springer US, 2009
2009
-
[45]
Wu and Q
Z. Wu and Q. He. Optimal switching sequence for switched linear systems.SIAM Journal on Control and Optimization, 58(2):1183–1206, 2020
2020
-
[46]
Zhang, J
W. Zhang, J. Hu, and A. Abate. On the value functions of the discrete-time switched lqr problem. IEEE Transactions on Automatic Control, 54(11):2669–2674, 2009
2009
-
[47]
Zhang, J
W. Zhang, J. Hu, and A. Abate. Infinite-horizon switched lqr problems in discrete time: A suboptimal algorithm with performance analysis.IEEE Transactions on Automatic Control, 57(7):1815–1821, 2012. A Initialization of Algorithm 1 The alternating optimization procedure descri...
2012
-
[2019]
11th IFAC Symposium on Nonlinear Control Systems NOLCOS 2019
2019
Reviewed August 2, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.