Consider the problem to minimize $x^2 + y^2$ on the constraint $(x-1)^3 - y^2 = 0$. Geometrically it is clear that $(1, 0)$ is the solution. However, we note that $\nabla f (1, 0) = (1, 0)^T$ and $\nabla g(1, 0) = \bf{0}$. Thus, we cannot find any $\lambda$ at the optimum point so that $\nabla f(1, 0) = \lambda \nabla g(1, 0)$. Can any one please help me out to know why this happens?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ So, solve $\nabla g = \lambda \times \nabla f$ instead. You just get $\lambda = 0$ which is perfectly consistent with proportionality. $\endgroup$– luluCommented Nov 2, 2017 at 11:52
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
The fact is that you are optimizing over a manifold which is not smooth. If you draw $M=\{(x,y)\in \mathbb{R}^2\ |\ (x-1)^3 = y^2\}$ you will notice that there is a cusp at $(1,0)$. If you consider a point of $M$ that is not the cusp there is a well defined tangent space and a normal space to $M$ at $x$. Searching for Lagrange multipliers geometrically means that you are requiring the gradient $\nabla f(x)$ to belong to the normal space of $M$ at $x$ (the normal space is generated by $\nabla g(x))$. This is because if the gradient has a component in the tangent space then you can make decrease the function. Notice that at points that are not the cusp, the normal and the tangent space are always linear subspaces of dimension $1$.
The problem is that at the cusp the set of admissible directions do not constitute a tangent space (they do not constitute a linear subspace). So you cannot simply require that the gradient do not have any component in this tangent space as you would do for other points.
So you need to split your problem in two: find the minimum of $f$ over $M\setminus \{(0,1)\}$ (and you will find that there is no minimum there) and the minimum of $f$ over $\{(0,1)\}$ which is $f(0,1)$ since the set is a singleton, to obtain the global minimum you just take the minimum of the two minimum. In this way you have reduced to two optimization problems over two smooth manifolds.
$\begingroup$
$\endgroup$
Another way way to construct this kind of situation (without also making the problem 100% trivial) is to consider a constraint like $(x^2-1)^2+(y^2-1)^2=0$. In this case, the constraint set just consists of finitely many points. Thus the Lagrange condition no longer really makes sense, because the "tangent plane" at any point in the constraint set is the whole space, and so the normal set to this tangent plane is just the zero vector.
Nonetheless the Lagrange condition is technically still correct if you move the $\lambda$ over to $\nabla f$ instead, i.e. write $\lambda \nabla f = \nabla g$. Then since $\nabla g = 0$ on the constraint set, you can take $\lambda =0 $ in this formulation. Geometrically the significance is still the same: $\nabla f$ and $\nabla g$ are parallel because the zero vector is parallel to every vector. This geometric relationship between the gradients is the main idea in Lagrange multipliers.
A more interesting way for this to happen is to consider optimization on a polygon. Lagrange multipliers will perhaps find extrema on the edges, but it will fail to detect extrema at the vertices even if they exist.
Consider for instance extremizing $(x-1)^2+(y-1)^2$ on the square of side length $2$ centered at the origin. The extrema are of course at $(1,1)$ and $(-1,-1)$. Lagrange asks for $(0,y-1)$ to be parallel to $(1,0)$, or $(-2,y-1)$ to be parallel to $(-1,0)$, or $(x-1,0)$ to be parallel to $(0,1)$, or $(x-1,-2)$ to be parallel to $(0,-1)$. The second one happens at $(-1,1)$ (finding what turns out to be a saddle). The fourth one happens at $(1,-1)$ (finding what turns out to also be a saddle). The first and third ones never happen.
