{'fraction_non_alphanumeric': 0.03957692140968399, 'fraction_numerical': 0.01244093805539902, 'mean_word_length': 4.491549631040228, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Robust pole placement with Moore's algorithm

We consider the classic problem of pole placement by state feedback. We adapt the Moore eigenstructure assignment algorithm to obtain a novel parametric form for the pole-placing gain matrix, and introduce an unconstrained nonlinear optimization algorithm to obtain a gain matrix that will deliver robust pole placement. Numerical experiments indicate the algorithm's performance compares favorably against several other notable robust pole placement methods from the literature.


I. INTRODUCTION
We consider the classic problem of pole placement for LTI systems in state space forṁ where, for all t ∈ R, x(t) ∈ R n is the state, and u(t) ∈ R m is the control input. A and B are appropriate dimensional constant matrices. We assume that B has full column rank. We let L = {λ 1 , . . . , λ ν } be a self-conjugate set of n complex numbers, with associated algebraic multiplicities M = {m 1 , . . . , m ν } satisfying m 1 + · · · + m ν = n. The problem of exact pole placement by state feedback (EPP) is that of finding a real matrix F such that the closed-loop matrix A + BF has non-defective eigenvalues in L, i.e F satisfies where Λ is a n × n diagonal matrix obtained from the eigenvalues of L, including multiplicities, and X is a non-singular matrix of closed-loop eigenvectors of unit length. If (A, B) has any uncontrollable modes, these are assumed to be included within the set L. The EPP problem has been studied for several decades, and the existence of such a matrix yielding diagonal Λ requires in particular m i ≤ m for all m i ∈ M is required. In this paper we shall assume (A, B, L, M) are such that at least one F exists that yields diagonal Λ. Notable early papers offering algorithms to obtaining the required gain matrix F include [3], which gave a method for single-input single output (SISO) system, but this was often found to be numerically inaccurate. Varga [4] gave a numerically reliable method to obtain F for multiple-input multiple output (MIMO) systems.
For SISO systems, F is unique, while for MIMO systems it is not, and this naturally invites the selection of F that achieves the desired pole placement and also possesses other desirable characteristics, such as minimizing the control input amplitude used, and improving numerical stability. In order to consider optimal selections for the gain matrix, it is important to have a parametric formula for the set of gain matrices that deliver the desired pole placement, and numerous such parameterizations have appeared. Bhattacharyya and de Souza [5] gave a procedure for obtaining the gain matrix by solving a Sylvester equation in terms of a n × m The classic eigenstructure assignment algorithm of B.C. Moore [9] quantified the freedom to simultaneously assign both the closed-loop eigenvalues, and also select the associated eigenvectors. As such it implicitly solved the EPP problem, but it did not explicitly provide a parametric formula for the pole-placing matrix, nor did it address any optimal pole placement problem. In this paper we adapt Moore's algorithm to obtain a simple parametric formula for the pole-placing gain matrix, in terms of an n × m parameter matrix. The method obtains the eigenvector matrix X by selecting eigenvectors from the nullspaces of the system matrices, and thus avoids the need for coordinate transformations.
The robust exact pole placement problem (REPP) involves solving the EPP problem and also obtaining F that renders the eigenvalues of A + BF as insensitive to perturbations in A, B and F as possible. Numerous results [10] have appeared linking the sensitivity of the eigenvalues to various measures of the conditioning of X, in terms of the Euclidean and Frobenius norms. This classic optimal control problem also has an extensive literature, and typically two approaches DRAFT have been used to obtain good robust conditioning.
Perhaps the best-known method for the REPP is that of Kautsky et al [7], which involved selecting an initial candidate set of closed-loop eigenvectors and then using a variety of heuristic methods to make these vectors more orthonormal. This method has been implemented as MATLAB R 's place command; this implementation includes a heuristic extension to accommodate complex conjugate pairs in L. This algorithm is also the basis of MATHEMATICA R 's KNVD command. The use of the place algorithm has become wide-spread in the control systems literature, and introductory texts advocating its use include [11] and [12], among many others.
Since the publication of [7], many alternative methods have been proposed for the REPP. Tits and Yang [13] revisited the heuristic methods of [7] and offered a range of improvements; the algorithms were shown to be globally convergent. Byers and Nash [14], Tam and Lam [15] and Varga [16] cast the problem as an unconstrained nonlinear optimization problem, in terms of the Frobenius conditioning, to be solved by gradient iterative search methods. [17] introduced a method for minimizing the 'departure from normality' robustness measure, which considers the size of the upper triangular part of the Schur form. Ait Rami et al [18] introduced a global constrained nonlinear optimal problem in terms of a Sylvester equation and showed that the solution could be approximated by a convex linear problem for which the authors gave an LMI-based algorithm.
Various authors have provided surveys comparing the performance of several of these algorithms. Sima et al [19] conducted testing of the algorithms from [4], [7] and [13] on collections of systems of varying dimensions; they concluded that the method of [13] generally gave superior Euclidean (2-norm) conditioning and also improved accuracy. [17] considered the eleven benchmark systems in the Byers-Nash collection (see Section IV for a discussion of this collection), and compared the author's proposed methods, based on the Schur form of the open loop systems, with those of [7] and [13] against a range of robustness measures. The methods of [17] generally gave inferior results to those of [7] and [13], with respect to the Frobenius conditioning. [18] tabulated figures results for the Frobenius conditioning performance of methods [7], [13], [14] and [16]. However, the conditioning values were compiled directly from these papers. Since some of these methods were introduced into the literature more than two decades ago, and noting that computational resources have improved dramatically over this time, using values from original publications may unfairly disadvantage the earlier methods, in particular [14]. DRAFT In this paper we add to this extensive literature in several ways. In Section 2 we introduce our parametric form for the pole-placing gain matrix that solves the EPP. The formula is an adaptation of the pole placement method of Moore [9]; the novelty here is to use Moore's method to obtain a parametric formula for both X, the matrix of eigenvectors and F , the pole-placing gain matrix.
We further show the parametric form is comprehensive, in that it generates all possible X and F that solve (2), for the case where the eigenvalues have multiplicity of at most m. In Section 3 we utilize this parametric form to propose an unconstrained optimization problem to seek solutions to the REPP, to be solved by gradient search methods. Our approach most closely resembles that of [14], but with a different parametric formulation for the pole-placing gain matrix.
In Section 4 we select five of the most prominent methods for the REPP [7], [13], [16], [14] and [18], and conduct extensive numerical testing to compare their performance against our method. The first three of these were chosen as they are widely used in the forms of the MATLAB R toolboxes place, robpole and sylvplace respectively. [14] has attracted a large number of citations over more than two decades, and [18] is the most recent publication to offer a novel approach for the REPP. All methods were implemented in MATLAB R 2012a, running on the same computing platform. In addition to conditioning, we also compare their accuracy, matrix gain and runtime. Finally, Section 5 offers some conclusions as to the relative performance of these six methods; our method will be shown to offer some performance advantages over all the other methods surveyed.

II. POLE PLACEMENT VIA MOORE'S ALGORITHM
We now revisit Moore's method [9] and adapt it to give a simple parametric formula for a gain matrix F that solves the pole placement problem, in terms of an arbitrary real parameter matrix. We begin with some definitions and notation. For each i ∈ {1, . . . , ν}, we define the where I n is the identity matrix of size n. We let T i be a basis matrix for the nullspace of S(λ i ), Finally, for any real or complex matrix X of with at least n + m rows, we define matrices π(X) and π(X) by taking the first n and last m rows of X, respectively. Proposition 2.1: Let the eigenvalues {λ 1 , . . . , λ ν } be ordered so that, for some integer s, the first 2s values are complex while the remaining are real, and for all odd i ≤ 2 s we have and let For almost every choice of the parameter matrix K, the rank of X is equal to n. The set of all m × n gain matrices F satisfying (2) is parameterised in K as where K is such that rank(X(K)) = n.
Proof: For any given K, let M(K) be partitioned according to where each V ′ i and W ′ i are matrices of dimensions n × m i and m × m i respectively, such that DRAFT and define W i similarly. Then matrices X, V and W in (5)-(7) may be written as . Now assume K is such that rank(X(K)) = n; then V (K) is non-singular, and we can obtain (10) can be written as Thus we obtain (2). To see that this formula is comprehensive, we let F be any real gain matrix satisfying (2). The nonsingular eigenvector matrix X is comprised of column vectors V ′ i of dimension n × m i corresponding to each eigenvalue, such that (13) and (14) hold. Applying . . , 2 s}, implies the conjugacy of K i and K i+1 . Thus we obtain M(K) in (4) yielding F in (8).
Finally we let K be arbitrary parameter matrix and consider the rank of X(K). We introduce Φ = π(T ) and denote Φ 1 , . . . , Φ ν as a basis for im Φ. If rank(X(K)) is smaller than n, then one column of the matrix [Φ 1 K 1,1 . . . Φ ν K ν,mν ] is linearly dependent of all the remaining ones.
(Here we have used K i,j to denote the j-th column of K i ). For brevity, let us assume this is the last column. Then there exist n − 1 coefficients α 1,1 , . . . , α ν,mν −1 (not all equal to zero) for has a unique solution in K ν,mν . As K ν,mν is an s ν -dimensional parameter vector, (15) constrains K ν,mν to lie upon an (s ν − 1)-dimensional hyperplane, which has empty interior. Thus the set of parameters K that lead to a loss of rank in X(K) is given by the union of at most n hyperplanes DRAFT of empty interior. This set therefore has empty interior, and thus also zero Lebesgue measure.
Thus we see that X(K) and hence V (K) are non-singular for almost all choices of the parameter matrix K.
The above formulation takes its inspiration from the proof of Proposition 1 in [9], and hence we shall refer to (5)-(8) as the Moore parametric form for X and F . We note however that [9] only considered the case of distinct eigenvalues, and did not offer any explicit parametric formula for the pole-placing gain matrix. Moreover, it did not show that all matrices X and F solving (2) could be parameterized in the above manner.
It is interesting to compare this parametric form with that of [7], in which the eigenvectors comprising X were obtained from the nullspaces of the matrices where y i and x i are the left and right eigenvectors associated with λ i . For the case where A+BF is non-defective but has repeated eigenvalues, see [20] for a definition of the corresponding condition numbers. Furthermore, we have [7] c ∞ := max where κ 2 (X) = X 2 X −1 2 and κ f ro (X) = X f ro X −1 f ro are the condition numbers of the matrix of eigenvectors X with respect to the Euclidean and Frobenius norms. Following [18], [14], [15], we propose to address the REPP problem by minimizing the condition number of X with respect to Frobenius norm. The objective function to be minimized is where the input parameter matrix K is defined as in Proposition 2.1. Note it is possible to reduce the Frobenius norm of a matrix X by suitably scaling the lengths of its column vectors. When X DRAFT is the solution to (2), such scaling does not improve the eigenvalue conditioning in (16). Hence we assume that the column vectors of X have been normalised.
As pointed out in [14], for efficient computation we can study an alternative objective function because the two objective functions are equivalent. An imported related problem is that of minimizing the norm of the gain matrix F . The minimum gain robust exact pole placement problem (MGREPP) involves simultaneously minimizing both the conditioning and the matrix gain via the weighted objective function where α is a weighting factor, with 0 ≤ α ≤ 1. Minimizing f 3 involves a gradient search employing the first and second order derivatives of κ f ro (X(K)) and F (K) f ro ; expressions for these were given in [1].

