can't find global minimizer from Lagrange Multiplier Rule

Question

I have an equality constraint function h and a function f to minimize. \begin{array}{c}{h : \mathbb{R}^{2} \rightarrow \mathbb{R}, (x,y) \mapsto 2 x-y} \\ {f : \mathbb{R}^{2} \rightarrow \mathbb{R},(x, y) \mapsto 100\left(y-x^{2}\right)^{2}+(1-x)^{2}}\end{array} By applying Lagrange Multiplier Rule, only single solution x=1 and y =2 is found to satisfy first order necessary condition. But when I check x=0 and y = 0, it also satisfy equality constraint h and even get smaller function value than solution(x=1 and y=2) from Lagrange Multiplier Rule. Does this mean that we can't rely on Lagrange Multiplier Rule to find global minimizer?

The Solution is as follow:

since $\nabla h(x) \neq 0, \nabla h(x)$ is linear independent and thus every $x \in \mathbb{R}^{2}$ with $h(x)=0$ is a regular point. Assume that $x$ satisfies the necessary first order condition for a local mimizer of $f$ subject to the constraint $h(x)=0 .$ Then

$$ \nabla f(x)+\lambda \nabla h(x)=0 $$

for a λ ∈ R. Because $$ \nabla f(x)=\left(\begin{array}{c}{-400 x\left(y-x^{2}\right)+2 x-2} \\ {200\left(y-x^{2}\right)}\end{array}\right) $$

this implies

$$ 0=\left(\begin{array}{c}{-400 x\left(y-x^{2}\right)+2 x-2+2 \lambda} \\ {200\left(y-x^{2}\right)-\lambda}\end{array}\right) $$

Hence $$ \lambda=200\left(y-x^{2}\right) $$ This implies, together with the previous equation, $$ 0=-2 \lambda x+2 x-2+2 \lambda=2\left(x(1-\lambda)-(1-\lambda)\right) $$ Hence $$ x=1 $$ since $h(x)=0,$ this implies $y=2$

Answer 1

You forgot another possible case. From $$0=2(x(1-\lambda)-(1-\lambda))=2(x-1)(1-\lambda),$$ it does not necessarily follow that $x=1$. Namely, if $\lambda=1$, we can have $x\neq 1$. We then get $$y-x^2=\frac{1}{200},\hspace{0.5cm} 2x-y=0$$ and thus $$x^2+\frac{1}{200}=2x\Leftrightarrow (x-1)^2=\frac{199}{200}\Leftrightarrow x=1\pm\sqrt{\frac{199}{200}}$$ and therefore $$y=2\pm\sqrt{\frac{199}{50}}.$$

Plugging these two pairs of values into $f$ yields (in both cases) a value of $\frac{399}{400}$, which is the global minimizer since $\frac{399}{400}<f(1,2)=100$. This is also smaller than $f(0,0)=1$

Answer 2

For the system of Lagrange equations that you determined,

$$ -400xy \ + \ 400x^3 \ - \ 2 \ + \ 2x \ \ = \ \ 2·\lambda \ \ , \ \ 200y \ - \ 200x^2 \ \ = \ \ -\lambda \ \ , $$

one could also eliminate $ \ \lambda \ $ to yield

$$ -200xy \ + \ 200x^3 \ - \ 1 \ + \ x \ \ = \ \ 200x^2 \ - \ 200y $$ $$ \Rightarrow \ \ 200 \ · \ (x^3 \ - \ x^2 \ + \ y \ - \ xy) \ + \ x \ - \ 1 \ \ = \ \ 0 $$ $$ \Rightarrow \ \ [ \ 200 · (x^2 - y) \ + \ 1 \ ] \ · \ (x - 1) \ \ = \ \ 0 \ \ . $$

Together with the constraint $ \ y \ = \ 2x \ \ , $ the second factor leads to the solution you found, $ \ x = 1 \ , \ y = 2 \ , $ with the function value $ \ f(1,2) \ = \ 100 \ \ . $ The first factor produces the quadratic equation

