On Submodularity and Controllability in Complex Dynamical Networks

Tyler H. Summers; Fabrizio L. Cortesi; John Lygeros

Source-linked AI summary

On Submodularity and Controllability in Complex Dynamical Networks

Tyler H. Summers, Fabrizio L. Cortesi, John Lygeros

arXiv:1404.7665v3Apr 30, 2014math.OCeess.SY

TL;DR

Large-network sensor and actuator placement requires optimizing real-valued controllability and observability metrics, yet the relevant combinatorial structure is poorly understood. The paper analyzes Gramian-based objectives and shows that several are modular or submodular, enabling exact or greedily approximated placement. These results are illustrated on random systems and a European power-grid actuator-placement problem.

Problem
Sensor and actuator placement must optimize real-valued controllability and observability metrics, but the structure of the resulting large combinatorial optimization problems is poorly understood.
Method
The paper studies set functions mapping actuator or sensor placements to scalar functions of controllability or observability Gramians.
Results
Several Gramian objectives are modular or submodular: modular objectives permit global optimization, while submodular objectives support approximation guarantees from greedy maximization.
Takeaways & Limitations
Gramian-based placement problems can yield globally optimal or near-optimal actuator and sensor selections using simple algorithms.

Abstract

from arXiv · show

Controllability and observability have long been recognized as fundamental structural properties of dynamical systems, but have recently seen renewed interest in the context of large, complex networks of dynamical systems. A basic problem is sensor and actuator placement: choose a subset from a finite set of possible placements to optimize some real-valued controllability and observability metrics of the network. Surprisingly little is known about the structure of such combinatorial optimization problems. In this paper, we show that several important classes of metrics based on the controllability and observability Gramians have a strong structural property that allows for either efficient global optimization or an approximation guarantee by using a simple greedy heuristic for their maximization. In particular, the mapping from possible placements to several scalar functions of the associated Gramian is either a modular or submodular set function. The results are illustrated on randomly generated systems and on a problem of power electronic actuator placement in a model of the European power grid.

I. INTRODUCTION

Large-network sensor and actuator placement requires optimizing real-valued controllability and observability metrics, but the combinatorial structure of these problems is poorly understood. This paper identifies modularity and submodularity properties that enable efficient or approximately optimal placement.

Motivation: Structural controllability based on driver-node counts can be crude or misleading in some network settings.The paper motivates richer quantitative metrics for placement decisions.
Motivation: Large placement problems cannot generally be solved by enumerating all possible actuator and sensor combinations.Brute force becomes infeasible as network size grows.
Contributions: The paper shows that linear functions of controllability or observability Gramians map placements to modular set functions.Modularity supports efficient global optimization.
Contributions: Gramian rank, log determinant, and negative inverse-Gramian trace are submodular set functions of actuator or sensor placements.Submodularity supports approximation guarantees through greedy maximization.
Contributions: The results are illustrated using randomly generated systems and power-electronic actuator placement in a European power-grid model.The paper also introduces dynamic network centrality measures based on control energy.

B. Energy-related controllability metrics

The controllability Gramian provides energy-related metrics describing how readily system states can be reached. The paper focuses on stable systems and reviews trace, inverse-trace, determinant, minimum-eigenvalue, and rank measures.

Gramian interpretation: The controllability Gramian quantifies the input energy required to move through the state space.Large Gramian values correspond to lower required energy in relevant directions.
Energy-related metrics: tr(Wc) measures average controllability across state-space directions and is inversely related to average energy.It is also closely related to the system H2 norm.
Energy-related metrics: tr(Wc^-1) is proportional to average energy, but the inverse does not exist for uncontrollable systems.A pseudoinverse-based alternative can be considered in that case.
Energy-related metrics: log det Wc measures the volume of states reachable with one unit or less of input energy.For uncontrollable systems, this volume is zero and log det Wc = -∞.
Energy-related metrics: λmin(Wc) is a worst-case metric for the state-space direction requiring the most control energy, while rank(Wc) gives controllable-subspace dimension.The main results also extend to finite-horizon and linear time-varying settings.

III. OPTIMAL SENSOR AND ACTUATOR PLACEMENT IN NETWORKS

Sensor and actuator placement is formulated as maximizing a set function over a fixed number of candidate locations. Modularity enables exact selection, while submodularity supports greedy approximation for otherwise infeasible combinatorial searches.

