Many networks we would like to steer, such as gene circuits, leader-follower robot swarms and opinion networks, cannot be pushed to an arbitrary target state. The inputs touch only a few nodes, so some directions of the state can never be influenced. Even so, these networks can often be herded: pushed until every node sits above a safety threshold, for example every expression level positive or every agent past a line. Separately, long-horizon economic optimal control has a well-understood regularity called the turnpike. Whatever the start and end points, optimal trajectories rush to one best steady state, stay there for most of the horizon, and leave only at the end. The turnpike is explained by strict dissipativity, an energy-like inequality saying that time spent away from the best steady state always costs extra. The trouble is that every turnpike theorem we have assumes the controller can reach that steady state exactly, and that assumption is precisely what herdable networks lack.
This note proposes a theory of turnpikes and strict dissipativity relative to a set of steady states rather than a point, built for systems that are herdable but not controllable. The theory is paired with graph-structured storage certificates that scale to sparse networks. The practical payoff is twofold: stability guarantees for short-horizon economic model predictive control on under-actuated networks, and a sharper notion of herdability. Classical herdability asks only whether the threshold can be crossed once. We ask whether it can be crossed and then cheaply held.
Core Claim
Take a linear network $\dot x = Ax + Bu$, split by the standard Kalman decomposition into a part $z_c$ that the inputs can move and a part $z_u$ that evolves on its own as $\dot z_u = A_u z_u$. A herdable system can have $z_u \neq 0$: it is herdable when the range of the controllability matrix $[B \mid AB \mid \dots \mid A^{n-1}B]$ contains a strictly positive vector, which is weaker than full rank. In such a system the set of reachable steady states is not a point. It is a family $\mathcal{S}(z_u)$ indexed by the uncontrollable component.
Our first claim concerns systems with an economic stage cost $l(x,u)$ and a threshold constraint $x \ge h$. When $A_u$ has only neutral modes (eigenvalues on the imaginary axis), as is common with conserved quantities and symmetric leader placements, the right object is a dissipation inequality relative to the set:
$$\lambda(x(t_2)) - \lambda(x(t_1)) \le \int_{t_1}^{t_2} \Big( l(x,u) - l^\star(z_u) - \alpha\big(\mathrm{dist}(x, \mathcal{S}^\star(z_u))\big) \Big)\, dt .$$
Here $\lambda$ is a storage function, $l^\star(z_u)$ is the best steady-state cost compatible with the frozen uncontrollable component, $\mathcal{S}^\star(z_u)$ is the set of minimizers, and $\alpha$ is a positive definite penalty on the distance to that set. We claim this inequality holds, and yields a set turnpike, under a condition we call sustainable herdability. That condition asks for a steady state $(x_s,u_s)$ with $Ax_s+Bu_s=0$, $x_s \ge h$ and $x_s$ in the affine slice fixed by $z_u$. It strictly separates two classes of systems. Some can be herded above $h$ only transiently, because an unstable uncontrollable mode eventually drags nodes back below the threshold. Others can be held there indefinitely. Once $l$ and the constraint $x \ge h$ are fixed, the minimizer set $\mathcal{S}^\star(z_u)$ is typically a single point within each slice. The genuinely set-valued part of the turnpike therefore comes from $z_u$, while the threshold coupling decides whether a slice has any feasible steady state at all.
Our second claim concerns structure. For the graph classes where herdability is decided by sign patterns alone, namely trees with unisigned layers and clustering-balanced or structurally balanced leader-follower graphs, a valid storage function can be built node by node. It takes the form $\lambda(x) = \sum_i \lambda_i(x_i)$, with linear terms obtained by passing steady-state Lagrange multipliers from the leaders down the layers. No large sum-of-squares program is needed.
Relation to Prior Work
The dissipativity side supplies the method and also the obstacle. On turnpike and dissipativity properties of continuous-time optimal control problems proves that strict dissipativity, optimal steady-state operation and turnpikes are equivalent, but only under exponential reachability of a single steady state. It also certifies storage functions by sum-of-squares programming on a small reactor model. Additional material to the paper "On necessity and robustness of dissipativity in economic model predictive control" proves that local controllability at the optimal steady state is necessary for strict dissipativity in economic model predictive control. On its face this rules out what we propose, so we address it directly. We read the result as forbidding point-wise dissipativity in uncontrollable directions, not dissipativity measured as distance to a set, and our construction asks for controllability only inside each slice $z_u = \text{const}$. Part of the work is to prove this reading holds and to find where it breaks.
Integral and measure-turnpike properties for infinite-dimensional optimal control systems shows that steady-state Lagrange multipliers give the storage function. We reuse that idea, slice by slice, as the source of the linear storage terms. The mean-field turnpike papers, The turnpike property for mean-field optimal control problems and Exponential turnpike property for particle systems and mean-field limit, get scalability from exchangeable agents. We seek it instead from sparse, signed, heterogeneous topology, which those papers do not handle.
The herdability side motivates the question but has no costs or certificates. Herdable Systems Over Signed, Directed Graphs and Herdability of Linear Systems Based on Sign Patterns and Graph Structures define herdability through the range test and give sign-pattern conditions. The latter reports that the general cyclic case is NP-hard, which constrains our certificate construction to structured graphs. Algebraic and Graph-Theoretic Conditions for the Herdability of Linear Time-Invariant Systems and On the herdability of linear time-invariant systems with special topological structures give tree and balanced-graph conditions, along with a reduction of herdability to the follower subsystem. All of these are open-loop reachability statements. None says what happens after the threshold is crossed, and that is our gap.
The closest attempt to lift dissipativity beyond points is Economic MPC of Markov Decision Processes: Dissipativity in Undiscounted Infinite-Horizon Optimal Control, with its discounted companion Functional Stability of Discounted Markov Decision Processes Using Economic MPC Dissipativity Theory. These move to the space of probability distributions to cope with noise, but they still assume a single optimal stationary measure and controllability in that space. Our relaxation is different in kind. The target is a deterministic set produced by structural under-actuation, not a measure produced by noise.
Research Program
The theoretical work has three parts. The first is to characterize sustainable herdability. We will prove it is implied by input connectability for internally positive systems (Metzler $A$, $B \ge 0$), and we will construct signed counterexamples that are herdable but not sustainably herdable. These counterexamples are trees with an unstable uncontrollable mode. The second part is to prove the set dissipation inequality, and the resulting set turnpike, for linear dynamics with convex costs and the polyhedral constraint $x \ge h$. We will handle the neutral case first. For the stable case we will add a moving-target turnpike that follows $\mathcal{S}^\star(z_u(t))$ as $z_u$ decays, and we expect convergence at the slower of the two rates: the controllable turnpike rate and the decay rate of $A_u$. The third part is to show that, on unisigned trees and balanced leader-follower graphs, the steady-state multipliers share a sign layer by layer, so the separable linear-plus-diagonal-quadratic storage function is valid. We will also show how the follower-subsystem reduction carries over to the storage function.
The computational work builds a certificate checker. It is a linear program, or a small semidefinite program, over separable storage functions, and its cost should grow with the number of edges rather than with $n^2$ or with polynomial degree. Once a certificate is found, it supplies a terminal cost for economic model predictive control with a short horizon.
Baselines
The naive reference point is threshold-constrained economic model predictive control with no certificate. This is standard receding-horizon optimization of $l$ under $x \ge h$, with no terminal cost and no stability argument. It shows what happens when one simply hopes the threshold holds. It will run on the same networks, horizons, solver and initial conditions as our method, with its single tuning knob, the horizon length, swept over the same grid we give ourselves. We beat it if, at short horizons, our certified controller has no threshold violations and lower closed-loop cost where the naive controller drifts or oscillates.
The strongest existing certification method is full-state sum-of-squares or semidefinite storage synthesis in the style of On turnpike and dissipativity properties of continuous-time optimal control problems. It is the strongest competitor because it is the one general tool known to produce storage functions, and on controllable systems it is complete for quadratic costs. We will give it the same networks, a time limit identical to ours, and degree two for linear problems. Because a plain point-wise run is ruled out by the necessity result, we also give it the best version we can: point-wise certification on the controllable subsystem alone, once per sampled $z_u$ slice, which is our method stripped of graph structure. The file reports no numbers on herdable networks, so there is no reported result found on Lacuna for this baseline on our testbed. The only reported figure for the method family is a degree-five polynomial certificate on the reactor model. Beating this baseline means matching its certified-or-not verdicts while cutting solve time by orders of magnitude as $n$ grows, or certifying instances where it runs out of time or memory.
For the discounted extension, the reference is strong discounted strict dissipativity from A New Dissipativity Condition for Asymptotic Stability of Discounted Economic MPC. That paper reports certified stability for discount factors as low as $\gamma = 0.3109$ on its linear-quadratic benchmark, against $\gamma \ge 0.846$ for earlier methods. On that controllable benchmark our method must reproduce, not beat, the 0.3109 figure, since there it collapses to their condition.
The key ablation removes the graph structure and searches over unstructured quadratic storage on the same set-based inequality. This separates what the set relaxation contributes from what separability contributes.
Why not just…?
Why not just pick an interior target $x^\star > h$ and run quadratic tracking control? When the controllability matrix is rank-deficient, a fixed $x^\star$ generally lies outside the reachable affine slice, so tracking it is infeasible or leaves a permanent offset. The herdability papers cited above show that such rank deficiency is typical of sparse leader-follower actuation. Even when $x^\star$ is reachable, tracking an arbitrary point gives up economic cost. We will measure both effects, infeasibility and the cost gap against the set turnpike, on the same networks.
Why not just take the Kalman decomposition and apply ordinary dissipativity to the controllable part, treating $z_u$ as a parameter? This is the real threat, and our construction does start there. It is sufficient, however, only when the uncontrollable part is frozen and the threshold does not couple the coordinates. Under $x \ge h$, the feasible steady states of $z_c$ depend on $z_u$. When $A_u$ is unstable, the slice can become infeasible, and no parameterized point-wise argument detects that. Sustainable herdability is exactly the condition that rules this case out. We include the decomposition as the ablation baseline above. If it certifies every instance we certify, at similar cost, then our theoretical contribution narrows to the sustainability condition plus the scalable separable certificates, and we will report it that way.
Why not just run model-free reinforcement learning or greedy heuristics? Functional Stability of Discounted Markov Decision Processes Using Economic MPC Dissipativity Theory argues that minimizing discounted cost does not by itself imply stability. Intervention in gene regulatory networks via greedy control policies based on long-run behavior reports that a heuristic baseline, mean first-passage time, occasionally failed to improve long-run behavior, while its conservative steady-state policy succeeded in all cases. Neither approach produces a certificate. We will include a learned policy in the closed-loop comparison only as an empirical reference.
Proposed Experiments
The testbeds are generated signed networks from the tree, clustering-balanced and structurally balanced families for which De Pasquale and Valcher give exact herdability verdicts, with $n$ ranging from 10 to several thousand. We add random topologies from the 11 graph generators in Benchmarking Structural Inference Methods for Interacting Dynamical Systems with Synthetic Data (code). These carry no herdability verdicts, so we decide herdability on them with the controllability-matrix range test. On top of these graphs we place linear dynamics with economic costs, such as actuation energy minus a weighted node-activity reward. The discounted linear-quadratic benchmark of Zanon and Gros serves as a controllable sanity check.
The metrics are the fraction of the horizon that the optimal trajectory spends within $\varepsilon$ of $\mathcal{S}^\star(z_u)$, the certificate verdict, the solve time as a function of $n$ and of edge count, the closed-loop threshold violations and suboptimality relative to a long-horizon solution, and the shortest horizon at which closed-loop behavior stays stable.
Three checks are decisive. First, on constructed herdable-but-not-sustainable trees, every controller must eventually violate $h$, and our condition must predict this before simulation; a single wrong prediction falsifies the sustainability theory. Second, on neutral-mode networks, optimal trajectories should converge to different steady states for different $z_u$ while all staying on the predicted set. A drift toward any point outside $\mathcal{S}^\star(z_u)$ falsifies the set turnpike. Third, the separable certificate should succeed on every unisigned tree and fail somewhere on unbalanced cyclic graphs, consistent with the NP-hardness result, and its failures should line up with the sign-pattern conditions rather than with network size.
References
- On turnpike and dissipativity properties of continuous-time optimal control problems
- Additional material to the paper "On necessity and robustness of dissipativity in economic model predictive control"
- Integral and measure-turnpike properties for infinite-dimensional optimal control systems
- The turnpike property for mean-field optimal control problems
- Exponential turnpike property for particle systems and mean-field limit
- Herdable Systems Over Signed, Directed Graphs
- Herdability of Linear Systems Based on Sign Patterns and Graph Structures
- Algebraic and Graph-Theoretic Conditions for the Herdability of Linear Time-Invariant Systems
- On the herdability of linear time-invariant systems with special topological structures
- Economic MPC of Markov Decision Processes: Dissipativity in undiscounted infinite-horizon optimal control
- Functional Stability of Discounted Markov Decision Processes Using Economic MPC Dissipativity Theory
- A new dissipativity condition for asymptotic stability of discounted economic MPC
- Intervention in gene regulatory networks via greedy control policies based on long-run behavior
- Benchmarking Structural Inference Methods for Interacting Dynamical Systems with Synthetic Data