Optimal sensor placement for linear systems

Bachelo a bei im S udiengang Ma hema ik Leh s uhl ü angewand e Ma hema ik Op imal Senso Placemen o linea Sys ems einge eich on: Maximilian P is e einge eich am: 17.08.2012 Be eue : P o . D . Tobias Damm D .-Ing. Ul ich Münz (Siemens AG) Abs ac The aim o senso placemen is o obse e he s a e o a dynamical sys em while using only a small pa o he a ailable ou pu in o ma ion. Thus, he obse e does no need senso s a e e y possible node o he sys em. We use senso placemen because i is no p ac ical o la ge-scale ne wo ks, such as powe g ids, o place senso s a each node. Wi h an op imal senso placemen we ob ain a subse o senso s which minimizes he obse e e o in compa ison o any o he subse o he same size. This means we gene a e an op imal obse a ion wi h he gi en numbe o senso s. We compu e he obse e e o , o he linea dynamical sys ems we conside , wi h he H2 -no m o he obse e e o sys em. In his app oach, we op imize bo h he subse o selec ed senso s and he obse e gain ma ix in pa allel. The op imiza ion p oblem is non-con ex bo h in a cons ain , which bounds he H2 -no m, as well as in he objec i e unc ion which uses a `0 -no m o coun he used senso s. To ob ain a semide ini e p og am, we i s elax he `0 -no m by an i e a i e eweigh ed `1 -no m. Second, we use a e o mula ion o he H2 -no m wi h linea ma ix inequali ies o eplace an occu ing bilinea and he e o e non-con ex e m. We use his compu a ionally e icien o mula ion o he senso placemen p oblem o de i e h ee algo i hms. Fu he mo e, exis ing algo i hms, which do no use he con ex e o mula ion o he op imiza ion p oblem, we e implemen ed. The algo i hms a e compa ed ex ensi ely ela ing o execu ion ime, pe o mance o he chosen senso s, and he applicabili y on a p ac ical p oblem. The p ac ical p oblem is a model o a high- ol age powe g id wi h he aim o measu e he phase angles and he equencies a e e y node. The esul o he compa ison is ha a algo i hm wi h a g eedy app oach sol es he op imiza ion p oblem as and usually wi h a good solu ion. Howe e , his algo i hm is p oblema ic because he sho sigh ed g eedy app oach canno exclude ha a wo s case solu ion is gene a ed. The bes esul s in gene al we e p oduced by a no el app oach made in his hesis. This no el algo i hm i e a i ely sol es he elaxed op imiza ion p oblem and inds nea -op imal senso subse s. Con en s 1 In oduc ion 7 2 P oblem Fo mula ion 9 2.1 P oblem Fo mula ion o Disc e e-Time Sys ems . . . . . . . . . . . . . . . . . . 9 2.2 P oblem Fo mula ion o Con inuous-Time Sys ems . . . . . . . . . . . . . . . . . 10 3 Con ex Relaxa ion o he Op imiza ion P oblem 11 3.1 Con ex Relaxa ion o he `0-Objec i e........................ 11 3.2 Re o mula ion o he H2-Pe o mance Cons ain . . . . . . . . . . . . . . . . . . 12 3.3 Algo i hms o Op imal Senso Placemen o Disc e e-Time Sys ems . . . . . . . 14 3.3.1 Algo i hm wi h Subs i u ion . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.3.2 Algo i hm wi h Cone Complemen a i y Linea iza ion . . . . . . . . . . . . 17 3.4 Algo i hm o Op imal Senso Placemen o Con inuous-Time Sys ems . . . . . 19 4 Compa ison o Di e en Algo i hms 23 4.1 S a e o he a Algo i hms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.1.1 G eedyAlgo i hm ............................... 23 4.1.2 B anch and Bound Algo i hm . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.2 Run imeCompa ison.................................. 24 4.3 Pe o manceCompa ison ............................... 26 4.4 Applica ionExample.................................. 28 4.5 Concluding Compa ison o he Algo i hms . . . . . . . . . . . . . . . . . . . . . . 31 5 Conclusion and Fu u e Di ec ions 33 6 Appendix - Ma hema ical De ini ions and No a ion 35 6.1 `0-Vec o -No m..................................... 35 6.2 H2-Sys em-No m.................................... 35 6.3 Ma icesandLMIs................................... 36 Bibliog aphy 37 5 1 In oduc ion In his hesis, we conside he p oblem o obse ing he s a e o dynamical sys ems, such as ene gy ne wo ks, as accu a e as possible wi h a small numbe o senso s. This p oblem is in e es ing since he e exis la ge ne wo ks, whe e i is no cos -e icien o place a senso a e e y node o he sys em. Consequen ly, we can no measu e all he s a es o he sys em which esul s in an obse e e o . The aim o his hesis is o ind an op imal subse o senso s, i.e. a subse , such ha e e y o he subse o he same size has a bigge obse e e o . The p oblem o senso selec ion appea s in se e al a eas o applica ion like obo ics, senso placemen o s uc u es, a ge acking, chemical plan con ol and wi eless ne wo ks as lis ed in Joshi and Boyd [2009]. The ield o applica ion o his hesis a e ene gy ne wo ks, especially high- ol age ne wo ks, as seen in he example o Sec ion 4.4. We conside he p oblem o choosing an op imal subse om among n po en ial senso s o a ime-in a ian linea dynamic sys em o s a e es ima ion subjec o whi e inpu noise. Each senso can measu e one componen o he ou pu ec o y . Thus he p ocess o senso selec ion educes he a ailable in o ma ion o he obse e . The senso selec ion consequen ly has an in luence on he obse e e o . The aim o his hesis is o choose an H2-op imal subse , i.e. a subse ha minimizes he H2 -no m o he obse e e o sys em. The H2 -no m desc ibes he o al ou pu ene gy o he impulse esponse o he e o sys em. A simple app oach o e alua e he bes k senso subse would be o calcula e he H2 -no m wi h an op imal obse e o all possible n k combina ions o subse s. Bu since n k g ows apidly wi h inc easing n and k , his me hod is no p ac ical. Fo example, wi h n = 50 po en ial senso s and k = 25 senso s o choose he e a e o e 1014 possible uples, so a sequen ial e alua ion is ob iously no possible. In his hesis, we p o ide se e al algo i hms, pa ly based on con ex op imiza ion, o a nea op imal solu ion o he senso selec ion p oblem. And we use one combina o ial algo i hm wi h a b anch and bound echnique o an op imal solu ion in o de o compa e he pe o mance o he elaxed algo i hms o his op imal solu ion. When compa ing he execu ion ime o he algo i hms, i can be seen ha he b anch and bound algo i hm is a NP-ha d p oblem, while he o he algo i hms ha e a polynomial compu a ional complexi y. The p oblem we conside consis s o wo componen s. Fi s we ha e o choose a subse o senso s which ha e o be used. Second, we ha e o calcula e an op imal obse e gain ma ix o hese se ings in o de o e alua e he objec i e unc ion. In his app oach, we p o ide a se ing ha sol es hese wo p oblems in pa allel. Va ious pape s ea ela ed p oblems o he one discussed he e. In Mo e al. [2011], we ind a gene al app oach o senso selec ion s a egies o wi eless senso ne wo ks. Howe e , he amewo k does no hold o ou case since he s a egy is chosen o a ini e ime ho izon. This ini eness is used in he included manipula ion o he op imiza ion p oblem o a ecu si ely de ined equa ion o he s a e es ima ion. Gi en an in ini e ime ho izon, we could no pe o m he same e o mula ions. 7 In Schule e al. [2012], we ind an almos dual p oblem o he obse e design in his hesis. This pape wi h he i le Decen alized S a e Feedback Con ol o In e connec ed P ocess Sys ems seeks o minimize he numbe o measu emen links be ween senso s and con olle s and c ea es a con ex op imiza ion p oblem, ha is simila o he p oblem de i ed in his hesis. Ne e heless, he de i a ion o he con ex op imiza ion p oblem is no applicable o he p oblem discussed he e, because, on he one hand, he con olle p oblem has sligh ly di e en bilinea i ies which ha e o be subs i u ed o con ex op imiza ion, and on he o he hand Schule e al. [2012] use he H∞-no m in con as o he he e applied H2-no m. The app oach in his hesis s a s wi h desc ibing he sys em o he es ima ion e o . By in oducing a design ma ix, we c ea e he possibili y o a y he se ing o he p oblem, i.e. o punish es ima ion e o s in ce ain s a es mo e han in o he s. In he nex s ep, we use a LMI-cha ac e iza ion o he H2 -no m o e o mula e his cons ain o a semide ini e one. The men ioned cons ain is elaxed in wo di e en ways ha a e wa ds esul in di e en algo i hms. The `0 -no m o obse e -spa si y in he objec i e is a non-con exi y ha is elaxed by an i e a i e weigh ed `1-no m. The es o he hesis is o ganized as ollows. We p esen he p oblem o mula ion in Chap e 2. In Chap e 3, we desc ibe con ex elaxa ions o he op imiza ion p oblem and he de i ed algo i hms bo h o disc e e- ime and con inuous- ime sys ems. In Chap e 4, ex ensi e compa ison o he di e en algo i hms is p esen ed, including a un ime and a pe o mance compa ison as well as an example o an ene gy-ne wo k model o es he algo i hms in p axis. The hesis concludes wi h a summa y and an ou look in Chap e 5. 8 2 P oblem Fo mula ion 2.1 P oblem Fo mula ion o Disc e e-Time Sys ems Conside he ollowing disc e e- ime dynamical sys em xk+1 =Axk+Bwk(2.1a) yk=Cxk, (2.1b) whe e k∈N+ 0 , xk∈Rn is he s a e o a sys em wi h n s a es and yk∈Rm , m≤n , is he se o possible senso s. The unknown inpu wk∈Rp is ze o-mean whi e noise wi h uni a iance. Assuming ha he ma ices A∈Rn×n , B∈Rn×p , and C∈Rm×n a e known, we de ine a Luenbe ge obse e . ˆxk+1 =Aˆxk+L(yk−ˆyk)(2.2a) ˆyk=Cˆxk, (2.2b) whe e L∈Rn×m desc ibes he obse e gain ma ix ha has o be designed. An op imal L could be ound by using he p inciple o he Kalman il e , which uses he same se up as he one desc ibed he e. We can exp ess he obse e e o e=x−ˆx: ek+1 = (A−LC)ek+Bwk(2.3a) zk=Wek. (2.3b) The ma ix W∈Rn×n can be used as a design ma ix when he desi ed accu acy o he obse a ions o ce ain s a es di e s o i a scaling has o be done. Elsewise W could simply be de ined as an iden i y ma ix. Le us assume he e exis s a s abilizing L . Thus we can gua an ee ha he H2 -no m o he sys em exis s and cha ac e ize he obse e e o wi h ha no m, again as in he se up o Kalman il e . Wi h he aim o minimize he numbe o used senso s wi h a bounded obse e e o we can de ine he ollowing simpli ied op imiza ion p oblem: min L”no. o senso s”(2.4a) s. . ||Σe(L)||2 2< γ, (2.4b) whe e Σ e ( L )is a sho o m o he e o sys em depending on L as desc ibed in (2.3). || ·||2 deno es he H2 -no m o he sys em and γ is a p ede ined uppe bound o he squa ed H2 - no m. The numbe o used senso s in (2.4) is he numbe o non-ze o columns in L , i.e. i e e y elemen o a column o L is ze o, he co esponding en y in yk has no in luence on he obse e sys em, 9 Algo i hm 1. Algo i hm wi h subs i u ion : Relaxed senso placemen algo i hm wi h linea iza ion ia subs i u ion o disc e e- ime sys ems 1. Se he i e a ion coun µ o ze o and choose an app op ia e alue o he pa ame e α . Ini ialize he weigh s ec o ω(0) o ω(0) j = 1 o j = 1 , . . . , n and choose a su icien ly small ε > 0. 2. Sol e he op imiza ion p oblem (3.6). 3. Upda e he weigh s: ω(µ+1) j=1 ||˜ L∗j||1+ε,j= 1, . . . , n. 4. Te mina e he i e a ion on con e gence wi h L = X−1˜ L . O he wise inc ease µ by 1 and e u n o S ep 2. 5. Imp o e he choice o Lby sol ing he op imiza ion p oblem: min γ, ˜ L,X γ(3.7a) s. . X=XT0(3.7b) ace(BTXB)< γ (3.7c) −X+WTW ATX−˜ CT˜ LT XA −˜ L˜ C−X!≺0, (3.7d) whe e ˜ C := C wi h p ede ined ze o lines. The j h line is se o ze o i he j h senso was emo ed in he p e ious solu ion o S ep 2 (i.e. i ||L∗j||1ε). The weigh s ec o ω(0) could also be ini ialized as a ze o ec o in S ep 2 o he algo i hm. Thus, he i s i e a ion would yield o a op imal obse e gain ma ix wi h no ze o columns in L and ω(1) would coun e ac he ac ual size o he column in an op imal non-spa se obse e . Wi h he cu en implemen a ion i is possible ha a senso is se o ze o in he i s i e a ion because he column o L is smalle han he o he columns. This is in gene al no equi alen o a bad pe o mance o he senso . In S ep 3 o Algo i hm 1, ˜ L o L could be used o pe o m he upda e on he weigh s. The eason why ˜ L is used he e is ha we wan o coun e ac he size o ˜ L in he objec i e. As men ioned in Rema k 1, i is equi alen o educe ei he he non-ze o columns o Lo ˜ L. In S ep 3 o Algo i hm 1, we in oduced he a iable ε o imp o e he eweigh ing wi h ω(µ) and a oid nume ical p oblems, such as di iding by ze o, as p oposed in Candes e al. [2008]. S ep 5 o Algo i hm 1 is necessa y, since he obse e , ha is calcula ed in he op imiza ion p oblem (3.6), has a subop imal obse e gain ma ix, because e en he eweigh ed `1 -no m in he objec i e minimizes he absolu e alue o he en ies o ˜ L . A e S ep 5, he exac H2 -no m o he obse e e o sys em can be calcula ed. The inequa ion ||L∗j||1ε in S ep 5 is equi alen o he s a emen ha he j h column is coun e ac ed wi h a maximum weigh . This means ha he co esponding senso is emo ed. The e o e, he j h senso is no conside ed when compu ing he imp o emen o L. Rema k 2. As w i en in equa ion (2.5), i is also possible o choose a cons an γ and emo e γ om he objec i e unc ion. We choose he o he way because i is on he one hand mo e 16 di icul o es ima e an app op ia e γ be o e s a ing he op imiza ion, and on he o he hand he algo i hm has no incen i e o choose he bes subse o k senso s, i ano he subse o k senso s also sa is ies he bound on he H2-no m. 3.3.2 Algo i hm wi h Cone Complemen a i y Linea iza ion As men ioned be o e, we will conside he ma ix inequali y (3.3) o pe o m a cone complemen- a i y linea iza ion. He e, you can see he ma ix inequali y again: −X+WTW AT−CTLT A−LC −X−1!≺0. (3.8) The ollowing Lemma is necessa y o o mula ing he algo i hm wi h cone complemen a i y linea iza ion. Lemma 3. Wi h X0 he ollowing s a emen s hold: (i) The ollowing wo exp essions a e equi alen : a) KX =I b) ace(KX) = nand K I I X!0 (ii) K I I X!0⇒ ace(KX)≥n. P oo : Ad (i): Unde condi ion o X0 he ollowing s eps a e alid: K I I X!0 ⇔Re o mula ion o he LMI wi h he Schu complemen : K−IX−1I0 ⇔K−X−10. Pos mul iplying wi h X leads o he nex ma ix inequali y. ⇔KX −I0 Wi h his e o mula ion he p oo o "a) ⇒ b)" is ob ious since KX = I implies ace( KX ) = ace(I) = nand KX −I0holds. Fo he p oo o "b) ⇒ a)" we will look a a cha ac e is ic o he ma ix inequali y KX −I 0 and use he p emise ace(KX) = ace(I) = n. ace(KX −I)=0is alid, because o ace(KX) = ace(I) = n. ⇒KX −I has all eigen alues equal o ze o. Because assuming ha KX −I has a posi i e eigen alue, which is possible since KX −I 0, would esul in KX −I ha ing a nega i e eigen alue so ha he sum o all eigen alues is ze o again. Tha leads o a con adic ion o he s a emen KX −I0. Ad (ii): Unde condi ion o X0 he ollowing s ep is alid: K I I X!0⇔KX −I0 ollows om he i s s eps o he p oo o (i). Since he ace o a ma ix is he sum o i s eigen alues, i esul s ha ace( KX ) ≥ ace ( I ) = n .  17 The lemma is i al o ou app oach o he second algo i hm because we now ha e he possibili y o in oduce a new a iable K ha beha es as he in e se o X . The LMI men ioned in Lemma 3 can be used as a cons ain , while ace( KX )can be pa o he objec i e unc ion. Wi h minimizing ace( KX ), we will ecei e K as he in e se o X because ace( KX ) ≥n and K=X−1a he minimum, whe e ace(KX) = n. Applying Lemma 3 o he ma ix inequali y (3.8), he op imiza ion p oblem (2.6) esul s in: min γ,L,X,K γ+α n X j=1 ω(µ) j||L∗j||1+β ace(XK)(3.9a) s. . X=XT0(3.9b) ace(BTXB)< γ (3.9c) −X+WTW AT−LTC A−LC −K!≺0(3.9d) K I I X!0, (3.9e) whe e β is ano he pa ame e o adjus ing he objec i e unc ion. As we can see, linea izing he ma ix inequali y esul ed in a bilinea e m in he objec i e unc ion. Ou aim is o ha e semide ini e p og am so we need o eplace he bilinea pa . We could use a linea iza ion me hod as seen in El Ghaoui e al. [1997] o sol e such a p oblem. A a gi en poin ( Xold, Kold ), a linea app oxima ion o ace(XK)is φlin(X, K) = cons an + ace(XKold +XoldK). The op imiza ion p oblem o he algo i hm wi h cone complemen a i y linea iza ion (CCL) is hen: min γ,L,X,K γ+α n X j=1 ω(µ) j||L∗j||1+β ace(XKold +XoldK)(3.10a) s. . X=XT0(3.10b) ace(BTXB)< γ (3.10c) −X+WTW AT−LTC A−LC −K!≺0(3.10d) K I I X!0. (3.10e) Algo i hm 2. Algo i hm wi h CCL : Relaxed senso placemen algo i hm wi h cone comple- men a i y linea iza ion o disc e e- ime sys ems 1. Find a easible solu ion o X in (3.4) and se Xold = X . I he e a e none, exi . Se he ou e i e a ion coun µand he inne i e a ion coun k o ze o. 2. Se Kold = X−1 old and choose app op ia e alues o he pa ame e s α , β , γ and δ . Ini ialize he weigh s ec o ω(0) o ω(0) j= 1 o j= 1, . . . , n and choose a su icien ly small ε > 0. 3. Sol e he op imiza ion p oblem (3.10). 18 4. I | ace ( XK ) −n|< δ , se k = 0 and go o S ep 5, else se k = k + 1, Xold = X and Kold =Kand go o S ep 3. 5. Upda e he weigh s: ω(µ+1) j=1 ||L∗j||1+ε,j= 1, . . . , n. 6. Te mina e he ou e i e a ion on con e gence. O he wise inc ease µ by 1 and e u n o S ep 3. 7. Imp o e he choice o L by sol ing he op imiza ion p oblem (3.7). De ine ˜ C := C wi h p ede ined cons an ze o lines. The j h line is se o ze o i he j h senso was emo ed in he p e ious solu ion o S ep 3 (i.e. i ||L∗j||1ε). Rema k 3. In S ep 1 o Algo i hm 2, he e a e se e al possibili ies o ind a easible solu ion in (3.4). You could pe o m one i e a ion o (3.6) and use he gene a ed X . In his case you could make he i s upda e o he weigh s ec o a e wa ds. Whe eas a as e me hod is o ind X by calcula ing a non-spa se Kalman il e and he co esponding Lyapuno ma ix o he obse e e o sys em. Bu in his case he ma ix X has o change much du ing he nex i e a ions o emo e senso s. This means ha a lo o i e a ions a e needed because he linea iza ion me hod punishes any changes in X and K . The e o e, he algo i hm emo es senso s only e y slowly. The objec i e unc ion o his algo i hm is di ided up in h ee di e en pa s, which a e he bound on he H2 -no m γ , he `1 - elaxa ion o he numbe o senso s, and he punishing e m o he in e se ma ix o X . These h ee e ms ha e o ally di e en unc ions in he op imiza ion p oblem and ha e a di e se scale o each e m. The e o e, i is ha d o ind he igh pa ame e iza ion o he e ms. Depending on he applica ion o he algo i hm, i is possible o educe he complexi y o he objec i e unc ion. I only a educed accu acy is needed o he esul , one could ake he e m β ace ( XKold + XoldK ) om he objec i e unc ion and use i as a cons ain . Wi h an app op ia e cons an ζ he cons ain could look like: ace(XKold +XoldK)<2n+ζ. As men ioned in Rema k 3, a e y small ace ( XKold + XoldK )slows down he emo al o senso s. The e o e, i could e en be an ad an age o pu his e m in o he cons ain s and allow g ea e inaccu acy in o de o ha e a esul wi h less senso s. 3.4 Algo i hm o Op imal Senso Placemen o Con inuous-Time Sys ems In his sec ion, we de i e he app oach o he algo i hm wi h subs i u ion o con inuous- ime sys ems. The algo i hm is e y simila o he one o disc e e- ime sys ems bu he LMI cha ac e iza ion o he H2-no m is di e en since he Lyapuno equa ion is o ano he o m. The ollowing Lemma is like Lemma 2, bu i is no necessa y o show he second equi alence since he subs i u ion e en wo ks when applied on he a iables in he Lyapuno inequali y. 19 Fu he mo e, in his hesis he cone complemen a i y linea iza ion is used only o disc e e- ime sys ems as in he li e a u e. Consequen ly, he augmen ed LMI o con inuous- ime sys ems is o no use o ou app oach. Lemma 4. (As in Riebe [2006]) Conside a con inuous- ime sys em wi h ans e unc ion G(s) = "A B C0#:= C(sI −A)−1B. The ollowing wo s a emen s a e equi alen : (i) ||G(s)||2 2< γ and Ais asymp o ically s able. (ii) The e exis s a posi i e de ini e symme ic solu ion P o he Lyapuno equa ion ATP + PA = −CTCand ace(BTPB)< γ. P oo : (pa ly as in Smi h [2010]) ||G(s)||2 2< γ ⇔1 2πZ∞ −∞ ace(G(jω)G(jω)∗)dω < γ, which is he de ini ion o he H2-no m on he equency domain. In he nex s ep we use an equi alen de ini ion on he ime domain. ⇔Z∞ 0 ace(g( )Tg( ))d < γ, whe e g( )is he impulse esponse o he sys em G(s). ⇔ ace[BT(Z∞ 0 eAT CTCA d )B]< γ ⇔ ace[BTPB]< γ, whe e Pis he obse abili y G amian (possible, since Ais s able) which is de ined as P=Z∞ =0 eAT CTCeA d . ⇔ ace[BTPB]< γ, P 0and ATP+PA =−CTC  We now conside he op imiza ion p oblem (p e iously desc ibed in (2.6)) min L,γ γ+α n X j=1 || n X i=1 |Lij| ||`0(3.11a) s. . ||Σe(L)||2 2< γ (3.11b) and apply he op imiza ion p oblem o a con inuous- ime sys em (as desc ibed in (2.8)) ˙e= (A−LC)e+Bw (3.12a) z=We. (3.12b) 20 Using Lemma 4, he esul ing op imiza ion p oblem is he ollowing: min γ,L,P γ+α n X j=1 ω(µ) j||L∗j||`1(3.13a) s. . P=PT0(3.13b) ace(BTPB)< γ (3.13c) ATP+PA −CTLTP−PLC +I= 0, (3.13d) whe e P is he solu ion o he Lyapuno equa ion as in Lemma 4 (ii). The cons ain (3.13d) could also be w i en as a LMI, i he ma ix P is eplaced by a ma ix Xcon which is de ined as he con inuous- ime equi alen o he ma ix Xmen ioned in he p oo o Lemma 2. We could now pe o m he subs i u ion ˜ L = PL as in Sec ion 3.3.1. Consequen ly, Rema k 1 holds also o his case and we eplace L in he objec i e unc ion wi h ˜ L . This esul s in he ollowing op imiza ion p oblem: min γ, ˜ L,P γ+α n X j=1 ω(µ) j||˜ L∗j||`1(3.14a) s. . P=PT0(3.14b) ace(BTPB)< γ (3.14c) ATP+PA −CT˜ LT−˜ LC +I= 0. (3.14d) The algo i hm wi h subs i u ion is hen o mula ed as: Algo i hm 3. Algo i hm wi h subs i u ion : Relaxed senso placemen algo i hm wi h linea iza ion ia subs i u ion o con inuous- ime sys ems 1. Se he i e a ion coun µ o ze o and choose an app op ia e alue o he pa ame e α . Ini ialize he weigh s ec o ω(0) o ω(0) j = 1 o j = 1 , . . . , n and choose a su icien ly small ε > 0. 2. Sol e he op imiza ion p oblem (3.14). 3. Upda e he weigh s: ω(µ+1) j=1 ||˜ L∗j||1+ε,j= 1, . . . , n. 4. Te mina e he i e a ion on con e gence wi h L = P−1˜ L . O he wise inc ease µ by 1 and e u n o S ep 2. 5. Imp o e he choice o Lby sol ing he op imiza ion p oblem: min γ, ˜ L,P γ(3.15a) s. . P=PT0(3.15b) ace(BTPB)< γ (3.15c) ATP+PA −˜ CT˜ LT−˜ L˜ C+I= 0, (3.15d) whe e ˜ C := C wi h p ede ined ze o lines. The j h line is se o ze o i he j h senso was emo ed in he p e ious solu ion o S ep 2 (i.e. i ||L∗j||1ε). 21 The commen s conce ning ˜ L , L , ε , and ω made abou he algo i hm wi h subs i u ion o disc e e- ime sys ems a e also applicable o his algo i hm. 22 4 Compa ison o Di e en Algo i hms In his chap e , he algo i hms o Chap e 3 a e compa ed wi h s a e o he a algo i hms. One is a g eedy app oach in wo di e en e sions as seen in Bach e al. [2010]. The o he algo i hm uses a b anch and bound echnique o p o ide an op imal solu ion which is also p esen ed in he i s pa o his chap e . In he second pa o he chap e , he algo i hms a e compa ed in e ms o compu a ion ime and H2 -pe o mance o he chosen subse o senso s. Addi ionally, he algo i hms ha e o sol e an applica ion example consis ing o a model o a powe g id. 4.1 S a e o he a Algo i hms In he ollowing, we discuss h ee algo i hms ha use he o iginal op imiza ion p oblem wi hou any elaxa ion. Hence, hese algo i hms canno use in e io poin me hods as he wo algo i hms men ioned be o e. These algo i hms do no op imize he chosen subse o senso s and he obse e gain ma ix in pa allel. In ac , he algo i hms compu e he H2 -no m o di e en subse s and compa e his H2 -pe o mance. Hence, he e is no change in di icul y o he compu a ion when he algo i hms a e implemen ed o disc e e- ime o con inuous- ime models. 4.1.1 G eedy Algo i hm The i s s a e o he a algo i hm, which is desc ibed, is a g eedy app oach ha is e y in ui i e. The algo i hm s a s wi h all senso s and compa es all subse s wi h n− 1senso s. A e u ning-o he wo s senso he algo i hm consequen ly sea ches o he wo s senso o he emaining subse . Consequen ly, he g eedy algo i hm inds subse s o e e y size. This g eedy algo i hm gene a es a as solu ion and is able o gi e an o e iew o how many senso s a e necessa y o which H2 pe o mance. Bu as he algo i hm emo es all he senso s sepa a ely, i could no accoun o co ela ion be ween ce ain senso subse s. This could lead o a e y poo pe o mance. The algo i hm sea ches o a subse o k senso s, whe e k is a p ede ined numbe wi h k < n . This means ha he algo i hm has o emo e n−ksenso s. De ine: J ( k1, k2, . . . , km )is he H2 -no m o he e o sys em wi h an op imal educed obse e which uses he senso s k1, k2, . . . , km wi h k1, k2, . . . , km∈ { 1 , 2 , . . . , n} . The e alua ion o his unc ion could be done wi h he p ede ined sys em ma ix C , in which one eplaces e e y column excep he columns k1, . . . , km wi h ze o columns in o de o emo e he co esponding senso s. One way o e alua e he unc ion is o sol e he op imiza ion p oblem (4.1) ha is p esen ed 23 below. min γ, ˜ L,X γ(4.1a) s. . X=XT0(4.1b) ace(BTXB)< γ (4.1c) −X+WTW ATX−CT˜ LT XA −˜ LC −X!≺0(4.1d) Algo i hm 4. G eedy algo i hm : G eedy app oach o he senso selec ion p oblem as in Bach e al. [2010]. 1. Ini ialize M:= {1,2, . . . , n}and i e a ion a iable i:= 1. 2. Compu e m=a g min lJ(M {l})wi h l∈M. 3. De ine M:= M m. 4. I i = n−k , end he algo i hm wi h he solu ion M . I no , inc ease i by one and go back o S ep 2. Mis he de e mined subse o senso s and J(M) he co esponding alue o he H2no m. The g eedy algo i hm could also be implemen ed backwa ds. This means, he algo i hm s a s wi h ze o senso s and hen i e a i ely adds he bes senso . This implemen a ion o he algo i hm is called e e se g eedy algo i hm in he ollowing. 4.1.2 B anch and Bound Algo i hm The nex algo i hm is a combina o ial algo i hm, which inds he op imal subse o k senso s, whe e k is a p ede ined numbe wi h k < n . The algo i hm is called b anch and bound algo i hm, because i a anges he senso s in b anches and looks o an uppe bound a he beginning o he algo i hm. I he algo i hm inds a good uppe bound, i is possible ha a lo o b anches, i.e. uples o senso s, will no ha e o be e alua ed. The exac algo i hm as i was implemen ed du ing he w i ing o his hesis and mo e de ails abou he algo i hm can be ound in Na end a and Fukunaga [1977]. 4.2 Run ime Compa ison Fo compa ison disc e e- ime dynamical sys ems a e gene a ed andomly wi h B, C, and, W as iden i y ma ices. The dynamic ma ix A is chosen andomly wi h each en y uni o mly, independen ly, and iden ically dis ibu ed on [0 , 1] and 80% ze o elemen s o ha e a spa se s uc u e as i is common in p axis o example when conside ing powe g ids. The con inuous- ime sys ems we e gene a ed by con e ing he andomly gene a ed disc e e- ime sys ems o a con inuous- ime model. The loss o he spa se s uc u e du ing he con e ing p ocess was no conside ed in his compa ison. Algo i hms 1, 2 and 3 ha e objec i e unc ions in which he numbe o chosen senso s is con olled only indi ec ly by chosing he pa ame e s α and β . Fo he es , he pa ame e s a e se so ha 24 abou one ou h o he senso s we e emo ed. Howe e o hese algo i hms, he pa am e iza ion has li le in luence on he execu ion ime i we assume con e gence o he algo i hms. Al hough a bad se o pa ame e s could easily esul in di e gence, especially when handling he algo i hm wi h CCL, and hus o no use ul solu ion. The b anch and bound algo i hm and he g eedy algo i hms had o choose subse s o n 2 senso s. In con as o he o he algo i hms, he execu ion ime is dependen on he numbe o chosen senso s, since bo h s a wi h all senso s and consequen ly emo e senso s. When choosing e y ew senso s, he b anch and bound algo i hm has a e y la ge execu ion ime. The algo i hm could e en be ou pe o med by an algo i hm, which ies all possible uples, because he uppe bound used in he b anch and bound algo i hm would be oo big and he e o e nea ly useless. The o mula ion o he op imiza ion p oblem o he algo i hms wi h subs i u ion and he algo i hm wi h CCL is a semide ini e p og amming p oblem, since he cons ain s a e linea ma ix inequali ies (see also in Vandenbe ghe and Boyd [1999]) and he objec i e is a con ex unc ion and can e en be ecas as a linea unc ion. This allows us o use in e io poin me hods which ha e polynomial complexi y as can be seen in S u m [1999]. The eweigh ed `1 elaxa ion usually needs only ew s eps o con e ge when he pa ame e ε is chosen app op ia e (as in Candes e al. [2008]). In he ( e e se) g eedy algo i hm, he numbe o compu a ions o an op imal obse e gain ma ix and he co esponding H2 -no m inc eases wi h n2 , whe e n is he numbe o s a es, assuming ha i has o educe a ce ain pe cen age o he seno s. The op imal obse e gain ma ix could be e alua ed as a Kalman il e , which has he complexi y o n3 . So he g eedy algo i hm also has polynomial complexi y. The e e se g eedy algo i hm compu es he op imal obse e gain ma ix as o en as he g eedy algo i hm when choosing a subse o n 2 senso s. Hence, he execu ion ime o hese wo g eedy algo i hms is he same. In he ollowing, we do no dis inguish be ween hese wo algo i hms when conside ing he un ime. The b anch and bound algo i hm is NP-ha d because a a wo s -case beha io i has o compu e mo e han all possible subse s o k senso s, which a e n k . Fo his eason he b anch and bound algo i hm was mainly used he e o ha e an op imal subse in o de o compa e he pe o mance o he o he algo i hms. This compa ison can be seen in he nex sec ion. Fo each size, we gene a ed 10 andom exampla y sys ems as desc ibed abo e. E e y algo i hm had o ind he op imal senso s o all hese sys ems. In Figu e 4.1 we see he execu ion ime in seconds. The displayed execu ion ime is he a e age o he di e en compu a ions. The dashed lines show he g eedy algo i hm and he b anch and bound algo i hm wi h a sligh ly changed implemen a ion. While he solid lines we e p oduced wi h algo i hms ha used an implemen a ion o he kalman unc ion in Ma lab, he dashed lines sol ed he op imiza ion p oblem (4.1), which was implemen ed wi h SeDuMi (S u m [1999]) and YALMIP (Lo be g [2004]). Bo h o he implemen a ions achie e he same esul s, bu he implemen a ion wi h SeDuMi and YALMIP needs mo e execu ion ime and allows a be e compa ison wi h he o he h ee algo i hms ha also use SeDuMi and YALMIP. As we can see, he g eedy algo i hm, which uses he kalman unc ion me hod o Ma lab, is he as es algo i hm. The algo i hm wi h subs i u ion and he algo i hm wi h CCL a e e y simila , bu he algo i hm wi h CCL needs mo e execu ion ime, which could be he e ec o he second loop in he algo i hm. Mo eo e , he algo i hm wi h CCL qui e o en di e ged which was no conside ed o he execu ion ime he e. 25 The algo i hm wi h cone complemen a i y linea iza ion has he same bene i s as he algo i hm wi h subs i u ion, excep o he good execu ion- ime and he easy pa am e iza ion. The algo i hm wi h CCL has a second loop inside o he i e a i e eweigh ed `1 -minimiza ion which slows he algo i hm down. The g ea disad an age o his algo i hm is ha i is e y ha d o pa ame e ize he algo i hm co ec ly. In he applica ion example no app op ia e pa ame e iza ion was ound al hough o e 50 di e en se s o pa ame e s we e ied. Ne e heless, he algo i hm only lead o useless esul s. The b anch and bound algo i hm gene a es he op imal solu ion and is easy o pa ame e ize. In con as o he o he algo i hms, he b anch and bound algo i hm has a non-polynomial complexi y and he e o e an execu ion- ime ha is no usable in p axis. The g eedy algo i hm is an in ui i e and as app oach which gene a es usually a good solu ion. Howe e , he sho sigh ed app oach canno conside he impo ance o ce ain senso s in small subse s. Ano he applica ion example was gene a ed whe e he g eedy algo i hm i s emo es he senso a he highes b anched node, al hough his senso would belong o he op imal subse a he end. I seems ha highly b anched nodes a e easy o obse e wi h a lo ac i e senso s so he senso a his node is emo ed a he beginning o he algo i hm. Howe e , wi h ew ac i e senso s, he highly b anched senso s a e impo an o obse e he s a es a o he nodes. I is possible ha his p ope y is mo e impo an when conside ing la ge ne wo ks and did no a ec he esul s in Sec ion 4.3. Howe e , in ou examples he g eedy algo i hm shows a good pe o mance and gene a es an o e iew o he H2-pe o mance o di e en sizes o subse s. The e e se g eedy algo i hm is also a as algo i hm wi h a good solu ion o ou examples. In con as o ou examples, mo e complex g ids wi h ins able pa s can no be sol ed by he e e se g eedy algo i hm because i needs an obse e wi h only one senso ha has a s able obse e e o sys em. I such a senso could no be ound, he algo i hm has no s a ing poin and ends wi h no esul . As he o he g eedy app oach, he e e se g eedy algo i hm can only pe o m sho sigh ed choices and canno conside co ela ion o he senso s. The e o e, i is possible ha a e y poo solu ion is p o ided. When sol ing a senso placemen p oblem in p axis, he algo i hm wi h subs i u ion and he ( e e se) g eedy algo i hm should be chosen. The ( e e se) g eedy algo i hm can p o ide a as o e iew o he pe o mance o he desi ed numbe o senso s and a i s subse . A e ha , he algo i hm wi h subs i u ion can be used o imp o e he chosen subse o con i m i s pe o mance. 32 5 Conclusion and Fu u e Di ec ions In his hesis, we conside ed a H2 -op imal senso placemen o linea dynamical sys ems o an in ini e ime ho izon. The model o he sys em can ei he be a disc e e- ime o a con inuous- ime model. Fu he mo e, he in luence o e o s on ce ain s a es o he sys em can be pa ame e ized as well as he subse o all possible senso s. The p oblem o senso placemen a ises in a ious ields o applica ion, o example a obse ing powe g ids as desc ibed in chap e 4. The aim is he e o educe cos s o expensi e senso s and s ill ha e he bes possible obse e sys em o a gi en numbe o senso s. The o iginal p oblem o senso placemen is a non-con ex p oblem, which can ei he be app oached by combina o ial algo i hms like he b anch and bound algo i hm o wi h g eedy algo i hms in di e en a ia ions, as desc ibed in Chap e 4. In con as o hese me hods, he main algo i hms in his hesis use ano he app oach. The p esen ed algo i hms op imize he s uc u e, i.e. he senso placemen , and he obse e gain ma ix in pa allel. Due o non-con exi ies, which a ise when coun ing he used senso s and when calcula ing he H2 -no m wi h an unknown obse e , we had o e o mula e he op imiza ion p oblem. The disc e e `0 -no m was elaxed wi h an i e a i e eweigh ed `1 -no m. The H2 -no m was w i en wi h a LMI cha ac e iza ion, which simpli ied eplacing he non-con ex bilinea pa ei he wi h a subs i u ion o wi h a cone complemen a i y linea iza ion. The p oposed app oaches we e hen de eloped in o algo i hms and implemen ed o e icien ly and accu a ely sol e he senso placemen p oblem. The men ioned algo i hms we e es ed in Chap e 4. The i s es was a compa ison o he execu ion ime depending on he sys em size. The second es checked on he H2 -pe o mance o he chosen senso subse s o he di e en algo i hms, while compa ing he abili y o pa ame e ize he algo i hms so ha di e en numbe s o senso s we e selec ed. Addi ionally, a p ac ical example was sol ed. He e, he algo i hms had o de e mine an op imal senso subse . The pe o mance o he chosen subse s we e compa ed. The example had sligh ly o he equi emen s o he algo i hms since he p oblem was mo e ill-condi ioned han he andomly gene a ed examples. This e ealed u he di icul ies when pa ame e izing he algo i hm wi h cone complemen a i y linea iza ion. The conclusion o all he es s is ha he algo i hm wi h subs i u ion is one o he bes o he p esen ed algo i hms, since i has no se e e lacks, e.g. execu ion ime o pa ame e iza ion, and a sa is ying pe o mance. Simila o he g eedy algo i hm, he algo i hm wi h subs i u ion o con inuous- ime sys ems has a e y sho execu ion ime despi e o i s no ad anced implemen- a ion. The g eedy app oach and he e e se g eedy app oach bo h lead o good solu ions a he conside ed examples and a e he as es algo i hms. The sho sigh ed p ocedu e does no in luence he pe o mance a he desc ibed examples. Fu u e esea ch conce ning his opic could expand his app oach in o he ollowing di ec ions. The assump ion ha he sys em ma ix Ais comple ely known may no be ul illed. I is mo e ealis ic o assume ha one knows A wi h ce ain inaccu acies. Ano he possibili y is ha a non-linea sys em can be es ima ed in a de ined sec o and ha he algo i hms use bounds o his sec o o de i e an op imal subse o senso s. 33 Ano he di ec ion o u u e esea ch could be he expansion o he model o ac ua o placemen which is he dual p oblem o he one desc ibed he e. Mo eo e , o ac ua o placemen usually he H∞ -no m is used. Consequen ly, he app oach would ha e o be adap ed o he LMI cha ac e iza ion o his no m. 34 6 Appendix - Ma hema ical De ini ions and No a ion 6.1 `0-Vec o -No m The `0 -no m o ec o s has mo e han one commonly used de ini ion like ||x||0 := limp→0||xi||p p o p∈R+ and x∈Rn . P ecisely said, he `0 -no m e e s o he numbe o non-ze o elemen s in a ec o . The e o e i is s aigh o wa d o de ine also: ||x||0:= n X i=1 |sign(xi)| wi h sign(xi) :=      −1 o xi<0 0 o xi= 0 1 o xi>0 Since he posi i e scalabili y (i.e. |α| ||x||0 = ||αx||0 o α∈R+ ) is no sa is ied in gene al, he `0-no m is in ac no a eal no m, howe e i is o en e e ed o as he 0-no m. The `0-no m can be elaxed using a `1-no m, which is de ined as ollows: ||x||1:= n X i=1 |xi|. 6.2 H2-Sys em-No m De ine G ( s ) = "A B C0# := C ( sI −A ) −1B as he s a e-space ealiza ion o he ans e ma ix, QC := R∞ 0eA BBTeAT d as he con ollabili y G amian and QO := R∞ 0eAT CCTeA d as he obse abili y G amian o con inuous- ime sys ems. The H2-no m o a sys em G(s)is de ined as (acco ding o Sche e and Weiland [2000]): ||G(s)||2:= s1 2πZ∞ −∞ ace(G(jω)G(jω)∗)dω. (6.1) This sys em no m is used o speci y he pe o mance o he sys ems in his hesis, because i is he ypical no m o obse e s o dynamical sys ems, e.g. he well-es ablished Kalman il e (see He nbe ge [2010]). A ypical in e p e a ion o he no m is o see ||G ( s ) ||2 as he o al ou pu ene gy o an impulse esponse o he sys em(as in Sche e and Weiland [2000]). 35 The ela ion o he H2-no m o he G amians o a sys em G(s) = "A B C0#is ||G||2 2= ace(CQCCT) = ace(BTQOB). The de ini ion o he H2 -no m o disc e e- ime sys ems is e y simila . De ine G ( z ) = "A B C0# := C ( zI −A ) −1B as he s a e-space ealiza ion o he ans e ma ix o a disc e e- ime sys em. Consequen ly, he H2-no m o disc e e- ime sys ems is de ined as: ||G(z)||2:= s1 2πZπ −π ace(G(ejω)G(ejω)∗)dω. (6.2) 6.3 Ma ices and LMIs Nex , we will gi e some no a ional speci ica ions o his hesis. Gi en a ma ix L∈Rn×n we will deno e L−1 and LT as he in e se and he anspose o he ma ix. L∗j wi h j∈1,2, . . . , m de ines he j h column o he ma ix L. A posi i e o nega i e de ini e (semide ini e) ma ix L is w i en as L 0( L 0) o L≺ 0 (L0) espec i ely, while >, <, ≤,≥deno e an elemen wise compa ison. 36 Bibliog aphy F. Bach, S.D. Ahipasaoglu, and A. d’Asp emon . Con ex elaxa ions o subse selec ion. A Xi p ep in A Xi :1006.3601, 2010. E.J. Candes, M.B. Wakin, and S.P. Boyd. Enhancing spa si y by eweigh ed `1 minimiza ion. Jou nal o Fou ie Analysis and Applica ions, 14(5):877–905, 2008. L. El Ghaoui, F. Ous y, and M. Ai Rami. A cone complemen a i y linea iza ion algo i hm o s a ic ou pu - eedback and ela ed p oblems. Au oma ic Con ol, IEEE T ansac ions on, 42 (8):1171–1176, 1997. M. Fazel. Ma ix ank minimiza ion wi h applica ions. PhD hesis, S an o d Uni e si y, 2002. M. He nbe ge . Mode ne Me hoden de Regelungs echnik III. Lec u e a he Ins i u e o Au oma ic Con ol in SS 2010, Technichal Uni e si y Munich, Ge many, Oc obe 2010. S. Joshi and S. Boyd. Senso selec ion ia con ex op imiza ion. Signal P ocessing, IEEE T ansac ions on, 57(2):451–462, 2009. P. Kundu , N.J. Balu, and M.G. Lauby. Powe sys em s abili y and con ol, olume 4. McG aw-hill New Yo k, 1994. J. Lo be g. Yalmip: A oolbox o modeling and op imiza ion in ma lab. In Compu e Aided Con ol Sys ems Design, 2004 IEEE In e na ional Symposium on, pages 284–289. IEEE, 2004. Y. Mo, R. Amb osino, and B. Sinopoli. Senso selec ion s a egies o s a e es ima ion in ene gy cons ained wi eless senso ne wo ks. Au oma ica, pages 1330–1338, 2011. P.M. Na end a and K. Fukunaga. A b anch and bound algo i hm o ea u e subse selec ion. Compu e s, IEEE T ansac ions on, 100(9):917–922, 1977. J. Riebe . Lec u e obus con ol. Lec u e a he Ins i u e o Sys ems Theo y and Au oma ic Con ol in WS 2006/2007, Uni e si y o S u ga , Ge many, Oc obe 2006. C. Sche e and S. Weiland. Linea ma ix inequali ies in con ol. Lec u e No es, Du ch Ins i u e o Sys ems and Con ol, Del , The Ne he lands, 2000. S. Schule , U. Münz, and F Allgöwe . Decen alized s a e eedback con ol o in e connec ed p ocess sys ems. In AdChem, 2012. R. Smi h. Robus con ol & con ex op imiza ion. Lec u e a he depa men o elec ical & compu e enginee ing in SS 2010, Uni e si y o Cali o nia, San a Ba ba a, USA, June 2010. J.F. S u m. Using sedumi 1.02, a ma lab oolbox o op imiza ion o e symme ic cones. Op imiza ion me hods and so wa e, 11(1-4):625–653, 1999. L. Vandenbe ghe and S. Boyd. Applica ions o semide ini e p og amming. Applied Nume ical Ma hema ics, 29(3):283–299, 1999. 37 Danksagung An diese S elle möch e ich mich ech he zlich bei He n D . Ul ich Münz ü die in ensi e Be euung bedanken, die eilweise iel Zei in Ansp uch nahm. Ohne die zahl eichen achlichen Diskussionen und in e essan en An egungen wä e diese A bei so nich zus ande gekommen. Auße dem bedanke ich mich auch bei de Siemens AG ü die E möglichung de A bei und die inanzielle Un e s ü zung wäh enddessen. He n P o . D . Tobias Damm danke ich ü die seh angenehme Koope a ion und die seh hil sbe ei e Bean wo ung bei allen achlichen ode o ganisa o ischen F ages ellungen. Schließlich bedanke ich mich noch bei He n P o . D . La s G üne ü die Be ei scha , die A bei des Zwei gu ach e s zu übe nehmen. E klä ung Hie mi e klä e ich, dass ich diese Bachelo a bei selbs s ändig e ass und keine ande en als die on mi angegebenen Quellen und Hil smi el benu z habe und dass ich diese A bei nich be ei s zu E langung eines akademischen G ades einge eich habe. Bay eu h, 17. Augus 2012