# Example satisfying Mangasarian-Fromovitz CQ but not LICQ

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?

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.

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