Eduardo D. Sontag

M. Vidyasagar

Jan C. Willems

Communication and Control Engineering Series, ISBN: 1-85233-044-9

From the cover: "This volume collects a discussion of more than fifty open problems which touch upon a variety of subfields, including: chaotic observers, nonlinear controllability, discrete event and hybrid systems, neural network learning, matrix inequalities, Lyapunov exponents, and many other issues. Proposed and explained by leading researchers, they are offered with the intention of generating further work, as well as inspiration for many other similar problems."

From Zentralblatt Math review 0945.93005: "History will tell if the proposed
problems will be solved through tricks or will open vast areas of knowledge
and if the relatively recent domain of systems science is mature enough so that
the open problems have the expected depth. At any rate, this book provides a
welcome goal-oriented research drive to the field.''

Dirk Aeyels, Joan Peuteman

**2. Positive system realizations**

Brian D. O. Anderson

**3. System approximation in the 2-norm**

A.C. Antoulas

**4. Is it possible to recognize local controllability
in a finite number of differentiations?**

Andrei A. Agrachev

From: Andrei A. Agrachev <agrachev@de.mian.su>

1998-10

I have found a very unpleasant misprint in my
chapter: Page 15, last line.

Written: ...0\in{\cal A}_t(N_3)...

Must be: ...0\in int\,{\cal A}_t(N_3)...

**5. Open problems in sequential parametric estimation**

Er-Wei Bai, Roberto Tempo, Yinyu Ye

**6. Conditions for the existence and uniqueness
of optimal matrix scalings**

Venkataramanan Balakrishnan

**7. Matrix inequality conditions for canonical
factorization of rational transfer function matrices**

Venkataramanan Balakrishnan

**8. Open problems in l_1 optimal control**

Bassam Bamieh, Munther A. Dahleh

**9. Efficient neural network learning**

Peter L. Bartlett

**10. Mechanical feedback control systems**

Anthony M. Bloch, Naomi Ehrich Leonard, Jerrold
E. Marsden

**11. Three problems on the decidability and
complexity of stability**

Vincent D. Blondel, John N. Tsitsiklis

**Open Problem 1** The static output feedback problem is the problem
of deciding for given matrices A, B and C whether there exists a matrix
K such that A+BKC has all its eigenvalues in the left half plane.
Can the static output feedback problem be decided
in time polynomial in the size of the matrices A, B and C?

A solution of a modified formulation of the Open Problem 1 (Static Output Feedback) is claimed by Mehran Mesbahi.

From: Mehran MESBAHI <mesbahi@grover.jpl.nasa.gov>

1999-01-01

We have shown that a semi-definite programming
approach can be adopted to determine the least order dynamic output feedback
which stabilizes a given linear time invariant plant. The problem addressed
includes as a special case, the static output feedback problem. The direct
implication of this result is that both the least order dynamic output
feedback and static output feedback synthesis problems are polynomial-time
solvable in the real model of computation.

A preprint of the contribution containing this
result can be downloaded from:

http://www.cds.caltech.edu/~mesbahi.

A. Megretski claims that there is something wrong in the solution proposed by M. Mesbahi, his argument is below.

From: Alexandre MEGRETSKI <ameg@mit.edu>

1999-06-04

Title: In the LMI's resulting from the static output feedback problem,
minimization of trace does not necessarily lead to minimization of rank.

