Numerical algorithms for inverse eigenvalue problems arising in control and nonnegative matrices
Kaiyang Yang · ANU Open Research (Australian National University) · 2006
An Inverse Eigenvalue Problem (IEP) is to construct a matrix which possesses both proscribed eigenvalues and desired structure. Inverse eigenvalue problems arise in broad application areas such as control design, system identification, principle component analysis, structure analysis etc. There are many different types of inverse eigenvalue problems and despite of a great deal of research effort being put into this topic many of them are still open and are hard to be solved. In this dissertation, we propose optimization algorithms for solving two types of inverse eigenvalue problems, namely, the static output feedback problems and the nonnegative inverse eigenvalue problems. Consequently, this dissertation is essentially composed of two parts. In the first part, three novel methodologies for solving various static output feedback pole placement problems are presented. The static output feedback pole placement framework encompasses various pole placement problems. Some of them are NP-hard, for example, classical pole placement [31]. That is, an efficient (i.e. polynomial time) algorithm that is able to correctly solve all instances of the problem cannot be expected. In this dissertation, a projective methodology, two trust region methods and a Gauss-Newton method are proposed to solve various instances of the pole placement problems. In the second part, two novel methodologies for solving nonnegative/stochastic inverse eigenvalue problems are presented. Nonnegative matrices arise in many application areas and attract a lot of research in matrix analysis community. Stochastic xvi inverse eigenvalue problem has potential applications in Markov chains and the theory of probability etc. In the small dimensional cases, i.e., the dimension of the resulting matrix is less or equal to 5, there exists necessary and sufficient conditions to fully characterize the problem. However when the dimension grows larger, the problem becomes much harder to be solved. The existing necessary conditions are too general and sufficient conditions are too specific. In general the proofs of the sufficient conditions are nonconstructive. In this dissertation, a projective methodology and two Newton type methods are proposed which are widely applicable to various nonnegative inverse eigenvalue problems. All of the problems considered are important and challenging in their area. The optimization methodologies are clearly stated and the algorithms are intensively tested. More than the problems being solved in this thesis, the algorithms appear to be quite useful in a lot more related problems, i.e., inverse eigenvalue problems subject to different structural constraints.