Linear Matrix Inequalities in System and Control Theory

1 LinearMatrixInequalitiesinSystemandContr olTheorySIAMS tudiesinAppliedMathematicsThisseriesofmo nographsfocusesonmathematicsanditsapplic ationstoproblemsofcurrentconcerntoindust ry,government, ,numericalanalysts,statisticians,enginee rs, eva, , ,LaurentElGhaoui,EricFeron,andVenkataram ananBalakrishnanStephenBoyd,LaurentElGha oui,EricFeron,andVenkataramananBalakrish nanLinearMatrixInequalitiesinSystemandCo ntrolTheorySocietyforIndustrialandApplie dMathematics PhiladelphiaCopyrightc ,stored, ,writetotheSocietyforIndustrialandApplie dMathematics,3600 UniversityCityScienceCenter,Philadelphia , [etal.]. (SIAM studiesinappliedmathematics; ) , : . : analyticsolutions totheseproblems, (by, ,theellipsoidalgorithmofShor,Nemirovskii ,andYudin),andsoaretractable, , , , :Wepresentnospecificexamplesornu-merical results, ,wehopethatthisbookwilllaterbeconsidered asthefirstbookonthetopic, sbookMathematicalControlThe-ory[Son90] [Kai80]byKailath,NonlinearSystemsAnalysi s[Vid92]byVidyasagar,OptimalControl:Line arQuadraticMethods[AM90]byAndersonandMoo re,andConvexAnalysisandMinimizationAlgor ithmsI[HUL93]byHiriart UrrutyandLemar [NN94] , , ,realizationtheory,andstate-feedbacksynt hesismethods, , , , , , , , , , , , , , (underF49620-92-J-0013),NSF(underECS-922 2391),andARPA(underF49620-93-1-0085).

2 El egationG en eralepourl (underNSFDCDR-8803012).Thisbookwastypese tbytheauthorsusingLATEX, ,CaliforniaLaurentElGhaouiParis,FranceEr icFeronCambridge,MassachusettsVenkataram ananBalakrishnanCollegePark, (LMIs).Sincetheseresult-ingoptimizationp roblemscanbesolvednumericallyveryefficie ntlyusingrecentlydevelopedinterior-point methods,ourreductionconstitutesasolution totheoriginalproblem,certainlyinapractic alsense, , : matrixscalingproblems, ,minimizingconditionnumberbydiagonalscal ing constructionofquadraticLyapunovfunctions forstabilityandperformanceanal-ysisoflin eardifferentialinclusions jointsynthesisofstate-feedbackandquadrat icLyapunovfunctionsforlineardifferential inclusions synthesisofstate-feedbackandquadraticLya punovfunctionsforstochasticanddelaysyste ms synthesisofLur e-typeLyapunovfunctionsfornonlinearsyste ms optimizationoveranaffinefamilyoftransfer matrices,includingsynthesisofmultipliers foranalysisoflinearsystemswithunknownpar ameters positiveorthantstabilityandstate-feedbac ksynthesis optimalsystemrealization interpolationproblems,includingscaling multicriterionLQG/LQR inverseproblemofoptimalcontrolInsomecase s,wearedescribingknown,publishedresults.

3 Inothers, ,however, ,thereaderwillseethatLya-punov , smethods,whicharetraditionally12 Chapter1 Introductionappliedtotheanalysisofsystem stability,canjustaswellbeusedtofindbound sonsystemperformance,providedwedonotinsi stonan analyticsolution . , (t)=Ax(t)( )isstable( ,alltrajectoriesconvergetozero)ifandonly ifthereexistsapositive-definitematrixPsu chthatATP+PA<0.( )TherequirementP>0,ATP+PA<0iswhatwenowcallaLyapunovinequalityonP, ,wecanpickanyQ=QT>0andthensolvethelinearequationATP+PA= QforthematrixP,whichisguaranteedtobeposi tive-definiteifthesystem( ) ,thefirstLMIusedtoanalyzestabilityofadyn amicalsystemwastheLyapunovinequality( ),whichcanbesolvedanalytically(bysolving asetoflinearequations).Thenextmajormiles toneoccursinthe1940 e,Postnikov,andothersintheSovietUnionapp liedLyapunov smethodstosomespecificpracticalproblemsi ncontrolengineering,especially, , byhand (for,needlesstosay,smallsystems).

4 Neverthelesstheywerejustifiablyexcitedby theideathatLyapunov stheorycouldbeappliedtoimportant(anddiff icult) e s1951book[Lur57]wefind:Thisbookrepresent sthefirstattempttodemonstratethattheidea sex-pressed60yearsagobyLyapunov,whicheve ncomparativelyrecentlyap-pearedtoberemot efrompracticalapplication, ,Lur eandotherswerethefirsttoapplyLyapunov , (second,thirdorder) s,whenYakubovich,Popov,Kalman,andotherre searcherssucceededinreducingthesolutiono ftheLMIsthataroseintheproblemofLur etosimplegraphicalcriteria,usingwhatweno wcallthepositive-real(PR)lemma(see ).ThisresultedinthecelebratedPopovcriter ion,circlecriterion,Tsypkincriterion, , (LMIsincontroltheory), s,especiallybyYakubovich[Yak62,Yak64,Yak 67].Thisisclearsimplyfromthetitlesofsome ofhispapersfrom1962 5, ,Thesolutionofcertainmatrixinequalitiesi nautomaticcontroltheory(1962),andThemeth odofmatrixinequalitiesinthestabilitytheo ryofnonlinearcontrolsystems(1965;English translation1967).

