Absolute Max/Min of f(x,y)=x^2+y^2-2x on D

[Feodalherren]

Homework Statement

f(x,y) = x^{2}+y^{2}-2x, D is a closed triangular region with vertices (2,0) (0,2) and (0,-2).
Find the absolute max and min of f on D.

Homework Equations

Hessian matrix.

The Attempt at a Solution

Taking the second partials I end up with the system of equations

2x-2=0
2y=0

Adding these two I get y = 1 - x
Then looking at the domain I plug in x=0 and x=2 and get my y values and my CP:s come out as
(0,1) and (2, -1)

The Hessian comes out as 4.

(I'm not showing all the work because it's simple stuff but takes forever to write down in itex.)

Since the Hessian is positive I know we're looking at min or max points, not saddles. Now the second partial of f with respect to x is 2, always positive. Therefore I conclude that both points are global minimums.
Wrong.

 

[LCKurtz]

Homework Statement

f(x,y) = x^{2}+y^{2}-2x, D is a closed triangular region with vertices (2,0) (0,2) and (0,-2).
Find the absolute max and min of f on D.

Homework Equations

Hessian matrix.

The Attempt at a Solution

Taking the second partials I end up with the system of equations

2x-2=0
2y=0

Adding these two I get y = 1 - x

No. You solve them simultaneously to get the point (1,0) as the only critical point. Then you have to check the boundaries.

 

[Feodalherren]

I thought solving a system of equations by adding them was perfectly legal algebra. Why doesn't it work? What do you mean by solving them simultaneously?
Thank you.

 

[Ray Vickson]

Homework Statement

f(x,y) = x^{2}+y^{2}-2x, D is a closed triangular region with vertices (2,0) (0,2) and (0,-2).
Find the absolute max and min of f on D.

Homework Equations

Hessian matrix.

The Attempt at a Solution

Taking the second partials I end up with the system of equations

2x-2=0
2y=0

Adding these two I get y = 1 - x
Then looking at the domain I plug in x=0 and x=2 and get my y values and my CP:s come out as
(0,1) and (2, -1)

The Hessian comes out as 4.

(I'm not showing all the work because it's simple stuff but takes forever to write down in itex.)

Since the Hessian is positive I know we're looking at min or max points, not saddles. Now the second partial of f with respect to x is 2, always positive. Therefore I conclude that both points are global minimums.
Wrong.

What on Earth were you doing? The two equations $2x - 2 = 0$ and $2y = 0$ have just one solution: $(x,y) = (1,0)$. This is inside the triangle, so is the global minimum (because the Hessian matrix $H$ is positive-definite:
H = \pmatrix{2&0\\0&2} There is only one minimum.

The maximum of f cannot be obtained by setting derivatives to zero, because of the constraints on x and y. In fact, the only interior-point optimum is the point (1,0) that we have already found, and it is a minimum. Therefore, the maximum must occur on the boundary of the triangular region, either on a "side" or at a "corner". You can figure out how to find the optima on each of the three sides, and you can just go ahead and compute f(x,y) at the three corners. Somewhere among these (at most) six points, the maximum will be found.

Alternatively, if you know about the Karush-Kuhn-Tucker (KKT) conditions, you can convert your triangular feasible region into a polyhedron defined by three inequality constraints, then apply KKT.

You might well ask: why should the maximization problem be so different from the minimization, and be so much harder? Well, it is a fact of life that maximization of a convex function over a polyhedral convex set (like your triangle) is a so-called NP-hard problem, whose solution in the worst case can involve complete enumeration of all corner points---of which there can be a huge number (exponential in the number of variables). There are no known good algorithms for such problems.

 

[LCKurtz]

I thought solving a system of equations by adding them was perfectly legal algebra. Why doesn't it work? What do you mean by solving them simultaneously?
Thank you.

It means to find all $(x,y)$ pairs that work in both equations at once. Since only $x=1$ satisfies the first equation and only $y=0$ satisfies the second one, the only pair that satisfies both is $(1,0)$.

Note that you could have just completed the square on the $x$ terms and written your function as $(x-1)^2 + y^2 -1$ so you don't even need calculus to find the minimum at $(1,0)$ of $-1$. But you still have to look for the maximum along the boundaries.

 

[Feodalherren]

Thanks Ray that's a great explanation. I'm not familiar with your method. I realized my mistake from before but I'm still left perplexed as to how to solve for the absolute maximum inside D.

I obviously can't plot points. There are infinitely many points along the line. Do I just try the corners or what?

 

[SammyS]

Thanks Ray that's a great explanation. I'm not familiar with your method. I realized my mistake from before but I'm still left perplexed as to how to solve for the absolute maximum inside D.

I obviously can't plot points. There are infinitely many points along the line. Do I just try the corners or what?

No.

The domain, D, of f(x ,y) is bounded by 3 line segments.

Find the equation for each of those lines. Then plug each of those into your function in a way that gives a function of only one variable, Find the max. for each of those. Also evaluate f(x, y) at the corners.

The max. probably does occur at a corner, but for other functions and/or other domains, that might not be the case.

 

[Ray Vickson]

Thanks Ray that's a great explanation. I'm not familiar with your method. I realized my mistake from before but I'm still left perplexed as to how to solve for the absolute maximum inside D.

I obviously can't plot points. There are infinitely many points along the line. Do I just try the corners or what?

Region D has three sides. One of these is the vertical side along the y-axis from y = -2 to y = +2. On that side the problem is to maximize g(y) = f(0,y), subject to -2 ≤ y ≤ 2. The solution is either inside the open interval (-2,2) or else is at one or both of the two ends y = -2 and/or y = +2. If there is no stationary point of g(y) in -2 < y < 2, or if there is one but it is a min instead of a max, then you must have an end-point max. In that case you can tell which end is a max just by by computing f(0,-2) and f(0,2)---basically, by inelegant brute-force. Possibly they are both maxima of g.

Another side is the line segment from (0,2) to (2,0), which is the line y = 2-x for 0 ≤ x ≤ 2. You can find the max on that side by solving the one-dimensional problem $\max f(x,2-x), \,0 \leq x \leq 2.$ This problem is similar to the one discussed above.

The third side is the segment from (0,-2) to (2,0), which is the line y = -2+x for 0 ≤ x ≤ 2. On this side you need so solve $\max f(x,-2+x), \,0 \leq x \leq 2.$ Again, this problem is similar to the other two mentioned.

 

[Feodalherren]

My god this is one ugly problem. Somebody better figure out an algorithm for this. I'm getting a headache just thinking about all the messy algebra.
Thanks for the help guys, I got it now.

 

[Ray Vickson]

No.

The domain, D, of f(x ,y) is bounded by 3 line segments.

Find the equation for each of those lines. Then plug each of those into your function in a way that gives a function of only one variable, Find the max. for each of those. Also evaluate f(x, y) at the corners.

The max. probably does occur at a corner, but for other functions and/or other domains, that might not be the case.

If you have access to some theory you can write down the solution almost at once.

Theorem: A convex function on a closed convex set always has its maximum at an extreme point. See, eg., http://coral.ie.lehigh.edu/~ted/files/ie417/lectures/Lecture5.pdf , Theorem 5, page 6.

In this case f is (obviously) convex and the set D is a closed convex polyhedron whose only extreme points are the three corners. Thus, we need only evaluate f at the three corners and take the largest value.