IV. PERFORMANCE COMPARISON OF ROBUST POLE PLACEMENT METHODS
In this section we conduct extensive numerical experiments to compare the performance of our method against those of [7], [18], [13], [14] and [16]. To provide a comprehensive contemporary survey, we implemented these algorithms on the same modern computer, an Intel R Core TM Quad CPU, Model Q9400 at 2.66 GHz with 3326 MB of RAM running Windows TM XP and MATLAB R 2012a. Implementation of [7] was done with MATLAB R 's place command. For [13] and [16], we used the robpole and sylvplace MATLAB R toolboxes, kindly provided to us by the authors.
For [14], [18] and our own method, we wrote MATLAB R toolbox implementations for each.
The [18] algorithm requires an LMI solver; we chose the public-domain cvx toolbox [21]. We shall refer to these as byersnash, rfbt and span (our own method). The names are derived from the names of the respective authors.
To obtain a fair comparison between these methods, we need to consider the runtime allocated to them. The methods of [14], [16] and our proposed method all employ gradient iterative searches, so the values they deliver are contingent upon the initial condition (input parameter matrix K) used. The sylvplace toolbox randomly generates an initial condition, and thus offers different outputs (different F ) each time it is run. To obtain repeatable results, we provided DRAFT the byersnash and span toolboxes with a pre-specified collection of input parameter matrices K composed of canonical vectors. The output shown from each of byersnash, sylvplace and span is the best result from all the initial conditions searched within the allocated runtime. By contrast place, robpole and rfbt all employ a designated starting point, and hence their runtime is simply the time taken to execute their method.