5 ThePRlemmaandextensionswereintensivelyst udiedinthelatterhalfofthe1960s,andwerefo undtoberelatedtotheideasofpassivity,thes mall-gaincriteriaintroducedbyZamesandSan dberg, ,itwasknownthattheLMIappearinginthePRlem macouldbesolvednotonlybygraphicalmeans,b utalsobysolvingacertainalgebraicRiccatie quation(ARE).Ina1971paper[Wil71b]onquadr aticoptimalcontrol, [ATP+PA+QPB+CTBTP+CR] 0,( )andpointsoutthatitcanbesolvedbystudying thesymmetricsolutionsoftheAREATP+PA (PB+CT)R 1(BTP+C)+Q=0,whichinturncanbefoundbyanei gendecompositionofarelatedHamiltonianmat rix.(See )Thisconnectionhadbeenobservedearlierint heSovietUnion,wheretheAREwascalledtheLur eresolvingequation(see[Yak88]).Soby1971, researchersknewseveralmethodsforsolvings pecialtypesofLMIs:direct(forsmallsystems ),graphicalmethods, ,thesemethodsareall closed-form or analytic solutionsthatcanbeusedtosolvespecialform sofLMIs.(Mostcontrolresearchersandengine ersconsidertheRiccatiequationtohavean analytic solution,sincethestandardalgorithmsthats olveitareverypredictableintermsoftheeffo rtrequired, )InWillems 1971 , ( ), ,Willems suggestionthatLMIsmighthavesomeadvantage sincomputationalalgorithms(ascomparedtot hecorrespondingRiccatiequations) (inourview) ,ithassomeimportantconsequences,themosti mportantofwhichisthatwecanreliablysolvem anyLMIsforwhichno analyticsolution hasbeenfound(orislikelytobefound).

6 [PS82]wereperhapsthefirstresearcherstoma kethispoint, e(extendedtothecaseofmul-tiplenonlineari ties)toaconvexoptimizationprobleminvolvi ngLMIs, (Thisproblemhadbeenstudiedbefore,butthe solutions involvedanarbitraryscalingmatrix.)Pyatni tskiiandSkorodinskiiwerethefirst,asfaras weknow,toformulatethesearchforaLyapunovf unctionasaconvexoptimizationproblem, ,HorisbergerandBe-langer[HB76] ,theideaofhavingacomputersearchforaLya-p unovfunctionwasnotnew itappears,forexample,ina1965paperbySchul tzetal.[SSHJ65]. , ,liketheellip-soidmethod,butincontrastto theellipsoidmethod, sworkspurredanenormousamountofworkinthea reaofinterior-pointmethodsforlinearprogr amming(includingtherediscoveryofefficien tmethodsthatweredevelopedinthe1960sbutig nored).Essentiallyallofthisresearchactiv itycon-centratedonalgorithmsforlinearand (convex) ,NesterovandNemirovskiidevelopedinterior -pointmethodsthatapplydirectlytocon-vexp roblemsinvolvingLMIs,andinparticular, ,severalinterior-pointalgorithmsforLMIpr oblemshavebeenimplementedandtestedonspec ificfamiliesofLMIsthatariseincontroltheo ry, : 1890:FirstLMIappears;analyticsolutionoft heLyapunovLMIviaLyapunovequation.

7 1940 s:ApplicationofLyapunov byhand . Early1960 s:PRlemmagivesgraphicaltechniquesforsolv inganotherfamilyofLMIs. Late1960 s:ObservationthatthesamefamilyofLMIscanb esolvedbysolvinganARE. Early1980 s:RecognitionthatmanyLMIscanbesolvedbyco mputerviaconvexprogramming. Late1980 , (general) , , (thatinmostcasesaretrivialtofigureout).W eareveryinformal,perhapsevencavalier, details ,itmaybeCopyrightc , ,thereaderwhowishestoimplementanalgorith mthatsolvesaproblemconsideredinthisbooks houldbepreparedtomakeafewmodificationsor additionstoourdescriptionofthe solution .Inasimilarway, ,foreachreducedproblemwecouldstate,proba blysimplify, ,wecanconsidervariousdualoptimizationpro blems,lowerboundsfortheproblem, , (whichalmostalwaysariseinthisform)andals owhenweconsiderstochasticsystems(toavoid thetechnicaldetailsofstochasticdifferent ialequations).Thelistofproblemsthatwecon siderismeantonlytoberepresentative, , ,wedescribemanyvariationsonproblems( ,computingboundsonmarginsanddecayrates); inlaterchapters,wedescribefewerandfewerv ariations, ,inwhichwehideproofs,precisestatements,e laborations, ,despiteitssize(over500entries).