$$ 200 \ · \ (x^2 - 2x) \ + \ 1 \ = \ 0 \ \ \Rightarrow \ \ 200x^2 \ - \ 400x \ + \ 1 \ = 0 \ \ , $$

which has the pair of solutions given by mxian , $$ \ x \ = \ \frac{400 \ \pm \ \sqrt{(-400)^2 \ - \ 4·200·1}}{2 \ · \ 200} \ \ = \ \ 1 \ \pm \ \frac{\sqrt{400 \ - \ 2}}{400} \ \ = \ \ 1 \ \pm \ \frac{\sqrt{398}}{20} $$ $$ \approx \ \ 0.0025 \ , \ 1.9975 \ \ , \ \ y \ \ = \ \ 2 \ \pm \ \frac{\sqrt{398}}{10} \ \ \approx \ \ 0.005 \ , \ 3.995 \ \ . $$

We can show that these two points are on the same level-curve for the function. It will simplify the writing a bit to use $ \ x = 1 \pm r \ \ , $ for which we have $$ f(1 \pm \ r \ , \ 2 \pm 2r ) \ \ = \ \ 100 \ · \ (2 \pm r \ - \ [1 \pm r]^2)^2 \ + \ (1 \ - \ [1 \pm r])^2 $$ $$ = \ \ 100 \ · \ (2 \ \pm \ 2r \ - \ 1 \ \mp \ 2r \ - \ r^2)^2 \ + \ (\mp r)^2 $$ $$ = \ \ 100 \ · \ (1 \ - \ r^2)^2 \ + \ r^2 \ \ = \ \ 100 \ - \ 199 · r^2 \ + \ 100·r^4 \ \ . $$

With $ \ r^2 \ = \ \frac{ 398 }{20^2} \ \ , $ the function value is then $$ \ 100 \ - \ 199 · \frac{ 2 · 199 }{400} \ + \ 100·\frac{ 2^2 · 199^2 }{400^2} \ \ = \ \ 100 \ - \ \frac{ 2 · 199^2 }{400} \ + \ \frac{199^2 }{400} \ \ = \ \ 100 \ - \ \frac{ 199^2 }{400} $$ $$ = \ \ \frac{100·400 \ - \ 199^2 }{400} \ \ = \ \ \frac{200^2 \ - \ 199^2 }{400} \ \ = \ \ \frac{2·199 \ + \ 1 }{400} \ \ = \ \ \frac{399}{400} \ \ = \ \ 0.9975 \ \ . $$

This is just to fill in a couple of details of what has already been presented.

The level-curves for the function are of some interest. If we had only the first term, $ \ 100 \ · \ (y \ - \ x^2)^2 \ = \ c \ $ would simply be the pair of "parallel" parabolas $ \ y \ = \ x^2 \ \pm \ \frac{\sqrt{c}}{10} \ \ . $ The inclusion of the second term in the function level-curves

$$ 100 \ · \ (y \ - \ x^2)^2 \ + \ (1 \ - \ x)^2 \ \ = \ \ c $$ has the effect of "closing over" the "ends" of the parabolas to produce a closed finite loop with an asymmetry about the $ \ y-$axis. For $ \ c = 100 \ \ $ (shown in the graphs above; the "granularity" is an artifact of the plotter used), these loop-ends occur near $ \ (-9 , 81) \ $ and $ \ (11 , 121) \ \ . $ As $ \ c \ $ decreases, this loop becomes increasingly asymmetrical, ultimately "degenerating" to the point $ \ (1,1) \ $ for $ \ c = 0 \ \ . $ With the constraint line $ \ y = 2x \ $ included in red, we see that $ \ (1,2) \ $ is a tangent point for the level curve $ \ c = 100 \ \ , $ the solution you had found.

For $ \ c \ = \ \frac{399}{400} \ \ , $ the level-curve loop have shrunk and become sufficiently asymmetrical that it now lies entirely to the right of the $ \ y-$ axis. (Again, the "crumbly" appearance of the plot is an artifice.) The close-up graphs show mxian's solutions on the constraint line. This loop passes very close to, but not through, the origin.