Direkt zum Inhalt

Lexikon der Mathematik: Selbstkonkordanz

zusammen mit der Selbstbeschränkung eine zentrale Eigenschaft von Barrierefunktionen, die ihre Verwendbarkeit bei Innere-Punkte Methoden sicherstellt.

Im wesentlichen geht es dabei um die Frage, inwieweit sich diese Verfahren auf allgemeinere konvexe Optimierungsprobleme als die lineare Programmierung ausdehnen lassen.

Wir betrachten das Minimierungsproblem \begin{eqnarray}{c}^{T}.x\to \min \end{eqnarray} auf einer Menge \(x\in S\subset {{\mathbb{R}}}^{n}\), die kompakt und konvex sei. Zudem nehmen wir an, daß das Innere S0 von S nicht leer sei. Man beachte, daß sich auf diese Art auch nichtlineare konvexe Zielfunktionen f(x) → min behandeln lassen: Zunächst führe man eine zusätzliche Variable \({x}_{n+1}\) ein; fügt man jetzt die Nebenbedingung \(f(x)\le {x}_{n+1}\) hinzu, und tauscht die Zielfunktion f gegen die neue lineare Zielfunktion \({x}_{n+1}\) aus, so hat das Problem \({{x}_{n+1}}\) → min unter \(x\in S,f(x)\le {x}_{n+1}\) die gewünschte Form, und seine Lösungen sind genau diejenigen des Ausgangsproblems.

Der Spezialfall \begin{eqnarray}S=\{x\in {{\mathbb{R}}}^{n}|{a}_{i}^{T}\cdot x-{b}_{i}\le 0, 1\le i\le m\}\end{eqnarray} liefert die lineare Programmierung. Hier spielt die logarithmische Barrierefunktion \begin{eqnarray}\Phi (x):=-\mathop{\sum ^{m}}\limits_{i=1}\mathrm{ln}({b}_{i}-{a}_{i}^{T}\cdot x)\end{eqnarray} eine fundamentale Rolle bei der Anwendung Innerer-Punkte Methoden. Es stellt sich dabei heraus, daß lediglich drei Eigenschaften von Φ für das Gelingen eines derartigen Verfahrens notwendig sind:

  • die Eigenschaft, eine Barrierefunktion zu sein;
  • die sogenannte Selbstkonkordanz: Φ ist eine konvexe C3 -Funktion auf S0 und erfüllt dort die Differentialgleichung \begin{eqnarray}|{D}^{3}\Phi (x)(h,h,h)|\le 2\cdot {\left({D}^{2}\Phi (x)(h,h)\right)}^{\frac{3}{2}}\end{eqnarray} für alle \(h\in {{\mathbb{R}}}^{n}\);
  • die sogenannte Selbstbeschränkung: Φ ist Lip-schitz-stetig bezüglich der lokalen Metrik, dievon seiner zweiten Ableitung erzeugt wird, d.h., \(\forall x\in {S}^{0},h\in {{\mathbb{R}}}^{n}\), gilt \begin{eqnarray}|D\Phi (x)h|\le \sqrt{\vartheta}\cdot {({D}^{2}\Phi (x)(h,h))}^{\frac{1}{2}}.\end{eqnarray}

    Hierbei ist ϑ ≥ 1 eine von Φ abhängige Konstante (der Parameter der Barrierefunktion).

    Selbstkonkordanz garantiert im wesentlichen schnelle lokale Konvergenz des Newtonverfahrens für die Nullstellensuche von DΦ: Das geforderte Verhältnis von D3 Φ zu D2 Φ drückt aus, daß die bei einer Linearisierung durchgeführte Approximation von D2Φ(x) durch D2 Φ (xk) (xk ein Iterationspunkt) relativ gut ist. Man beachte, daß der geforderte Faktor 2 beliebig ist und durch jedes α > 0 ersetzt werden kann. Man betrachtet häufig α = 2, da sich diese Wahl für die Barrierefunktion — ln(t) ergibt.

    • Die Selbstbeschränkung bewirkt, daß die obige lokale Konvergenz in einem genügend großen Einzugsbereich vorliegt. Zusammenfassend gilt dann:

    Sei Φ eine selbstkonkordante und selbstbeschränkte Barrierefunktion auf S, und sei x0 ∈ S0ein Startpunkt.

    Dann läßt sich ausgehend von x0eine Innere-Punkte Methode ausführen, die zu vorgegebenem ε > 0 in Polynomzeit (Turingmodell) einen Punkt xε erzeugt, der \begin{eqnarray}{c}^{T}\cdot {x}_{\varepsilon}-\mathop{\min}\limits_{x\in S}{c}^{T}\cdot x\le \varepsilon \end{eqnarray}erfüllt.

    [1] Nemirovskii, A.S.; Nesterov, Y.: Interior-point polynomial algorithms in convex programming. SIAM Publications, Philadelphia, 1994.

    Copyright Springer Verlag GmbH Deutschland 2017
    • Die Autoren
    - Prof. Dr. Guido Walz

    Schreiben Sie uns!

    Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

    Artikel zum Thema

    Themenkanäle

    Partnerinhalte

    Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.