Discontinuity of a constraint in Lagrange Method

[kostoglotov]

Homework Statement

My question is quite specific, but I will include the entire question as laid out in the text

Consider the problem of minimizing the function f(x,y) = x on the curve y^2 + x^4 -x^3 = 0 (a piriform).

(a) Try using Lagrange Multipliers to solve the problem

(b) Show that the minimum value is f(0,0) = 0 but the Lagrange condition $\nabla f(0,0) = \lambda \nabla g(0,0)$ is not satisfied for any value of $\lambda$

(c) Explain why Lagrange Multipliers fail to find the minimum values in this case

Homework Equations

The Attempt at a Solution

[/B]
I've answered (c) correctly, but I'm not happy with my own answer, because I don't really understand why it's correct.

I arrived at the answer by plotting f(x,y) = x in Matlab with contour curves of the constraint and then zoomed in on the contour curve where it equals 0.

I got this:

It's hard to see, but where that red ring is, is (0,0,0), which is the constrained min of f(x,y). So I can see graphically that my constraint is discontinuous at (0,0).

The solutions manual to the text gives the answer as "$\nabla g(0,0) = 0$ and one of the conditions of the Lagrange method is that $\nabla g(x,y) \neq 0$".

Ok, so a condition of the method is that the grad vector of the constraint not be a zero vector. But why?

I tried solving the general form of the constraint as a limit as (x,y) approach (0,0) but couldn't get an answer. Yet I can clearly see on the graph that the constraint as a level curve at g(x,y) = 0 is discontinuous at (0,0).

If I hadn't had Matlab available, I wouldn't have been able to answer this question. How could I have approached it analytically?

 

[Ray Vickson]

Homework Statement

My question is quite specific, but I will include the entire question as laid out in the text

Consider the problem of minimizing the function f(x,y) = x on the curve y^2 + x^4 -x^3 = 0 (a piriform).

(a) Try using Lagrange Multipliers to solve the problem

(b) Show that the minimum value is f(0,0) = 0 but the Lagrange condition $\nabla f(0,0) = \lambda \nabla g(0,0)$ is not satisfied for any value of $\lambda$

(c) Explain why Lagrange Multipliers fail to find the minimum values in this case

Homework Equations

The Attempt at a Solution

[/B]
I've answered (c) correctly, but I'm not happy with my own answer, because I don't really understand why it's correct.

I arrived at the answer by plotting f(x,y) = x in Matlab with contour curves of the constraint and then zoomed in on the contour curve where it equals 0.

I got this:

It's hard to see, but where that red ring is, is (0,0,0), which is the constrained min of f(x,y). So I can see graphically that my constraint is discontinuous at (0,0).

The solutions manual to the text gives the answer as "$\nabla g(0,0) = 0$ and one of the conditions of the Lagrange method is that $\nabla g(x,y) \neq 0$".

Ok, so a condition of the method is that the grad vector of the constraint not be a zero vector. But why?

I tried solving the general form of the constraint as a limit as (x,y) approach (0,0) but couldn't get an answer. Yet I can clearly see on the graph that the constraint as a level curve at g(x,y) = 0 is discontinuous at (0,0).

If I hadn't had Matlab available, I wouldn't have been able to answer this question. How could I have approached it analytically?

In order for the Lagrange multiplier method be a provably valid necessary (not sufficient) condition for a max or min of $f(x,y)$ at $(x_0,y_0)$, it is necessary to satisfy some type of constraint qualification at that point. There are several types, but the simplest and most "computable" qualification is that the gradient vectors of the constraint functions be linearly independent at there. For a single constraint $g(x_1, x_2, \ldots, x_n) = 0$ that means that $\nabla g \neq \vec{0}$ at the point $p_0 = (x_{10}, x_{20}, \ldots , x_{n0})$.

If you do not have a constraint qualification, the Lagrange multiplier rule may, or may not hold; it just cannot be guaranteed by a theorem.

Basically, if you have a nonzero gradient, you can think of solving for one of the variables in terms of the others in a neighborhood of your "optimum" $p_0$. So, eg,, if $g_1 \neq 0$ (where $g_i = \partial g/ \partial x_i |_{p_0}$) then along the constraint $g = 0$ we have
$$dx_1 = -\frac{g_2}{g_1}\, dx_2 - \ldots - \frac{g_n}{g_1}\, dx_n$$
so (with $f_i = \partial f/ \partial x_i |_{p_0}$) we have
$$df(\vec{x})|_{\vec{x} = p_0} = f_1\, dx_1 + f_2 \, dx_2 + \cdots + f_n \, dx_n \\ = \left( f_2 - \frac{f_1}{g_1} g_2 \right) \,dx_2 + \cdots + \left(f_n - \frac{f_1}{g_1} g_n \right)\, dx_n \\ = (f_2 - \lambda g_2)\, dx_2 + \cdots + (f_n - \lambda g_n)\, dx_n$$
where $\lambda = f_1 / g_1$. Now, in a neighborhood of $p_0$ we can regard the variables $x_2, \ldots, x_n$ as independent, so we need the above $df = 0$. Those give components $2, \ldots, n$ of the Lagrange conditions. Component 1 holds as well, since we can re-write the definition of $\lambda$ in the form $f_1 - \lambda g_1 = 0$.

Note that there is more involved here than just the "geometry" of the constraint set; it matters how what geometrical object is represented. For example, take the problem
$$\min x^2 + y^2, \;\; \text{subject to } \; \; x + y = 1.$$
The obvious solution is at (1/2,1/2), and the Lagrange multiplier rule holds.

