双排落地式钢管脚手架专项施工方案

PRIMAL-DUALINTERIOR-POINTMETHODSFORSEMIDEFINITEPROGRAMMING:CONVERGENCERATES,STABILITYANDNUMERICALRESULTSFARIDALIZADEHy,JEAN-PIERREA.HAEBERLYz,ANDMICHAELL.OVERTONxSIAMJ.OPTIM.c°1998SocietyforIndustrialandAppliedMathematicsVol.8,No.3,pp.746{768,August1998007Abstract.Primal-dualinterior-pointpath-followingmethodsforsemideniteprogrammingareconsidered.Severalvariantsarediscussed,basedonNewton'smethodappliedtothreeequations:primalfeasibility,dualfeasibility,andsomeformofcenteringcondition.Thefocusisonthreesuchalgorithms,calledtheXZ,XZ+ZX,andQmethods.FortheXZ+ZXandQalgorithms,theNewtonsystemiswelldenedanditsJacobianisnonsingularatthesolution,undernondegeneracyassump-tions.TheassociatedSchurcomplementmatrixhasanunboundedconditionnumberonthecentralpathunderthenondegeneracyassumptionsandanadditionalrankassumption.Practicalaspectsarediscussed,includingMehrotrapredictor-correctorvariantsandissuesofnumericalstability.Com-paredtotheothermethodsconsidered,theXZ+ZXmethodismorerobustwithrespecttoitsabilitytostepclosetotheboundary,convergesmorerapidly,andachieveshigheraccuracy.Keywords.semideniteprogramming,eigenvalueoptimization,interior-pointmethod,convexprogrammingAMSsubjectclassications.65K10,90C25PII.S10526234963047001.Introduction.LetSndenotethevectorspaceofrealsymmetricnnma-trices.Denotethedimensionofthisspacebyn2=n(n+1)2:(1.1)ThestandardinnerproductonSnisAB=trAB=Xi;jAijBij:ByX0(X0),whereX2Sn,wemeanthatXispositivesemidenite(positivedenite).Considerthesemideniteprogram(SDP)minX2SnCXs:t:AkX=bk;k=1;:::;m;X0;(1.2)ReceivedbytheeditorsJune4,1996;acceptedforpublication(inrevisedform)May27,1997;publishedelectronicallyJuly20,1998.([e-mail]).TheresearchofthisauthorwassupportedinpartbyNationalScienceFoundationgrantCCR-9501941andOceofNavalResearchcontractN00014-96-1-0704.zMathematicsDepartment,FordhamUniversity,Bronx,NY10458([e-mail]).TheresearchofthisauthorwassupportedinpartbyNationalScienceFoundationgrantCCR-9401119.xComputerScienceDepartment,CourantInstituteofMathematicalSciences,NewYorkUniver-sity,NewYork,NY10012([e-mail]).TheresearchofthisauthorwassupportedinpartbyNationalScienceFoundationgrantCCR-9625955.746PRIMAL-DUALMETHODSFORSEMIDEFINITEPROGRAMMING747whereb2Rm,C2Sn,andAk2Sn,k=1;:::;m.ThedualSDPismaxy2Rm;Z2SnbTys:t:Pmk=1ykAk+Z=C;Z0:(1.3)Thefollowingassumptionsholdthroughoutthepaper.Assumption1.ThereexistsaprimalfeasiblepointX0,andadualfeasiblepoint(y;Z)withZ0.Assumption2.ThematricesAk;k=1;:::;m,arelinearlyindependent;i.e.,theyspananm-dimensionallinearspaceinSn.Thecentralpathconsistsofpoints(X;y;Z)2SnRmSnsatisfyingtheprimalanddualfeasibilityconstraintsaswellasthecenteringconditionXZ=I(1.4)forsome2R,0.Itiswellknown[11,7]thatunderAssumptions1and2(X;y;Z)existsandisuniqueforall0,andthat(X;y;Z)=lim!0(X;y;Z)(1.5)existsandsolvestheprimalanddualSDPs.Furthermore,becauseXandZcom-mute,thereexistsanorthogonalmatrixQsuchthatX=QDiag(1;:::;n)(Q)T;Z=QDiag(!1;:::;!n)(Q)T;(1.6)wheretheiand!i,respectivelytheeigenvaluesofXandZ,satisfyi!i=;i=1;:::;n:(1.7)Withoutlossofgenerality,assumethat1


nand!1


!n:(1.8)As!0,thecenteringcondition(1.4)reducestothecomplementarityconditionXZ=0,implyingthatX=QDiag(1;:::;n)QT;Z=QDiag(!1;:::;!n)QT(1.9)forsomeorthogonalmatrixQ,withtheeigenvaluecomplementarityconditioni!i=0;i=1;:::;n.Observethatiand!iarethelimitsofiand!ias!0,andQmaybetakentobealimitpoint(notnecessarilyunique)ofthesetfQ:0g.Wehave1


nand!1


!n:(1.10)Interior-pointmethodsforsemideniteprogrammingwereoriginallyintroducedby[11,4].Earlypapersonprimal-dualmethodsinclude[17]and[6].Apreliminaryversionofthepresentworkappearedas[2].Convergenceanalysisofprimal-dualpath-followingmethodsforSDPappearedrstin[7,13,12].Weareprimarilyconcernedwithfourmethods,whichwecalltheXZ,XZ+ZX,Nesterov{Todd(NT),andQmeth-ods.TheXZmethodrstappearedin[6,7].TheXZ+ZXmethodwasintroducedin748FARIDALIZADEH,JEAN-PIERREA.HAEBERLY,ANDMICHAELL.OVERTON[2]andwasrecentlyanalyzedin[8,9].TheNTmethodwasgivenin[13,12]anditsimplementationwasrecentlydiscussedin[16].TheQmethodoriginallyappearedin[1].Manyotherpapersonsemideniteprogramminghaverecentlybeenannounced.Thepaperisorganizedasfollows.Insection2weintroduceseveralalgorithmsinacommonframeworkbasedonNewton'smethod,focusingontheXZandXZ+ZXvariants.Insection3westudytheJacobianoftheNewtonsystemforthevariousmethodsundernondegeneracyassumptions,anddiscussimplicationsforlocalcon-vergencerates.Insection4weconsidertheconditioningoftheSchurcomplementmatrixonthecentralpath,againundernondegeneracyassumptions.Thisleadstotheissueofnumericalstability,discussedinsection5.WeintroducetheQmethodinsection6.Insection7,wepresentcomputationalresults.Ourmainfocusisonthenondegeneratecase;thisassumption(denedinsection3)impliesuniqueprimalanddualsolutions.Wetaketheviewthatitisimportanttounderstandhowmethodsbehaveonnondegenerateproblems.