Numerical treatment of nonlinear semidefinite programs [Elektronische Ressource] / vorgelegt von Christoph Helmut Vogelbusch

Numerical Treatment of NonlinearSemidefinite ProgramsInaugural-DissertationzurErlangung des Doktorgrades derMathematisch-Naturwissenschaftlichen Fakultat¨der Heinrich-Heine-Universit¨at Du¨sseldorfvorgelegt vonChristoph Helmut Vogelbuschaus RatingenDezember 2006Aus dem Institut fur Mathematik der¨Heinrich-Heine-Universita¨t Du¨sseldorfGedruckt mit der Genehmigung derMathematisch-Naturwissenschaftlichen Fakultat der¨Heinrich-Heine-Universit¨at Du¨sseldorfReferent: Prof. Dr. Florian JarreKoreferent: Prof. Dr. Helmut RatschekTag der mundlichen Prufung: 31.01.2007¨ ¨ZusammenfassungDieDissertation Numerical Treatment of Nonlinear Semidefinite ProgramsdiskutiertzweiAlgorithmen zum Losen¨ von nichtlinearen, nicht konvexen semidefiniten Programmen(SDPs).AusgangspunktfurdieForschungenwarenmathematischeProbleme,diebeiderSchalt-¨1kreissimulation auftreten. Fur diese als nichtlineare SDPs formulierbaren Probleme ex-¨istierte kein brauchbarer Loser.¨Ein nichtlineares SDP wird in dieser Dissertation gegeben durchmin{ C•X |F(X)=0, X ∈S }+n n mHierbei sind C,X ∈ S symmetrische Matrizen und F : S → R eine nichtlinearen×nAbbildung. C • X ist das Standard-R -Skalarprodukt, gegeben durch die Spur desTProdukts C X,TC•X :=tr(C X).n n×nDie Menge S ist der Teilkegel der reellen Matrizen in R , der die symmetrischen+nMatrizen mit nicht negativen Eigenwerten umfasst. Weiter bezeichnen wir mit S den++Kegel der symmetrischen Matrizen, deren Eigenwerte positiv sind.
Publié le : dimanche 1 janvier 2006
Lecture(s) : 27
Tags :
Source : DOCSERV.UNI-DUESSELDORF.DE/SERVLETS/DERIVATESERVLET/DERIVATE-3652/1652.PDF
Nombre de pages : 89
Voir plus Voir moins
Numerical Treatment of Nonlinear Semidefinite Programs
Inaugural-Dissertation
zur Erlangung des Doktorgrades der Mathematisch-NaturwissenschaftlichenFakult¨at derHeinrich-Heine-Universita¨tDu¨sseldorf
vorgelegt von
Christoph Helmut Vogelbusch
aus Ratingen
Dezember 2006
AusdemInstitutf¨urMathematikder Heinrich-Heine-Universit¨atD¨usseldorf
Gedruckt mit der Genehmigung der Mathematisch-NaturwissenschaftlichenFakult¨atder Heinrich-Heine-Universit¨atDusseldorf ¨
Referent:
Koreferent:
Prof. Dr. Florian Jarre
Prof. Dr. Helmut Ratschek
Tagdermu¨ndlichenPru¨fung:
31.01.2007
Zusammenfassung
Die DissertationNumerical Treatment of Nonlinear Semidefinite Programsdiskutiert zwei AlgorithmenzumL¨osenvonnichtlinearen,nichtkonvexensemidenitenProgrammen (SDPs). Ausgangspunktf¨urdieForschungenwarenmathematischeProbleme,diebeiderSchalt-kreissimulation1ierbrmulPsforeSDniaehcltslinseaediurF¨n.tereftauemel-xeneraborP istiertekeinbrauchbarerLo¨ser. Ein nichtlineares SDP wird in dieser Dissertation gegeben durch
min{CX|F(X) = 0, X∈ S+}
Hierbei sindC, X∈ Snsymmetrische Matrizen undF:SnRmeine nichtlineare Abbildung.CXist das Standard-Rn×n-Skalarprodukt, gegeben durch die Spur des ProduktsCTX,
CX:= tr(CTX).
Die MengeSn+ist der Teilkegel der reellen Matrizen inRn×n, der die symmetrischen Matrizen mit nicht negativen Eigenwerten umfasst. Weiter bezeichnen wir mitSn+den + Kegel der symmetrischen Matrizen, deren Eigenwerte positiv sind. EineSemidenitheitsbedingungl¨asstsichu¨berdieUnterdeterminantenauchalsnicht-lineareBedingungschreiben.EineBeru¨cksichtigungsolchernichtlinearenNebenbeding-ungenfu¨hrtallerdingszuentartetenProblemenundistnichtezientlo¨sbar.In[St05] beschreibtStingleinealternativeMethodezumL¨osennichtlinearerSDPs,diezurgleichen Zeit wie diese Dissertation entstand. Die Methode in [St05] basiert auf einem modifizierten Barriereansatz und wurde ebenfalls implementiert. In der Praxis werden daher Algorith-menverwendet,diedieSemidenitheitsbedingungalsKegelbedingungber¨ucksichtigen. DererstehiervorgestellteAnsatzsolcheProblemeezientzul¨osenistdasSSP(Se-quential Semidefinite Programs”) Verfahren. Dieses Verfahren lehnt sich an das SQP Ver-fahrenan,dasdieL¨osungnichtlinearerProgrammedurchdassequentielleL¨osenquadratis-cher Programme der Form
mΔiXn{CΔX12+BX,ΔX]|F(X) + DF(X)[ΔX] = 0, X+ ΔX∈ S+}
anna¨hert.BeimSSPVerfahrenwirddieL¨osungeinesnichtlinearensemidenitenPro-grammsdurcheineFolgevonlinearenSDPsangena¨hert.ErsteanalytischeErgebnisse bescheinigen dem SSP Verfahren die gleichen theoretischen Konvergenz Ergebnisse wie demSQPVerfahren.DieseAnalysenverwendenfu¨rdielinearisiertenProblemedieexakte HessematrixderLagrangefunktion.Leidergibtesf¨urdiedarausentstehendenapproxima-tivenProblemenurdannezienteLo¨ser,wenndieseMatrixpositivsemidenitist.Fur ¨ den SQP Fall gibt es unter milden Voraussetzungen positiv semidefinite Approximationen, die auf den linearisierten Nebenbedingungen mit der Hessematrix der Lagrangefunktion u¨bereinstimmen.
1Unsere Beispiele wurden gestellt von den Lucent/Bell Laboratorien
In dieser Dissertation wird gezeigt, dass es solche positiv semidefiniten Approximationen der Hessematrix der Lagrangefunktion im SSP Fall nicht immer gibt. Die Hessematrix von nichtlinearen SDPs kann auf den linearisierten Nebenbedingungen negative Eigenwerte haben.DerGrundhierf¨urist,dassdieRandkr¨ummungdessemidenitenKegelsnichtin der Lagrangefunktion eingeht. WeiterzeigenwiranHandeinesBeispiels,dassdasSSPVerfahrenfu¨rjedebeschr¨ankte positiv semidefinite Approximation der Hessematrix nicht schneller als linear konvergieren kann.Diesbildeteinen¨uberraschendenKontrastzudemSQP-Verfahren. Im Rahmen dieser Dissertation wurde das SSP Verfahren auch implementiert, um die Schaltkreis-Problemezul¨osen.Eszeigtsich,dassdasSSPVerfahreneineguteglobale Konvergenzfu¨rdiegetestetenProblemehat. ImKapitel¨uberdieSSP-ImplementierungstellenwireineneueSchrittweitenkontrolle vor:dieerweitertenFilter.DasSSPVerfahrenhatf¨uralleunsvorliegendenBeispielemit den erweiterten Filtern eine deutlich schnellere Konvergenz als eine Penalty-Linesearch oder die standard Filter Methode. Eine besondere Eigenschaft dieser erweiterten Filter ist, dass sie einen guten Indikator liefern, wann wir Nahe am Optimum sind, wann es also sinnvollwa¨reaufeinenL¨osermitschnellerlokalKonvergenzzuwechseln. UmdieSt¨arken,dieschnelleglobaleKonvergenz,desSSPVerfahrenszunutzenund Schw¨achendesSSPVerfahrens,dielinearelokaleKonvergenz,zuvermeidenschlagenwirin dieserArbeiteinenhybridenLo¨servor.DieserhybrideLo¨serverwendetdasSSPVerfahren umdemOptimumnahezukommenundwechseltdannzueinenschnellenlokalenLo¨ser. AlsschnellenlokalenLo¨serbetrachtenwireineInnere-Punkte-Methode(IPM). F¨urdieseIPM,wirdzuna¨chsteinzentralerPfadinderNa¨hederOptimalLo¨sung deniert.WirstelleneinenPra¨diktor-KorrektorAlgorithmusvor,derdiesemPfadfolgt. Um beim Folgen dieses Pfades eine Abstiegsrichtung zu erhalten, muss die Summe
H+F1E
auf den linearisierten Nebenbedingungen positiv definit sein. Hierbei istHdie Hessematrix der Lagrangefunktion undF1Eein Symmetrisierungsterm. Da der TermF1Ebereits positiv definit ist, ist ein naheliegender Ansatz, eine positiv semidefinite Approximation vonHn,hnelhr¨anssehaereVfrSsPSneedenMdIPeredttrichshcuSeidaD.nednezuverw folgtauchf¨urdasIPMbeieinerpositivsemidenitenApproximationvonHeine langsame Konvergenz. Wir zeigen, dass eine positiv definite Approximation vonH+F1E ∈ S+n+gefunden werdenkann,fu¨rdiediequadratischeKonvergenzerhaltenbleibt,fallseineschwache Barrierebedinungerfu¨lltist. Theoretischwirdf¨urdenPra¨diktorschritteineApproximationbeno¨tigt,dieinnur gewisseRichtungenpositivdenitist.F¨ureinegenerellepositivdeniteApproxima-tion,ergebenabereinigeVorteile.DaeinesolcheApproximationsowohlf¨urPra¨diktor-alsauchdenKorretkorschrittverwendetwerdenkann,istesmo¨glichRang-1oderRang-2 Updatesfu¨rH+F1Enennnnadegegnienienn.reesDi¨oekntieesolchepositivdeuzed Approximation vonH+F1Ekonvergieren und eine superlineare Konvergenz erreichen. Zus¨atzlichistdieDekompositioneinerpositivdenitenMatrixezienter,daf¨urdiesedas Choleskiverfahren verwendet werden kann.
ii
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.