It is well known that the problem of finding
$K$ such that $A+BKC$ is a Hurwitz matrix, is equivalent to finding matrices
$P,Q>0$ such that the LMI conditions \EQ{A}{ B_{\perp}'(AP+PA')B_{\perp}\le-\e
I,\C_{\perp}'(A'Q+QA)C_{\perp}\le-\e I,\ X\ge0} are satisfied for some
$\e>0$, and the matrix \[ X=\AR{cc}{P&I\\I&Q}\ge0\] has minimal
possible rank, where $B_{\perp}$ and $C_{\perp}$ are the ``orthogonal complements''
to $B$ and $C$ respectively, i.e. matrices with a maximal number of linearly
independent columns such that \[B'B_{\perp}=0,\ \ CC_{\perp}=0.\] In fact,
static feedback stabilization is possible if and only if there exist $P,Q$
satisfying \rf{A} such that the rank of $X$ equals $n$ (where $n$ is the
size of $A$), i.e. such that $PQ=I$.

In a paper by Mesbahi, it was claimed that minimization
of the trace of $P+Q$ subject to \rf{A} will automatically lead to minimization
of rank of $X$. The following is a counterexample to the statement. Take
\[ A=\AR{cc}{1&t\\-t&0},\ B=C'=\AR{c}{0\\1},\] where $t>1$ and
$t\approx1$ (one can use $t=1.005$, for example).

Then the associated static output feedback problem
has a solution $K=-0.5(1+t^2)$. On the other hand, minimization of the
trace of $P+Q$ subject to \rf{A} {\em and} $PQ=I$ yields a minimum of $4t(t^2-1)^{-1/2}$.
Finally, it can be shown that minimization of the trace of $P+Q$ subject
to \rf{A} with $\e=0$ but {\em without}the condition $PQ=I$ yields a strictly
lower minimum.

For example, with $t=1.005$, we have $4t(t^2-1)^{-1/2}\approx40.1498$
while the matrices \[Q=\AR{cc}{1.711&1.7031\\1.7031&3.08},\P=\AR{cc}{1.711&-1.7031\\-1.7031&3.08}\]
satisfy \rf{A} with $\e=0.0001$ and have the total trace of $9.582$.

Therefore, minimization of the trace of $P+Q$
subject to \rf{A} will not lead to the minimization of the rank of $X$
in the example.

From: Mehran MESBAHI <mesbahi@aem.umn.edu>

1999-06-08

I have received comments/suggestions/corrections
from the reviewers which have to be incorporated in the paper- if all goes
well, I will post the update as soon as these corrections are included-
otherwise I will write an appendix to the paper, explaining the problems
and why they could not be resolved.

From: Mehran MESBAHI <mesbahi@grover.jpl.nasa.gov>

2001-01-22

Please add a note under my entry, as to the availability
of a recent version of my paper which can be found at http://www.aem.umn.edu/people/faculty/mesbahi/papers/ofp.ps

**Open Problem 2**
For what values of n and m is ``stability of all infinite
products" decidable?

From: Vincent Blondel

2001-10

Considerable progress has been made on this problem and
on its connections with the finiteness conjecture. In particular, the finiteness
conjecture has been shown to be false in:

Asymptotic
height optimization for topical IFS, Tetris heaps, and the finiteness conjecture,
to appear in the Journal of the American Mathematical Society.

**12. Simultaneous stabilization of linear systems and
interpolation with rational functions**

Vincent D. Blondel

From: Vincent Blondel

2001-10

Solution to one of the problems appears in:

Solution to the "Champagne problem" on the simultaneous stabilisation of three
plants, Systems & Control Letters, Volume 37, Issue 3, July 1999, Pages 173-175
Vijay V. Patel.

**13. Forbidden state control synthesis for timed Petri
net models**

R.K. Boel, G. Stremersch

**14. On matrix mortality in low dimensions**

Olivier Bournez, Michael Branicky

**15. Entropy and random feedback**

Stephen P. Boyd

**16. A stabilization problem**

Roger Brockett

From: Luc MOREAU <lmoreau@ensmain.rug.ac.be>

1999-12-20

Together with Dirk AEYELS, I have written down a constructive
solution for the single input single output second order case. Details may be
found in:

L. Moreau and D. Aeyels Stabilization by means of periodic
output feedback Conference Proceedings, 38th IEEE Conference on Decision and
Control, Phoenix, Arizona, USA, December 7-10, 1999, pp. 108-109

and in the manuscript

L. Moreau and D. Aeyels A note on periodic output feedback
stabilization.

The manuscript is available at:http://ensmain.rug.ac.be/~lmoreau/pub_lm.html

From: A. Akutowicz; in the Zentralblatt review of the book (review number 0945.93005)

2001

Let us observe that the problem of R. Brockett i.e. global
output stabilization of a linear observable and controllable system via a nonautonomous
gain (``It seems that little is lost by assuming that'' \dots{} the gain ``is
periodic'') could be treated through the periodic Riccati equation but one could
require more than stabilization like determination of the characteristic or
Lyapunov exponents and require a construction of the gain (R. Brockett asks
about conditions on existence of the gain). In the periodic case, the problem
has been treated in the reviewer's thesis.

**17. Spectral factorization of a spectral density with
arbitrary delays**

Frank M. Callier, Joseph J. Winkin

From: Joseph WINKIN <Joseph.Winkin@fundp.ac.be>

1999-03-11

The paper "The spectral factorization problem for multivariable
distributed parameter systems" by Frank M. Callier and Joseph J. Winkin contains
a detailled solution of the proposed problem. It will appear in the Journal
of Integral Equations and Operator Theory.

A postscript version of the paper is available from:

http://www.fundp.ac.be/~jwinkin/calwinIEOT.ps

The spectral factorization problem for multivariable distributed parameter systems, F.M. Callier & J. Winkin, Integral Equations and Operator Theory, Vol. 34, 1999, pp. 270-292.

**18. Lyapunov exponents and robust stabilization**

F. Colonius, D. Hinrichsen, F. Wirth

**19. Regular spectral factorizations**

Ruth F. Curtain, Olof J. Staffans

**20. Convergence of an algorithm for the Riemannian
SVD**

Bart De Moor

**21. Some open questions related to flat nonlinear
systems**

Michel Fliess, Jean Levine, Philippe Martin, Pierre Rouchon

**22. Approximation of complex $\mu $**

Minyue Fu

**23. Spectral value sets of infinite-dimensional systems**

E. Gallestey, D. Hinrichsen, A. J. Pritchard

**24. Selection of the number of inputs and states**

Christiaan Heij

**25. Input-output gains of switched linear systems**

J. P. Hespanha, A. S. Morse

**26. Robust stability of linear stochastic systems**

D. Hinrichsen, A. J. Pritchard

**27. Monotonicity of performance with respect to its
specification in Hinfinity control**

Hidenori Kimura

**28. Stable estimates in equation error identification:
An open problem**

Roberto Lopez-Valcarce, Soura Dasgupta

**29. Elimination of latent variables in real differential
algebraic systems**

Iven Mareels, Jan C. Willems

**30. How conservative is the circle criterion?**

Alexandre Megretski

From: Siegfried M. Rump <rump@tu-harburg.de>

2001-03-08

Part 3 of the problem 30 is solved in the following way:

1) The statement is true for gamma = (3+2sqrt(2))*n
, i.e., for every circulant H with sigma_max(H)>=gamma there exists a nonzero
vector x with | H x | >= | x | .

2) There exists a sequence of matrices H_n with
sigma_max(H_n) >= 1/2 n for n odd, and sigma_max(H_n) >= 1/4 n for n even such
that there does not exist a nonzero vector x with | H_n x | >= |
x | .

