Open Problems in Mathematical Systems and Control Theory

Vincent D. Blondel
Eduardo D. Sontag
M. Vidyasagar
Jan C. Willems

Springer Verlag, London, 1999
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.''



1. Uniform asymptotic stability of linear time-varying systems
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