Linear independence constraint qualification

Die Linear independence constraint qualification oder kurz LICQ ist in der Optimierung eine Bedingung an die Regularität des gestellten Problems. Ist die MFCQ in einem Punkt ${\tilde {x}}$ erfüllt und ist dieser Punkt ein lokales Minimum, so sind auch die Karush-Kuhn-Tucker-Bedingungen an diesem Punkt erfüllt. Gilt die LICQ, so ist auch die MFCQ und die Abadie CQ automatisch erfüllt, die Umkehrung gilt aber nicht. Somit ist die LICQ eine Vorraussetzung, um ein notwendiges Optimalitätskriterium zu gewinnen.

Definition

Gegeben ist ein Optimierungsproblem in der Form

$\min _{x\in X}f(x)$

wobei $X=\{x\in \mathbb {R} ^{n}\,|\,g_{i}(x)\leq 0,h_{j}(x)=0,\;i=1,\dots ,k;\;j=1,\dots l\}$

die Restriktionsmenge ist und alle Funktionen stetig differenzierbar sein sollen. Es sei $K(x)=\{i\,|\,g_{i}(x)=0\}$ die Menge der Indizes, bei denen die Ungleichungsrestriktionen mit Gleichheit erfüllt sind. Dann erfüllt ein zulässiger Punkt ${\tilde {x}}\in X$ des restringierten Optimierungsproblems die LICQ, wenn die Gradienten $\nabla h_{j}({\tilde {x}})$ und $\nabla g_{i}({\tilde {x}})$ mit $i\in T({\tilde {x}})$ linear unabhängig sind.

Beispiel

LICQ

Betrachten wir als Beispiel die Restriktionsfunktionen $g_{1}(x)=x_{1}+x_{2}-1\leq 0$ und $g_{2}(x)=x_{1}^{2}+x_{2}^{2}-1\leq 0$. Wir untersuchen, ob der Punkt ${\tilde {x}}=(0,1)$ die LICQ erfüllt. Die Gradienten sind $\nabla g_{1}({\tilde {x}})=(1,1)$ und $\nabla g_{2}({\tilde {x}})=(2,0)$. Beide Ungleichungsrestriktionen sind im untersuchten Punkt aktiv und die Gradienten sind linear unabhängig. Daher erfüllt der Punkt die LICQ.

MFCQ ohne LICQ

Betrachtet man die Restriktionsfunktionen $g_{1}(x)=-x_{2}\leq 0$ und $g_{2}(x)=x_{1}^{4}-x_{2}\leq 0$ mit und untersucht diese Im Punkt ${\tilde {x}}=(0,0)$, so ist die LICQ nicht erfüllt. Die Gradienten $\nabla g_{1}({\tilde {x}})=(0,-1)$ und $\nabla g_{2}({\tilde {x}})=(0,-1)$ sind linear abhängig und beide Ungleichungen sind im untersuchten Punkt aktiv. Die MFCQ sind aber erfüllt, da für den Vektor $d=(0,1)$ gilt, dass $\nabla g_{i}({\tilde {x}})^{T}d<0$.

Literatur

• C. Geiger, C. Kanzow: Theorie und Numerik restringierter Optimierungsaufgaben. Springer, 2002. ISBN 3-540-42790-2. http://books.google.de/books?id=spmzFyso_b8C