3
$\begingroup$

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

enter image description here

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

Read comments if you wanna understand why he got it.

$\endgroup$
1
+100
$\begingroup$

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.

$\endgroup$
11
  • $\begingroup$ Dosnt the saddle point also have gradient zero? $\endgroup$
    – user123124
    Dec 28 '17 at 12:43
  • $\begingroup$ @user1 Yes, it is the Lagrangian being minimized that is not necessary. It is necessary for a minimum to be a critical point of the Lagrangian, at least if f and g are sufficiently smooth. $\endgroup$
    – Ian
    Dec 28 '17 at 12:46
  • $\begingroup$ oh, you/he mean it could happen that $x$ is min of $f$ but then a max or saddle of $\ell$ ? $\endgroup$
    – user123124
    Dec 28 '17 at 12:47
  • $\begingroup$ @user1 That's right (though it will have to be a saddle, never a max). $\endgroup$
    – Ian
    Dec 28 '17 at 12:57
  • $\begingroup$ alright thanks. I dont think thats clear from what he writes. He says that the gradiant of the Lagrianian need not to be zero as far as I understand. He donst mention minimum. $\endgroup$
    – user123124
    Dec 28 '17 at 12:59
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ So does this resolve all the questions that you originally had in a satisfactory manner? $\endgroup$
    – Qmechanic
    Jan 4 '18 at 19:44
  • $\begingroup$ @Qmechanic yes. Your answer and interpretation was also a possiblity tho that was really confusing thats why I emailed the author. $\endgroup$
    – user123124
    Jan 5 '18 at 7:00

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.