Tehnici deOptimizareCristianOARAFacultateadeAutomaticasiCalculatoareUniversitateaPolitehnicaBucurestiSplaiulIndependentei313,Bucuresti,RomaniaFax: +40213234234Email: oara@riccati.pub.roCAPITOLUL1: Introducere 0Capitolul 1: INTRODUCEREOptimizareTipurideProblemeDimensiuneaProblemelorAlgoritmiIterativisiConvergentaCAPITOLUL1: Introducere 1 Introducere1. Optimizare Principiufundamentalaluneimultitudinideproblemecomplexedealocaresidecizie; Implicaselectiadevaloripentruomultimedevariabileinterrelationateprinfocalizareaatentieiasupraunei singurobiectivproiectat(alesspecial)pentruacuanticaperformantasi amasuracalitateadeciziei;Obiectivul: Estedeobiceiofunctiesaufunctionala; Estemaximizatsauminimizatcuposibileconstrangeri carelimiteazaalegereavalorilor pentruvariabile; Izoleaza si caracterizeaza un aspect relevant al unei probleme in timp ce teoria optimizariifurnizeazauncadruadecvatpentruanaliza; Poate: Protulsaupierdereaintr-unmediudeafaceri; Vitezasaudistantaintroproblemadezica; Veniturileprobabileintr-unmediudeinvestitiisupuseriscului;CAPITOLUL1: Introducere 2 Optimizare Bunastaresocialaincontextulplanicariiguvernamentale;Atentie! Este foarte rar posibil sa reprezentamtoate complexitatile interactiunilor dintre variabile,constrangerisiobiective; Formulareauneiproblemedeoptimizaretrebuiesaeprivitadoarcaoaproximatie; Intocmai ca si in alte domenii ale ingineriei abilitatile in modelare si o judecata corecta ininterpretarearezultatelorsuntabsolutnecesarepentruaobtineconcluziirelevante; Experientapracticasiintelegereaprofundaateorieisuntcheiasuccesului; Trebuie stapanit compromisul in construirea unui model matematic care descrie exactcomplexitateaproblemei (sucientdecomplex)si careestefezabil dinpunctdevederenumeric(nupreacomplex)Accentul cursului: Stapanirea acestui compromis si obtinerea de abilitati pentru a putea construimodeleinmodexpertceeaceinseamna: Identicareasisurprindereaaspectelorimportantealeuneiprobleme; Abilitateadeadistingemodelelefezabiledecelenefezabileprinstudiereatehnicilorexistentesiateorieiasociate; Extindereateorieidisponibileincazulunornoisituatii;CAPITOLUL1: Introducere 3 Optimizare2. Tipuri deProblemeVomconsiderainprincipalurmatoarelesubiecte: ProgramareLiniara ProblemeNeconstranse ProblemeConstranse(cuconstrangerialgebrice) Subiecte avansate in domeniul Controlului Automat al Sistemelor: (Control Optimal; OptimizareH-2siH-innit,optimizareNeharisiAproximanti,InegalitatiMatriceale,JocuriDiferentiale)ProgramareLiniara: Functiileobiectivsuntcombinatiiliniaredenecunoscute; Constrangerilesuntegalitatisauinegalitatimatricialeinnecunoscute; Acestemetodesuntrelativpopularedatoritafazeidemodelaresinuatatdatoritateorieirelativsimple; Sepoatetestachiarsipentruproblemeneliniarefacanduseinprealabiloliniarizare;CAPITOLUL1: Introducere 4 TipurideProblemeExemplu: Problemacuoconstrangeredebuget. Avemosumadebani xapecaretrebuiesaoimpartimintredouacheltuielidetipulx1 +x2 B.xi: sumaalocataactivitatiii;B: bugetultotal. Sapresupunemcafunctiaobiectivestegreutateamaxima. Atunciavemmaximizeaza w1x1 +w2x2undex1 +x2 B,x1 0, x2 0,unde wieste greutatea unitara (pe unitatea de pret) i. Aceasta este o problema tipica (sielementara)deprogramareliniara.Problemeledeprogramareliniaraaparadeseaineconomiesi nantesi mai rarininginerie. Deaceeanevomconcentrainspecialasupraproblemelordeprogramareneliniara.ProblemefaraConstrangeri: Auoimportantaatatteoreticacatsipractica; Dinpunctdevederepracticoproblemaconstransapoateintotdeaunatransformataprintr-osimplareformulareintr-oproblemaneconstransa(InproblemanoastracubugetulconstrangereaCAPITOLUL1: Introducere 5 TipurideProblemenuestefoarterelevantaintrucatintotdeaunaputemimprumutabani launanumitcost(rataadobanzii)); Dinpunctdevedereteoreticproblemelecuconstrangeri potinmultecazuri transformateinproblemefaraconstrangeri(deexempluoegalitatedeformax1 +x2=B); Inmajoritateacazurilor problemelefaraconstrangeri sunt piatradetemeliepentruaintelegeproblemelemaisosticatecuconstrangeri;ProblemecuConstrangeri: Inpracticaestemai uzual si mai simplusaformulamdirect oproblemacuconstrangerileeinaturale(deexempluoproblemacomplexaestereformulatasubformacatorvasubproblemecuanumiteconstrangeriinerente); Formulareamatematicagenerala:minimizeaza f(x)cu hi(x)=0, i=1, 2, . . . , m,gj(x) 0, j=1, 2, . . . , r,x Sundexesteunvectorndimensional denecunoscute, f, hisi gjsuntfunctii dexcuvalori si Sesteosubmultimealui Rn;festefunctiaobiectiv sihi, gjsi Ssuntconstrangerile.CAPITOLUL1: Introducere 6 TipurideProblemeNota: Inmoduzual vomintroduceanumiteipotezesuplimentare, inprincipal pentruafaceproblemelenetedeintr-unanumitsens,conducandlaasanumitaprogramareinvariabilecontinue: f(si hi, gj) sunt de obicei presupuse continue si uneori chiar cu derivate continue de un anumitordin(micivariatiiinxconduclamicivariatiialediverselorvaloriasociatecuproblema);Sesteinmoduzual osubmultimeconexapentruaasiguracamici variatii alelui xramaninsubmultime;CAPITOLUL1: Introducere 7 TipurideProbleme3. DimensiuneaProblemelorOmasuraacomplexitatii unei problemedeprogramareestedimensiuneamasurataintermeniinumaruluidevariabilenecunoscute si/saunumaruldeconstrangeri.Avand in vedere performanta calculatoarelor moderne distingem urmatoarele clase de probleme: Dimensiunemica(avandpanala5variabilesi/sauconstrangeri); Dimensiunemedie(avandintre5si100variabile); Dimensiunemare(avandmaimultde100poate1000saumaimultevariabile).Aceasta clasicare nu este desigur rigida dar reecta abordarile de calcul oarecum diferite pentruacesteclasedeprobleme. Teoriamatematicaclasicaincluzandmutiplicatori Lagrange, teoremedetipKuhnTucker si extensiilelor seaplicaproblemelorindiferentdedimensiunealor. Totusiteorianuestepotrivitaatuncicandabordamoproblemadpdvalgoritmicintrucatnutineseamadedicultatileasociatecurezolvareacuuncalculatoraecuatiilorrezultanddinconditiilenecesaredeordinul 1. De aceea trebuie sa dezvoltam instrumente numerice eciente pentru cautarea punctelordeoptiminlocsarezolvamdirectrespectiveleecuatii. Inzilelenoastre, tehniciledecautarepotaplicatepentrurezolvareaunor problemedeprogramareneliniarade500variabilesi problemeCAPITOLUL1: Introducere 8 DimensiuneaProblemelordeprogramareliniarade400variabilesi 1000constrangeri (denimastfel deproblemecainddedimensiunemedie).Probleme cu mai multe variabile si/sau constrangeri trebuie rezolvate cu proceduri speciale careexploateazastructuraspecialaaacestora.CAPITOLUL1: Introducere 9 DimensiuneaProblemelor4. Algoritmi Iterativi si ConvergentaCeimaimultialgoritmidezvoltatipentruarezolvaproblemedeoptimizaresuntiterativi: Seselecteazaunvectorintitialx0inmultimea S; Algoritmulgenereazaunvectormaibunx1 S; Algoritmulesterepetatsipebazaluix0si/saux1esteselectatunvectorsimaibunx2 S; Segasesteunsirdepunctedinceincemai bunex0, x1, x2, x3, . . . , xk, . . .caretindecatrepunctulsolutiex; Procesul esteterminat imediat ceseajungelaxsaucandestegasit unpunct sucient deapropiat(dinmotivepractice).Teoriaalgoritmiloriterativiseimpartiteintreiaspectecesesuprapunintr-ooarecaremasura: Dezvoltareaalgoritmului propriuzis(bazatapeproblemadeprogramareparticulara, structurasainerentasiecienta(performanta)calculatoarelornumerice); Vericarea ca respectivul algoritm genereaza un sir care converge la punctul solutie (convergentaglobala); Vitezasaurataconvergentei sereferalacatderepedeseapropiedesolutiesirul depuncte(convergentalocala)CAPITOLUL1: Introducere 10 AlgoritmiIterativisiConvergentaOteoriebunainlocuiestecusucces1000rulari pecomputerRezultatedisponibile: Programare liniara: nu exista inca o teorie folositoare privind convergenta metodei simplex(probabil ceamai vechesi importantametodadeprogramareliniara); acestlucrusedatoreazaconvergentei intrunnumarnitdepasi; Suntdisponibileanumiteestimari euristicesi ovastaexperientapractica; Programareneliniara: Proprietatiledeconvergentaaleunui numar maredealgoritmi aufostdeduse analitic prin metode relativ elementare si au fost vericate prin numeroase exemplenumerice;Teoriarateideconvergentaareanumiteproprietatiatractive: Estesimplapentrumultialgoritmisosticati; Oclasa larga de algoritmi relativ diferiti au acceasi rata de convergenta. Mai precis, inmultecazuri existaoratacanonicadeconvergentaasociatacuoproblemadeprogramarecareguverneazadiversiialgoritmiaplicatiaceleiprobleme; Perglobal,teoriaconvergenteiestesimplasiputernica.CAPITOLUL1: Introducere 11 AlgoritmiIterativisiConvergentaCapitolul 2: PROPRIETATIDEBAZAALESOLUTIILORSIALGORITMILORInprincipalconsideramurmatoareaproblema:minimizeaza f(x)cu x (1)undefesteofunctiecuvalorirealesi(multimeafezabila) Rn.Ipotezadebaza: coincidecu Rnsauesteosubmultimesimplaalui Rn.Cuprins1. ConditiiNecesaredeOrdinul12. ExempledeProblemefaraConstrangeri3. ConditiideOrdinul24. FunctiiConvexesiConcave5. MinimizaresiMaximizaredeFunctiiConvexe6. ConvergentaGlobalaaAlgoritmilordeDescrestere7. VitezadeConvergentaCAPITOLUL2: ProprietatideBaza 121. Conditii NecesaredeOrdinul IntaiPrimaproblema: Existavreosolutie?Principalulinstrumentteoretic: TeoremaluiWeierstrass.Principalul scop: Caracterizarea punctelor solutie si obtinerea unor algoritmi care sa le gaseasca.Deosebimdouatipuridepunctesolutie:-punctedeminimlocal-punctedeminimglobalDenitia1. Unpunctx esteunpunctdeminimrelativ (saupunctdeminimlocal)aluifpestedacaexista>0a.i. f(x) f(x)oricarex aatlaodistantadexmaimicaca. Dacaf(x)>f(x)oricarex , x ,=x, intr-ovecinatatealui x, atunci xestepunctdeminimrelativinsensstrict alluifpeste.Denitia2. Unpunctx estepunctdeminimglobalalluifpestedacaf(x) f(x)oricarex . Dacaf(x)>f(x)oricarex , x ,=xatunci xesteunpunctdeminimglobalinsensstrict alluifpeste.CAPITOLUL2: ProprietatideBaza 13 ConditiiNecesaredeOrdinulIntaiAtentie! Candabordamoproblemapresupunemimplicitcaneintereseazaminimeleglobale; Realitatea numerica cat si cea teoretica dicteaza ca trebuie sa ne multumim cu puncte de minimrelativ; De regula, conditiile si solutiile globale pot obtinute doar daca functia poseda anumiteproprietatideconvexitatecegaranteazacaoriceminimrelativesteglobal.Pentruaobtineconditiilecetrebuiesatisfacuteintr-unpunctdeminim,incepemprinastudiavariatiilede-alungul unor directii fezabileinjurul lui x, cazincarefunctiadevinedeosinguravariabila.Denitia3. Dandu-sex vectoruldesteo directiefezabilainxdaca existaun>0astfelincatx +d oricare,0 .Propozitia4.[Conditii necesaredeordinul 1] Fie o submultime inRnsi e fc1ofunctiedenitape. Dacaxesteunpunctdeminimrelativalluifpeste,atuncipentruoriced Rncareesteodirectiefezabilainx,avemf(x)d 0.CAPITOLUL2: ProprietatideBaza 14 ConditiiNecesaredeOrdinulIntaiUncaz particular important este candxeste ininteriorul lui (cade exemplucandestemultimedeschisa)siecaredirectiedinxestefezabila!!!!Corolarul 5.[Cazul neconstrans] Fieosubmultimealui Rnsi ef c1ofunctiedenitape. Dacaxesteunpunctdeminimrelativalui fpesi dacaxestepunctinteriorpentru,atuncif(x)d=0.Nota: Incazul neconstransobtinemnecuatii cunnecunoscutecarepotrezolvateexplicitinmultesituatii(cadeexemplucandfunctiaobiectivestepatratica); Ecuatiilecarerezultasuntingeneralneliniaresifoartecomplicatderezolvat; Abordareanoastra este nuinspre rezolvareaecuatiilor ci inspre gasireaunui sir iterativ careconvergecatrex.Exemplul 6. Consideramproblemaminimizeaza f(x1, x2)=x21x1x2 +x223x2peste R2. Punctdeminimgloballax1=1,x2=2.CAPITOLUL2: ProprietatideBaza 15 ConditiiNecesaredeOrdinulIntaiExemplul 7.minimizeaza f(x1, x2)=x21x1 +x2 +x1x2,cand x1 0, x2 0.Punctdeminimglobalx1=0.5, x2=0incarederivatelepartialenuseanuleaza. Cutoateacesteadeoareceoricedirectiefezabilatrebuiesasatisfacax2 0,avem f(x)d 0pentruoricedirectiefezabilainx.CAPITOLUL2: ProprietatideBaza 16 ConditiiNecesaredeOrdinulIntai2. ExempledeProblemefaraConstrangeriExemplul 8.[Productie] O problema uzuala in economie este determinarea celui mai bun mod deacombinadiverseintrari pentruaproduceunoarecareprodus. Sestiefunctiaf(x1, x2,, xn)care dacantitateade produse realizate cafunctie de intrarile x1, x2,, xn. Pretul unitar alprodusului este qsi preturile unitare ale intrarilor sunt p1, p2,, pn. Producatorul dorindsamaximizezeprotultrebuiesarezolveproblemamaximizeaza qf(x1, x2,, xn) p1x1p2x2 pnxn.Conditiilenecesaredeordinulintaispuncaderivatelepartialeinraportcuxitrebuiesaseanuleze,obtinandcelenecuatiiqfxi(x1, x2,, xn)=pi, i=1, 2,, n.Exemplul 9.[Aproximare] Optimizarease foloseste curent inteoriaaproximarii de exempluvezi IdenticareaSistemelor. Sapresupunemcavalorilefunctiei gsuntdeterminateexperimentalinmpuncte, x1, x2,, xmcaavandvalorileg1, g2,, gm. DorimsaaproximamfunctiagCAPITOLUL2: ProprietatideBaza 17 2. ExempledeProblemefaraConstrangeriprintr-unpolinomh(x)=anxn+an1xn1+ +a0,unden0,x2>0,atunciconditiilenecesaredeordinul1sunt3x212x1x2=0, x21 + 4x2=0.Acesteaauosolutiex1=x2=0careesteunpunctpefrontiera,darexistadeasemeneaosolutiex1=6, x2=9. Saobservamcapentrux1xat inx1=6, functiaobiectivatingeunminimrelativinraport cux2inx2=9. Reciproc, cux2xat lax2=9, functiaobiectivatingeunminimrelativinraportcux1lax1=6. Inciudaacestui fapt, punctul x1=6, x2=9nuesteunminimrelativpentrucaHessianulesteF=

