On necessary conditions for constrained optimization in $\mathbb{R}^{n}$

Question

I am confused by a what Liberzon writes in his book on optimal control on page 12 and beginning of 13 regarding necessary conditions for optimality.

He starts of by showing the first order condition for constrained optimality of $f$ w.r.t $h$ i.e

If $x$ is constrained minima of $f$ then $\nabla f(x)+ \lambda\nabla h(x)=0$ for some $\lambda$.

To make this more explicit he defines the augmented cost functional,

$\ell(x,\lambda)=\nabla f(x)+ \lambda\nabla h(x)$.

He then shows that if $x$ is constrained minima and $\lambda$ is its Lagrange multiplier then $\nabla \ell=0$ at this point. All good and well so far.

Next he argues,

If $(x,\lambda)$ is a minima for $\ell$ then $h(x)=0$ and subject to these constraints $x$ also minimize $f$ i.e the gradient of $\ell$ is zero.

But then he stresses that this is not a necessary condition for optimality if we only assume that $x$ is a constrained minima of $f$. I don't understand what he means here. What situation is he referring to? And what does he wanna say?

He just showed that there always are multipliers for any constrained minima and hence we should be able to repeat one of his above arguments to get that the gradient is zero of $\ell$. But this can't be it. Is he referring to a situation where he don't wanna assume anything about $\lambda$?.

Does anyone understand this?

His book is free online http://liberzon.csl.illinois.edu/teaching/cvoc.pdf

Also here is the text

OBSERVE THAT THE BOUNTY IS NOT AWARDED TO THE RIGHT ANSWER!

Read comments if you wanna understand why he got it.

Answer 1

I emailed the author. What he wants to say it that the necessity does not follow from the argument with the agumented cost BUT it is still true and it does follow from the first argument.

Answer 2

In nice enough geometry the basic Lagrange condition that $\nabla f$ and $\nabla g$ are parallel is necessary. Specifically, if the gradient of f and the constraint are not parallel then there is a vector v perpendicular to the gradient of g with $v^T \nabla f<0$. Going a sufficiently small distance in the direction of v and then projecting to the constraint surface then gives a point arbitrarily close to the initial point and on the surface with smaller objective function. Problems arise only at things like corners on the constraint surface.

However the point in the augmented space does not need to minimize the Lagrangian in general, it could be a saddle point. Some convexity type assumptions are needed to ensure that the Lagrangian is actually minimized.

Answer 3

OP got a point. There seems to be a typo. The word necessary should be replaced with sufficient in 2 place in the first paragraph of p. 16 in Ref. 1, or equivalently, the second paragraph of p. 13 in Ref. 2.

This conclusion is supported by at least 2 facts:

1. The author mentions a handful of times in subsection 1.2.2 that it is assumed that $x^{\ast}$ is a regular point, i.e. $\nabla h_i(x^{\ast})$, $i=1, \ldots m$, are assumed linearly independent. In a regular point, eq. (1.27) in Ref. 1 and eq. (1.28) in Ref. 2 are indeed necessary but not sufficient conditions.

2. Also the next paragraph

   "Even though the condition in terms of Lagrange multipliers is only necessary and not sufficient..."

   fits well with this typo interpretation. See also this Math.SE post for an illuminating example.

References:

1. D. Liberzon, Calculus of Variations and Optimal Control Theory: A Concise Introduction, 2012.

2. Preprint version of Ref. 1. A PDF file is available here from the author's homepage.