×

On the generation of random stable polynomials. (English) Zbl 1227.65008

Summary: We discuss various techniques for random generation of stable polynomials, both in discrete and continuous time. These different methods are presented in a unified framework – to provide a “global vision” of the potentials of random generation techniques for stable polynomials. We first show how general-purpose random sampling schemes can be adapted to the problem at hand and present specific techniques for generation, discussing pro et contra of these methodologies. We then demonstrate how a whole class of random generation mechanisms can descend in an almost direct way from classical stability analysis tests. Also, Matlab implementation issues are duly considered. Possible applications to control are indicated and illustrative results of simulations are provided.

MSC:

65C05 Monte Carlo methods
65D20 Computation of special functions and constants, construction of tables
33F05 Numerical approximation and evaluation of special functions
26C05 Real polynomials: analytic properties, etc.

Software:

Matlab; RACT
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ackermann, J.: Robust control. (2002)
[2] Akaike, H.: Statistical predictor identification. Ann inst stat math 22, 203-217 (1970) · Zbl 0259.62076
[3] Andrieu, C.; Doucet, A.: An improved method for uniform simulation of stable minimum phase real ARMA (p, q) processes. IEEE signal process lett 6, No. 6, 142-144 (1999)
[4] Antsaklis, P. J.; Michel, A. N.: Linear systems. (1997)
[5] Barmish, B. R.: New tools for robustness of linear systems. (1994) · Zbl 1094.93517
[6] Barmish, B. R.; Lagoa, C. M.: The uniform distribution: A rigorous justification for its use in robustness analysis. Math control signal syst 10, 203-222 (1997) · Zbl 0892.93042
[7] Beadle, E. R.; Djuric, P. M.: Uniform random parameter generation of stable minimum-phase real ARMA (p, q) processes. IEEE signal process lett 4, No. 9, 259-261 (1997)
[8] Benidir, M.; Picinbono, B.: Comparison between some stability criteria of discrete time filters. IEEE trans acoust speech signal process 36, No. 7, 933-1001 (1988) · Zbl 0653.93044
[9] Bharucha-Reid, A. T.; Sambandham, M.: Random polynomials. (1986) · Zbl 0615.60058
[10] Blanchini, F.; Sznaier, M.: A convex optimization approach to fixed-order controller design for disturbance rejection in SISO systems. Ieee tac 45, No. 4, 784-789 (2000) · Zbl 1004.93032
[11] Blondel, V. D.; Tsitsiklis, J. N.: A survey of computational complexity results in systems and control. Automatica 36, No. 9, 1249-1274 (2000) · Zbl 0989.93006
[12] Bobyleva, O. N.; Pyatnitskii, E. S.: Piecewise-linear Lyapunov functions and localization of spectra of stable matrices. Autom remote control 62, No. 9, 1417-1427 (2001) · Zbl 1093.34541
[13] Boyd, S. P.; Elghaoui, L.; Feron, E.; Balakrishnan, V.: Linear matrix inequalities in system and control theory. Philadelphia: SIAM (1994) · Zbl 0816.93004
[14] Burke, J. V.; Henrion, D.; Lewis, A. S.; Overton, M. L.: Stabilization via nonsmooth, nonconvex optimization. Ieee tac 51, No. 11, 1760-1769 (2006) · Zbl 1366.93490
[15] Calafiore, G.; Dabbene, F.: Control design with hard/soft performance specification: A Q-parameter randomization approach. Int J control 77, No. 5, 461-471 (2004) · Zbl 1061.93042
[16] Candés, E. J.; Recht, B.: Exact matrix completion via convex optimization. Found comput math 9, No. 6, 717-772 (2009) · Zbl 1219.90124
[17] Dabbene, F.; Polyak, B.; Tempo, R.: On the complete instability of interval polynomials. Syst control lett 56, 431-438 (2007) · Zbl 1118.93042
[18] Diaz-Barrero, J. L.; Egozcue, J. J.: Characterization of polynomials using reflection coefficients. Appl math E-notes 4, 114-121 (2004) · Zbl 1074.30006
[19] Djaferis, T. E.; Pepyne, D. L.; Cushing, D. M.: A new parameterization of stable polynomials. Ieee tac 47, No. 9, 1546-1550 (2002) · Zbl 1364.93589
[20] Durbin, J.: The Fitting of time series models. Rev inst int stat 28, 233-243 (1960) · Zbl 0101.35604
[21] Edelman, A.; Kostlan, E.: How many zeros of a random polynomial are real?. Bull am math soc 32, 1-37 (1995) · Zbl 0820.34038
[22] Fam, A. T.: The volume of the coefficient space stability domain of monic polynomials. In proc int symp circ syst, 1780-1783 (1989)
[23] Fam, A.; Meditch, J.: A canonical parameter space for linear systems design. Ieee tac 23, No. 3, 454-458 (1978) · Zbl 0377.93021
[24] Franke, J.: A Levinson-durbin recursion for autoregressivemoving average processes. Biometrika 72, No. 3, 573-581 (1985) · Zbl 0596.62083
[25] Gantmacher, F. R.: The theory of matrices. Providence: AMS (1959) · Zbl 0085.01001
[26] Girko, V. L.: Circular law. Theory probab appl 29, 694-706 (1984)
[27] Gryazina, E. N.; Polyak, B. T.: Stability regions in the parameter space: D-decomposition revisited. Automatica 42, No. 1, 13-26 (2006) · Zbl 1121.93028
[28] Hughes CP, Nikeghbali A. The zeros of random polynomials cluster uniformly near the unit circle. Report No: AIM 2004-11, available at http://www.arxiv.org/abs/math.CV/0406376. · Zbl 1144.30005
[29] Jarominek, W.: Investigation of linear systems of automatic control by means of determinant stability margin indices. In proc 1960 IFAC congress, London: butterworth 1, 76-84 (1961)
[30] Jury, E. I.: Inners and stability of dynamic systems. (1974) · Zbl 0307.93025
[31] Keel, L. H.; Bhattacharyya, S. P.: Robust stability and performance with fixed-order controllers. Automatica 35, No. 10, 1717-1724 (1999) · Zbl 0945.93600
[32] Lagoa CM, Sznaier M, Barmish BR. An algorithm of generating transfer functions uniformly distributed over H1 balls. In Proc CDC, Orlando, FL, 2001, pp. 5038-5043
[33] Lai, Y. S.: A generalized test for discrete system stability. IEEE trans acoust speech signal process 32, 1242-1243 (1984) · Zbl 0575.93057
[34] Levinson, N.: Thewiener RMS error criterion in filter design and prediction. J math phys 25, 261-278 (1947)
[35] Lipatov, A. V.; Sokolov, N.: Some sufficient conditions for stability and instability of continuous linear stationary systems. Automat remote control 39, 1285-1291 (1979) · Zbl 0427.93040
[36] Lovász, L.: Hit-and-run mixes fast. Math program 86, 443-461 (1999) · Zbl 0946.90116
[37] Manabe, S.: Coefficient diagram method. In proc. 14th IFAC symp automat control in aerospace, Seoul (1998)
[38] Mansour, M.; Kraus, F. J.: On robust stability of Schur polynomials. Inst autom control ind electron (1987)
[39] Mehta, M. L.: Random matrices. (2004) · Zbl 1107.15019
[40] Makhoul, J.: Linear prediction: a tutorial review. Proc IEEE 63, 561-580 (1975)
[41] Nemirovsky, A. S.: Several NP-hard problems arising in robust stability analysis. Math control signal syst 6, 99-105 (1993) · Zbl 0792.93100
[42] Nemirovskii, A. S.; Polyak, B. T.: Necessary conditions for the stability of polynomials and their use. Autom remote control 55, No. 11, 1644-1649 (1994) · Zbl 0854.93110
[43] Nurges, Ü.: Reflection coefficients of polynomials and stable polytopes. Ieee tac 54, No. 6, 1314-1318 (2009) · Zbl 1367.93441
[44] Nurges, Ü.: Robust pole assignment via reflection coefficients of polynomials. Automatica 42, 1223-1230 (2006) · Zbl 1122.93033
[45] Nurges, Ü.; Rüstern, E.: The distance from stability boundary and reflection vectors. In proc ACC, anchorage, AK, 3908-3913 (2002)
[46] Oppenheim, A. V.; Schafer, R. W.: Discrete-time signal processing. (1989) · Zbl 0676.42001
[47] Ya, I. Petrikevich: Randomized methods of stabilization of the discrete linear systems. Autom remote control 69, No. 11, 1911-1921 (2008) · Zbl 1163.93399
[48] Petrikevich, Ya.I.; Polyak, B. T.; Shcherbakov, P. S.: In proc IFAC workshop “adaptation and learning in control and signal processing” (ALCOSP’07). Fixed-order controller design for SISO systems using Monte Carlo technique (2007)
[49] Polyak, B.; Halpern, M.: Optimal design for discrete-time linear systems via new performance index. Int J adapt control signal process 15, No. 2, 129-152 (2001) · Zbl 0996.93060
[50] Polyak, B. T.; Shcherbakov, P. S.: Superstable linear control systems. I: analysis. Autom remote control 63, No. 8, 1239-1254 (2002) · Zbl 1094.93510
[51] Santhi, K. R.; Ponnavaiko, M.; Gangatharan, N.: A comparative study of stability testing approaches of two-dimensional recursive digital filters. J comput sci 4, No. 12, 976-981 (2008)
[52] Schüsslerh, W.: Astability theorem for discrete systems. IEEE trans acoust speech signal process 24, 87-89 (1976)
[53] Shcherbakov, P.; Dabbene, F.: In proc 3rd IEEE multiconference on systems and control, MSC’2009. On random generation of stable polynomials, 406-411 (2009)
[54] Silva, G. J.; Datta, A.; Bhattachaiyya, S. P.: PID controllers for time-delay systems. (2007)
[55] Smith, R. L.: Efficient Monte Carlo procedures for generating points uniformly distributed over bounded regions. Oper res 32, 1296-1308 (1984) · Zbl 0552.65004
[56] Sondergeld, K. P.: A generalization of the Routh-Hurwitz stability criteria and an application to a problem in robust controller design. Ieee tac 28, No. 10, 965-970 (1983) · Zbl 0532.93043
[57] Szegö, G.: Orthogonal polynomials. Providence: American mathematical society (1975) · Zbl 0305.42011
[58] Sznaier, M.; Lagoa, C. M.; Mazzaro, M. C.: An algorithm for sampling subsets of H1 with applications to risk-adjusted performance analysis and model (in)validation. Ieee tac 50, No. 3, 410-416 (2005) · Zbl 1365.93532
[59] Tempo, R.; Calafiore, G.; Dabbene, F.: Randomized algorithms for analysis and control of uncertain systems. London: Springer-verlag (2004) · Zbl 1079.93002
[60] Tremba, A.; Calafiore, G.; Dabbene, F.; Gryazina, E.; Polyak, B.; Shcherbakov, P.; Tempo, R.: RACT: randomized algorithms control toolbox for Matlab in proc 17th world congress of IFAC. Seoul, 390-395 (2008)
[61] Tsoi, A. C.: Inverse Routh-Hurwitz array solution to the inverse stability problem. Electron lett 15, No. 18, 575-576 (1979)
[62] Verriest, E. I.; Michiels, W.: Inverse Routh table construction and stability of delay equations. Syst control lett 55, No. 9, 711-718 (2006) · Zbl 1100.93040
[63] Zhu, Zh.; Man-Cho, So.A.; Ye, Y.: Fast and near-optimal matrix completion via randomized basis pursuit. Preprint (2009) · Zbl 1269.15031
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.