6x12x22x12x14

careevaluatinx1=6, x2=9esteF=

18 1212 4

cenuestepozitivsemidenit. Prinurmaresolutiapropusanuesteunpunctdeminimrelativ.CAPITOLUL2: ProprietatideBaza 21 ConditiideOrdinulDoiConditii SucientepentruunMinimRelativIntarind conditiile de ordinul 2 din Propozitia 11 obtinem un set de conditii ce implica ca x esteun minim relativ. Consideram in continuare numai probleme neconstranse (sau in care minimul esteininteriorulregiuniifezabile)deoarececazulmaigeneralesteextremdetehnicsiareoimportantateoreticasipracticamarginala.Propozitia14.[Conditii necesaredeordinul 2cazul neconstrans] Fie f c2o functiedenitaintr-oregiuneincarexesteinterior. Presupuneminpluscai) f(x)=0;ii) F(x)>0.Atuncixesteunpunctdeminimlocalstrictalluif.CAPITOLUL2: ProprietatideBaza 22 ConditiideOrdinul24. Functii Convexesi ConcavePentruaobtineoteoriecareestecapabilasacaracterizezepunctedeminimglobalsinunumailocal introducemanumitepresupuneri detipconvexitatecarefacrezultatelemai puternicedar inacelasitimprestrangariadeaplicatii.Denitia15. Ofunctiefdenitaintromultimeconvexaestenumitaconvexadacapentruoricex1, x2 siorice,0 1,arelocf(x1 + (1 )x2)) f(x1) + (1 )f(x2).Dacapentruorice,00] (62)si amobtinut o noua solutie fezabila cu vectorul aqinlocuit de ap, unde p este indexul ceminimizeaza(62). Dacaminimul (62)esteobtinut simultanpentrumai multi indici atunci nouasolutie este degenerata si oricare vector avand componenta corespunzatoare nula se poate consideracaparasindbaza!Dacanici unul dintre akqnueste pozitiv, atunci toti coecientii lui (61) cresc (sauramanconstanti)candil crestempesinusepoateobtinenici onouasolutiefundamentala! Inaceastasituatieobservamcasistemul Ax=b, x 0aresolutii fezabilecucoecienti oricatdemari deunderezultacamultimeaKasolutiilorfezabileestenemarginita!Pescurt: Dandu-seosolutiefundamentalafezabilasi unvector arbitrar aqsunt posibiledouasituatii:Existaonouasolutiefundamentalafezabilaavandu-lpeaqinbaza(inloculunuiadintrevectoriioriginali);Multimeasolutiilorfezabileestenemarginita!CAPITOLUL9: MetodaSimplex 169 PuncteExtremeAdiacenteIlustrareaoperatiilorintablou:a1a2a3 amam+1am+2 anb1 0 00 a1,m+1 a1,m+2 a1,n b10 1 00 a2,m+1 a2,m+2 a2,n b20 0 10 ...........................0 01am,m+1 am,m+2 amn bm(63)Acest tablou are o solutie cu baza a1, a2,, am. Presupunemca bi0 a.i. solutiafundamentalacorespunzatoareestefezabila. Dorimintroducereacoloanei q>msi mentinereafezabilitatii. Pentruadeterminacareelementdincoloanaqsal folosimcapivot(si deci cevectoral bazei vaeliminat)folosim(62)ptr. calcularearapoartelorxkakq=bkakq, k=1, 2,, m, dincareilalegempecelmaimicnenegativ,sipivotamperespectivul akq.InterpretareGeometricaExistadouainterpretarigeometricealeconceptelorintroduse:Inspatiul incare este reprezentat x: Regiunea fezabila este omultime convexa iar solutiilefundamentalefezabilesuntpuncteleextreme(vezi cursul precedent). Puncteleextremeadiacentesuntpunctecarestaupeolaturacomuna.CAPITOLUL9: MetodaSimplex 170 PuncteExtremeAdiacenteInspatiulincaresuntreprezentatecoloaneleluiAsib;Relatiafundamentalaesteb=n

