pipette
ESEspañol

Dissipation Bounds and Hardness in Globally Asymptotically Stable Quadratic Systems

Subhransu S. Bhattacharjee

Preprint

In the authors' words

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 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 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 , where P denotes deterministic polynomial time, no polynomial-time algorithm attains these guarantees on all inputs.

Main resultThe abstract does not state a limitation.

Appeared: Thursday, October 22. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 7 pages, 3 figures