Slater-Bedingung

Die Slater-Bedingung oder auch Slater constraint qualification oder kurz Slater CQ ist eine wichtige Voraussetzung, dass notwendige Optimalitätskriterien in der konvexen Optimierung gelten. Die Slater-Bedingung ist eine Bedingung an die Regularität des gestellten Problems. Ist die Slater-Bedingung erfüllt und ist ein Punkt $\tilde{x}$ ein lokales Minimum, so sind auch die Karush-Kuhn-Tucker-Bedingungen an diesem Punkt erfüllt. Somit ist die Slater-Bedingung eine wichtige Voraussetzung, um für einen gegebenen Punkt überprüfen zu können, ob dieser ein Optimum ist.

Außerdem wird die Slater-Bedingung bei der Lagrange-Dualität als Voraussetzung für die starke Dualität genutzt.

Sie ist nach Morton L. Slater (1921–2002) benannt, einem Mathematiker an den Sandia National Laboratories.

Definition

Starke Version

Gegeben sei ein konvexes Optimierungsproblem von der Form

$\begin{array}{ccc}\text{Minimiere }& f(x)& \\ \text{unter den Nebenbedingungen }& g_i(x)\le 0& i=1,\dots ,k\\ & l_j(x)=a_j^{T}x-b_j\le 0& j=1,\dots ,l\\ & h_k(x)=a_k^{T}x-b_k=0& k=1,\dots ,m\end{array}$

mit konvexer Zielfunktion $f$, konvexen und nichtaffinen Ungleichungsrestriktionen $g_i(x)$ sowie affinen Ungleichungs- und Gleichungsrestriktionsfunktionen $l_j(x)$ und $h_k(x)$. Sei $D\subset {ℝ}^n$ der Definitionsbereich des Problems, also die größte konvexe Menge, auf der alle $g_i(x)$ und $f$ wohldefiniert und konvex sind. Das Problem erfüllt die Slater-Bedingung, wenn es mindestens einen relativ inneren Punkt $\tilde{x}$ von $D$ gibt, so dass

• alle konvexen Ungleichungsnebenbedingungen strikt erfüllt sind: $g_i(\tilde{x})<0$
• alle affinen Ungleichungs- und Gleichungsnebenbedingungen erfüllt sind: $l_j(\tilde{x})\le 0$ und $h_k(\tilde{x})=0$.

Schwache Variante

Gelegentlich findet sich auch die schwächere Variante, dass für mindestens einen relativ inneren Punkt $\tilde{x}$ alle Ungleichungsnebenbedingungen strikt erfüllt sein müssen: $g_i(\tilde{x})<0,l_j(\tilde{x})<0$ und die Gleichungsrestriktionen erfüllt sein müssen. Dieser Fall ist in dem obigen Fall enthalten, aber in der Literatur häufig zu finden, da er leichter zu zeigen ist. Er deckt jedoch zum Beispiel nicht alle Fälle von starker Dualität bei linearen Programmen ab.

Bei verallgemeinerten Ungleichungen

Verwendet man verallgemeinerte Ungleichungen und K-konvexe Funktionen und erhält damit Restriktionen wie

$g_i(x){\preccurlyeq }_{K_i}0$,

so ersetzt man das echtkleiner durch die strikte verallgemeinerte Ungleichung ${\prec }_{K_i}$. Somit gilt bei konvexen Problemen mit verallgemeinerten Ungleichungen die Slater-Bedingung, wenn es einen relativ inneren Punkt $\tilde{x}$ gibt, so dass alle Gleichungsrestriktionen in $\tilde{x}$ erfüllt sind und für alle Ungleichungsrestriktionen gilt, dass $g_i(\tilde{x}){\prec }_{K_i}0$ ist.

Für fast konvexe Funktionen

Ist ein Optimierungsproblem der Form

$\begin{array}{cc}\text{Minimiere }& f(x)\\ \text{unter den Nebenbedingungen }& g(x)\in -K\\ & x\in R\end{array}$

gegeben für einen Ordnungskegel $K$ mit nichtleerem Inneren und Abbildungen $f:V\mapsto ℝ$ und $g:V\mapsto Y$. Dabei sind $V,Y$ normierte reelle Vektorräume und die Funktion $K:V\mapsto ℝ\times Y$ definiert durch $K(x)=(f(x),g(x))$ ist fast konvex bezüglich des Kegles ${ℝ}_{+}\times K$. $R$ sei eine beliebige nichtleere Teilmenge von $V$.

Dann erfüllt das Problem die Slater-Bedingung, wenn es einen zulässigen Punkt $\tilde{x}$ gibt (das heißt $\tilde{x}\in R,g(\tilde{x})\in -K$), so dass $g(\tilde{x})\in \mathrm{int}(-K)$ ist. Dabei ist $\mathrm{int}(M)$ das Innere der Menge $M$. Diese Formulierung enthält sowohl den Fall mit verallgemeinerten Ungleichungen (dann ist $K$ ein echter Kegel) als auch die schwache Variante.

Beispiel

Betrachten wir als Beispiel die Funktionen $g_1(x)=(x_1/2{)}^2+x_2^2-1,g_2(x)=x_1^2+(x_2/2{)}^2-1$ und $l_1(x)=x_1-x_2$. Die Menge $\{x\in {ℝ}^2|g_1(x)\le 0,g_2(x)\le 0,l_1(x)\le 0\}$ ist Restriktionsmenge eines konvexen Problems. Angenommen, die Zielfunktion hat als Definitionsbereich den gesamten ${ℝ}^2$. Dann ist $D={ℝ}^2$ und es muss noch ein strikt zulässiger Punkt bezüglich $g_1,g_2$ gefunden werden, der zulässig bezüglich $l_1$ ist. Der Punkt $(-0.5,-0.5)$ erfüllt diese Voraussetzung, somit erfüllt das Problem die Slater-Bedingung.

Beziehung zu anderen constraint qualifications

Die Slater-Bedingung impliziert die Abadie CQ, die Umkehrung gilt aber nicht. Der Hauptunterschied zu anderen constraint qualifications ist, dass die Slater-Bedingung eine Bedingung an das gestellte Problem ist und nicht wie bei anderen CQ an einen gewissen Punkt. Dies macht die Slater-Bedingung leichter zu überprüfen und liefert die Regularität aller zulässigen Punkte des Problems. Eingeschränkt wird ihre Verwendung durch die Tatsache, dass sie nur für konvexe Probleme gilt.

Literatur

• Florian Jarre, Josef Stoer: Optimierung. Springer, Berlin 2004, ISBN 3-540-43575-1.
• C. Geiger, C. Kanzow: Theorie und Numerik restringierter Optimierungsaufgaben. Springer, 2002. ISBN 3-540-42790-2. https://books.google.de/books?id=spmzFyso_b8C&hl=de

Weblinks

• Buch Convex Optimization von Stephen Boyd und Lieven Vandenberghe (PDF) (engl.)