Dissipation Bounds and Hardness in Globally Asymptotically Stable Quadratic Systems
En palabras de los autores
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.
Apareció: jueves, 22 de octubre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 7 pages, 3 figures