11
$\begingroup$

On Wikipedia's page for the KKT conditions, it is stated that Mangasarian-Fromovitz constraint qualification (MFCQ) is weaker than linear independent constraint qualification (LICQ). What is a counter-example to the claim MFCQ $\Rightarrow$ LICQ?

$\endgroup$
8
$\begingroup$

Consider the following minimization problem

\begin{eqnarray} \min &&\quad f(x) ~&= -x &\\ \text{s.t.} &&\quad g_1(x) & =x &\le 0\\ &&\quad g_2(x) & = 2x &\le 0 \end{eqnarray}

which attains the unique global minimum for $x^* = 0$. Note that both constraints are active in this point.

By definition, $\nabla g_1(x^*) = 1$ and $\nabla g_2(x^*) = 2$.

MFCQ

The gradients of the equality constraints are linearly independent at $x^*$ and there exists a vector $d \in \mathbb{R}^n$ such that $\nabla g_i(x^*)^\top d < 0$ for all active inequality constraints and $\nabla h_j(x^*)^\top d = 0$ for all equality constraints.

In this case, we can choose $d = -1$ to obtain $\nabla g_i(x^*)^\top d < 0$ for all $i \in \{1,2\}$. We have no equality constraints. It follows that MFCQ holds.

LICQ

The gradients of the active inequality constraints and the gradients of the equality constraints are linearly independent at $x^*$.

At $x^*$, both constraints are active and their gradients are clearly not independent. It follows that LICQ does not hold.

We conclude that MFCQ $\Rightarrow$ LICQ is false.

$\endgroup$
  • 2
    $\begingroup$ Extra credit if your counterexample does not satisfy Linear Constraints Qualification, i.e., has nonlinear constraints. $\endgroup$ – Mark L. Stone Nov 3 at 14:40
  • 5
    $\begingroup$ @MarkL.Stone For extra credit: replace the constraints by $g_1(x) = x^2 + x$ and $g_2(x) = x^2 + 2x$. $\endgroup$ – Kevin Dalmeijer Nov 3 at 14:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.