Can Lagrange Multipliers Avoid Meaningless Critical Points in Optimization?

[Cyrus]

For the proof of lagrange multipliers, it is based on the assumption that the function you are optimizing, f(x,y,z), takes on an extreme value at the point (x0,y0,z0), and that any curve that passes through this point has the tangent vector perpendicular to the gradient vector. That seems fair enough. But it is possible to have more than one point be the extreme value. In which case you could make a curve that passes through both extreme value points. Even if this is the case, I don't think it posses any problems, because when you work it out, you still get the derivative equal to zero at the first extreme value your concerned with. But what about critical points that are meaningless. Like in the case of x^3, x=0 would be an extreme value, but its not a max or a min. Likewise, there might be an extreme value on your constrained optimization function that acts like x^3 near zero. The function can increase, slow down, stop, then decrease on the surface near that point. So if you use lagranges method, you would find that point, and plug it into the constrained equation, and find a value for f(x,y,z) at that point. Is there something to this that I am missing that allows for lagranges method to avoid this pitfall?

 

[matt grime]

work out an example, see what happens.

eg try maximizing x^2+y^2 subject to the conditions y=x^3+1, this is a case where you have one of your points of inflection...

 

[Cyrus]

hmmm, I did your example. If I do it by direct substitution I find three points, x=0, y=1; x=-.8462932 y=.39387; x=-.347794 y=.957930606. This agrees with the graph on matlab. x=0 is a local min, x=-.8462932 is an absolute min, x=-.347794 is a local max. When I use lagranges method, I can only find two solutions. I can't get the solution for x=0, which is odd. I did get the local max value, so I should be able to get the local min value as well.

Edit: Never mind I got the solution of x=0, y=1 via lagrange as well now too.

Ok, I attached a graph to show you my question a little better. The blue graph is that of the function given the restriction. You think I said that the critical point had to do with the constraint equation, i.e. y=x^3+1. Thats not what I am saying at all. What I am saying is, look at the red line. I added that myself. Let's say given SOME constraint equation, it looks like the blue curve, plus the red curve. That point that WAS a maximum, is now going to be an inflection point of the equation under constraint. Since it IS a CRITICAL point, the derivative is going to equal zero there. So if you do lagranges method or direct substitution, its going to spit that value at you. And you will plug it into the function to find the value at that point. But without a visual aid, you might not know if that is a max or a min. See what I mean?

 

[EnumaElish]

I guess you should be checking some 2nd-order condition (e.g. strict concavity or convexity) at each extremum that you find.

 

[Cyrus]

I think so too, I am trying to think of a proper equation and constraint equation that would prove my point, but I am drawing a blank. I want the equation with the constraint to look like a cubic function. That would prove my point.

Ah, here is a simple one. Let's say the equation of the function were optimizing, after giving it SOME constraint, takes on the form, x^6+x^3.
This has two critical points, an absolute max, and an inflectoin point at 0,0. If I were to use lagranges method and get 0,0 as a possible anwser, then that's enough to show that lagrange might possibly spit out values that make no sense, if you don't double check them graphically.

Ah perfect I've come up with what I am talking about.

Take F(x,y) = x^6 + y
the constraint g(x,y)= y-x^3 = 1

You can do a direct substitution easily and find that it has two critical values, one at an abs min, one at an inflection point.

x=0 y=1 is the inflection point, and x=-.7937022 y=.75 is the abs min.


HA! HA ! HA! Looky what lagrange tells us. It says that x=0 y=1 and x=(-3/6)^(1/3)= -.79370526. So it proves exactly my point. The gradient IS perpendicular to the CRITICAL points of the function under constraint. In the proof of lagranges method, they say, "suppose f has an EXTREME value at a point P(x0,y0,z0) on the surface S and..." Its not that it has to be EXTREME, it just has to be CRITICAL. You can use the function I made up, use lagrange, and get a bogus anwser. Yeah, that's an inflection point, lagrange will spit out an anwser for you, and you can plug it in and get a value, but so what. Its not even a local min or max, none the less absolute. Without a graph, or pluging in values NEAR that point, I don't see how you can judge if its a valid anwser or not. Does any of what I am saying make any sense to anyone?

To be more sensible, even if there is one of these critical points, we know that one of two things can happen. The function can continue unbounded in one direction, and be bound in the other, as in the this case when you graph it. Which means that there WILL be at least ONE value that WILL be, at least, a local max or min. The time caution should be used is if lagrange gives you only one critical value, because that value may be an inflection point only. In that case, there is no local or absolute max /min.

This seems to make good sense, because an inflection point would be another place where the functiong g(x,y) would be tangent to f(x,y) for two particular level curves. And it would make sense if this extends into functions of three variables for a saddle point.

 

[matt grime]

wait a minute, you didn't realize that a solution via lagrangian multipliers is not necessarily a maximum/minimum at all? Surely that is one of the first things they tell you, that it is not a sufficient condition. (the example I gavve has no maximum by the way, that was what you were supposed to realize).

 

[Cyrus]

I know it has no maxium. Actually, stewart does not say outright in the proof that it might not be a max/min. In his proof, he bases it soley on the fact that the point where the gradients are parallel is a Extreme point. Then I realized that critical points such as inflection points would have the same effect on the gradient, so his proof could have been extended to say the gradients are parallel at any CRITICAL curve, no matter what curve you choose to use.

 

[matt grime]

fix notation: optimize f subject to constrant g.

there is nothing that states that where grad(f) and grad(g) are parralel has to be any kind of local maximum for either function. It amy, it may not, it is immaterial.

now, apart from inventing the term "critical curve" what are you getting at, cos I'm getting lost again.?

 

[Cyrus]

Typo, should have wrote critical point. "what I am getting at" is the proof limits itself to extreme values, but its more than just extreme values where lagrange method hold true, that the gradients are parallel.

 

[matt grime]

but its more than just extreme values where lagrange method hold true, that the gradients are parallel.

Yes, obviously, as Stewart states (if i recall correclty from teaching from it 4, no 5, years ago), and as we can easily visualize. as i said before being a "solution" found by lagrange multipliers is not a sufficient condition (nor even necessary) for an extremal value.

 

[Cyrus]

As always, thanks for your help matt. I do need to go back and work on that earlier thread about the function F(x,y,z)= f(x,y)-z. I am still having trouble with it. Please remember I am not a math major, I am just trying to fully understand these proofs for the fun of it. ;-)

 

[matt grime]

Do you have a good visualization of what is goin on with lagrange multipliers? the easiest description is as follows. Suppose that we want to maximize f(x,y,z) with constraint that x,y,z lie on the surface g(x,y,z)=0 which are

Now, imagine, for argument's sake that f(x,y,z)=x^2+y^2+z^2. now the way to imagine it is to hink of a balloon being blown up, this represents the f, and the first time it touches the surface g=0 is our minimal point (it is the smallest value of f lyingon the surface). This shows why lagrange multipliers work when they work. there is nothing to stop us supposing that if we blow up the balloon more we get another point where they touch again (and it cannot be minimal).