k=1aixi.Un exemplu cu m=2si n=4este reprezentat in Figura 9.1. Osolutie fezabila este oreprezentarealui bfolosindcombinatii semipozitivedeai. Osolutiefundamentalafezabilaesteoreprezentarealuibfolosindnumaimcombinatiipozitive.a2ba1a4a3Figura9.1Observaticaputemplecacuobazaformatadina1sia2darnudina1sia4! Dacaplecamcua1si a2si pentruaobtineobazaadiacentail adaugampea3, atunci automatiesea2. Dacailadaugampea4atunciieseautomata1!CAPITOLUL9: MetodaSimplex 171 PuncteExtremeAdiacente3. Determinareaunei Solutii MinimeFezabileCestimdeja?Cum sa pivotam si indata ce am selectat o noua coloana arbitrara care va intrain baza stim sa determinam care coloana iese din baza a.i. solutia sa ramana fezabila (sau respectivsadeterminamcasolutiaestenemarginita).Cedorimincontinuare? Cumselectamcoloanapecareovomintroduceinbazaa.i. sareducemvaloareafunctiei!Cuplamceledouaidei si obtinemmetodasimplex!Presupunem ca avem solutia fundamentala fezabila xT= xTB0

= x1x2. . . xm0 . . . 0

impreunacutabloula1a2a3 amam+1am+2 anb1 0 00 a1,m+1 a1,m+2 a1,n b10 1 00 a2,m+1 a2,m+2 a2,n b20 0 10 ...........................0 01am,m+1 am,m+2 amn bm.(64)CAPITOLUL9: MetodaSimplex 172 DeterminareauneiSolutiiMinimeFezabileValoareafunctieicorespunzatoareoricareisolutiiestez=n

i=1cixi=cTBxB=:z0, cTB= c1. . . cm

. (65)Dacaatribuimvalori arbitrarelui xm+1, . . . , xnvariabilelefundamentaleseobtindin(64) prinformulelex1= b1

nj=m+1a1jxjx2= b2

nj=m+1a2jxj......xm= bm

nj=m+1amjxj.(66)Folosind(66)sepoteliminavariabilelex1, . . . , xmdinformulagenerala(65)siseobtinez=cTx=z0 + (cm+1zm+1)xm+1 + (cm+2zm+2)xm+2 + + (cnzn)xn(67)undezj:=m

i=1aijcj, m+ 1 j n. (68)Relatia (67) este fundamentala pentru determinarea coloanei pivot ce va introdusa in bazaintrucat davaloareafunctiei inorice punct al solutiei Ax=bintermenii variabilelor liberexm+1,, xn.CAPITOLUL9: MetodaSimplex 173 DeterminareauneiSolutiiMinimeFezabileDin aceste formule se poate deduce daca exista vreun avantaj in inlocurirea unei varibilefundamentalecuunanoua. Deexemplu, dacaunul dintrecoecientii cj zjestenegativpentruun j, m+1 j n, atunci cresterea lui xjde la zero la o valoare pozitiva va descreste valoareafunctieisidecivageneraosolutiemaibuna!Deducemacumrelatiiledintr-oaltaperspectiva. Fieaicoloanaiatabloului. Oricesolutiesatisfacex1e1 +x2e2 + +xmem=b n

j=m+1xjajLuandprodusulscalaralacesteiecuatiivectorialecucTBobtinemm

i=1cixi=cTBb n

j=m+1xjzjincarezj:=cTBaj. Adunand

nj=m+1cjxjambilormembriseobtinerelatiaanterioaracTx=z0 +n

j=m+1(cj zj)xj. (69)Teorema103.[Imbunatatireasolutiei fundamentalefezabile] Fie o solutie fundamentalafezabila nedegenerata avand valoarea corespunzatoare a functiei obiectiv z0si presupunemcaCAPITOLUL9: MetodaSimplex 174 DeterminareauneiSolutiiMinimeFezabileexista j a.i. cj zj0stabilindastfel carevector parasestebaza. Infelul aceastas-adeterminatcarecomponentaestenoul pivotsi deci Ek+1. ReturnarelaPasul1.Observatia107. Pentru stocarea matricilor Eeste necesara memorarea a numai m+1 numere:(p, v1, . . . , vm). Maimult,nicinuestenevoiesareconstituimmatricileEinmodexplicitcidoarformuleledemultiplicatEladreaptacuunvectorcoloana(Pasii 1si 3)si lastangacuunvectorlinie(Pasul2)!Observatia108. In cazul rezolvarii unor probleme de dimensiuni mari prin aceasta metodamajoritateainformatiilor sepot pastrainmemoriilemai lentealemasinii decalcul (HDD, DVD,CAPITOLUL9: MetodaSimplex 190 MetodaSimplexRevizuitaetc). Coloanelelui AsepotaduceinmemoriaRAMinmodindividual, si sepotinmulti cuB1prinaducereasuccesivainmemoriaRAMavectorilordedimensiunem + 1cedenescmatricileE.Observatia109. Problemelededimensiuni mari careaparuzual inprogramarealiniaraaumultastructura,implicandadeseacamatriceaA(sidesemeneamatriceaB)suntmatricirare(cuputineelemente nenule). In orice caz, B1nu este matrice rara in general si acest fapt evidentiaza avantajulformei produs. Un avantaj suplimentar al formei produs este ca vectorii (p, v1, v2, . . . , vm) denindmatricile Esunt probabil ei insasi rari, generand o reducere masiva in memoria si timpul de executienecesare.ReinversarePentruproblemededimensiunimarisauprostconditionatenumericeroriledecalculseacumuleazapanalaunnivel lacareB1esteputernicimprecisa! Evaluareaerorii lapasul curentsefaceevaluandBxB bin care xBeste valoarea curenta gasita prin formula xB=B1b in care pentru calculul lui B1sefoloseste valoarea curenta a lui B1. Daca eroarea este semnicativa este recomandata reinversareacat mai exact posibil a lui Bsi restartatea procedurii. Aceasta operatie se numeste reinversaresi esteocomponentaesentialaaoricarei biblioteci deprograme. Pentruinversarealui BsepoateCAPITOLUL9: MetodaSimplex 191 MetodaSimplexRevizuitafolosi orice proceduranumeric stabila, cel mai adeseafolosindu-se proceduri de pivotare incarepivotiisealeglaecarepasa.i. saminimizezeeroriledecalcul.In cazul formei produs reinversarea serveste si pentru controlulnecesaruluidememorie: sirullungdematrici elementarecedescriuinversalui Besteinlocuit cuunsir demmatrici ! Maimult,inacestcazalegereapivotilorsefacea.i. samentinemstructurarara(inafaradeacurateteacalculelor).CAPITOLUL9: MetodaSimplex 192 MetodaSimplexRevizuita8. MetodaSimplexviaDescompunereaLUInprocedurapropusainsectiuneaprecedentaamvazut caparcurgereaunui pas dinmetodasimplexnuestedependentadecunoastereaexplicitaainversei B1ci derezolvareaunorsistemedeecuatii avandmatriceacoecient B. Cuaceastaobservatieprocedurasimplexdinsectiuneaprecedentasepoatedainforma:Algoritmul simplexrevizuit:Pasul 0: SedabazacurentaB.Pasul 1: SecalculeazasolutiacurentaxBcesatisfaceBxB=b;Pasul 2: SerezolvaTB=cTBsisecalculeazacoecientuldecostrelativrTD:=cTDTD.DacarD 0,STOP;valoareacurentaesteoptimala;Pasul 3: Se alege q a.i. rq0, i=1, 2,, m. Dacanuexista aiq>0,STOP.Problemaestenemarginita. Altfel sealegeuni =ppentrucareseatingeminimul si decivectorulpvaparasibaza;CAPITOLUL9: MetodaSimplex 193 MetodaSimplexviaDescompunereaLUPasul 5: ActualizeazaB. ReturnarelaPasul1.Din procedura de mai sus se observa ca intr-adevar nu este nevoie de B1ci doar de rezolvareaatrei sistemedeecuatii liniare, douaavandu-l peBdreptcoecientmatriceal si unul peBT. Inprocedurile anterioare sistemele erau implicit rezolvate prin operatiile corespunzatoare de pivotare pemasuracametodaprogresa. Dpdval ecientei si precizieinumericemetodadepivotareprezentatanuestelafel deecientaprecumeliminareaGaussianapentrusistemegeneraledeecuatii liniare.InconsecintaarerostsaadaptameliminareaGaussianapentrumetodasimplex, rezultatul indoversiuneametodeisimplexrevizuitecareareostabilitatenumericamaibunasipentruproblemededimensiunimarioferaeconomiiimportantedememorie.Neconcentramasupracelortreisistemecetrebuierezolvatelaecarepas:BxB=b, TB=cTB, Baq=aq. (83)PresupunemcaBafostdescompussubformaB=LUundeLsi Usuntmatrici inferiorrespectivsuperior triangulare(presupunempentrusimplitatecanuavemnevoiedereordonarepelinii sepoaterelaxadarcomplexitateaexpunerii cresteconsiderabil). Deci ecaresistem(83)sepoaterezolvaprinrezolvareaadouasistemetriangulare.CheiacresteriiecienteimetodeisimplexconstainactualizareaecientaaacestordouamatriciCAPITOLUL9: MetodaSimplex 194 MetodaSimplexviaDescompunereaLUtriangularecandseschimbaunsingurvectorbaza! Presupunemcalainceputul metodei simplexavemB= a1a2. . . am

