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

Description

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.

Sujets

• Mathematics

Informations

• Publié par: heinrich-heine-universitat_dusseldorf
• Publié le: 01 janvier 2006
• Nombre de lectures: 27
• Langue: Deutsch

Extrait

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,nichtkonvexensemidefinitenProgrammen (SDPs). Ausgangspunktf ¨ urdieForschungenwarenmathematischeProbleme,diebeiderSchalt- kreissimulation 1 ierbrmulPsforeSDniaehcltslinseaediurF ¨ n.tereftauemel-xeneraborP istiertekeinbrauchbarerLo ¨ ser. Ein nichtlineares SDP wird in dieser Dissertation gegeben durch

min{C•X|F(X) = 0, X∈ S + }

Hierbei sindC, X∈ S n symmetrische Matrizen undF:S n →R m eine nichtlineare Abbildung.C•Xist das Standard-R n×n -Skalarprodukt, gegeben durch die Spur des ProduktsC T X,

C•X:= tr(C T X).

Die MengeS n + ist der Teilkegel der reellen Matrizen inR n×n , der die symmetrischen Matrizen mit nicht negativen Eigenwerten umfasst. Weiter bezeichnen wir mitS n + den + Kegel der symmetrischen Matrizen, deren Eigenwerte positiv sind. EineSemidefinitheitsbedingungl ¨ asstsichu ¨ berdieUnterdeterminantenauchalsnicht- lineareBedingungschreiben.EineBeru ¨ cksichtigungsolchernichtlinearenNebenbeding- ungenfu ¨ hrtallerdingszuentartetenProblemenundistnichteffizientlo ¨ 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,diedieSemidefinitheitsbedingungalsKegelbedingungber ¨ ucksichtigen. DererstehiervorgestellteAnsatzsolcheProblemeeffizientzul ¨ osenistdasSSP(“Se- quential Semidefinite Programs”) Verfahren. Dieses Verfahren lehnt sich an das SQP Ver- fahrenan,dasdieL ¨ osungnichtlinearerProgrammedurchdassequentielleL ¨ osenquadratis- cher Programme der Form

m Δ i X n{C•ΔX 1 2 +B[ΔX,ΔX]|F(X) + DF(X)[ΔX] = 0, X+ ΔX∈ S + }

anna ¨ hert.BeimSSPVerfahrenwirddieL ¨ osungeinesnichtlinearensemidefinitenPro- grammsdurcheineFolgevonlinearenSDPsangena ¨ hert.ErsteanalytischeErgebnisse bescheinigen dem SSP Verfahren die gleichen theoretischen Konvergenz Ergebnisse wie demSQPVerfahren.DieseAnalysenverwendenfu ¨ rdielinearisiertenProblemedieexakte HessematrixderLagrangefunktion.Leidergibtesf ¨ urdiedarausentstehendenapproxima- tivenProblemenurdanneffizienteLo ¨ ser,wenndieseMatrixpositivsemidefinitist.Fur ¨ den SQP Fall gibt es unter milden Voraussetzungen positiv semidefinite Approximationen, die auf den linearisierten Nebenbedingungen mit der Hessematrix der Lagrangefunktion u ¨ bereinstimmen.

1 Unsere 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 ¨ ummungdessemidefinitenKegelsnichtin 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 definiert.WirstelleneinenPra ¨ diktor-KorrektorAlgorithmusvor,derdiesemPfadfolgt. Um beim Folgen dieses Pfades eine Abstiegsrichtung zu erhalten, muss die Summe

H+F −1 E

auf den linearisierten Nebenbedingungen positiv definit sein. Hierbei istHdie Hessematrix der Lagrangefunktion undF −1 Eein Symmetrisierungsterm. Da der TermF −1 Ebereits positiv definit ist, ist ein naheliegender Ansatz, eine positiv semidefinite Approximation vonHn,hnelhr ¨ anssehaereVfrSsPSneedenMdIPeredttrichshcuSeidaD.nednezuverw folgtauchf ¨ urdasIPMbeieinerpositivsemidefinitenApproximationvonHeine langsame Konvergenz. Wir zeigen, dass eine positiv definite Approximation vonH+F −1 E ∈ S + n + gefunden werdenkann,fu ¨ rdiediequadratischeKonvergenzerhaltenbleibt,fallseineschwache Barrierebedinungerfu ¨ lltist. Theoretischwirdf ¨ urdenPra ¨ diktorschritteineApproximationbeno ¨ tigt,dieinnur gewisseRichtungenpositivdefinitist.F ¨ ureinegenerellepositivdefiniteApproxima- tion,ergebenabereinigeVorteile.DaeinesolcheApproximationsowohlf ¨ urPra ¨ diktor- alsauchdenKorretkorschrittverwendetwerdenkann,istesmo ¨ glichRang-1oderRang-2 Updatesfu ¨ rH+F −1 Enennnnadegegnieniefinn.reesDi ¨ oeknfitieesolchepositivdeuzed Approximation vonH+F −1 Ekonvergieren und eine superlineare Konvergenz erreichen. Zus ¨ atzlichistdieDekompositioneinerpositivdefinitenMatrixeffizienter,daf ¨ urdiesedas Choleskiverfahren verwendet werden kann.

ii