CS Paper Radar

Complexity of Output Feedback Stabilization

Amir Ali Ahmadi, Abraar Chaudhry, Ijay Narang, Yukai Tang

cs.CC math.OCeess.SY ·submitted 2026-09-17 16:21 UTC · v2

Abstract

We show that unless P = NP, there cannot be a polynomial-time (or even pseudo-polynomial-time) algorithm for output feedback stabilization of a linear dynamical system with a linear controller. This settles one of the best-known open problems in control theory. The result holds in both continuous and discrete time. We also present a family of stabilizable linear dynamical systems for which no polynomial-time algorithm can write down a stabilizing controller in its standard representation.

Closest papers

Nearest neighbours by meaning across the whole index.

Robust stabilization of discrete-time linear systems requires nonlinear dynamic feedback

eess.SY math.OC ·2026-08-19 ·Amir Shakouri, Marieke Heidema, Henk J. van Waarde
theory similarity 0.61
Abstract · 8 pages

This paper studies the problem of robust stabilization of linear input-state systems in discrete time. We prove that for any compact set of stabilizable systems, there exists a dynamic state-feedback controller that globally asymptotically stabilizes all systems in the set. In addition, we show that for some compact sets of stabilizable systems, no nonlinear static or linear dynamic state-feedback law can achieve this task. This proves that, in general, robust stabilization requires a feedback law that is both nonlinear and dynamic. We extend our study to robust exponential stabilization with a given rate of decay. Finally, for polytopic sets of systems, we introduce an algorithm for the design of robust feedback laws.

0.29

On the NP-Hardness of Unconstrained Static Output Feedback Stabilization

eess.SY ·2026-09-30 ·Gal Barkai, Iman Shames
similarity 0.60
Abstract

In this paper we give a polynomial-time reduction from the Subset Sum Problem to unconstrained static output feedback stabilization, establishing its NP-hardness. The construction uses two scalar building blocks to impose approximate discrete choices and a weighted-sum constraint. Once the problem is encoded, we relate the stability of the $N+1$ decoupled loops encoding the problem to that of a coupled plant. This is accomplished by leveraging frequency separation via a band-pass transformation, and comparing the root counts of the true characteristic polynomial with that of the different blocks in different regions of the right half-plane. The construction then naturally bounds every stabilizing gain and gives explicit modulus-margin estimates, ensuring that the plant data have polynomial binary encoding length.

0.46

Robust Data-Driven Output Feedback for Systems With Unknown Input Delays

eess.SY ·2026-10-31 ·Ngoc Tuan Dinh, Ba Huy Nguyen, Alexey Peregudin, Egor Dogadin
similarity 0.56
Abstract · 6 pages, 1 figure. Submitted jointly to IEEE Control Systems Letters (L-CSS)

In a history-feedback realization, an input delay increases memory without increasing the number of unknown physical coefficients. We use this structure to design output-feedback controllers for discrete-time systems with one input, one output, and known undelayed order, using noisy input-output data. For a known delay, we derive a necessary and sufficient linear matrix inequality for common-quadratic stabilization of all models consistent with the data. Optimizing its equation-error bound gives a robustness margin for the measured record. For an unknown constant delay in a known interval, we characterize noiseless delay ambiguity and give a sufficient condition for one controller to stabilize all models for every delay consistent with the error bound. Under stated excitation and nondegeneracy assumptions, this procedure is feasible for all sufficiently small equation errors. Numerical examples compare robustness at equal controller memory and show that certified stabilization can succeed while distinct delay models remain compatible with the same data.

0.31

A Polynomial-Time Algorithm for the Minimal Input/Output Node Cardinality Disturbance Decoupling Problem over Networks via Output Feedback

eess.SY math.OC ·2026-10-15 ·Luca Claude Gino Lebon, Jorke de Vlas, Johannes K. Fichte, Claudio Altafini
similarity 0.55
Abstract · MATLAB functions implementing the results presented in this article are available in the GitLab repository: https://gitlab.liu.se/lucle71/no…

For networked systems, we propose a polynomial-time algorithm for solving the minimal input/output node cardinality disturbance decoupling problem via output feedback. The algorithm computes an optimal solution, namely, a pair of minimum-cardinality sets of control input and measurement output nodes that achieve disturbance decoupling, by solving a min-cut/max-flow problem on an extended network.

0.28

Distributed Output-Feedback Control for Linear Multichannel Systems

eess.SY ·2026-11-13 ·Ruixuan Zhao, Guitao Yang, Boli Chen, Thomas Parisini
similarity 0.55
Abstract

