Lösung großer konischer Programme mithilfe augmentierter primal-dualer Funktionen

点击翻译按钮获取中文摘要

Konvexe Optimierungsprobleme lassen sich stets als konische lineare Programme (KLPs), d.h. als lineare Optimierungsprobleme über einem konvexen Kegel umformulieren. Unter gewissen Nichtentartungsvoraussetzungen lässt sich die Optimallösung des KLP als Schnitt einer affinen Mannigfaltigkeit L + b mit dem primal-dualen Kegel K charakterisieren. Für Punkte in L + b ist das Quadrat q des Abstandes zu K eine konvexe differenzier bare Funktion, deren Hessematrix fast überall definiert ist. Die Ableitung von q ergibt sich aus einfachen Projektionen auf K und L und ist somit in vielen Anwendungen auch für höher-dimensionale Probleme noch berechenbar, die mit Newton-artigen Ansätzen nicht mehr gelöst werden können. Die Minimierung von q ist äquivalent zur Lösung von KLP und soll mit einer Variante des BFGS-Verfahrens vorgenommen werden. Da die Funktion q in der obigen Form in der Regel im Optimalpunkt entartet ist, sollen gewisse lokale Regularisierungen untersucht werden. Des weiteren soll die Konvergenz von Verfahren niederer Ordnung wie cg oder BFGS bei semiglatten Funktionen untersucht werden. Ferner sollen Verallgemeinerungen auf entartete KLPs und auf semidefinite Komplementaritätsprobleme betrachtet werden.