Please can someone help me with the follwoing optimisation: Minimize $-x+y$ subject to $0 \leq x \leq a$ and $0 \leq y \leq 1$ and $x^2 \leq y$.
I am not sure how to deal with inequality constraints. Do I still make the Lagrangian: $$L(x,y,\lambda_1, \lambda_2, \lambda_3) = -x+y+ \lambda_1(x^2-y) + \lambda_2(x-a) + \lambda_3(y-1)$$ and then find the derivatives and make them equal 0? I am not sure what to do.
I'll try to solve it using an example to make it clearer. We'll solve the same problem, but I'll use some value for $a$. Let it be $a = \frac 12$. now we have the following conditions:
$$f(x,y) = y-x$$ $$g(x) = x - \frac 12 \le 0$$ $$h(y) = y - 1 \le 0$$ $$j(x,y) = x^2 - y \le 0$$
Now the Lagrangian looks like:
$$F(x,y,\lambda,\lambda_1, \lambda_2) = y-x + \lambda(\frac 12 - x) + \lambda_1(1-y) + \lambda_2(y-x^2)$$
Now we take partial derivatives:
$$F_x = -1 - \lambda - 2\lambda_2x = 0$$ $$F_y = 1 - \lambda_1 + \lambda_2 = 0$$
We know that the last three terms(constrains) must equal $0$ and gradients $\lambda, \lambda_1, \lambda_2$ must have non-negative value. Now we have 8 distinctive cases:
Case 1: $\lambda = \lambda_1 = \lambda_2 = 0$
This case is contradiction, beacuse substituting back into the partial derivatives we'll get $-1 = 0$ and $1=0$, which is impossible.
Case 2: $\lambda = \lambda_1 = y-x^2 = 0$
This would imply that $\lambda_2 = -1$. Now substituting into the first partial derivative we have;
$$-1 + 2x = 0$$ $$2x = 1$$ $$x = \frac 12$$
This implies that $y = \frac 14$
So now we have one potential solution $(x,y) = (\frac 12, \frac 14)$
Case 3: $\lambda = 1-y = \lambda_2 = 0$
Also this case is contradiction, because in the first partial derivative we'll end up with $-1 = 0$
Case 4: $\lambda = 1-y = y-x^2 = 0$
Now we have that $y=1 = x^2$, beacuse only positive values are allowed, we have $x=1$, but from the constrain $x \le \frac 12$ so this case doesn't provide a solution.
Case 5: $\frac 12 - x = \lambda_1 = \lambda_2 = 0$
This case leads to contradiction in the second partial derivative.
Case 6: $\frac 12 - x = \lambda_1 = x^2-y = 0$
This implies that $x = \frac 12$, implying that $y = \frac 14$. But we've already obtained this solution, so there aren't new solution in this case.
Case 7: $\frac 12 - x = y-1 = \lambda_2 = 0$
This implies that $x= \frac 12$ and $y=1$. This solution satisfy all conditions so we obtatin another solution: $(x,y) = (\frac 12, 1)$
Case 8: $\frac 12 - x = y-1 = x^2-y = 0$
This case doesn't provide a solution, because it's impossible all three conditions to be fulfilled at same time.
Plugging the two solution into the initial function we have:
$$f(\frac 12, \frac 14) =\frac14 - \frac12 = -\frac 14$$ $$f(\frac 12, 1) = 1 - \frac 12 = \frac 12$$
The first one is the global minima, while the second is a saddle point.
If you check the boundary, you'll get another few solution, but you'll just find a few saddle point and the maxima, that occurs at $f(0,1) = 1 - 0 = 1$
An approach using analytic geometry.
Problem: Minimize $ - x +y $ , $x \in [0,a]$, $a \gt 0$, $y \in [0,1] $, subject to $x^2 \leq y$ .
1) $a \geq 1$.
Consider the parabola $y = x^2 $in the first quadrant. Of interest are $y -$ values on or above the parabola, where $x \in [0,1 ]$ ( since $y(1) =1$ ).
Now look at the family of straight lines $y = x + C$. Each line $y$ has slope $m = 1$ and $y$ - intercept $C$.
A tangent to the parabola has a slope $y'(x) = 2x$.
Choose: $x = 1/2$, then $y = 1/4$, and $y'(1/2) = 1$.
At the above point a member of the family $y = x + C$ touches the parabola.
$C = y - x = 1/4 - 1/2 = - 1/4$.
Any member of the family $y = x + C$ with smaller $C$ will be parallel, pass below, and have no common points with our area of interest.
$Min (C) = min (y - x) = - 1/4$ .
2) $a \geq 1/2$.
The above reasoning can be repeated to find
$Min (C) = - 1/4$.
3) $a \lt 1/2$.
We consider the area of interest, on or above the parabola $y = x^2$ where $x \in [0,a]$ and $y \in [0,1]$.
Choose the boundary point $x = a$, then $y = a^2$.
We find C for a line that passes through this point.
$C = y - x = a^2 - a = (a - 1/2)^2 - 1/4$.
Reasoning for our choice:
This line $y = x + (a - 1/2)^2 - 1/4$ has one common point with the parabola, the boundary point. No other point is common to both curves. (Note also: $f'(x) \lt 1$ for $x \in [0,a]$)
Any smaller choice for $C$, I.e. moving south on the $y -$axis, will result in a line parallel to the above, below, that does not intersect $y = x^2$ for $x \in [0,a]$.
$Finally :$
$Min (C) = min (y - x) = (a - 1/2)^2 - 1/4$.
Comments welcome.
Ok, here's what you do, you use Lagrange Multipliers to solve it on the BOUNDARIES of the allowed region, and you search for critical points (minima or maxima) within the interior of the region, not near its boundary. You compare all the distinct solutions and you find the one that optimizes it the most. If the point you're looking for is in the interior, it will be a critical point, and if it's on the boundary, it will be found using Lagrange Multipliers, so you have to do both to cover all your bases. Just remember, you have several distinct regions you need to test over for the boundary, namely you need to test along the line x=0 and y between 0 and 1, you need to test the line x=a for y between 0 and 1, etcetera. A pain to be sure. And then, finally, you have to test the CORNERS of the region too, just to be absolutely certain that the minimum isn't on one of the corners. Actually, since the function you're trying to minimize is linear, I can all but guarantee you the minimum WILL be one of the corners, if not for that x^2
I think Stefan4024 made a mistake in his answer. I shall hence write my own solution and compare the result and argument for why I believe the provided answer is wrong.
First, we have that we must minimize:
$f_1(x,y)=-x+y$
Let's convert it to a maximization problem by multiplying by -1:
$f_2(x,y)=x-y$
We now specify the constraints in the generic form:
${h_j(x,y)}\leq{0}$
Which gives:
$-a\le h_1(x,y)=x-a\leq{0}$
$-1\le h_2(x,y)=y-1\leq{0}$
$-y\le h_3(x,y)=x^2-y\leq{0}$
As for the lagrange equation:
$\nabla{f_2(x,y)}=\sum_i{\lambda_i\cdot\nabla{g_i(x,y)}}+\sum_j{\mu_j\cdot\nabla{h_j(x,y)}}$
Since we have no fixed constraints, we can omit g's sum entirely such that:
$\nabla{f_2(x,y)}=\sum_j{\mu_j\cdot\nabla{h_j(x,y)}} \Rightarrow (1,-1)=\mu_1(1,0)+\mu_2(0,1)+\mu_3(2x,-1)$
The second last step in formulating the problem is to state that: $\forall{j},\mu_j\ge0$. Here is where I think the Stefan4024 answer fails, as I think his answer has no consistent usage of this specifier; and thus an invalid answer comes up. I question the validity of the assertion that it is a saddle point, as the Hessian matrix shows that it is indeterminate (0) at that point. The invalidity can be observed in Case 2, where $\lambda_2 = -1$.
The last step will be to formulate the tightness of inequalities through:
$\forall j, \mu_j\cdot h_j(x,y) = 0$
Which implies that either of the factors are 0.
Here are all equation/inequalities for a quick reference.
Case 1: $\mu_1 = \mu_2 = \mu_3 = 0$
Plugging the values into equation 2, we observe that -1 = 0; such that this case is a contradiction.
Case 2: $\mu_1=\mu_2=x^2-y=0$
From equation 2 we get $1=\mu_3$, such that substituting in equation 1 results in $\frac{1}{2}=x$.
Since $y=±\sqrt{x}$ according to $x^2-y=0$, we observe from eq. 3.2 that $0\le y$, such that y can only be $\frac{1}{4}$.
Point: $(2^{-1}, 4^{-1})$
Case 3: $\mu_1=y-1=\mu_3=0$
We observe that equation 1 grants: 1=0, which invalidates case 3.
Case 4: $\mu_1=y-1=x^2-y=0$
From equation 1 we get: $\mu_3=\frac{1}{2x}$, by substituting in eq. 2, we get: $\mu_2=\frac{1}{2x}-1$.
Since $y=1, x=±1$, we get from the above that $\mu_2=\frac{1}{2x}-1$, which only results in a negative result in either case, in which case $\mu_2 \lt 0$, which invalidates this case.
Case 5: $x-a=\mu_2=\mu_3=0$
From equation 2 we observe that -1 = 0, which contradicts this case.
Case 6: $x-a=\mu_2=x^2-y=0$
From equation 2 we get $\mu_3=1$, which we plug into the first, giving:
$1/2=x$. Since $y=1, x^2=y$, then x must be ±1, which contradicts that it must be 1/2.
Case 7: $x-a=y-1=\mu_3=0$
Pluggin into equation 2, we get $\mu_2=-1$ which is invalid.
Case 8: $x-a=y-1=x^2-y=0$
$x=a, y=1, y=x^2 \Rightarrow 1=a^2 \Rightarrow a=±1$. From our boundaries, we observe that a is always larger than 0, thus, a = 1.
Plugging the values into equation 1: $1=\mu_1+\mu_3\cdot2$, we observe that our system of equations is unsolvable, so this answer is invalidated.
We have acquired only 1 point: A = $(1/2, 1/4)$
$f_1($**A**$) = -1/4$
We can easily observe that this answer is only valid for $a \ge 1/2$. As stated before, Stefan has a "saddle point" on this linear curve at (1,1), which appears invalid to me (as I think his answer used a negative/positive lambda quite liberally.)
When $a$ becomes smaller than 1/2, we need to solve for boundary points; which appear to me to be located at $(a, a^2)$ (Without evidence).