Engineers who choose where to put a handful of actuators in a power grid or a sensor network usually optimize an average measure of how easy the network is to steer or observe. Average measures have a convenient mathematical property, diminishing returns, that guarantees a simple one-at-a-time greedy choice is close to optimal. The quantity that matters for safety is different. It is the worst-case energy: how much effort it takes to push the system in its hardest direction, or how badly the system can be estimated from the chosen sensors. That quantity lacks diminishing returns. This proposal targets the regime where the mismatch hurts most. Here the budget is barely enough to make the network controllable at all, so a single actuator adds nothing measurable and only certain combinations help. We propose a ladder of tractable surrogate objectives that interpolates from the average measure to the worst-case one. Greedy selection is run along the ladder, and the lower and upper surrogates are used to return a per-instance certificate of how far the chosen set can be from optimal.
Put in two sentences: worst-case steerability has a "nothing, then suddenly something" structure near the minimum actuator budget, which blinds greedy selection. A family of regularized inverse-energy objectives that ranges from average to worst case can guide the search through that flat region and bound the answer from both sides. The same mathematics covers sensor selection through the observability side of the problem, so one method serves both placement tasks.
Background and the gap
For a stable linear network $\dot x = Ax + Bu$, the controllability Gramian $W$ measures the energy needed to reach each state. Reaching $x_f$ costs $x_f^T W^{-1} x_f$, and the hardest direction costs $1/\lambda_{\min}(W)$. When actuators are picked from candidate input columns $b_i$, the Gramian adds up: $W_S = \sum_{i\in S} W_i$. Controllability Metrics, Limitations and Algorithms for Complex Networks shows that $\lambda_{\min}(W)$ collapses exponentially with network size when few nodes are driven. Its corollary, that actuator counts must grow linearly with network size, makes the near-minimal-budget regime the practically important one. Eigenvalue clustering, control energy, and logarithmic capacity gives a spectral reason why $\lambda_{\min}$ can be tiny even for controllable systems.
On the optimization side, Submodularity of energy related controllability metrics and On Submodularity and Controllability in Complex Dynamical Networks prove that trace, rank, log-determinant and negative inverse-trace have diminishing returns. They also prove that $\lambda_{\min}$ does not. They handle singular Gramians with a two-stage greedy: first raise rank, then optimize energy. That procedure has no guarantee over the total budget. These papers supply both the method we reuse and the negative result that motivates us.
Performance guarantees for greedy maximization of non-submodular controllability metrics bounds the submodularity ratio $\gamma$, which measures how far a function is from diminishing returns, and the curvature $\alpha$, which measures how far it is from purely additive. It reports greedy above 90% of optimum and no observed violations in thousands of trials. However, it explicitly assumes a base actuator set that already makes the system controllable. That paper constrains our claim: away from the controllability threshold, plain greedy on $\lambda_{\min}$ is probably fine, and we do not claim otherwise. Our claim lives exactly where its assumption fails.
Minimal Actuator Placement with Optimal Control Constraints supplies the key technical tool. Adding $\epsilon I$ makes the transfer energy $x_f^T(W_S+\epsilon I)^{-1}x_f$ well defined on singular Gramians, and the result has diminishing returns. That paper, however, treats one fixed transfer $x_0\to x_f$ and minimizes actuator count, not worst-case energy under a budget.
Finally, Competitive Influence Maximization within Time and Budget Constraints in Online Social Networks: An Algorithmic Approach uses "sandwich" bounds, lower and upper submodular functions around a hard objective, for information cascades on social graphs. Think globally, act locally shows that threshold-type objectives can reward concentrated rather than dispersed seeds. We borrow the sandwich logic and the clustering-versus-dispersion question. Neither has been applied to Gramian spectra.
Core Claim
Near the minimum controllable budget, $\lambda_{\min}(W_S)$ is zero for most small sets and becomes positive only for complementary combinations. This is a synergy structure, and it defeats greedy on $\lambda_{\min}$ (all early gains tie at zero) and the rank-first two-stage method (the completing set is chosen without regard to conditioning). We define the surrogate family
$$ T_{\epsilon,p}(S) = \mathrm{Tr}\big[(W_S + \epsilon I)^{-p}\big], \qquad \epsilon>0,\ p\ge 1, $$
where $W_S$ is the Gramian of set $S$ and $I$ the $n\times n$ identity, $n$ being the number of states. Because the sum of the eigenvalues raised to $-p$ lies between the largest term and $n$ times it,
$$ T_{\epsilon,p}(S)^{-1/p} \;\le\; \lambda_{\min}(W_S)+\epsilon \;\le\; n^{1/p}\, T_{\epsilon,p}(S)^{-1/p}. $$
The two knobs do different jobs. At $p=1$, minimizing $T$ is a sum of Tzoumas-style supermodular transfer energies, so greedy keeps the classic $(1-1/e)$ guarantee for every $\epsilon$, including on singular Gramians. The price is a loose sandwich factor of $n$. As $p$ grows, the sandwich tightens toward exact $\lambda_{\min}$, but diminishing returns may fail. For large $\epsilon$ the objective approaches the additive trace measure; for small $\epsilon$ it focuses on the weakest directions.
We claim three things. First, annealing $\epsilon$ downward and $p$ upward lets greedy cross the flat region using graded information. Second, the trade-off between sandwich tightness and diminishing returns can be measured per instance. Third, the result is a set of actuators (or, through the observability Gramian, sensors) with a per-instance certificate of the form "within X% of optimal worst-case energy." Such a certificate is tighter than the instance-independent bounds of Summers and Kamgarpour.
Research Program
The first step is analysis. On small instances where we can enumerate every subset, we will compute the empirical submodularity ratio of $-T_{\epsilon,p}^{-1/p}$ and of $\lambda_{\min}$ itself as a function of budget $k$ relative to the minimal driver count, of $\epsilon$, and of $p$. We expect the ratio of $\lambda_{\min}$ to drop sharply only within a few actuators of the controllability threshold. That pattern would reconcile the clean empirical results of Performance guarantees for greedy maximization of non-submodular controllability metrics with the known non-submodularity. If the ratio stays near one even at the threshold, the motivating premise is wrong, and we will report that.
The second step is the algorithm. Greedy runs along a schedule of $(\epsilon,p)$ pairs, either restarting from scratch or warm-starting with swaps, and keeps the candidate set with the best true $\lambda_{\min}$. Following the sandwich logic of Zhou et al., the certificate combines the $(1-1/e)$ bound on the $p=1$ surrogate with the measured ratio of true $\lambda_{\min}$ to the surrogate bounds at the returned set.
The third step is a structural question. Do worst-case-optimal sets near threshold cluster inside graph communities, as in complex contagions, or disperse, as log-determinant solutions do on the European grid? We will answer it on community-structured graphs and relate the answer to Fiedler partitions as used by Pasqualetti et al.
The fourth step is the sensor side. The dual problem chooses output rows $c_i$ to maximize $\lambda_{\min}$ of the observability Gramian. That is the worst-case estimation quality, and the same method applies unchanged.
Baselines
The naive reference points are random sets and top-degree nodes. The 23-node experiment in Actuator Placement for Optimizing Network Performance under Controllability Constraints already shows hub-first choices can be badly suboptimal: greedy reached a cost of 15976.0 against an optimal 6043.8. A method that does not clearly beat these points has nothing to offer.
The strongest existing combinatorial competitor is the two-stage rank-then-energy greedy of Submodularity of energy related controllability metrics, run with $\lambda_{\min}$ as the second-stage objective. It is the only published procedure designed for the singular regime. For the related average measure it reports roughly 98% of the optimal log-determinant on a 25-state system. Alongside it we run plain greedy on $\lambda_{\min}(W_S+\epsilon I)$ with fixed $\epsilon$, as in Performance guarantees for greedy maximization of non-submodular controllability metrics. That baseline reports greedy above 90% of the global optimum on Barabási–Albert, Erdős–Rényi and L-shaped mesh graphs. This 90% figure is the number to beat, specifically in the near-threshold budgets that paper did not isolate.
We also run greedy on log-determinant as an average-case surrogate. Finally, we run the convex relaxation that maximizes $\lambda_{\min}(\sum_i x_i W_i)$ over fractional weights summing to $k$, followed by top-$k$ and randomized rounding. Its relaxed optimum gives an upper bound on the best achievable value.
The sensor-side reference is QR column pivoting on modal bases from PySensors 2.0. This is a strong, widely used open-loop heuristic, but it ignores the dynamics.
The ablations isolate the key ingredient. The first is $p=1$ with fixed $\epsilon$, a pure diminishing-returns surrogate. The second is annealed $\epsilon$ with $p=1$. The third is fixed $\epsilon$ with $p$ increasing. These tell us whether the gain comes from crossing the flat region, from the tighter sandwich, or from both.
All methods receive the same candidate sets, the same Gramians computed once, and the same wall-clock budget. Any extra cost of our schedule is charged against us, and the schedule length is fixed on held-out graph instances before testing.
Beating the field means three things. On enumerable instances, our method must achieve higher true $\lambda_{\min}$ (lower worst-case energy) than two-stage greedy, with a gap that is statistically significant over many random graphs in the near-threshold band. It must at least match the 90% level in the band and not fall below the baselines elsewhere. On large instances, its certified ratio must be tighter than the instance-independent Summers–Kamgarpour bound.
Why not just…?
Why not just run greedy on $\lambda_{\min}$, since it already gets 90%? That figure comes from experiments assuming an initial controllable base set. With zero to a few actuators every candidate gives the same regularized $\lambda_{\min}$, so the first choices are tie-breaks. Our budget sweep relative to minimal driver count tests directly whether this matters. If plain greedy matches our method even at threshold, the algorithmic claim fails and only the certificate remains as a contribution.
Why not just optimize log-determinant, which has guarantees and spreads actuators well? Log-determinant rewards volume. It will happily accept one nearly unreachable direction if the others are large, which is exactly the failure worst-case energy is meant to catch. The Gramian conditioning analysis in Eigenvalue clustering, control energy, and logarithmic capacity suggests such directions are common. We will report how often the log-determinant optimum has a markedly worse $\lambda_{\min}$ than the best set found.
Why not just solve the convex relaxation of $\lambda_{\min}$ and round? This is the most serious alternative. The relaxation is concave and tractable at the scales in the file, and it provides an upper bound. Our concern is that near threshold the fractional optimum spreads small weights over many candidates to achieve full rank, and rounding then destroys controllability. That is an empirical question we settle head-to-head. If rounding matches us in solution quality, we will reposition the contribution as the analysis of where non-submodularity bites and as certificates that complement the relaxation bound. We will also use the relaxation bound itself as the optimality reference on instances too large to enumerate.
Why not just pick hubs or central nodes? The evidence in Actuator Placement for Optimizing Network Performance under Controllability Constraints and the trace-clustering pathology in Optimal Sensor and Actuator Placement in Complex Dynamical Networks argue against it. Hubs cover already-reachable modes, and worst-case energy is set by the modes they miss. We include degree as a sanity floor.
Proposed Experiments
The enumerable tier uses random stable Barabási–Albert, Erdős–Rényi and L-shaped mesh networks of 16 to 25 states, matching the published settings. We sweep $k$ from the minimal driver count to several times it, so near-threshold behavior is visible, and compare against exhaustive optima. We also rerun the 23-node matroid network from the matroid paper with worst-case energy and the structural controllability constraint imposed.
The large tier uses the 74-bus, 148-state Continental European grid model with 2,701 candidate links, where the published experiments report runtime and log-determinant placements. There is no reported result on Lacuna for $\lambda_{\min}$-based selection on the European grid model, so here the comparison is against the baselines run by us, with the relaxation upper bound as reference. The IEEE 118-bus system serves as a second grid, using Pasqualetti et al.'s Fiedler-boundary placement as an additional structured baseline. Stochastic block-model graphs with tunable community strength are used for the clustering-versus-dispersion study.
The sensor experiments repeat all tiers on the observability side against QR pivoting.
The metrics are true worst-case energy $1/\lambda_{\min}$ of the returned set, its ratio to the exhaustive optimum or the relaxation bound, the certified ratio, the empirical submodularity ratio by budget, and runtime. The decisive check is the near-threshold band on enumerable graphs. If our method does not beat two-stage greedy and rounded relaxation there, the central claim is wrong.
References
- Controllability Metrics, Limitations and Algorithms for Complex Networks
- Eigenvalue clustering, control energy, and logarithmic capacity
- Submodularity of Energy Related Controllability Metrics
- On Submodularity and Controllability in Complex Dynamical Networks
- Performance guarantees for greedy maximization of non-submodular controllability metrics
- Minimal actuator placement with optimal control constraints
- Competitive Influence Maximization within Time and Budget Constraints in Online Social Networks: An Algorithmic Approach
- Think Globally, Act Locally: On the Optimal Seeding for Nonsubmodular Influence Maximization
- Actuator Placement for Optimizing Network Performance under Controllability Constraints
- PySensors 2.0: A Python Package for Sparse Sensor Placement
- Optimal Sensor and Actuator Placement in Complex Dynamical Networks