THESIS (OTHER THAN BRIEF EXCERPTS REQUIRING ONLY P

NUMERICALALGORITHMSFORINVERSEEIGENVALUEPROBLEMSARISINGINCONTROLANDNONNEGATIVEMATRICESByKaiyangYangSUBMITTEDINPARTIALFULFILLMENTOFTHEREQUIREMENTSFORTHEDEGREEOFDOCTOROFPHILOSOPHYATTHEAUSTRALIANNATIONALUNIVERSITYCANBERRA,AUSTRALIAOCTOBER2006c°CopyrightbyKaiyangYang,October2006THEAUSTRALIANNATIONALUNIVERSITYDEPARTMENTOFINFORMATIONENGINEERING,RSISETheundersignedherebycertifythattheyhavereadandrecommendtotheResearchSchoolofInformationSciencesandEngineeringforacceptanceathesisentitled“NumericalAlgorithmsforInverseEigenvalueProblemsArisinginControlandNonnegativeMatrices”byKaiyangYanginpartialfulfillmentoftherequirementsforthedegreeofDoctorofPhilosophy.Dated:October2006ResearchSupervisors:Prof.JohnB.MooreDr.RobertOrsiiiTHEAUSTRALIANNATIONALUNIVERSITYDate:October2006Author:KaiyangYangTitle:NumericalAlgorithmsforInverseEigenvalueProblemsArisinginControlandNonnegativeMatricesDepartment:InformationEngineering,RSISEDegree:Ph.D.PermissionisherewithgrantedtoTheAustralianNationalUniversitytocirculateandtohavecopiedfornon-commercialpurposes,atitsdiscretion,theabovetitleupontherequestofindividualsorinstitutions.SignatureofAuthorTHEAUTHORRESERVESOTHERPUBLICATIONRIGHTS,ANDNEITHERTHETHESISNOREXTENSIVEEXTRACTSFROMITMAYBEPRINTEDOROTHERWISEREPRODUCEDWITHOUTTHEAUTHOR’SWRITTENPERMISSION.THEAUTHORATTESTSTHATPERMISSIONHASBEENOBTAINEDFORTHEUSEOFANYCOPYRIGHTEDMATERIALAPPEARINGINTHISTHESIS(OTHERTHANBRIEFEXCERPTSREQUIRINGONLYPROPERACKNOWLEDGEMENTINSCHOLARLYWRITING)ANDTHATALLSUCHUSEISCLEARLYACKNOWLEDGED.iiiToBojiuYangandPingSun,MyParentsandHongsenZhang,MyHusband.ivTableofContentsTableofContentsvListofFiguresixListofSymbolsxStatementofOriginalityxiAcknowledgementsxiiiAbstractxvIIntroduction11Introduction21.1InverseEigenvalueProblems.......................21.2OutlineoftheThesis...........................3IIBackground82ComputationalComplexity102.1Introduction................................102.2WhatdoesitMeanforaProblemtobeNP-Hard?...........112.3ComputationalComplexityinControl.................122.4Summary.................................133Projections143.1Introduction................................14v3.2Projections................................143.3AlternatingProjections..........................163.4Summary.................................20IIIProjectiveMethodologies214AProjectiveMethodologyforSolvingInverseEigenvalueProblemsforNonnegativeMatrices234.1Introduction................................234.2TheSymmetricProblem.........................264.3TheGeneralProblem...........................294.4ComputationalResults..........................364.4.1SNIEP...............................374.4.2NIEP...............................404.5Summary.................................415GeneralizedPolePlacementviaStaticOutputFeedback:aMethodologyBasedonProjections425.1Introduction................................425.2Methodology...............................475.2.1TheSymmetricProblem.....................475.2.2TheGeneralNonsymmetricProblem..............515.3ComputationalResults..........................545.3.1ClassicalPolePlacement:RandomProblems..........555.3.2ClassicalPolePlacement:AParticularProblem........565.3.3ContinuousTimeStabilization:RandomProblems......575.3.4AHybridProblem........................595.4Summary.................................606Extensions:SimultaneousStabilizationandDecentralizedControl616.1Introduction................................616.2Methodology...............................646.2.1SimultaneousStabilization....................656.2.2DecentralizedControl.......................666.3ComputationalResults..........................676.3.1SimultaneousStabilization:RandomProblems.........67vi6.3.2SimultaneousStabilization:ParticularProblems........686.3.3DecentralizedControl:RandomProblems...........696.4Summary.................................70IVTrustRegionMethodsandaGauss-NewtonMethod717StaticOutputFeedbackPolePlacementviaaTrustRegionApproach737.1Introduction................................737.2TrustRegionMethods..........................757.2.1BasicMethodology........................767.2.2ConvergenceResults.......................797.3DerivativeCalculations..........................817.4AdditionalComments..........................827.5ComputationalResults..........................847.5.1RandomProblems........................847.5.2ParticularProblems.......................867.5.3RepeatedEigenvalues.......................877.6Summary.................................898AGauss-NewtonMethodforSolvingInverseEigenvalueProblemsforNonnegativeMatrices918.1Introduction................................918.2NewtonMethods.............................938.3DerivativeCalculations..........................948.4ComputationalResults..........................958.4.1SNIEP...............................958.4.2NIEP...............................978.5Summary.................................97VConclusionandFutureWork999ConclusionandFutureWork1009.1Conclusion.................................1009.2FutureWork................................101viiAResultsf