NP-hardness of some linear control design problems^{∗}

Vincent Blondel^{†}  John N. Tsitsiklis^{‡}

May 3, 1995

Consider the following three classical control problems:

Stabilization by static output feedback. This is perhaps the most basic problem in control theory. We are given a linear system

ẋ(t) = Ax(t) + Bu(t)
y(t) = Cx(t)

and we consider a static feedback control law of the form

u(t) = Ky(t).

The resulting closed loop system is

ẋ(t) = (A + BKC)x(t).

The problem is to find necessary and sufficient conditions on the triplet of real matrices (A, B, C) under which there exists a feedback gain matrix K such that A + BKC is stable. When C is not invertible, no general necessary and sufficient conditions are known.

Simultaneous stabilization by static output or state feedback. Our second problem is a generalization of the static output feedback problem. Suppose that for each i, i = 1, …, k, we are given a linear system

ẋ(t) = A_{i}x(t) + B_{i}u(t)
y(t) = C_{i}x(t).

Under the feedback control law

u(t) = Ky(t)

the ith closed loop system is

ẋ(t) = (A_{i} + B_{i}KC_{i})x(t).

∗This research was supported by the AFOSR under grant AFOSR–91–0368 and by the ARO under grant DAAL03–92–G0309. The first author also gratefully acknowledges support from KTH, Stockholm.

†INRIA Rocquencourt, Domaine de Voluceau BP105, 78153 Le Chesnay Cedex, France

‡Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, MA 02139, USA

The problem is to find conditions on the triplets of real matrices (A_{i}, B_{i}, C_{i}), i = 1, …, k, under which there exists a matrix K such that A_{i} + B_{i}KC_{i} is stable for each i. This problem is unsolved even if C_{i} = I for all i (state feedback).

Stabilization by decentralized static output feedback. We now impose some structure on the feedback gains. Consider a linear system of the form

ẋ(t) = Ax(t) + ∑_{i=1}^{k} B_{i}u_{i}(t)
y_{i}(t) = C_{i}x(t),  i = 1, …, k,

and suppose that we are interested in a static decentralized controller of the form

u_{i}(t) = K_{i}y_{i}(t), i = 1, …, k.

The closed loop system is

ẋ(t) = (A + ∑_{i=1}^{k} B_{i}K_{i}C_{i})x(t),

which is of the same form as in stabilization by static output feedback except that several of the entries of K are forced to zero. This leads us to the problem of finding conditions on the triplet of real matrices (A, B, C) under which there exists a matrix K with a given structure such that A + BKC is stable. The problem can be further constrained by requiring the matrix structure to be block diagonal, the blocks to have a bounded norm, or the blocks to be identical.

A common feature of these three problems is that, although they are easy to state, neither closed–form nor efficient algorithmic solutions are known. It is rather improbable that closed–form solutions to these problems are possible. On the other hand, algorithmic solutions do exist as we now argue.

All of the problems that we have described are finitely parametrized. They all involve the search for a controller (the — possibly partitioned — matrix K) which can be specified in terms of finitely many real parameters. In theory, it is thus possible to apply the following methodology: (a) parametrize the gain matrix K in terms of finitely many real coefficients; (b) express the matrix stability condition(s) in terms of the coefficients of the system(s) and of the controller; (c) use the Routh-Hurwitz test on the resulting characteristic polynomial(s). One is then left with a (large) set of multivariable polynomial inequalities that have to be simultaneously satisfied for some choice of the controller coefficients. Checking the existence of controller coefficients that satisfy this system of multivariable inequalities can be performed using the Tarski-Seidenberg elimination theory. The Tarski-Seidenberg elimination method leads, after a finite number of rational operations, to a yes-no answer regarding the existence of a solution. The method is systematic and amenable to computer implementation. Thus, all three problems described above are algorithmically solvable.

In this contribution we show that some of the above problems and their variations are very unlikely to allow for efficient algorithmic solutions. We adhere to the general consensus in computer science that identifies algorithmic efficiency with polynomial time computability. We then show that some of the above problems are NP-hard, meaning that every problem in NP can be reduced them. Thus, unless P=NP, these problems are not polynomial time solvable.

Our results will be proved as corollaries of the following main theorem: testing for the presence of a stable matrix in a family of matrices whose members have entries that are either fixed to some given real number or vary in the closed unit interval [−1, 1] is an NP-hard problem. This latter result complements a recent theorem of Nemirovskii who showed that testing for the stability of all elements of such a family of matrices is an NP-hard problem.