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 S⁰ 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:

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 D³ Φ zu D² Φ drückt aus, daß die bei einer Linearisierung durchgeführte Approximation von D²Φ(x) durch D² Φ (x^k) (x^k 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 x₀ ∈ S⁰ein Startpunkt.

Dann läßt sich ausgehend von x₀eine 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.