A. Robust conditioning comparison using the Byers and Nash benchmark examples
Byers and Nash [14] gave a collection of eleven benchmark example systems, and many authors, including [13], [16] and [18] used these examples to compare the performance of their pole placement methods. Following this well-established tradition, our first set of comparisons employs these well-known examples. The results are given in Table I. We have used κ f ro (X) as the performance measure, and we also show the matrix gain used.
The average runtimes for place, robpole and rfbt for the 11 sample systems were 0.05, 0.095 and 14.1 seconds, respectively. For byersnash, sylvplace and span we arbitrarily set the runtime to be n seconds, where n is the system dimension, leading to average runtimes of 4.5 seconds, this being the average of the system dimensions in the collection.
Ignoring differences in the conditioning of smaller than 1%, we conclude that byersnash and span had the best or equal best conditioning in all 11 examples. sylvplace and rfbt had the best or equal best in 7 cases, while robpole had best or equal best in 5 cases. Finally place gave the best or equal best in 4 cases. place and robpole had the shortest runtimes, while rfbt had noticeably the longest. We note that the conditioning numbers given here differ significantly from those that were published in [14] and [18]. This may be explained by the fact that these authors did not require the columns of X to be of unit length. Since methods [7] and [13] normalise the columns of X, this is essential for a fair comparison of all six methods.

