Linear independence constraint qualification

Die Linear independence constraint qualification oder kurz LICQ ist eine wichtige Voraussetzung, dass notwendige Optimalitätskriterien in der nichtlinearen Optimierung gelten. Sie ist eine Bedingung an die Regularität eines zulässigen Punktes. Ist die LICQ in einem Punkt ${\displaystyle {\tilde {x}}}$ erfüllt und ist dieser Punkt ein lokales Minimum, so sind auch die Karush-Kuhn-Tucker-Bedingungen an diesem Punkt erfüllt.

Definition

Gegeben ist ein Optimierungsproblem in der Form

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

wobei

${\displaystyle 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 ${\displaystyle K(x)=\{i\,|\,g_{i}(x)=0\}}$ die Menge der Indizes, bei denen die Ungleichungsrestriktionen mit Gleichheit erfüllt sind, d. h. die Ungleichungsrestriktion ${\displaystyle g_{i}(x)}$ ist aktiv. Dann erfüllt ein zulässiger Punkt ${\displaystyle {\tilde {x}}\in X}$ des restringierten Optimierungsproblems die LICQ, wenn die Gradienten ${\displaystyle \nabla h_{j}({\tilde {x}})}$ und ${\displaystyle \nabla g_{i}({\tilde {x}})}$ mit ${\displaystyle i\in K({\tilde {x}})}$ linear unabhängig sind.

Beispiel

LICQ

Betrachten wir als Beispiel die Restriktionsfunktionen ${\displaystyle g_{1}(x)=x_{1}+x_{2}-1\leq 0}$ und ${\displaystyle g_{2}(x)=x_{1}^{2}+x_{2}^{2}-1\leq 0}$. Wir untersuchen, ob der Punkt ${\displaystyle {\tilde {x}}=(0,1)}$ die LICQ erfüllt. Es ist ${\displaystyle K({\tilde {x}})=\{1,2\}}$, da beide Ungleichungen in ${\displaystyle {\tilde {x}}}$ aktiv sind. Die Gradienten sind ${\displaystyle \nabla g_{1}({\tilde {x}})=(1,1)^{T}}$ und ${\displaystyle \nabla g_{2}({\tilde {x}})=(0,2)^{T}}$. 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 ${\displaystyle g_{1}(x)=-x_{2}\leq 0}$ und ${\displaystyle g_{2}(x)=x_{1}^{4}-x_{2}\leq 0}$ und untersucht diese im Punkt ${\displaystyle {\tilde {x}}=(0,0)}$, so ist die LICQ nicht erfüllt. Die Gradienten ${\displaystyle \nabla g_{1}({\tilde {x}})=(0,-1)^{T}}$ und ${\displaystyle \nabla g_{2}({\tilde {x}})=(0,-1)^{T}}$ sind linear abhängig und beide Ungleichungen sind im untersuchten Punkt aktiv. Die MFCQ sind aber erfüllt, da für den Vektor ${\displaystyle d=(0,1)}$ gilt, dass ${\displaystyle \nabla g_{i}({\tilde {x}})^{T}d<0}$.

Vergleich mit anderen constraint qualifications

Gilt die LICQ, so ist auch die MFCQ und daher die Abadie CQ automatisch erfüllt. Die LICQ hat im Gegensatz zur MFCQ und zur Abadie CQ den Vorteil, dass sie leicht zu überprüfen ist. Ein Nachteil ist, dass sie nicht so allgemein gültig ist wie die anderen constraint qualifications. Dies wird durch das obige Beispiel illustriert. Es gelten die Implikationen

${\displaystyle {\text{LICQ}}\implies {\text{MFCQ}}\implies {\text{Abadie CQ}}}$.

Die Umkehrungen gelten aber nicht.

Literatur

• 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