silasfarsitulcicluluivomaveaB= a1a2. . . ap1ap+1. . . amaq

(vectorulaps-ainlocuitcuaq). SaobservamcaBseobtinedinBprineliminarealui ap,siftareavectorilorcuindicimaimarisprestangasiadaugarealuiaqinextremitateadreapta. AvemL1B= L1a1L1a2. . . L1ap1L1ap+1. . . L1amL1aq

= u1u2. . . up1up+1. . . umL1aq

=HincareuisuntexactcoloaneleluiUiarmatriceaHareformaH =CAPITOLUL9: MetodaSimplex 195 MetodaSimplexviaDescompunereaLUcu zerouri sub diagonala principala in primele k 1 coloane si zerouri sub elementul imediat de subdiagonalaprincipalainrestul decoloane. MatriceaHsepoateconstrui faracalculesuplimentaredeoareceuisunt cunoscutesi L1aqestedejacalculat atunci candserezolvaal treileasistem(83). Tot ceavemdefacut estesaanulamelementelenenulesubdiagonalefolosinddeexemplueliminareaGaussiana. Innal seobtinematriceasuperiortriangularaUcaurmareaaplicarii unortransformaridetipulMi=___________11...1mi1...1___________, i=k, k + 1, . . . , m1 (84)subformaU=Mm1Mm2 MkH. (85)ObtineminnalB=LH=LM1kM1k+1 M1m1U, (86)L=LM1k. . . M1m1(87)CAPITOLUL9: MetodaSimplex 196 MetodaSimplexviaDescompunereaLUsidecidescompunereaB=LU. (88)SeobservacaLsecalculeazasimplusiesteinferiortriunghiularadeoareceM1i=_________11...1mi1...1_________Observatia110. Exista multe variante concrete de implementare: transformarile Mise potmemora in loc sa evaluamL; descompunerea LUse poate reevalua periodic (similar ca lareinversare) si se pot folosi intreschimbari de linii si coloane pentru a mximiza stabilitatea sau pentruaminimizadensitateadescompunerii(veziExercitiile)CAPITOLUL9: MetodaSimplex 197 MetodaSimplexviaDescompunereaLU9. ConcluziiMetodasimplex se bazeazape faptul cadacavaloareaoptimalaaunui programliniar estenita atunci seatingelaosolutiefundamentalafezabila. Exista douainterpretariposibile alemetodeisimplex: (Prinvariatii continue): Sepleacacuosolutiefezabilafundamentalasi unadintrevariabilelenefundamentaleestecrescutaincetdelazero. Intimpceaceastavariabilaestecrescuta,restuldevariabilefundamentalesunt ajustatea.i. sasepastrezefezabiliatea. Schimbareafunctieiobiectiv la o schimbare unitara a variabilei nefundamentale este coecientul de cost relativasociatcuvariabilanefundamentala. Dacacoecientul estenegativ, valoareafunctiei obiectivesteimbunatatitapemasuracevariabilanefundamentalaestecrescutapanainpunctul incareocresteremai marevioleazafezabilitatea. Inacestpunctunadintrevariabilelefundamentaleestezerosisefaceintreschimbareacuvaribilanefundamentala. (Prin variatii discrete): Deoarece este necesar sa consideram doar solutii fundamentale fezabile,se selecteaza diverse baze sise calculeaza solutiile fundamentale corespunzatoare prin rezolvareaunor sisteme de ecuatii liniare. Logica alegerii unor noi baze este generata de coecientii de costrelativ.ConcluziiTehnici deOptimizare(ParteaaIIIa: Control Optimal)CristianOARAFacultateadeAutomaticasiCalculatoareUniversitateaPolitehnicaBucurestiSplaiulIndependentei313,Bucuresti,RomaniaFax: +4013234234Email: oara@riccati.pub.roConcluziiCapitolul 10: INTRODUCERERecapitulatinotiuniledelaTSI+II:SemnalSistemControlControlAutomatComportareDezirabilaaunuiSistemCAPITOLUL11: NOTIUNIDEBAZA 200 NotiunideBazaCapitolul 11: NOTIUNIDEBAZASistemLiniarProprietatideBazaaleSistemelorLiniareSpatiideSemnalesiFunctiideTransferEvolutiipeSpatiulStarilorGeneratedeIntrariL2OperatorulL2IntrareIesireDescriereDinamica: x(t) = Ax(t) +Bu(t),y(t) = Cx(t) +Du(t),(89)incaret R,x(t) Rnestestarea,u(t) Rmesteintrarea,y(t) Rpesteiesireasistemului,siA,B,C,DsuntmatriciconstantededimensiuniadecvateA Rnn, B Rnm, C Rpn, D Rpm.Comportareaintrareiesireasistemului (89) estedescrisaconvenabil dematriceadetransferCAPITOLUL11: NOTIUNIDEBAZA 201 NotiunideBazacareestematricearationalapropriededimensiunip mG(s):=C(sI A)1B +D=

A BC D

(s). (90)Facand o schimbare de variabile de forma x:=Tx (Tmatrice inversabila), vectorul transformat xsatisface x(t) = A x(t) + Bu(t),y(t) = C x(t) + Du(t),(91)incareA:=TAT1, B:=TB, C:=CT1, D:=D. (92)NOTA:G(s)seobtineluandtransformataLaplacein(89)si explicitandy(s)cafunctiedeu(s)informay(s)= G(s)u(s) (93) Incepand cu o reprezentare a lui Gca matrice rationala proprie putemintotdeauna obtinereprezentaredestare(89)scriindrealizareastandard(A, B, C, D)alui G. Sepoateintotdeaunaasiguraminimalitatearealizarii.CAPITOLUL11: NOTIUNIDEBAZA 202 NotiunideBaza Oschimbare de variabila (transformare de similaritate sau transformare de echivalenta) nuafecteazaspectrulmatriciiAnicimatriceadetransferintrareiesire.CAPITOLUL11: NOTIUNIDEBAZA 203 NotiunideBazaProprietati deBazaaleSistemelorLiniareUnsistemsenumeste stabil: dacatoatevalorilepropriialeluiAsuntin C antistabil: dacatoatevalorilepropriialeluiAsuntin C+ dihotomic: dacaAnuarevaloripropriipeaxaimaginaraNOTA: Stabilitatea, antistabilitatea, dihotomiasi proprietatileI/Osuntinvariantesubtransformari decoordonate Facand o transformare de coordonate T, un sistem dihotomic se poate descompune intro partestabilasiunaantistabila:A=TAT1=

AOO A+

]n]n+, B=TB=

BB+

, C=CT1= CC+

. .nn+(94)CAPITOLUL11: NOTIUNIDEBAZA 204 ProprietatideBazaaleSistemelorLiniareincareAestestabilasiA+esteantistabila.Unsistemsenumeste: Controlabil: daca(A, B)satisfacerank sI A B

=n, s Stabilizabil: daca(A, B)satisfacerank sI A B

=n, s, Re s 0ExistaFa.i. A +BFestestabila Antistabilizabil: daca(A, B)satisfacerank sI A B