Optimization formulation: Placement optimization selects a k-element subset of candidate locations to maximize a controllability metric.Each subset receives a real-valued set-function score.
Optimization formulation: Brute-force enumeration quickly becomes infeasible because the number of candidate subsets grows factorially with network size.The paper therefore studies structural properties of the objective function.
Submodularity: Submodularity expresses diminishing returns: adding an element to a smaller set gives a larger gain than adding it to a larger set.This property supports tractable approximation strategies.
Modularity: Modular objectives are optimized globally by evaluating each element individually, sorting the values, and selecting the top k.Each element contributes independently to the total function value.
Greedy optimization: For monotone increasing submodular objectives, greedy selection has a provable worst-case approximation guarantee.The bound is the best achievable by any polynomial-time algorithm assuming P ≠ NP, although practice can be better.

B. Trace of the Gramian

For stable dynamics, actuator placements contribute additively to the controllability Gramian. Consequently, a weighted trace of the Gramian is modular and can be optimized by ranking individual placements.

Gramian construction: For each candidate placement subset, the input matrix combines an existing matrix with the selected actuator columns.The associated Gramian satisfies a Lyapunov equation.
Modularity result: The weighted trace f(S) = tr(CW_S C^T) is a modular set function.This holds for any weighting matrix C.
Modularity result: The result follows because the subset Gramian is a sum of individual placement Gramians and trace is linear.Each placement therefore contributes independently to the objective.
Placement consequence: The optimal k-placement solution is obtained by evaluating each actuator separately, sorting the scores, and choosing the best k.For this metric, adding an actuator cannot decrease controllability.

C. Trace of the inverse Gramian

The trace of the inverse controllability Gramian is submodular under an invertibility assumption, while its negative is monotone increasing with actuator additions.

Assumption: The trace of the inverse Gramian is analyzed assuming every associated controllability Gramian is invertible.This includes systems with an existing controllable actuator set to which additional actuators are added.
Submodularity: The derived marginal-gain function for adding an actuator is monotone decreasing over nested actuator sets.The proof uses Gramian additivity, matrix inverse derivatives, and semidefinite ordering.
Submodularity: The resulting negative-trace set function is submodular.The conclusion follows from the monotonicity of the derived marginal-gain function.
Monotonicity: Adding an actuator cannot decrease controllability because the controllability Gramian is additive.This establishes monotone increase of the selected objective under actuator additions.

D. Log determinant of the Gramian

The log determinant of the controllability Gramian is submodular and monotone increasing, with weighted variants retaining these properties under stated rank conditions.

Log determinant: The log determinant of the controllability Gramian is submodular and monotone increasing.The proof shows marginal gains decrease as the actuator set grows.
Proof: The proof establishes decreasing marginal gains using the matrix derivative of log det and semidefinite Gramian ordering.The derivative is expressed through a trace involving the inverse Gramian.
Related metric: The normalized geometric mean n√det WS is also submodular and monotone increasing.It is a non-negatively scaled version of n log det WS.
Weighted metrics: Weighted variants using a state-weight matrix are submodular and monotone increasing when C has full row rank.The weighting allows different state directions to receive different importance.
Scope: For non-full-rank Gramians, log determinant is undefined or interpreted as −∞ and cannot distinguish among uncontrollable actuator subsets.Rank and continuous pseudoinverse-based metrics are discussed as alternatives for uncontrollable systems.

F. Smallest eigenvalue of the Gramian

Although several Gramian metrics are submodular, the smallest eigenvalue is not generally submodular: a concrete example violates diminishing returns.

Counterexample: The smallest eigenvalue λmin(WS) is a concave matrix function whose induced actuator set function need not be submodular.The paper presents this as a counterexample to extending submodularity to every concave Gramian function.
Diminishing returns: Submodularity requires diminishing gains, with Δ(s | A) ≥ Δ(s | B) whenever A ⊆ B and s ∉ B.The marginal gain is defined as f(A ∪ {s}) − f(A).
Example: For b3, diminishing returns hold after selecting b1: Δ(b3 | {b1}) = 0.037 ≥ 0.033 = Δ(b3 | {b1, b2}).
Example: For b3, diminishing returns fail after selecting b2: Δ(b3 | {b2}) = 0.001 ≤ 0.033 = Δ(b3 | {b1, b2}).This violation establishes that the smallest-eigenvalue set function is not submodular in the example.

