Sums of squares relaxations of polynomial semidefi

ResearchReportsonMathematicalandComputingSciencesSeriesB:OperationsResearchDepartmentofMathematicalandComputingSciencesTokyoInstituteofTechnology2-12-1Oh-Okayama,Meguro-ku,Tokyo152-8552JapanSumsofSquaresRelaxationsofPolynomialSemidefiniteProgramsMasakazuKojima†ResearchReportB-397,November2003Abstract.ApolynomialSDP(semidefiniteprograms)minimizesapolynomialobjectivefunctionoverafeasibleregiondescribedbyapositivesemidefiniteconstraintofasymmet-ricmatrixwhosecomponentsaremultivariatepolynomials.SumsofsquaresrelaxationsdevelopedforpolynomialoptimizationproblemsareextendedtoproposesumsofsquaresrelaxationsforpolynomialSDPswithanadditionalconstraintforthevariablestobeintheunitball.ItisprovedthatoptimalvaluesofasequenceofsumsofsquaresrelaxationsofthepolynomialSDP,whichcorrespondtodualsofLasserre’sSDPrelaxationsappliedtothepolynomialSDP,convergetotheoptimalvalueofthepolynomialSDP.TheproofoftheconvergenceisobtainedbyfullyutilizingapenaltyfunctionandageneralizedLagrangiandualsthatwererecentlyproposedbyKimetalforsparsepolynomialoptimizationproblems.Keywords.PolynomialOptimizationProblem,SumsofSquaresOptimization,SemidefiniteProgramRelaxation,LagrangianRelaxation,LagrangianDual,PenaltyFunction,BilinearMatrixInequality,GlobalOptimization.†DepartmentofMathematicalandComputingSciences,TokyoInstituteofTechnol-ogy,2-12-1Oh-Okayama,Meguro-ku,[e-mail]1IntroductionApolynomialSDP(semidefiniteprogram)isanonlinearandnonconvexoptimizationprob-lemofminimizingarealvaluedpolynomialobjectivefunctiona(x)subjecttoamatrixinequalityA(x)Oi.e.,aconstraintforA(x)tobepositivesemidefinite.Herexdenotesavectorvariableinthen-dimensionalEuclideanspaceandA(x)anm×msymmetricmatrixwhose(i,j)thcomponentAij(x)isarealvaluedpolynomialinx.ThepolynomialSDPisageneralizationofthestandardSDP(see,forexample,[5,9])withalinearobjec-tivefunctionandanLMI(linearmatrixinequality)constrainttoapolynomialobjectivefunctionandaPMI(polynomialmatrixinequality)constraint.Itincludesawideclassofproblems,e.g.,POPs(polynomialoptimizationproblems)whereA(x)isadiagonalmatrixandaBMI(bilinearmatrixinequality)whereAij(x)isaquadraticfunction.ThepurposeofthispaperistoproposeSOS(sumofsquares)relaxationmethodsforapolynomialSDPwithanadditionalballconstraintx∈B(theunitballinthen-dimensionalEuclideanspace)byextendingSOSrelaxationsintroducedforPOPs[6,7].WepresentamethodofgeneratingasequenceofSOSrelaxationproblemswhoseoptimalvaluesconvergetotheoptimalvalueofthepolynomialSDP.ByapplyingatechniqueestablishedinSOSrelaxationmethods,wecanconvertitintoasequenceofstandardSDPs.TworelatedapproachesprovideasequenceofSDPrelaxationswhoseoptimalvaluesconvergetotheoptimalvalueofagivenPOP.Theoneisadualapproachandtheotherisaprimalapproach.ThedualapproachisbasedonSOSrelaxations[6,7].Intherecentpaper[2],KimetalpresentedamethodtoobtainasequenceofSDPrelaxationsbythedualapproach.TheyalsoshowedthatthequalityofthesequenceofSDPrelaxationswasstrengthenedbyapplyingapenaltyfunctiontechniqueandageneralizedLagrangiandual.TheuseofthepenaltyfunctiontechniqueandthegeneralizedLagrangiandualprovidedaconvenientwaytoexploitsparsityofpolynomialsinthePOPandthusitwaspossibletointroduceSOSrelaxationsforasparsePOP.ThemethodproposedinthispaperforthepolynomialSDPisstemmedfromthoseresultsin[2].Inparticular,weintroduceapenaltyfunctionandageneralizedLagrangianfunctionforthepolynomialSDPwiththeconstraintx∈B.Themainemphasisisplaced,however,onconvergenceanalysisofthemethodbutnotonexploitingsparsityofthepolynomialSDP.AprimalapproachalsoproducesasequenceofSDPrelaxationsforthepolynomialSDPbyextendingLasserre’sSDPrelaxationmethod[1,4]forPOPstothepolynomialSDP.TheseSDPsaredualsoftheonesderivedinthedualapproachmentionedabove.AkeyideabehindtheextensionofLasserre’sSDPrelaxationliesinthefollowingfact.Leth(x)bea(1+ℓ)-dimensionalcolumnvectorofascalarconstant1andrealvaluedpolynomialsh1(x),h2(x),...,hℓ(x)inx.ThenaPMIA(x)OisequivalenttoaPMItoh(x)h(x)T
⊗A(x)O,whereM⊗NdenotestheKroneckerproductoftwomatricesMandN.Thisideawaspresentedasatechniquetoderiveavalidconstraintinthepaper[3],butpolynomialSDPswerenotinvestigated.TheextensionpresentedhereemployssometechniquesintheoriginalSDPrelaxationbyLasserreforaPOPsuchaslinearizingthepolynomialobjectivefunctionandtheresultingPMIconstrainttoastandardSDPwithanLMI.Wementionthattheprimalapproachismoredirectandeasiertounderstandthanthedualapproach.However,themethodinthispaperispresentedintermsofthedualapproachinsteadoftheprimalapproachbecauseourtheoreticalanalysisisbasedonthe1dualapproach.Theremainingofthepaperisorganizedasfollows:InSection2,wedescribethedefi-nitionsofsymmetricpolynomialmatricesandsumsoftheirsquaresafterintroducingsomenotationandsymbols,andthenshowacharacterizationofsumsofsquaresofpolynomialmatricesintermsofpositivesemidefinitematrices.InSection3,weconvertthepolyno-mialSDPwiththeadditionalunitballconstraintx∈BintoasequenceofPOPsoverthesingleconstraintx∈Bwhoseoptimalvaluesconvergetotheoptimalvalueoftheorigi-nalpolynomialSDPusingapenaltyfunctionapproach.Section4includestheextensio