Hard limits on energy loss estimates in stable quadratic systems
Dissipation Bounds and Hardness in Globally Asymptotically Stable Quadratic Systems
Computational Complexity
Summary
This paper studies how much energy can be lost over time in certain stable mathematical systems used to model dynamics. The authors show that figuring out the worst-case energy loss or how quickly energy disappears is very hard—so hard that no fast computer program can do it for every system. This is true even when given helpful information that proves the system is stable. The findings set clear boundaries on what can be efficiently computed about these systems' energy behavior.
What this means in practice
- •For control system engineers: Recognize fundamental computational limits when estimating energy dissipation or stability margins in quadratic control systems.
- •For power grid operators: Understand inherent difficulties in predicting energy loss dynamics in grid stability models involving damped quadratic systems.
A theory result. No direct application yet.
Authors
Subhransu S. Bhattacharjee
Abstract
We study worst-case finite-time energy dissipation in quadratic systems with proved global asymptotic stability (GAS). Estimating the maximum retained energy fraction to any fixed positive additive error below $1/2$ is NP-hard, even when the input includes a strict quartic Lyapunov function and proof of strictness, both constructed in polynomial time. NP denotes nondeterministic polynomial time. For a partially damped family, the unit-sphere minimum norm of the coupling map equals the structured coefficient distance to loss of GAS. Positive distances at most $1/2$ give two-sided inverse-square halving-time bounds with explicit coefficient factors. Polynomial-factor approximation of the least dissipated fraction, halving time or coefficient distance is NP-hard. Additive hardness persists throughout an explicit coefficient neighborhood and under direct damping with exponential stability, a strict quadratic Lyapunov function and a Hurwitz Jacobian. Unless $\mathrm{P}=\mathrm{NP}$, where P denotes deterministic polynomial time, no polynomial-time algorithm attains these guarantees on all inputs.