Therefore the best possible gamma is known up to a constant
factor. The solution will be published in

S.M. Rump: Conservatism of the Circle Criterion - Solution
of a problem posed by A. Megretski, to appear in IEEE Trans. Autom. Control, scheduled
9/2001.

Conservatism of the circle criterion---solution of a problem posed by A. Megretski, IEEE Trans. Automat. Control 46 (2001), no. 10, 1605--1608.

From: Alexandre Megretski <ameg@MIT.EDU>

2001-03-09

I am quite sure (checked this many times) that the answer
to Problem 3 in my article "How conservative is the circle criterion?" is that
SUCH A CONSTANT (not depending on n) DOES NOT EXIST !!! I apologize for
not reporting this earlier, but the only conclusion from the negative result
is that Problem 3, unfortunately, is irrelevant to the solution of the more
important questions 1 and 2, so I did not make an effort of making this public).
I will be glad to provide a construction of a sequence of matrices H_n for which
gamma grows with n up to infinity.

Alexandre Megretski has provided the construction described above. A file (in pdf) describing the construction is available: problem30.pdf.

**31. On chaotic observer design**

Henk Nijmeijer

**32. The minimal realization problem in the max-plus
algebra**

Geert Jan Olsder, Bart De Schutter

From: Vincent Blondel <blondel@inma.ucl.ac.be>

1998-12-20

The problem is shown to be NP-hard in the preprint: ``The
presence of a zero in an integer linear recurrent sequence is NP-hard to decide
" Vincent Blondel, Natacha Portier. The preprint is available at: http://www.inma.ucl.ac.be/~blondel/publications/

The presence of a zero in an integer linear recurrent sequence is NP--hard to decide, V. D. Blondel, N. Portier, To appear in Linear Algebra and Its Applications.

**33. Input design for worst-case identification**

Jonathan R. Partington

**34. Max-plus-times linear systems**

Max Plus

**35. Closed-loop identification and self-tuning**

Jan Willem Polderman

**36. To estimate the L2-gain of two dynamic systems**

Anders Rantzer

**37. Open problems in the area of pole placement**

Joachim Rosenthal, Jan C. Willems

**38. An optimal control theory for systems defined
over finite rings**

Joachim Rosenthal

**39. Re-initialization in discontinuous systems**

J.M. Schumacher

**40. Control-Lyapunov functions**

Eduardo D. Sontag

**41. Spectral Nevanlinna-Pick Interpolation**

Allen R. Tannenbaum

**42. Phase-sensitive structured singular value**

André L. Tits, V. Balakrishnan

**43. Conservatism of the standard upper bound test**

Onur Toker, Bram de Jager

Prof. Megretski has announced at the CDC session (December 1998) that this problem is now solved. We have contacted the proposers. Information is still lacking but will be provided as soon as available.

From: Onur TOKER <onur@ccse.kfupm.edu.sa> and Alexandre MEGRETSKI <ameg@mit.edu>

1999-02-25

The problem is solved in the recent preprint by Sergei
Treil (prepared when he was on sabbatical at LIDS, MIT).

The paper can be downloaded from: http://www.math.msu.edu/~treil/papers/mu/mu-abs.html.

