La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Partagez cette publication

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