Slater-Bedingung

Gegeben sei ein konvexes Optimierungsproblem von der Form

${\displaystyle {\begin{aligned}{\text{Minimiere }}&f(x)&\\{\text{unter den Nebenbedingungen }}&g_{i}(x)\leq 0&i=1,\dots ,k\\&l_{j}(x)=a_{j}^{T}x-b_{j}\leq 0&j=1,\dots ,l\\&h_{k}(x)=a_{k}^{T}x-b_{k}=0&k=1,\dots ,m\end{aligned}}}$

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

• alle konvexen Ungleichungsnebenbedingungen strikt erfüllt sind: ${\displaystyle g_{i}({\tilde {x}})<0}$
• alle affinen Ungleichungs- und Gleichungsnebenbedingungen erfüllt sind: ${\displaystyle l_{j}({\tilde {x}})\leq 0}$ und ${\displaystyle h_{k}({\tilde {x}})=0}$.

Gelegentlich findet sich auch die schwächere Variante, dass für mindestens einen relativ inneren Punkt ${\displaystyle {\tilde {x}}}$ alle Ungleichungsnebenbedingungen strikt erfüllt sein müssen: ${\displaystyle 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.

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

${\displaystyle g_{i}(x)\preccurlyeq _{K_{i}}0}$,

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

Ist ein Optimierungsproblem der Form

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

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

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