Now suppose that instead of representing the line as $x+y-1 = 0$ we (stupidly) represent it as $g_1(x,y) = (x+y-1)^2 = 0$. We get exactly the same $(x,y)$ point set in both cases, but now the problem
$$\min x^2 + y^2, \;\ \text{subject to} \;\ (x+y-1)^2 = 0$$
fails to satisfy the Lagrange multiplier rule. At the optimum (1/2,1/2) there is NO Lagrange multiplier $\lambda$.

 

[kostoglotov]

Does the constraint being discontinuous at a point have anything to do with being unable to solve the system of equations at that point?

I can see the system of equations and understand this much

$$1 = \lambda (4x^3-3x^2)...1)$$
$$0 = \lambda 2y...2)$$
$$y^2+x^4-x^3 = 0...3)$$

dividing eqn 2 by eqn 1 $0 = \frac{2y}{4x^3-3x^2}, y = 0$

y = 0 into 3) $0^2 + x^4-x^3 = 0, x^4 = x^3, x = 1, \lambda = 1$

edit: wait...$\lambda$ could equal anything couldn't it?

Following this, evaluating the Lagrange method at (0,0) yields

$$1 = \lambda \times 0$$
$$0 = \lambda \times 0$$

And of course this system of equations cannot exist as the first isn't possible, and the second is true for all $\lambda$

The max seems fine though, as (1,0) satisfies the constraint, and gives f(x,y) = 1.

This is hard to think about...I'll end it with a simpler question.

Am I right in thinking that in this instance, $\nabla g = 0$ is a result of the discontinuity, but that in general, other things besides discontinuities could also cause $\nabla g = 0$, and that I shouldn't worry too much about the discontinuity, and just focus on the fact that the system of equations won't resolve when $\nabla g = 0$...?

 

[Ray Vickson]

Does the constraint being discontinuous at a point have anything to do with being unable to solve the system of equations at that point?

I can see the system of equations and understand this much

$$1 = \lambda (4x^3-3x^2)...1)$$
$$0 = \lambda 2y...2)$$
$$y^2+x^4-x^3 = 0...3)$$

dividing eqn 2 by eqn 1 $0 = \frac{2y}{4x^3-3x^2}, y = 0$

y = 0 into 3) $0^2 + x^4-x^3 = 0, x^4 = x^3, x = 1, \lambda = 1$

edit: wait...$\lambda$ could equal anything couldn't it?

Following this, evaluating the Lagrange method at (0,0) yields

$$1 = \lambda \times 0$$
$$0 = \lambda \times 0$$

And of course this system of equations cannot exist as the first isn't possible, and the second is true for all $\lambda$

The max seems fine though, as (1,0) satisfies the constraint, and gives f(x,y) = 1.

This is hard to think about...I'll end it with a simpler question.

Am I right in thinking that in this instance, $\nabla g = 0$ is a result of the discontinuity, but that in general, other things besides discontinuities could also cause $\nabla g = 0$, and that I shouldn't worry too much about the discontinuity, and just focus on the fact that the system of equations won't resolve when $\nabla g = 0$...?

You must be using the word "discontinuity" if a different way from my understanding, because there is nothing at all "discontinuous" about the function $g(x,y) = y^2 + x^4-xx^3$ near $(x,y) = (0,0)$. In fact, $g$ has continuous partial derivatives of all orders at (0,0) or at any other point.

It is true that the feasible set comes to a sharp point at (0,0). Is that what you mean?

And, if you go back and read my response completely, you will see that I gave you an example where the constraint qualification fails but there is nothing like your "discontinuity" at all---nothing like a constraint set coming to a point, or anything similar.

Anyway, I answered your question as best I knew how: the constraint qualification fails at (0,0), so the Lagrange multiplier method could fail. In this case, it fails, indeed.

 

[kostoglotov]

It is true that the feasible set comes to a sharp point at (0,0). Is that what you mean?

It looked like a cusp discontinuity to me.

 

[kostoglotov]

Sorry but I have to clear this up, and I was wondering if you could still help me understand.

I was thinking that the contour y^2+x^4-x^3 = 0 has a cusp discontinuity at (0,0).

A WolframAlpha graph shows something similar: http://www.wolframalpha.com/input/?i=y^2+++x^4-x^3+=+0

I know that's just a contour, a level curve, and not the f(x,y) function as a surface, but surely if one of the level curves looks like that, then won't the surface have a bit of a "spine" in it where a tangent plane can't be put tangent to the surface?? If so, wouldn't that make it discontinuous?

 

[Ray Vickson]

Sorry but I have to clear this up, and I was wondering if you could still help me understand.

I was thinking that the contour y^2+x^4-x^3 = 0 has a cusp discontinuity at (0,0).

A WolframAlpha graph shows something similar: http://www.wolframalpha.com/input/?i=y^2+++x^4-x^3+=+0

I know that's just a contour, a level curve, and not the f(x,y) function as a surface, but surely if one of the level curves looks like that, then won't the surface have a bit of a "spine" in it where a tangent plane can't be put tangent to the surface?? If so, wouldn't that make it discontinuous?

No, your surface (and your curve) do not have a "discontinuity"---in the technical sense of "continuity" and "discontinuity".The curve could be drawn without lifting your pencil from the paper, which is the poor man's definition of continuity. However, while the curve is continuous it is not smooth, in the sense that the unit tangent vector is not an everywhere continuously-differentiable function of the arc length, due to the kink at (0,0). There is a discontinuity in the tangent vector, not in the curve itself.