B. Robust conditioning comparison with sets of higher-dimensional systems
To probe more deeply into the performance delivered by these six methods, we need to and matrix gain of each method, we computed, for each system j ∈ {1, . . . , 500} and each method ⋆ ∈ {place, robpole, byersnash, sylvplace, rfbt, span}, • κ f ro (⋆, j): the Frobenius conditioning of method ⋆ for the j-th system; • c ∞ (⋆, j): the c ∞ conditioning of method ⋆ for the j-th system; • ∆(⋆, j): the accuracy of method ⋆ on the j-th system, equal to the largest absolute value difference between each eigenvalue of A + BF and the corresponding λ i in L.
• F f ro (⋆, j): the Frobenius norm of F from Method ⋆ on system j.
Noting that place is the industry standard for the REPP, we chose to compare all the other methods according to their ability to improve upon place, and computed comparative performance indices relative to place for each method, and for each performance criterion, as follows: (1 − index(⋆, ∆)) 500 = 500 j=1 ∆(⋆, j) ∆(place, j) (23) The results show that the best performance for robustness and gain minimisation were given by span, byersnash and sylvplace. Both sylvplace and rfbt were less accurate than place, by several orders of magnitude in the case of rfbt, which also required substantially longer runtime.
DRAFT While all methods offered improved conditioning with reduced gain over place, this was reduced for the larger values of m, which may be attributed to the improved performance of place when it has more control inputs to work with.

