1
$\begingroup$

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

|cite|improve this question
$\endgroup$
0
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Write down the stationary condition for the Lagrangian and you will see that they are not satisfied. $\endgroup$ – user251257 Jul 3 '15 at 2:43
  • 1
    $\begingroup$ 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. $\endgroup$ – hardmath Jul 3 '15 at 2:46
  • $\begingroup$ I thought you might want to think about it yourself first. next time I will call it hints. $\endgroup$ – user251257 Jul 3 '15 at 2:48
  • $\begingroup$ 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. $\endgroup$ – hardmath Jul 3 '15 at 2:50
  • 1
    $\begingroup$ 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 $\endgroup$ – user251257 Jul 3 '15 at 11:29
2
$\begingroup$

(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.

|cite|improve this answer
$\endgroup$

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.