=n, s, Re s 0.Notiuniduale: Observabilitate,Detectabilitate,AntidetectabilitateCAPITOLUL11: NOTIUNIDEBAZA 205 ProprietatideBazaaleSistemelorLiniareSpatii deSemnalesi Matrici deTransferDEFINIM: L(C0): spatiul Banachal functiilotmatricialecomplexeG(s)caresuntmarginitepe C0,cunormaL(C0)jGj:=supsC0(G(s)) (95)incare: valoareasingularamaxima. RH: subspatiul rational constanddinmatrici proprii p mcuelementemarginitepeaxaimaginara. RH+,pmspatiulmatricilorrationalepropriicuelementeanaliticein C+ C0 RH,pmspatiulmatricilorrationalepropriicuelementeanaliticein C C0.NOTA: DacaAestedicotomic G RL. DacaAestestabila G RH+ DacaAesteantistabila G RH .CAPITOLUL11: NOTIUNIDEBAZA 206 SpatiideSemnalesiMatricideTransfer Unsistemcumatriceadetransfer RH+estestabilintrareiesire(coincidecuRH+ ) Unsistemstabil (numitsi internstabil cuAstabila)esteintotdeaunastabil insensintrareiesire. Reciprocanuesteadevaratadecatdacarealizareaestestabilizabilasidetectabila.Problema centrala inTeoria sistemelor: stabilitatea interna pentruca garanteaza ca oricesemnal deenergienita(normaL2nita)injectatoriundeinsistemgenereazasemnaledeenergiemarginita(normaL2nita).PentrufunctiidetransferavemjGj=supR(G(j))=supRjG(j)jin care jj este norma operatoriala indusa a matricii (= norma indusa a operatorului intrareiesireasistemului).NOTA: NormaLaunui sistemestenitadacasi numai dacamatriceadetransferesteanaliticapeaxaimaginaraincluzandlainnit! Norma La unui sistem da energia maxima a semnalului de iesire cand intrarea este un semnaldeenergiemarginitade1! Celmaiprostcaz!CAPITOLUL11: NOTIUNIDEBAZA 207 SpatiideSemnalesiMatricideTransferRezultateasupranormei LTeorema111.[Teoremalui Rellich] Fie matricea nn M(x)=M(x) depinzand continuudeparametrul real xapartinandintervalului I. Atunci existafunctii realecontinue1, . . . , ndenitepeI,a.i. n(x) . . . 1(x),pentruoricexinI,si(M(x))= i(x)].Corolarul 112. Pentru G RLpm,(G(j))depindecontinuude R,estemarginitasiisiatingemaximumpentru [, ],undeprindenitie G(j)= G(j)=D.Teorema113. PresupunemcasiruldesistemeGk=

AkBkCkDk

, k N, (96)estea.i. Ak A, Bk B, Ck CsiDk Dcandk , Asi Aksuntstabile, siG(s)=C(sI A)1B +D 0. AtuncilimkjGkj=0.Demonstratie: Rezultatulpoatesunaevidentdarnuestedeloctrivial!!!!CAPITOLUL11: NOTIUNIDEBAZA 208 SpatiideSemnalesiMatricideTransferRezultateprivindnormaL2DEFINIM: Spatiul L2(M): Spatiul Hilbert al functiilor complexe matriciale (vectoriale sauscalare)G(t)pentrucare_MTrace [G(t)G(t)]dt< , (97)unde M estesau Z,(, ), C0,sauD.Inparticular, L2(C0)estespatiul Hilbertal functiilormatriciale(vectorialesauscalare)G(s)cunormaL2(C0)nitajGj2:= 12_Trace [G(j)G(j)]d]12. (98)NOTA: DacaG Gesteofunctierationalaatunci normaL2(C0)estenitadacasi numai dacaGnuarepolipeaxaimaginarasiestestrictproprie. NormaL2aunui sistemdaenergiasemnalului deiesirecandlaintrareseaplicaunimpulsDirac!!!CAPITOLUL11: NOTIUNIDEBAZA 209 SpatiideSemnalesiMatricideTransferCalculul alternatival normelorPresupunemD=0siAstabila. NormaL2(C0)alui G sepoatecalculafolosindjGj2=[Trace (BTQB)]12=[Trace (CPCT)]12(99)incarePsiQsuntunicelesolutiialeurmatoarelorecuatiiAP+PAT+BBT=0, ATQ+QA +CTC=0. (100)PpD=0siAantistabila. NormaL2(C0)alui G sepoatecalculafolosindjGj2=[Trace (BTQB)]12=[Trace (CPCT)]12(101)unde Psi QsuntunicelesolutiialeecuatiilorAP+ PATBBT=0, ATQ+ QA CTC=0. (102)CalcululnormeiLnecesitaintotdeaunaocautareiterativa!!!CAPITOLUL11: NOTIUNIDEBAZA 210 SpatiideSemnalesiMatricideTransferEvolutii inSpatiul StarilorCorespunzatoareIntrarilorL2Investigamsolutiileparticularealesistemuluidiferential x=Ax +Bu, (103)undeA Rnn, B Rnm,incazul incareuesteofunctieL2,m(, ): spatiul HilbertalfunctiilordepatratintegrabilinsensLebesguepe(, ),luandvaloriin Rm.Dacau L2,mdenimnormaL2aluiu:juj2:=(_ju(t)j2dt)12< .Fiedeasemenea L2,m+: subspatiileinchisealuiL2,mdefunctiicusuport[0, ) L2,m: subspatiileinchisealuiL2,malfunctiilorcusuport(, 0]Nota:L2,m=L2,m+L2,m.CAPITOLUL11: NOTIUNIDEBAZA 211 EvolutiiinSpatiulStarilorCorespunzatoareIntrarilorL2Solutii L2alelui x = Ax +BuCautamsolutiiL2incazurileurmatoare:1. Subconditiiinitiale2. Peintreagaaxadetimp: Astabila Aantistabila Adihotomica AarbitraraCAPITOLUL11: NOTIUNIDEBAZA 212 EvolutiiinSpatiulStarilorCorespunzatoareIntrarilorL21. SolutiisubconditiiintitialeFie Rnarbitrar,siu L2,m+. Fiex,usolutiacaresatisfacex(0)=datadeformuladevariatieaconstantelorx,u(t)=eAt +_t0eA(t)Bu()d, t 0 (104)sauinformaoperatorialax,u= +1u (105)cu: RnL2,n+, ()(t):=eAt, t 0, (106)si1:L2,m+L2,n+, (1u)(t):=_t0eA(t)Bu()d, t 0. (107)NOTA: Acestidoioperatorinusuntcunecesitatemarginiti DacaAestestabila,atuncix,uL2,n+siambiioperatorisi 1suntmarginiti.Ne intereseaza si alte solutii ale x=Ax+Bu (pe intreaga axa de timp). In orice caz, proprietatilelor depindputernicdespectrul lui Asi trebuiedeci considerateseparat cazurileincareAestestabila,antistabila,dihotomica,siarbitrara.CAPITOLUL11: NOTIUNIDEBAZA 213 EvolutiiinSpatiulStarilorCorespunzatoareIntrarilorL22. SolutiipeintreagaaxaTeorema114. FieAstabila. Atunci pentruecareu L2,m, ecuatia x=Ax + Buareosolutieunicaxue(absolutcontinua)inL2,n,datadexue(t)=_teA(t)Bu()d, t R. (108)Putemdenioperatorulmarginit 1e:L2,mL2,nprin(1eu)(t):=_teA(t)Bu()d, t R (109)siobtinemformaoperatorialaasolutieixue= 1eu. (110)Maimult,avemurmatoareleconexiuniintreceidoioperatori 1introdusipanaacum1=Pn+1ePm+= 1ePm+ , (111)undePrsuntproiectiileortogonalealeluiL2,rpeL2,r.CAPITOLUL11: NOTIUNIDEBAZA 214 EvolutiiinSpatiulStarilorCorespunzatoareIntrarilorL2Teorema115. FieAantistabila. Atuncipentruoricareu L2,m,ecuatia x=Ax +BuareosolutieunicaxueinL2,n(absolutcontinua)datadexue(t)= _teA(t)Bu()d, t R. (112)Analog,putemdeniinacestcazoperatorulliniarmarginit 1e:L2,mL2,ndatde(1eu)(t):= _teA(t)Bu()d, t R, (113)a.i. xue= 1eucontinuasaevalida.Teorema116. FieAdihotomica. Atunci,oricareuinL2,m,ecuatia x=Ax +BuareounicasolutieinL2,ndatadexue(t)=_teA(t)Bu()d _teA(t)+Bu()d, t R (114)undeand+suntproiectiilelui RnpesubspatiilestabilesiantistabilealeluiA.Similar, denimoperatorul liniarmarginit 1e:L2,mL2,n, xue:= 1eusi 1:L2,m+L2,n+,1:=Pn+1ePm+ , xu:= 1u.CAPITOLUL11: NOTIUNIDEBAZA 215 EvolutiiinSpatiulStarilorCorespunzatoareIntrarilorL2Cazul general: AarbitrarAsacumamvazut,inacestcazdenimsolutiile(cuconditiiinitiale)x,uprinx,u(t)=eAt +_t0eA(t)Bu()d, t 0. (115)Ingeneral, x,unueste inL2,n+. Este interesant saconsiderammultimeaacelor functii deintrareucarefacx,uintegrabila(inpatratul normei). Acesteintrari potvazutecastabilizandsistemulinbucladeschisa. Introducem/:= u:u L2,m+a.i.x,uL2,n+]. (116)DacaAestestabilaatunci /=L2,m+. Ingeneral,avem:Lema117. Presupunem(A, B)stabilizabilasi e Foreactiestabilizatoare. Fie Rnsiu L2,m+. Atunci u /dacasi numai dacau=Fx,vF+ v,incarevestearbitrarainL2,m+six,vFesteunicasolutieinL2,n+alui xF=(A +BF)xF+Bv, xF(0)=.CAPITOLUL11: NOTIUNIDEBAZA 216 EvolutiiinSpatiulStarilorCorespunzatoareIntrarilorL2Operatorul L2IntrareIesireConsideramunsistemliniarcuAdihotomicasiunu L2,marbitrar. Atunci x(t) = Ax(t) +Bu(t),y(t) = Cx(t) +Du(t)(117)sepoaterescriecax = xue= 1euy = (C1e +D)u (L2,p).Sistemul(117)denesteastfelunoperatorliniarmarginitdinL2,minL2,p:(u)(t)=_tCeA(t)Bu()d _tCeA(t)+Bu()d +Du(t). (118)Printr-otransformareTcaredescompunesistemulinpartilesalestabilesiantistabileobtinem(u)(t)=_tCeA(t)Bu()d _tC+eA+(t)B+u()d +Du(t). (119)CAPITOLUL11: NOTIUNIDEBAZA 217 OperatorulL2IntrareIesireDeoareceAestedihotomica,G(s)=C(sI A)1B +D RLpm.Dacay L2,p, u L2,msunta.i.y= u,atuncitransformateleFourier y, u L2(C0), y(j)= G(j) u(j), a.p.t.Teorema118. Dacasistemul estedihotomic, atunci normaoperatorului intrareiesireesteegalacunormaL(C0)matriciisaledetransfer,i.e.,jj= jGj. (120)Avemurmatorulrezultatincazulunuisisteminversabil(avandDinversabila).Propozitia119. FieDinversabilasi A BD1Cestedihotomica. Atunci operatorul intrareiesire esteinversabilsiinversasaesteoperatorulintrareiesirealsistemului x(t) = (A BD1C)x(t) + BD1y(t),u(t) = D1Cx(t) + D1y(t).(121)CAPITOLUL11: NOTIUNIDEBAZA 218 OperatorulL2IntrareIesireCapitolul12: OPTIMIZAREPATRATICA&TRIPLETEPOPOVDenitiisiEchivalentaTransformarisubEchivalentaIndiciPatraticiSistemulRiccatiEcuatiaMatricialaAlgebricaRiccatiSistemulKalmanYakubovichPopovSistemulHamiltonianFunctiaPopovOperatorulI/OalSistemuluiHamiltonianCAPITOLUL12: OPTIMIZAREPATRATICA&TRIPLETEPOPOV 219 DenitiisiEchivalentaDenitii si EchivalentaDenitia120.[TripletPopov] Untripletdematrici:=(A, B; P), P:=