C. Weighted gain minimisation and conditioning problem
Among the methods in our survey, only [16] (sylvplace) considered the MGREPP problem (20). Our Survey 3 compares the performance of sylvplace and span for the same 500 sample systems used in Survey 2, with m = 2, for several different values of the weighting factor α.
We again gave span and sylvplace 20 seconds of runtime per sample system, and computed the performance improvement indices (21)-(24) relative to the gain matrix delivered by place; again larger figures indicate greater improvement. The results are shown in Table III. Both methods were able to offer significant reductions in gain, at the price of some reduction in the robustness measures, relative to the pure robustness problem (α = 1). However span did so with far superior accuracy. Considering the impact of different values of the weighting factor, we see that for α = 0.1, there was little difference in the conditioning, and only slight improvement in the matrix gain. For α → 0 we observed up considerable reduction in the matrix gain, but this eventually comes at the cost of significantly inferior conditioning. These results suggest values around α = 0.001 can give a good balance between these two criteria.

D. Systems with uncontrollable modes
The EPP problem remains well-posed for systems with uncontrollable modes, provided these are included within the set L. The methods place, sylvplace, robpole, rfbt all assumed controllability of the system, as part of their problem formulation. In principle this involves no loss of generality, since the application of a Householder staircase transformation can decompose any system into its controllable and uncontrollable parts. Nonetheless is it is interesting to consider the ability of these toolboxes to accommodate uncontrollable modes. In our final survey, we obtained 100 systems (A, B), with n = 3 and m = 2, that contained one uncontrollable mode.
We then chose L to include this mode, plus one pair of complex conjugate modes. We defined failure to solve the EPP as being any one of (i) an error was returned upon execution of the algorithm, (ii) any of the closed-loop poles differed by more than 5% from their desired location, and (iii) the gain of F was undefined or greater than 10 10 . We observed failures as follows: place, DRAFT sylvplace, robpole and rfbt had 100, 98, 30 and 12 failures, respectively; we concluded these toolboxes in their present form cannot reliably solve the EPP in these conditions. byersnash and our method span had no failures; we attribute their superior reliability to their usage of nullspace methods. Uncontrollable modes increase the column dimension of the corresponding nullspace basis matrix; for byersnash and span this is readily accommodated by adjusting the row dimension of the parameter matrix.

V. CONCLUSION
We have introduced a parametric formula for the exact pole placement of linear systems via state feedback, derived from Moore's classic eigenstructure method. This parametric form was used to formulate the robust and minimum gain exact pole placement problem as an unconstrained optimization problem, to be solved by gradient iterative methods.
The method was implemented as a MATLAB R toolbox called span, and its performance was compared against several other methods from the classic and recent literature. All methods considered gave superior performance to the widely used MATLAB R place command, albeit with somewhat longer runtime. When the Frobenius conditioning of the eigenvector matrix is used as the robustness measure, the best performance was provided by the our proposed method, and also the Byers-Nash method. The results suggest that, in comparison with heuristic methods, gradient iterative methods are best able to take advantage of the high levels of computational power that are now widely available. They also suggest that methods based on nullspaces of appropriate system matrices may offer superior accuracy of pole placement to those adopting Sylvester matrix transformations. For a given system (A, B, L, M), byersnash and span will in general yield quite different gain matrices, offering different performance values, so both methods should be considered for optimal performance. While Byers and Nash considered only the robustness, our method is able to accommodate a combined robustness and gain minimization approach, enabling the designer to obtain significantly reduced gain in exchange for somewhat inferior conditioning.
The authors would like to thank Andre Tits and Andreas Varga for providing us with copies of their robpole and sylvplace toolboxes, and Ben Chen for bringing the classic eigenstructure assignment paper by B.C. Moore [9] to our attention. We also thank the anonymous reviewers for some constructive suggestions. DRAFT [7] byersnash [14] robpole [13] κ f ro (X)