Linear independence constraint qualification

The linear independence constraint qualification or LICQ for short is an important prerequisite for the necessary optimality criteria to apply in non-linear optimization . It is a condition of the regularity of a feasible point. If the LICQ is fulfilled at one point and this point is a local minimum , then the Karush-Kuhn-Tucker conditions are also fulfilled at this point. ${\displaystyle {\tilde {x}}}$

definition

There is an optimization problem in the form

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

in which

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

is the restriction set and all functions should be continuously differentiable . Let it be the set of indices for which the inequality restrictions are satisfied with equality. Then a feasible point of the restricted optimization problem fulfills the LICQ if the gradients and with are linearly independent . ${\displaystyle K(x)=\{i\,|\,g_{i}(x)=0\}}$ ${\displaystyle {\tilde {x}}\in X}$ ${\displaystyle \nabla h_{j}({\tilde {x}})}$ ${\displaystyle \nabla g_{i}({\tilde {x}})}$ ${\displaystyle i\in K({\tilde {x}})}$

example

LICQ

As an example, consider the restriction functions and . We investigate whether the point meets the LICQ. It is because both inequalities are active. The gradients are and . Both inequality restrictions are active in the examined point and the gradients are linearly independent. Therefore the point fulfills the LICQ. ${\displaystyle g_{1}(x)=x_{1}+x_{2}-1\leq 0}$ ${\displaystyle g_{2}(x)=x_{1}^{2}+x_{2}^{2}-1\leq 0}$ ${\displaystyle {\tilde {x}}=(0,1)}$ ${\displaystyle K({\tilde {x}})=\{1,2\}}$ ${\displaystyle {\tilde {x}}}$ ${\displaystyle \nabla g_{1}({\tilde {x}})=(1,1)^{T}}$ ${\displaystyle \nabla g_{2}({\tilde {x}})=(0,2)^{T}}$

MFCQ without LICQ

If one looks at the restriction functions and and examines them in point , the LICQ is not fulfilled. The gradients and are linearly dependent and both inequalities are active in the examined point. The MFCQ are fulfilled, however, since it holds for the vector that . ${\displaystyle g_{1}(x)=-x_{2}\leq 0}$ ${\displaystyle g_{2}(x)=x_{1}^{4}-x_{2}\leq 0}$ ${\displaystyle {\tilde {x}}=(0,0)}$ ${\displaystyle \nabla g_{1}({\tilde {x}})=(0,-1)^{T}}$ ${\displaystyle \nabla g_{2}({\tilde {x}})=(0,-1)^{T}}$ ${\displaystyle d=(0,1)}$ ${\displaystyle \nabla g_{i}({\tilde {x}})^{T}d<0}$

Comparison with other constraint qualifications

If the LICQ applies, the MFCQ and therefore the Abadie CQ are also automatically fulfilled. In contrast to the MFCQ and the Abadie CQ, the LICQ has the advantage that it is easy to check. One disadvantage is that it is not as general as the other constraint qualifications . This is illustrated by the example above. The implications apply

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

But the inversions do not apply.

literature

• C. Geiger, C. Kanzow: Theory and numerics of restricted optimization tasks . Springer, 2002. ISBN 3-540-42790-2 . http://books.google.de/books?id=spmzFyso_b8C