预览加载中，请您耐心等待几秒...

0-1多项式规划问题的SDP松弛方法(英文).docx

预览
1/2
2/2

在线预览结束，喜欢就下载吧，查找使用更方便

下载提示 文本预览

如果您无法下载资料，请参考说明：

1、部分资料下载需要金币，请确保您的账户上有足够的金币

2、已购买过的文档，再次下载不重复扣费

3、资料包下载后请先用软件解压，在使用对应软件打开

0-1多项式规划问题的SDP松弛方法(英文) 0-1PolynomialOptimizationProblemswithSDPRelaxationMethod 0-1polynomialoptimizationproblemsrefertoacertainclassofcombinatorialoptimizationproblems.Theobjectivefunctionisapolynomialoftheproblemvariables,wherethevariablescanonlytakebinaryvaluesof0or1.Thistypeofproblemisubiquitousinvariousapplicationfields,suchascomputerscience,engineering,economics,andmanagement.Examplesincludemax-cutproblem,quadraticunconstrainedbinaryoptimization(QUBO)problem,andvehicleroutingproblem.However,thisclassofproblemshasbeenprovedtobeNP-hard,whichimpliesitisveryhardtofindexactsolutioninapolynomialtime.Thus,researchersresorttoapproximationalgorithms,amongwhichSemidefiniteprogramming(SDP)relaxationmethodisawidelyappliedone. SDPrelaxationmethodisfoundedonSDPproblems.LetSdenotethesetofsymmetricn*nmatrices.AnSDPproblemcanbeformulatedasthefollowing: minimizetr(CX) subjecttotr(AiX)=bi,X>=0,i=1,2,...,m whereXisasymmetricn*npositivesemidefinitematrix,tr(•)denotestraceofamatrix,C,A1,A2,...,AmaresymmetricmatricesinS,andb1,b2,...,bmarescalars.ThefirstconstraintenforcesXtobepositivesemidefinitewhiletheotherconstraintsimposelinearconstraintsonX. TheSDPrelaxationofa0-1polynomialoptimizationproblemisobtainedbyrelaxingthebinaryconditionontheproblemvariables,andtransformingtheoptimizationproblemintoacontinuousoptimizationonafeasiblepolytope.ThekeyideaisthatabinarymatrixBcanbewrittenasBB^T,whereBisabinaryvector,andB^TdenotesthetransposeofB.Then,wereplaceeachbinaryvariablex_ibytheproductx_iy_i,wherey_iisanewvariablethatsatisfiesy_i^2=y_iandy_i>=0.Hence,theproductx_iy_icantakecontinuousvaluesbetween0and1.Moreover,theconstraintx_i^2=x_icanbetransformedtoy_i^2=y_i. LetPdenotethefeasiblepolytopedeterminedbythetransformedproblem.ThentheSDPrelaxationproblemcanbeformulatedas minimizeF(y) subjecttoy=BB^T whereF(y)isthepolynomialobjectivefunctionintermsofy,andBisabinarymatrix. TheadvantageoftheSDPrelaxationmethodliesinitsabilitytoprovideanupperboundontheoptimalvalueofthe0-1polynomialoptimizationp