G. Dynamic network centrality measures

The paper defines control-energy centrality measures from controllability Gramians, framing node importance by control effort rather than graph structure alone.

Definition: Control-energy centrality measures quantify node importance through the ability to move a stable network around its state space with low-energy control.The construction assumes a stable linear dynamics matrix A and possible actuator placement at each node.
Measures: The proposed measures include Average Controllability Centrality, Average Control Energy Centrality, and Volumetric Control Energy Centrality.
Construction: Each node-specific measure is based on its infinite-horizon controllability Gramian.The Gramian is defined through the system dynamics and the node-specific input direction.
Interpretation: These dynamical centralities can identify important nodes differently from purely graph-based centrality measures.The greedy actuator-selection algorithm chooses the currently most central node at each iteration.

H. Computational scaling for large networks

The paper describes several techniques for scaling greedy actuator selection to large structured networks, including exploiting sparsity, parallelism, and submodularity.

Sparse Lyapunov-equation algorithms compute low-rank Gramians while exploiting the rank-one structure of individual actuators.
Greedy iterations can be parallelized by pre-computing individual-actuator Gramians independently and summing them for any actuator set.
The accelerated Minoux greedy algorithm uses submodularity to reduce marginal-gain evaluations and can provide orders-of-magnitude practical speedups.

IV. NUMERICAL EXAMPLES

The numerical examples evaluate actuator selection using a system dynamics matrix, candidate input directions, and a fixed number of actuators to optimize a controllability metric.

The experiments use a dynamics matrix A, candidate input columns V, and an integer k specifying how many actuators to select.
The selected actuator subset forms an input matrix whose controllability metric is maximized.

A. Greedy performance on random systems

On randomly generated stable systems, greedy selection is near-optimal for the log determinant and produces distinct eigenvalue trade-offs across continuous controllability metrics.

For n = 25 and k = 7, greedy log determinant optimization produced a selection better than 99.93% of all other 7-actuator subsets.The exhaustive comparison used all possible selections of 7 actuators from 25 candidates.
Trace optimization globally optimizes the largest Gramian eigenvalues, while trace-inverse and log determinant balance large and small eigenvalues.The latter two metrics produce similar eigenvalue distributions and improve smaller eigenvalues relative to trace optimization.
Trace-inverse and log determinant provide near-optimal greedy selections through submodularity, although global optimality is not guaranteed.
The minimum-eigenvalue metric performs slightly worse on average than trace-inverse for the smallest eigenvalue in this example.Greedy optimization of this non-submodular metric nevertheless performs comparably on other eigenvalues and exceeds trace on most smaller eigenvalues.
The comparisons average Gramian eigenvalues over 10,000 random stable dynamics matrices for greedy selection of 7 actuators from 25 candidates.

B. Power electronic actuator placement in the European power grid

The paper illustrates its placement results on a 74-bus European grid model with HVDC actuators, comparing controllability-Gramian trace and log-determinant objectives. The example uses a linearized system because nonlinear controllability metrics are computationally difficult, and shows that greedy optimization yields distinct placement patterns.

Model and placement problem: HVDC links are modeled as ideal current sources that can instantaneously inject AC currents at their terminal buses in a swing-equation-based system.Each link has three degrees of freedom, while each generator contributes rotor-angle and frequency states.
Trace metric: The best trace-metric placements include long lines spanning major network quadrants and correlate with lightly damped rotor-angle modes.Additional high-ranked placements are concentrated in the southeast, indicating room to improve control authority there.
Log-determinant metric: Greedy log-determinant optimization, preceded by rank-based selection until controllability is reached, produces longer, more evenly distributed lines than the trace metric.No node is part of more than one HVDC line, although both metrics align with lightly damped rotor-angle modes and yield quite different placements.
Trace metric: The trace metric’s top placements provide substantial benefit over other candidates, with the optimal value defined as the sum of the first 10 placement contributions.Figure 4 sorts each actuator placement by the amount it adds to the controllability Gramian trace.
Implications and scope: The placement study illustrates that Gramian-based metrics support globally optimal or near-optimal actuator placement, with corresponding results applying to observability-based sensor placement.The broader conclusion identifies modular and submodular Gramian metrics as enabling simple greedy optimization.