Electromagnetic Modeling of the Propagation Characteristics of Satellite Communications Through Composite Precipitation Layers Science and Technology, 8 (2003) 27-31 © 2003 Sultan Qaboos University On the Computation of the Maximum Uncertainty Volume of Stable Polynomials F.M. Al-Sunni Department of System Engineering, King Fahad University of Petroleum and Minerals, Dahran 31261, Saudi Arabia, Email: alsunni@ccse.kfupm.edu.sa. غير المعامالت بواسطة طرق الحلول المثلىحساب قيمة أكبر حجم لت فؤاد محمد عيسى السني ندرس كال . ي األنظمة فنقترح طريقة تعتمد على الحلول المثلى من أجل إيجاد أكبر قدر من تغير المعامالت : خالصة طريقة المقترحة بعد تقديم ال . من األنظمة الخطية مع وجود صندوق من األخطاء في المعامالت وكذلك معين من الدوال .نستعرض استخدامها عن طريق تطبيقها على بعض األمثلة ABSTRACT: In this paper we propose a non-linear optimization based approach for the computation of the stability region for uncertain polynomials. Both box of polynomials and diamond of polynomials are addressed. Examples are presented as an illustration. KEYWORDS: Optimization, Uncertain Polynomials, Box Polynomials, Diamond Polynomials. 1. Introduction T he computation of the largest perturbations of a given system without violating stability is of great interest for analysis and controller design. Considerable work has been reported in the literature focusing on this issue. The work in Barmish (1984) makes use of the Kharitonov result (Kharitonov, 1978) to find the smallest destabilizing perturbations in the parameters by examining the four Hurwitz testing matrices. The work assumes equal perturbations to all the parameters. In Chapellat et al. (1988) a procedure for obtaining the largest stability ball is proposed. The authors in Blanchini et al. (1998) proposed to find the minimum destabilizing volume for uncertain systems, and in Kim et al. (1988) the case of bivariate polynomials was studied. In Hollot (1988), it was proposed to use the markov parameters of a polynomial to study the stability margin, and Djaferis (1989) studied polynomials with linear uncertainty. The diamond of polynomials case was studied in Barmish et al. (1992). In this study we make use of the link established by Mansour et al. (1992) between the celebrated Kharitonov results and the positive definiteness of the associated Hermite matrices (Anderson, 1972), to produce a non-linear programming approach for obtaining the largest volume in the parameter space around a stable nominal polynomial. The statement of the problem is given in the following section, followed by the proposed scheme in section three. Examples are presented in section four, and section five concludes the paper. 2. Statement of the problem Definition 1. N(s) is called an interval polynomial if it is given by 27 F.M. AL-SUNNI n n n n slslsllsN ++++= − − 1 110 ..........)( with the parameters in the given intervals bounded below by the minimum value , and above by the maximum value (i.e. l ];[ iii ll∈ ) Definition 2. p(s,d) represents diamond of polynomials if n n n n sdsdsdddsP ++++= − − 1 110 .....),( (1) with real coefficients di known to lie in the (n+1)-dimensional diamond centered at d* = (d*0….d*n). This means that d = [d0 d1 d2……dn] is a possible value for the parameters if where nDd ∈ }||.......|||:|{ **11 * 00 rdddddddD nnr ≤−+−+−= (2) and r is the radius of the diamond. Definition 3. The Hermite matrix H associated with a given polynomial of order n, p(s,d) is an n by n symmetric matrix with entries given by (3) 1 1 ( 1) ; , i k i ij n k n i j k k H d d j i and i j e+ − + − − + = = − ≥ +∑ ven evenjiandijH ji +<= ,; oddisji += ;0 We now present the stability results for both: the box of polynomials, and a diamond of polynomials. Lemma 1: The interval polynomial N(s) is stable (Kharitonov, 1978) for all li if the following four polynomials, of order n, are stable: 2 3 1 1 2 3( ) ......-0N s 1 l s l s l s−= + + + + 2 3 2 0 1 2 3( ) ......N s l l s l s l s− − −= + + + + 2 3 3 0 1 2 3( ) ......N s l l s l s l s− −= + + + + 2 3 4 0 1 2 3( ) ......N s l l s l s l s− −= + + + + Lemma 2: (Barmish et al., 1992) The diamond of polynomials (1) is stable for all d, if the following eight polynomials are stable: rDd ∈ P1(s,d) = P(s,d*) + r P2(s,d) = P(s,d*) - r P3(s,d) = P(s,d*) +rs P4(s,d) = P(s,d*) -rs P5(s,d) = P(s,d*) + rsn-1 P6(s,d) = P(s,d*) - rs-n-1 P7(s,d) = P(s,d*) + rsn P8(s,d) = P(s,d*) - rsn Lemma 3: (Anderson, 1972) A polynomial is stable if the associated Hermite matrix is positive definite. It is the objective of this paper to find the maximum range of the parameters which maintain the stability of the polynomials. Both the interval and the diamond like uncertainty will be addressed. In our development, Lemmas 1 and 3 will be used to formulate the problem for finding the maximum volume of uncertainty, for interval polynomials, as a 28 ON THE COMPUTATION OF THE MAXIMUM UNCERTAINTY VOLUME optimization problem. Also, lemmas 2 and 3 will be used for the formulation of the case of a diamond of polynomials. 3. An optimization-based approach 3.1 Interval polynomials In order to find the maximum range, we propose to find the interval ranges which maximize the volume of the box of uncertainty, Vb. To fix notation, let a*i be the nominal value of parameter ai. Let the parameter ai belong to the range [ . The width of this range is equal to . The volume of the box of uncertainty is given by ], ** uii l ii aa δδ −− u i l i δδ + V )( 0 u i l i n ib δδ +Π= = Our proposed scheme is to maximize Vb1 subject to the stability constraints given by the positive definiteness of the four Hermite matrices corresponding to the Kharitonov polynomials. The problem of finding the maximum stabilizing volume may then be presented as )( 5 0, u i l iib VMax u i l i δδ δδ +Π= = subject to the constrains given by Hi > 0 i = 1, 2, 3, 4 3.2 Diamond polynomials A similar approach may be suggested for the study of stability radius of a diamond of polynomials. We need to maximize the volume of the diamond, Vd, subject to the positive definiteness of the eight Hermite matrices associated with the eight polynomials given in lemma 2. The volume of the diamond, Vd, with radius r, is a fraction multiple of the volume of the box Vb, with length 2r. So the NLP problem to solve is 1)2( += nb r rVMax subject to the constraints represented by Hi>0, i = 1,2……..8 with Hi the Hermite matrix associated with the i polynomial given in lemma 2. Note that Hth i are functions of one parameter, r, only. The problem of maximizing the volume Vb is a non-linear optimization problem. A global maximum is not guaranteed. however, the proposed approach gives the flexibility of finding the effect of individual parameters and it also can put some constraints on the uncertainties being symmetric or not etc. The optimization can be performed using the Matlab optimization routine called “constr”. This routine allows the user to provide the objective function, and the constraints of the optimization problem and produces the maximum value after the optimization is done. 4. Examples 4.1 Example 1 Consider the following fourth order stable polynomial (Barmish 1984) P(s) = s4 + 5s3 + 8s2 + 8s + 3 29 F.M. AL-SUNNI We would like to find the values of and for the interval polynomial which maximizes liδ u iδ ))()()(( 33221100 ulululul bV δδδδδδδδ ++++= subject to Hi>0, i = 1, ..4, which are the Hermite matrices associated with the four Kharitonov polynomials. If we restrict the changes and to be the same, then we have the situation usually studied in the literature. This is also the case studied in (Barmish 1984). The result of the optimization scheme is = = 1.81, i = 0, 1, 2, 3 (This represents a one parameter optimization problem). The result is in agreement with the result reported by Barmish. l iδ u iδ u iδ l iδ Now we relax the constraints and assume that = , but they are different for different values of i. The resulting stability volume is given by the following parameter intervals: l iδ u iδ [[1,1], [2.318, 7.682], [6.33, 9.67], [5.93, 10.07], [1.71.4.29]] and with the removal of the above restriction, we have the following intervals: [[1,1], [5, 20.28], [8, 103365.4], [8, 30.027], [0,3]] 4.2 Example 2 Consider now the example studied in (Blanchini el at. 1998). The example they studied is a sixth order polynomial given by p(s) = s6 + 4s5 + 4s4 + 6s3 + 3s2 + 2s + 0.5 The one parameter optimization case resulted in the values of = = 0.0512, and with different and for different i, the resulting intervals are given by: l iδ u iδ l iδ u iδ [[1,1], [3.91, 4.09], [3.91, 4.09], 5.88, 6.12], [2.99, 3.01], [1.96, 2.04], [.47, .53]] 4.3 Example 3 Here we consider a diamond of polynomials studied in (Barmish et al., 1992) and given by: p(s) = s4 + 3s3 + 6.49s2 + 7.98s + 3.45 The objective is to find the maximum value of r, such that the polynomial (1) is stable for all parameters in Dn given in (2). Our proposed method resulted in the diamond Dr given by Dn = {d : |da-3.49| + |d1 – 7.98| + |d2 – 6.49| + |d3 – 3| + |d4 – 1|≤ 0.9593}| This is very close, but larger compared to the value of r = 0.9467 obtained in Barmish et al. (1992). 5. Conclusions An optimization-based approach is proposed for obtaining the largest volume of perturbations of the plant parameters, the use of which is illustrated via examples. The case of 30 ON THE COMPUTATION OF THE MAXIMUM UNCERTAINTY VOLUME polynomials with parameters which are affine in some uncertain parameters can be addressed using the proposed approach. 6. Acknowledgements The author would like to express his appreciations for the support provided by KFUPM. References ANDERSON, B.D., 1972, The reduced Order Hermite Criterion with Applications to Proof of Lienard-Chipart Criterion, IEEE Transaction on Automatic Control, 17:669-672. BARMISH, B.O., 1984, Invariance of Strict Hurwitz Property for polynomials with perturbed Coofficients, IEEE Transaction on Automatic Control, 29(10):935-936. BARMISH, B.R., TEMPO, R., HOLLOT, C.V. and KANG, H.I, 1992, An Extreme Point Result for Robust Stability of a Diamond of Polynomials, IEEE Transaction on Automatic Control, 37( 9): 1460-1462. BLANCHINI, F., TEMPO, R., and DABBCNE, F., 1998, Computation of the Minimum Destabalizing Volume for Interval and Affine Families of Polynomials, IEEE Transaction on Automatic Control, 43(8):1159-1163. CHAPELLAT, H., BHATTACHARYYA, S.P., and KEEL, L.H., 1988, Stability Margin for Hurwitz Polynomials, Proceeding of the 27th IEEE Decision and Control Conference, 1:1392-1398. DJAFERIS, T.E., 1989, The Largest Stability Hypercube for Families of Polynomials with Lincar Uncertainty, American Control Conference, 1: 633-638. HOLLOT, C.V., 1988, On Markov’s Theorem: It is Like Kharitonov’s but Twice as Nice, Proceeding of the 27th IEEE Decision and Control Conference, 1: 515-518. KHARITONOV, V.L., 1978,Syumpototic Stability of an Equilibrium Position of a Family of Systems of Linear Differential Equations Differentsial’nye Uravneniya, 14:2086-2088. KIM, K.D., and BOSE, N.K., 1988 Invariance of Strict Hurwitz Property for Bivariate Polynomials Under Coofficients Perturbations, IEEE Transaction on Automatic Control, 33(12):1172-1174. MANSOUR, M., and ANDERSON, B.D., 1992, Kharitonov’s Theorem and the Second method of Lyapunov Robustness of Dynamic Systems with Parameter Uncertainties, edited by M. Mansour, Berlin, Birkhauser. Received 28 December 2001 Accepted 21 May 2003 31 On the Computation of the Maximum Uncertainty Volume of Stable Polynomials F.M. Al-Sunni Department of System Engineering, King Fahad University of Petroleum and Minerals, Dahran 31261, Saudi Arabia, Email: alsunni@ccse.kfupm.edu.sa.