**44. When does the algebraic Riccati equation have
a negative semi-definite solution?**

Harry L. Trentelman

**45. Representing a nonlinear input-output differential
equation as an input-state-output system**

A.J. van der Schaft

**46. Shift policies in QR-like algorithms and feedback
control of self-similar flows**

Paul Van Dooren, Rodolphe Sepulchre

**47. Equivalences of discrete-event systems and of
hybrid systems**

J.H. van Schuppen

**48. Covering numbers for input-output maps realizable
by neural networks**

M. Vidyasagar

**49. A powerful generalization of the Carleson measure
theorem?**

George Weiss

From: Dmitry Kalyuzhniy-Verbovetzky (in Zentralblatt reviews)

2000

Partington, Jonathan and Weiss, George, Admissible observation
operators for the right-shift semigroup, Math. Control Signals Systems 13 (2000),
no. 3, 179--192.

Consider a continuous-time linear system whose state space is a complex Hilbert space $X$, and whose output space is complex one-dimensional. Let $A$ be its main operator, i.e., the generator of the evolution semigroup of operators $T\sb t\colon x\sb 0\mapsto x(t)\ (x\sb 0\in D(A))$ in $X$, and $C$ be its observation operator, i.e., the output signal $y$ is generated by this system by the formula $y(t)=Cx(t), t\geq 0$. The operator $C$ is called infinite-time admissible if there is a constant $m\sb 0>0$ such that $\Vert y\Vert \sb {L\sp 2[0,\infty )}\leq m\sb 0\Vert x\sb 0\Vert $ for any $x\sb 0\in D(A)$, i.e., the operator from $D(A)$ to $C[0,\infty )$ defined by $y(t)=CT\sb tx\sb 0$ has a bounded extension to an operator $\Psi \colon X\to L\sp 2[0,\infty )$. If $C$ is infinite-time admissible, then the estimate $\Vert C(sI-A)\sp {-1}\Vert \sb {{\scr L}(X,C)}\leq m/\sqrt{{\rm Re}\,s}$ holds for any $s$ in the right half-plane, with $m=m\sb 0/\sqrt{2}$. It was conjectured by the second author [in Estimation and control of distributed parameter systems (Vorau, 1990), 367--378, Birkhauser, Basel, 1991; MR 93a:93065] that the converse implication is also true. While this conjecture is still open for the general case of a strongly continuous semigroup, it was proved for some particular cases, namely, for normal semigroups [op. cit.], and for exponentially stable right-invertible semigroups [G. Weiss, in Open problems in mathematical systems and control theory, 267--272, Springer, London, 1999; see MR 2000g:93003 CMP 1 727 973 ]. In the paper under review, it is proved that this conjecture is true for the right-shift semigroup on $L\sp 2[0,\infty )$. The authors derive this result using Fefferman's theorem on boundedness of the Hankel operator constructed by a BMO-function.

From: Hans Zwart <twhans@math.utwente.nl>

2000-10-18

The conjecture that was posed as an open problem by George
Weiss in Chapter 49 of ``Open Problems in Mathematical Systems and Control Theory''
seems to be completely solved. In general, it appears to be false, as is shown
by Birgit Jacob and Hans Zwart in ``Disproof of two conjectures of George Weiss'',
Memorandum No. 1546, Faculty of Mathematical Sciences, University of Twente, The
Netherlands. However, there are some very nice special cases for which the conjecture
holds. Apart from the cases that were already mentioned by George Weiss in his
open problem paper, it has recently be shown by Birgit Jacob and Jonathan Partington
that the conjecture holds for contraction semigroups, see B. Jacob and J. Partington,
The Weiss conjecture on admissibility of observation operators for contraction
semigroups, to appear in Integral Equations and Operator Theory.

Jacob, Birgit; Partington, Jonathan R. The Weiss conjecture on admissibility of observation operators for contraction semigroups. Integral Equations Operator Theory 40 (2001), no. 2, 231--243.

**50. Lyapunov theory for high order differential systems**

Jan C. Willems

**51. Performance lower bound for a sampled-data signal
reconstruction**

Yutaka Yamamoto, Shinji Hara

From: Leonid Mirkin <mirkin@techunix.technion.ac.il>

28-10-2002

Please find attached the PDF version of my paper "Yet
Another H-inf Discretization", coauthored by Gilead Tadmor. We believe
that the paper (implicitly) solves Open Problem 51 from the book "Open
Problems in Mathematical Systems and Control Theory" (we show that the
problem can be always reduced to an equivalent discrete-time H-inf problem,
solution to which is standard). The paper is also available at: http://meeng.technion.ac.il/Research/TReports/2002/ETR-2002-03.html

**52. Coprimeness of factorizations over a ring of distributions**

Yutaka Yamamoto

**53. Where are the zeros located?**

Hans Zwart