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.]

2 ]. (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).

3 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.

4 Includingsynthesisofmultipliersforanalys isoflinearsystemswithunknownparameters positiveorthantstabilityandstate-feedbac ksynthesis optimalsystemrealization interpolationproblems,includingscaling multicriterionLQG/LQR inverseproblemofoptimalcontrolInsomecase s,wearedescribingknown,publishedresults; inothers, ,however, ,thereaderwillseethatLya-punov , smethods,whicharetraditionally12 Chapter1 Introductionappliedtotheanalysisofsystem stability,canjustaswellbeusedtofindbound sonsystemperformance,providedwedonotinsi stonan analyticsolution.

5 , (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).

6 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 ).

7 ThisresultedinthecelebratedPopovcriterio n,circlecriterion,Tsypkincriterion, , (LMIsincontroltheory), s,especiallybyYakubovich[Yak62,Yak64,Yak 67].Thisisclearsimplyfromthetitlesofsome ofhispapersfrom1962 5, ,Thesolutionofcertainmatrixinequalitiesi nautomaticcontroltheory(1962),andThemeth odofmatrixinequalitiesinthestabilitytheo ryofnonlinearcontrolsystems(1965;English translation1967).ThePRlemmaandextensions wereintensivelystudiedinthelatterhalfoft he1960s,andwerefoundtoberelatedtotheidea sofpassivity,thesmall-gaincriteriaintrod ucedbyZamesandSandberg, ,itwasknownthattheLMIappearinginthePRlem macouldbesolvednotonlybygraphicalmeans,b utalsobysolvingacertainalgebraicRiccatie quation(ARE).

8 Ina1971paper[Wil71b]onquadraticoptimalco ntrol, [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.

9 (Mostcontrolresearchersandengineersconsi dertheRiccatiequationtohavean analytic solution,sincethestandardalgorithmsthats olveitareverypredictableintermsoftheeffo rtrequired, )InWillems 1971 , ( ), ,Willems suggestionthatLMIsmighthavesomeadvantage sincomputationalalgorithms(ascomparedtot hecorrespondingRiccatiequations) (inourview) ,ithassomeimportantconsequences,themosti mportantofwhichisthatwecanreliablysolvem anyLMIsforwhichno analyticsolution hasbeenfound(orislikelytobefound). [PS82]wereperhapsthefirstresearcherstoma kethispoint, e(extendedtothecaseofmul-tiplenonlineari ties)toaconvexoptimizationprobleminvolvi ngLMIs, (Thisproblemhadbeenstudiedbefore,butthe solutions involvedanarbitraryscalingmatrix.)

10 PyatnitskiiandSkorodinskiiwerethefirst,a sfarasweknow,toformulatethesearchforaLya punovfunctionasaconvexoptimizationproble m, ,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.