8 , , x=Axisourshortformfordx/dt=Ax(t).HereAis aconstantmatrix;whenweencountertime-vary ingcoefficients,wewillexplicitlyshowthet imedependence,asin x=A(t) ,wedropthedummyvariablefromdefiniteinteg rals,writingforexample, T0uTydtfor T0u(t)Ty(t) ,weadopttheconventionthattheoperatorsTr( traceofamatrix)andE(expectedvalue)havelo werprecedencethanmultiplication,transpos e, ,TrATBmeansTr(ATB). ,byBoydandElGhaoui[BE93], (thatpresumablywouldhavebeensubmittedfor publicationasapaper) ,andlaterBalakrishnan,startedaddingmater ial,andsoonitwasclearthatwewerewritingab ook, (LMI)hastheformF(x) =F0+m i=1xiFi>0,( )wherex RmisthevariableandthesymmetricmatricesFi =FTi Rn n,i=0,..,m, ( )meansthatF(x)ispositive-definite, ,uTF(x)u>0forallnonzerou ,theLMI( )isequivalenttoasetofnpolynomialinequali tiesinx, ,theleadingprincipalminorsofF(x) ,whichhavetheformF(x) 0.( )ThestrictLMI( )andthenonstrictLMI( )arecloselyrelated,butaprecisestatemento ftherelationisabitinvolved,sowedeferitto ( )isaconvexconstraintonx, ,theset{x|F(x)>0} ( )mayseemtohaveaspecializedform, ,linearinequalities,(convex)quadraticine qualities,matrixnorminequalities,andcons traintsthatariseincontroltheory,suchasLy apunovandconvexquadraticmatrixinequaliti es, (1)(x)>0.

9 ,F(p)(x)>0canbeexpressedasthesingleLMIdi ag(F(1)(x),..,F(p)(x))> , , theLMIF(1)(x)>0,..,F(p)(x)>0 willmean theLMIdiag(F(1)(x),..,F(p)(x))>0 .WhenthematricesFiarediagonal,theLMIF(x) > (convex) :theLMI[Q(x)S(x)S(x)TR(x)]>0,( )78 Chapter2 SomeStandardProblemsInvolvingLMIswhereQ( x)=Q(x)T,R(x)=R(x)T,andS(x)dependaffinel yonx,isequivalenttoR(x)>0,Q(x) S(x)R(x) 1S(x)T>0.( )Inotherwords,thesetofnonlinearinequalit ies( )canberepresentedastheLMI( ).Asanexample,the(maximumsingularvalue)m atrixnormconstraint Z(x) <1,whereZ(x) Rp qanddependsaffinelyonx,isrepresentedastheLMI[IZ(x)Z(x)TI]>0(since Z <1isequivalenttoI ZZT>0).Notethatthecaseq= (x)TP(x) 1c(x)<1,P(x)>0,wherec(x) RnandP(x)=P(x)T Rn ndependaffinelyonx,isexpressedastheLMI[P (x)c(x)c(x)T1]> ,theconstraintTrS(x)TP(x) 1S(x)<1,P(x)>0,whereP(x)=P(x)T Rn nandS(x) Rn pdependaffinelyonx,ishandledbyintroducin ganew(slack)matrixvariableX=XT Rp p,andtheLMI(inxandX):TrX<1,[XS(x)TS(x)P(x)]> ; , ,theLya-punovinequalityATP+PA<0,( )whereA Rn nisgivenandP= (x)>0, theLMIATP+PA<0inP meansthatthematrixPisavariable.

10 (Ofcourse,theLyapunovinequality( )isreadilyputintheform( ), ,..,Pmbeabasisforsymmetricn nmatrices(m=n(n+1)/2).ThentakeF0=0andFi= ATPi PiA.)LeavingLMIsinacondensedformsuchas( ),inadditiontosavingnotation,mayleadtomo reefficientcomputation;see ,considerthequadraticmatrixinequalityATP +PA+PBR 1 BTP+Q<0,( )Copyrightc ,B,Q=QT,R=RT>0aregivenmatricesofappropriatesizes,andP = [ ATP PA QPBBTPR]> ( )isconvexinP, , >0,ATP+PA<0,TrP=1,( )whereP Rk ( )intheformF(x)> ,..,Pmbeabasisforsymmetrick kmatriceswithtracezero(m=(k(k+1)/2) 1)andletP0beasymmetrick kmatrixwithTrP0= (P0, ATP0 P0A)andFi=diag(Pi, ATPi PiA)fori=1,.., ( )asLMIs, (x)>0,thecorrespondingLMIP roblem(LMIP)istofindxfeassuchthatF(xfeas )>0ordeterminethattheLMIisinfeasible.(By duality,thismeans:FindanonzeroG 0suchthatTrGFi=0fori=1,..,mandTrGF0 0;seetheNotesandReferences.)Ofcourse, solvingtheLMIF(x)>0 ,considerthe simultaneousLyapunovstabilityprob-lem (whichwewillseein ):WearegivenAi Rn n,i=1.