This paper investigates distributed output-feedback stabilization of linear multichannel systems in which agents exchange state estimates without disclosing local control inputs or feedback gains. Remote control actions are treated as unknown inputs and geometrically decoupled from stable quotient-error dynamics. The proposed framework accommodates nontrivial intersections of local loss subspaces by retaining the coupling between the plant and common estimation errors. A Hurwitz condition on the coupled dynamics, together with a sufficient consensus-gain bound, guarantees exponential closed-loop convergence for every fixed feedback selection in a compact family. For polytopic feedback families, a quotient-preserving parameterization of output injections enables joint synthesis of nominal feedback and observer gains via alternating linear matrix inequalities, followed by a convex semidefinite program certifying a common consensus gain. A numerical example demonstrates the effectiveness of the proposed design.

0.28

A New Approach for Feedback Stabilization and its Application for Data-Driven Control of Polynomial Systems

eess.SY math.OC ·2026-08-10 ·Diego de S. Madeira, Joao Gabriel N. Silva, Wilkley B. Correia, Antonis Papachristodoulou
theory similarity 0.55
Abstract

Inspired by recent developments in dissipativity-based control, this work proposes new sufficient conditions for asymptotic stabilization of nonlinear systems using state feedback. We prove that this new framework is well suited for data-driven control of polynomial systems using noisy measurements, a topic that has lately attracted considerable attention. Two iterative procedures for data-based state feedback design are provided using the proposed framework, that use sum-of-squares (SOS) optimization. Typical limitations of conventional SOS methods based on alternating (D-K) procedures for controller design, such as the need to provide an initialization for a control-Lyapunov function (CLF), are overcome in this paper. Numerical examples demonstrate the applicability and the advantages of the new strategies.

0.04

Discrete-time polynomial systems with inputs and outputs: structure, reachability, observability, and minimal realizations

eess.SY math.OC ·2026-09-29 ·Eduardo D. Sontag
similarity 0.55
Abstract

We study the realization problem for discrete-time input/output polynomial systems. These are formalized using tools from commutative algebra and algebraic geometry as systems whose state spaces are algebraic varieties, or more abstractly the set of k-points of an affine k-scheme, where k is an arbitrary infinite field. The input/output behaviors of such systems are described by "polynomial response maps" in which outputs are polynomial functions of past inputs. The main results show that every polynomial response map admits a canonical (quasi-reachable and algebraically observable) realization, which is unique up to isomorphism. The key to the approach is to linearize dynamics by considering a "dual" system in which states are functions defined on states. Finite dimensionality of the canonical realization, and its polynomiality, are characterized in terms of the space, algebra, and field of observables of the map, as well as in terms of algebraic input/output difference equations, and by a Jacobian rank criterion. A particular subclass consists of the maps that we call "bounded," defined by the property that their degree in the past inputs is uniformly bounded. Bounded maps are shown to be finitely realizable if and only if they are realizable by finite-dimensional state-affine systems, whose theory in turn reduces to that of rational formal power series. We also study the lattice of quasi-reachable realizations of a given map, including normal realizations. This work is an update of the PhD thesis written by the author in 1976; connections to recent work are briefly discussed in the last section.

0.38

Stability Transfer for Autonomous Systems via Higher-Order Taylor-Truncated Lyapunov Certificates

eess.SY math.OC ·2026-10-13 ·Jose D. Hoyos, Zehui Lu, Shaoshuai Mou
published similarity 0.54
Abstract

We develop analytical sufficient conditions for certifying the local asymptotic stability of nonlinear autonomous systems based on Lyapunov functions derived from their finite-order Taylor polynomial approximations. This approach translates the stability analysis problem from the original nonlinear dynamics to a more computationally tractable polynomial domain. The derived conditions allow for the explicit calculation of a guaranteed inner approximation of the region of attraction ($\mathrm{ROA}$). We show how sum-of-squares (SOS) programming and grid search can be used to systematically search for polynomial Lyapunov functions that yield a large certified threshold radius and extract a certified invariant set inner approximation of the $\mathrm{ROA}$ of the nonpolynomial original system. The framework is then applied to a control tuning problem: finding reduced-effort Linear Quadratic Regulator (LQR) controllers that ensure that a given initial state of interest belongs to the certified $\mathrm{ROA}$ of the nonpolynomial closed loop system. The effectiveness of the overall methodology is demonstrated using a pendulum with nonlinear damping and a nonlinear control system.

0.29