Q LLTR

=PT,unde ARnn, BRnm, Q=QTRnn, LRnm, R=RTRmm, siP R(n+m)(n+m),senumestetripletPopov. Semnicatie: Reprezentarepescurtauneiperechiconstanddin: Unsistemdinamiccontrolat x=Ax +Bu (122) UnindicepatraticdeperformantaJ=_t1t0wT(t)Pw(t)dt, w(t):=

x(t)u(t)

, (123)undex(t)siu(t)satisfac(122). ReprezentarealternativaexplicitaaunuitripletPopovca=(A, B; Q, L, R)CAPITOLUL12: OPTIMIZAREPATRATICA&TRIPLETEPOPOV 220 DenitiisiEchivalentaDenitia121.[Echivalentasi tripletePopov] DouatripletePopov = (A, B; Q, L, R), = (A, B; Q,L, R),senumesc(X, F)echivalentedacaexistaF RmnsiX=XT Rnna.i.A = A +BF,B = B,Q = Q+LF+FTLT+FTRF+ ATX+XA,L = L +FTR +XB,R = R.(124) EchivalentFeedback(sauFechivalent): X=0 EchivalentRedusF=0siXa.i. Q=0(ecuatieLyapunov: Q+ATX+XA=0) Relatia de mai sus este intr-adevar o relatie de echivalenta ce satisface axiomele corespunzatoare.CAPITOLUL12: OPTIMIZAREPATRATICA&TRIPLETEPOPOV 221 DenitiisiEchivalentaTransformari subEchivalentaVedem in continuare cum se transforma diversele obiecte asociate cu un indice patratic + sistemdinamiccontrolat(saucuuntripletPopov)subrelatiadeechivalenta: Indicepatratic SistemulalgebricRiccati(ARS) EcuatiaalgebricaRiccati(ARE) SistemulKalman-Popov-Yakubovich(KPYS) SistemulHamiltonian Fascicolul(matricial)Hamiltonianextins(EHP) FunctiaPopov OperatorulI/OalsistemuluiHamiltonianCAPITOLUL12: OPTIMIZAREPATRATICA&TRIPLETEPOPOV 222 TransformarisubEchivalentaIndicePatraticJ(, u):=_0

xu

T

Q LLTR

xu

dt=

x,uu

,

Q LLTR

x,uu

L2,n+L2,m+,(125)undex,u(t)=eAt +_t0eA(t)Bu()d, t 0 (126)estesolutia x=Ax +Bu, x(0)= (127)u /:= u:u L2,m+a.i.x,uL2,n+] (128) Reamintire: Multimea /contineaceleintrari carefacsolutiax,udepatratintegrabil. Acesteintraristabilizeazasistemulinbucladeschisa!!! DacaAestestabila,J(, u)estedenitapentrutoti Rnsiu L2,m+i.e. /=L2,m+.Propozitia122. Fie=(A, B; P)sie =(A, B; P)un(X, F)echivalent. Atunci:J(, u)=J(, u) +TX, (u /) unde u= Fx,u+u.CAPITOLUL12: OPTIMIZAREPATRATICA&TRIPLETEPOPOV 223 TransformarisubEchivalentaSistemul AlgebricRiccatiSistemuldeecuatiiinnecunoscuteleF Rmn, X=XT Rnn,

ATX+X.A +Q L +XBBTX+LTR

.MatriceadeDisipativitate

IF.

=0 (129)senumestesistemulalgebricRiccati(ARS)asociatcu: ARS().Denitia123. O pereche (X, F) satisfacand (129), cu X=XTsi A+BFstabila, se numestesolutiestabilizantaaARS().Propozitia124. Fie(X, F),(X, F)solutiistabilizantealeARS(). AtunciX=X..Observatie: FesteingeneralneunicadacaRnuesteinversabila!!!Propozitia125. Fie=(A, B; P)si =(A, B; P)un(X, F)equivalent.(Xs, Fs)esteosolutie(stabilizanta)aARS() (XsX, FsF)esteosolutie(stabilizanta)aARS().CAPITOLUL12: OPTIMIZAREPATRATICA&TRIPLETEPOPOV 224 TransformarisubEchivalentaEcuatiaAlgebricaRiccati (ARE)Ecuatia algebrica Riccati este un caz particular al sistemului Riccati atunci cand Restenensingulara. Intr-adevar,avempentruX=XT,F= R1(BTX+LT),ATX+XA (XB +L)R1(BTX+LT) +Q=0(130)careesteecuatiaalgebricaRiccatiasociatacu.Denitia126. OsolutiesimetricaXsenumestestabilizantadacaA + BFestestabila. Fsenumestereactiestabilizanta.Corolarul 127. DacaARE()areosolutiestabilizantaatunciaceastaesteunica.Corolarul 128. Fie =(A, B; P) si =(A, B; P) doua triplete Popov (X, F) echivalente.XsestesolutiastabilizantaaARE()XsXestesolutiastabilizantaaARE(). Maimult,FRicc=FRiccF. (131)CAPITOLUL12: OPTIMIZAREPATRATICA&TRIPLETEPOPOV 225 TransformarisubEchivalentaSistemul KalmanYakubovichPopovOinlocuirecomodaaecuatieiRiccatifolositapentruacompletaformapatrata.Fie=(A, B; Q, L, R),Rinversabila,Jommmatricedesemn. SistemulneliniarR = VTJV ,L +XB = WTJV ,Q+ATX+XA = WTJW,(132)senumestesistemulKalmanPopovYakubovich(KPYS)informaJ: KPYS(, J).NOTA:Rinversabila JinversabilaJ=

Im1Im2

