# Do we really need the constraint qualification?

I can't keep my fingers off Nocedal/Wright's Numerical Optimization (1999,1E) and I apologize. But maybe YOU can shed light on the question:

Why does a point $x \in \mathbb{R}^n$ need to satisfy the linear independence constraint qualification (LICQ) AND the stationarity of the Lagrange equation to qualify as a prospective local solution to a static constrained optimization problem?

Or, to put it in other words,

Do we really need the LICQ for a first-order necessary optimality condition?

What's wrong with the following conclusion from the set of implications that I collected (all references taken from the book given above)?

1. There are Lagrange multipliers s.t. the Lagrange is stationary at $x$. $\stackrel{12.4}{\Leftrightarrow}$ Any element $\varphi$ in $F_1$ satisfies $(\nabla f)^T\varphi \ge 0$.
2. $d$ is a limiting direction. $\stackrel{12.3.i}{\implies}$ $d \in F_1$
3. $x$ is a local solution. $\stackrel{12.2}{\implies}$ For any limiting direction $d$, we have that $(\nabla f)^Td \ge 0$.

From (2) we have that the set of limiting directions is a subset of $F_1$. From (1) we have that the stationarity of the Lagrangian is equivalent to the non-negativity of $(\nabla f)^Td$ for any element of $F_1$.

According to (3) I'd say the necessary condition for $x$ being a solution is given by the stationarity of the Lagrangian alone, since the proofs of Lemma 12.4, Lemma 12.3.i and Theorem 12.2 do not depend on LICQ (if I got it correctly).

Thank you!

Max

The example $$\min \quad x \quad \text{s.t.} \quad x^2 \le 0,\, x\in\mathbb R$$ shows that constraint qualifications are indeed necessary, as the Lagrangian isn't stationary at the optimum.

• Write down the stationary condition for the Lagrangian and you will see that they are not satisfied. – user251257 Jul 3 '15 at 2:43
• One liners rarely make good Answers. It's up to you as the one attempting an Answer to present a "curated" explanation of the ideas. See the Help Center FAQ for more about how to answer well. – hardmath Jul 3 '15 at 2:46
• I thought you might want to think about it yourself first. next time I will call it hints. – user251257 Jul 3 '15 at 2:48
• I'm not the OP of the Question. I appreciate that you wish me to think about the Question for myself, and I will do so. Hints, where not specifically requested by the OP, are best presented as Comments. – hardmath Jul 3 '15 at 2:50
• 1) $F_1$ is the tangent cone of the linearized problem of original problem. $F_1$ as you stated here is in general not the tangent cone of the original problem. 2) For the example I stated, $F_1=\mathbb R$ and the tangent cone is $\{0\}$, as the only feasible point is $0$. 3) This affect your question, as the example shows stationary of the Lagrangian along is not necessary for a minimum. 4) There are other constraint qualifications, strictly weaker than LICQ. See regularity conditions (or constraint qualifications) under en.m.wikipedia.org/wiki/Karush–Kuhn–Tucker_conditions – user251257 Jul 3 '15 at 11:29

(Since my edit proposal was rejected and further comments were discouraged, please consider my following extension to user251257's answer)

Some remarks to the answer from the author of the question:

My claim was that the stationarity of the Lagrangian alone is the necessary condition for a point to be a local solution of the optimization problem:

$$x^* \text{ is a local solution} \implies (\exists \lambda) \: \nabla \mathcal{L}(x^*) = 0,$$

which is equivalent to

$$(\forall \lambda) \nabla \mathcal{L}(x^*) \neq 0 \implies x^* \text{ is not a local solution}.$$

Now user251257 has given an example that shows

$$(\forall \lambda) \nabla \mathcal{L}(x^*) \neq 0 \wedge x^* \text{ is a local solution},$$

which is the exact negation of the above given (claimed) implication.