, sgn (R)=J. (133)Denitia129. Untriplet dematrici (X=XT, V, W)cesatisface(132)a.i. A + BFestestabila,pentruF:= V1W, (134)senumestesolutiestabilizantaasistemuluiKPYS(, J)siFsenumestereactiastabilizanta.CAPITOLUL12: OPTIMIZAREPATRATICA&TRIPLETEPOPOV 226 TransformarisubEchivalentaNOTA: Daca (X=XT, V, W) este o solutie a KPYS(, J) Xeste o solutie simetrica a ARE(). DacaXeste osolutie simetricaaARE(), atunci putemalege V a.i. R=VTJV (cuconditiasgn (R)=J). Atunci luamW:=(L + XB)V1J1caresatisfacedeasemeneaultimaecuatie. Prinurmare(X, V, W)esteosolutieaKPYS(, J). ReactiaRiccaticoincidecureactiasistemuluiKPYSF:= V1W.CONCLUZII: Sistemul KPYS(, J) are o solutie (stabilizanta) (X=XT, V, W) daca si numai dacaARE()areosolutie(stabilizanta)Xsisgn (R)=J. Daca(X, V, W),(X,V ,W)suntsolutiistabilizantealeKPYS(, J),atunciX= X. DacaJ=ImsauJ= Im,atunciKPYSdevineKPYSinformadepozitivitateR = VTV,L +XB = WTV,Q+ATX+XA = WTW,(135)CAPITOLUL12: OPTIMIZAREPATRATICA&TRIPLETEPOPOV 227 TransformarisubEchivalentasauinformadenegativitateR = VTV,L +XB = WTV,Q+ATX+XA = WTW.(136)Propozitia130. FieuntripletPopovsi (X, V, W)osolutieaKPYS(, J). Pentruoricareu /avemJ(, u)=_V u +Wx,u, J(V u +Wx,u)_L2,m++TX. (137)Propozitia131. Fie = (A, B; P) si = (A, B; P) doua triplete Popov (X, F)echivalente.(Xs, Vs, Ws)esteosolutie(stabilizanta)pentruKPYS(, J)(XsX, Vs, Ws +VsF)esteosolutie(stabilizanta)pentruKPYS(, J).CAPITOLUL12: OPTIMIZAREPATRATICA&TRIPLETEPOPOV 228 TransformarisubEchivalentaSistemul HamiltonianFie=(A, B; Q, L, R). Sistemuldiferentialliniar x = Ax +Bu, = Qx AT Lu,v = LTx +BT +Ru,(138)senumestesistemulHamiltoniancutimpcontinuu: HS().Ne intereseaza acele functii (u, x, ) care fac v=0 pentru sistemul Hamiltonian (determinaminacestfelpunctelecritice).Propozitia132. Fie=(A, B; P)si =(A, B; P)(X, F)echivalente.(u, x, ) v=0pentruHS()(pentruunanumitintervaldetimp)(u Fx, x, Xx) v=0pentruHS()(peacelasiintervaldetimp).CAPITOLUL12: OPTIMIZAREPATRATICA&TRIPLETEPOPOV 229 TransformarisubEchivalentaFascicolul (matricial)Hamiltonianextins(EHP)Fie=(A, B; Q, L, R). FascicolulmatricialsMN,cuM:=__I O OO I OO O O__, N:=__A O BQ ATLLTBTR__, (139)senumestefascicolulHamiltonianextins: EHP().Observatii: Matricile Msi Nsunt patrate (2n+m) (2n+m),dar sMNnu este o problemadevaloripropriistandardintrucatMestesingular!!! Cutoateacestea,dacaResteinversabil,avemQ(MN)Z=

I2nOO O

HOO Im

, (140)Q=__InO BR1O InLR1O O Im__, Z=__InO OO InOR1LTR1BTR1__,CAPITOLUL12: OPTIMIZAREPATRATICA&TRIPLETEPOPOV 230 TransformarisubEchivalentaH:=

A BR1LTBR1BTQ+LR1LTAT+LR1BT

. (141)DeciavemoproblemadevaloripropriiclasicasI2nHpentrumatriceaHamiltonianaH. EHP()esteexactfascicoluldetransmisie(sistem)alHS(). Cumsunteminteresatiinsolutiiceanuleazaiesireasistemului HSestenatural cafascicolul sistemsajoaceunrol central incaracterizareaacestora. Dacaluamv=0inHS()obtinemunsistemdescriptordiferentialz(t):=__x(t)(t)u(t)__M z=Nz.Propozitia133. Fie =(A, B; Q, L, R),=(A, B; Q,L, R) doua triplete Popov (X, F)echivalente. AtunciEHP()siEHP()suntlegateprinsMN=U(sMN)V, (142)undeU:=__I O OX I FTO O I__, V:=__I O OX I OF O I__. (143)CAPITOLUL12: OPTIMIZAREPATRATICA&TRIPLETEPOPOV 231 TransformarisubEchivalentaFunctiaPopov(intimpcontinuu)Fie=(A, B; Q, L, R). Pentrus C \ (A) (AT)]denimfunctiamatricialarationala(s):=[BT(sI AT)1I]

Q LLTR

(sI A)1BI

, (144)cesenumestefunctialuiPopov.Nota:=____A O BQ ATLLTBTR____, i.e., este exact matricea de transfer de la u la v a HS(). EHP()esteexactfascicoluldetransmisieasociatcuaceastarealizareaafunctieiPopov. esteautoadjuncta,i.e.,areurmatoareasimetrie: (s)=T(s) (=:(s)). se numeste si densitate spectrala introdusa de Popov in celebra monograe:HiperstabilitateaSistemelor Automate(1960); joacaunrol major inidenticari, prelucrareasemnalelor,sistemeautomate,teoriacircuitelor,etc.CAPITOLUL12: OPTIMIZAREPATRATICA&TRIPLETEPOPOV 232 TransformarisubEchivalentaFactorizareSpectralaPropozitia134. Fie=(A, B; P), =(A, B; P)douatriplete(X, F)echivalente.1. Pentrus C \ (A) (AT) (A) (AT)](s)= SF(s)(s)SF(s), (145)undeSF:=

A BF I

. (146)2. Maimult,daca(Xs=XTs , Fs)esteosolutieaARS()(sauARE),atunci(s)= SFs(s)RSFs(s) (147)unde SFseste(146)scrisapentruF=Fs. (Identitateadefactorizarespectrala)CAPITOLUL12: OPTIMIZAREPATRATICA&TRIPLETEPOPOV 233 TransformarisubEchivalentaCapitolul13: TEORIERICCATI:ABORDAREDINAMICASIFRECVENTIALAOperatorulI/OalSistemuluiHamiltonianPrincipalulRezultatinDomeniulTimpCazulClasicdePozitiviate: LQPRidicareaIpotezeideStabilitateConditiadeSignaturaOptimizareMaxmin/JocuriDinamiceConditiiFrecventialeConditiadeSignaturaFrecventialaInegalitatimatricialeRiccatiCapitolul13: TEORIERICCATI:ABORDAREDINAMICASIFRECVENTIALA 234 OperatorulI/OalSistemuluiHamiltonianOperatorul I/Oal Sistemului HamiltonianFixamun triplet Popov =(A, B; Q, L, R), ARnn, BRnm, si investigamexpresiile indicilor patratici pentru diverse solutii ale ecuatiilor diferentiale. Fie Adihotomica.InvestigamintaicriteriulpatraticextinsJe,(u):=_

xu

T

Q LLTR

xu

dtundeu L2,msi xestesolutiapeintreagaaxaaecuatiei diferentialeliniare x=Ax + Bu.SubstituindsolutiaL2,ndatadexue= 1eu,obtinemJe,(u) =

xueu

,

Q LLTR

xueu

=

u, 1eI

Q LLTR

1eI

u

= u, 7e,u) , (148)unde 7e,esteunoperatorliniarmarginitdinL2,minL2,mdatde7e,:=R +LT1e +1eL +1eQ1e= 7e,. (149)Capitolul13: TEORIERICCATI:ABORDAREDINAMICASIFRECVENTIALA 235 OperatorulI/OalSistemuluiHamiltonianTeorema135. Fie=(A, B; Q, L, R)untriplet Popov. DacaAestedihotomica, atuncioperatorul 7e,esteoperatorulL2intrareiesirealsistemuluiHamiltonian.FieAstabila. Pentruecareu L2,m+indicelepatraticJ(, u)estebinedenit. Inlocuimsolutiax,u= +1u,pentrux(0)=:J(, u) =

x,uu

,

Q LLTR

x,uu

=

1O I

u

,

Q LLTR

1O I

u

=

u

,

O1I

Q LLTR

1O I

u

=

u

,

1o,117

u

, (150)incaretotioperatoriiceintervinsuntliniarmarginiti:1o,: Rn Rn, 1o,:=Q, (151)1:L2,m+ Rn, 1:=(Q1 +L), (152)7:L2,m+L2,m+, 7:=R +LT1 +1L +1Q1= 7. (153)Capitolul13: TEORIERICCATI:ABORDAREDINAMICASIFRECVENTIALA 236 OperatorulI/OalSistemuluiHamiltonianNOTA: DacaAestestabilaatunci 7esteoperatorul Toeplitzavanddrept simbol functiaPopov. Intradevar, functiaPopovestematriceadetransferasistemului Hamiltoniansi 7esteoperatorulToeplitzasociatcuoperatorulintrareiesirealsistemuluiHamiltonian 7e,.Denitia136. Fie unoperatorliniarmarginitdinL2,minL2,p. Denim1. OperatorulcauzalHankelasociatcu : H:=Pp+]L2,m2. OperatorulHankelanticauzalasociatcu : H:=Pp]L2,m+.3. OperatorulToeplitzcauzalasociatcu , T:=Pp+]L2,m+.4. OperatorulToeplitzanticauzalasociatcu : T:=Pp]L2,mundePrsuntproiectiileortogonaleuzualealeluiL2,rpeL2,r.Capitolul13: TEORIERICCATI:ABORDAREDINAMICASIFRECVENTIALA 237 OperatorulI/OalSistemuluiHamiltonianRezultatul CentralDat =(A, B; Q, L, R) cu ARnn, BRnm, scopul principal este obtinereaconditiilornecesaresisucientedeexistentaasolutieistabilizatoareaARE()ATX+XA (XB +L)R1(BTX+LT) +Q=0, (154)intermeniioperatoruluiToeplitz 7introdusmaisus.7:L2,m+L2,m+, 7:=R +LT1 +1L +1Q1= 7. (155)Teorema137. Fie=(A, B; Q, L, R)untripletPopovcuAstabila. Urmatoarelearmatiisuntechivalente:1. RestenesingularasiARE()areo(unica)solutiestabilizantaX:= 1o,171 12. OperatorulToeplitz 7(avanddreptsimbolfunctiaPopov)areoinversamarginitaCapitolul13: TEORIERICCATI:ABORDAREDINAMICASIFRECVENTIALA 238 RezultatulCentralCorolarul 138. Fie =(A, B; Q, L, R) un triplet Popov cu Astabila. Presupunemcaoperatorul Toeplitz 7are o inversa marginita si e Xsolutia stabilizanta a ARE(). Atunci avemJ(, u)=__x,uu_,

Q LLTR

_x,uu__L2,n+L2,m+=TX (156)pentruorice Rnsiu= 71 1.Nota: Nusefacenici opresupunereprivindpozitivitatealui R, Q, sauaaltor matrici. Putemdeciformulainacestcadrujocurinecooperative,teoriiledetipNash,punctesa,H,etc. In plus avem formule operatoriale pentru solutia stabilizanta a ecuatiei Riccati si pentru valoareacriteriuluipatraticinpunctulcritic.Capitolul13: TEORIERICCATI:ABORDAREDINAMICASIFRECVENTIALA 239 RezultatulCentralCazul ClasicdePozitivitate: LQPPresupunereade bazaaici este camatriceaReste pozitiv denita(coecientul termenuluipatratic).Corolarul 139. Fie=(A, B; Q, L, R)untripletPopovcuAstabila.1. R>0siARE()areosolutiestabilizantaX Operatorul 7e,estecoerciv2. Dacaoperatorul 7e,estecoercivatunciminimulindiceluipatraticesteminuL2,m+J(, u)=TX, Rn, (157)si minimul seatingepentruu=u= 71 1si satisfacedeasemeneau=Fx, undeF:= R1(BTX+LT)estereactiaRiccati.3. Dacainplus

Q LLTR

0, (158)sioperatorul 7e,estecoerciv,atunciX 0.Capitolul13: TEORIERICCATI:ABORDAREDINAMICASIFRECVENTIALA 240 CazulClasicdePozitivitate: LQPPutemrelaxaconditiadecoercivitateprecumurmeaza.Corolarul 140. Fie =(A, B; Q, L, R) un triplet Popov cu A stabila. Presupunem ca R>0sicaperechea(A, B)estecontrolabila. Daca7e, 0, (159)atunci existaosolutiesimetricaXaARE(), a.i. pentruF:= R1(BTX+ LT)saavem(A +BF) C C0. (NumimXosolutiesemistabilizanta aARE).Corolarul 141.[EcuatiaRiccati clasicadecontrol] Fie s= (A, B; CTC, 0, I) tripletulPopov standard de control si presupunemca (A, B) si (C, A) sunt stabilizabila si respectivdetectabila. AtunciARE(s)ATX+XA XBBTX+CTC=0 (160)areosolutiestabilizantapozitivsemidenita.Capitolul13: TEORIERICCATI:ABORDAREDINAMICASIFRECVENTIALA 241 CazulClasicdePozitivitate: LQPRidicareaIpotezei deStabilitateFolosindoreactieestetrivial sarelaxamipotezadestabilitateinceadestabilizabilitateasupraperechii(A, B).NOTA:DacaARE()areosolutiestabilizantaatunciautomatperechea(A, B)trebuiesaestabilizabila.Teorema142. Fie =(A, B; Q, L, R) un triplet Popov cu (A, B) stabilizabila. Atunciurmatoareledouaarmatiisuntechivalente.1. RestenensingularasiARE()areo(unica)solutiestabilizanta.2. ExistaF Rmna.i. A + BFestestabilasi Fechivalentul lui , =(A, B; Q,L, R),areunoperatorToeplitzasociat 7ceesteinversabil.NOTA: Daca punctul 2 al Teoremei este adevarat pentru un Fstabilizant, atunci are loc pentruoriceFstabilizant.Capitolul13: TEORIERICCATI:ABORDAREDINAMICASIFRECVENTIALA 242 RidicareaIpotezeideStabilitateConditiadeSignaturaAmvazut caexistentaunei solutii stabilizanteaecuatiei AREesteintimlegatadeexistentaunei inversemarginiteaoperatorului Toeplitz 7. Uncazsimpluincareinversabilitateaacestuioperatorestegarantataestecazuldepozitivitate.Incontinuareelaboramoconditiemai sosticatapentruinversabilitateaoperatorului Toeplitz7. Aceastaconditienumitaconditiadesignatura,esterelevantapentrujocuriledinamice(Nash)si vajucaunrol central inrezolvareacelormai importanteproblemedinteoriasistemeloroptimalesirobuste.Fie=(A, B; Q, L, R),cuA Rnnstabila,B Rnm. PartitionamB=[B1B2], Bi Rnmi, i=1, 2, m1 +m2=m, (161)simatricileLsiRlepartitionamcorespunzatorinacordcuB,i.e.,L=[L1L2], R=

R11R12RT12R22

. (162)Solutiaproblemeicuconditiiinitiale x=Ax +B1u1 +B2u2, x(0)=, (163)Capitolul13: TEORIERICCATI:ABORDAREDINAMICASIFRECVENTIALA 243 ConditiadeSignaturasescriecax,u1,u2= +11u1 +12u2.Avemdeasemenea7=

711712712722

. (164)NOTA: 722coincidecuoperatorulToeplitz 72asociatcutripletulPopov2=(A, B2; Q, L2, R22). (165)Teorema143. Fie=(A, B; Q, L, R)untripletPopovavandmatricilepartitonatecamaisussiAstabila. Daca 722>>0si711= 71171271227120(peaxaimaginara)2. Daca oricare armatie de la 1. este indeplinita, minimul indicelui patratic esteminuL2,m+J(, u) =TX Rnsi se atinge pentru u=Fx, unde F :=R1(BTX+LT)estereactiaRiccatistabilizanta.3. Daca

Q LLTR

0, (173)sioricarearmatie1. esteindeplinitaatunciX 0.Corolarul 148.[Relaxareaipotezei depozitivitate] Fie = (A, B; Q, L, R) un tripletPopov cu Astabila. PresupunemR>0 si (A, B) este controlabila. Daca 0,atunci existaosolutiesimetricaXaARE(), a.i. pentruF:= R1(BTX+ LT)saavem(A +BF) C C0. (NumimXosolutiesemistabilizanta aARE).Capitolul13: TEORIERICCATI:ABORDAREDINAMICASIFRECVENTIALA 249 ConditiiFrecventialeCazul dePozitivitate: AarbitraraCorolarul 149. Fie=(A, B; Q, L, R)untripletPopov. Presupunemca:a. Perechea(A, B)estestabilizabila.b. Realizarealui ,=____A O BQ ATLLTBTR____, (174)estecontrolabilasiobservabilapeaxaimaginara.c. (j)>0, R.AtunciARE()areosolutiestabilizanta Xsiminu/ J(, u)=TX.Daca

Q LLTR

0,atunciX 0.Capitolul13: TEORIERICCATI:ABORDAREDINAMICASIFRECVENTIALA 250 ConditiiFrecventialeConditiadeSignaturainDomeniul FrecventialPrezentamin continuare o versiune in domeniul frecvential a conditii de signatura pentruoperatori. DefaptvomdaunrezultatmaiputernicpentrusistemulKYPS().ConsideramdinnoutripletulPopov=(A, B; Q, L, R)cuB,LsiRpartitionatecaB= B1B2

, L= L1L2

, R=

R11R12RT12R22

, (175)(Bi Rnmi, i=1, 2, m=m1 + m2). FiefunctiaPopov partitionatainconcordantacuR,=

11121222

. (176)IntroducemdeasemeneamatriceadesemnJ:=

Im1Im2

. (177)NotamtripletulPopov2=(A, B2; Q, L2, R22). Esteusordevericatca 22= 2.Capitolul13: TEORIERICCATI:ABORDAREDINAMICASIFRECVENTIALA 251 ConditiadeSignaturainDomeniulFrecventialOconditiesucientaTeorema150. Fie=(A, B; Q, L, R)untripletPopovcuAstabilasi intrarilepartitionatecamaisus. Presupunem 22>0pe C0. Dacaexistaun S RH+,m2m1a.i. I S

IS

>0). Dinmomentcestimcaexistentaunei solutii stabilizanteesteechivalentacuinversabilitatealui 7, esteextremdeinteresant sagasimosituatieincareexistentasolutiei stabilizanteimplicaconditia(178). Acestaestescopulurmatorului rezultat care este piatra de temelie a solutiilor problemelor de control optimal si robust:problemaNehari,problemadecontrolHsirobusteteastabilizarii.Capitolul13: TEORIERICCATI:ABORDAREDINAMICASIFRECVENTIALA 252 ConditiadeSignaturainDomeniulFrecventialOConditieNecesarasi SucientaTeorema151. Fie=(A, B; Q, L, R)untripletPopovcuintrarilepartitionatecamai sus.Presupunemca:a. Aestestabila.b. 22>0pe C0.c.

Q L2LT2R22

0.I.Urmatoarelearmatiisuntechivalente:1. Exista S RH+,m2m1caresatisfaceinegalitateadesignatura. I S

IS