Angela Pamerson is a world-famous lifeguard. One day after lunch, she is walking back to the...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
Angela Pamerson is a world-famous lifeguard. One day after lunch, she is walking back to the beach when she spots a person drowning out in the water. The beach stretches out in an east to west direction and is 50 meters wide along its length. South of the beach is a strip of grass. The drowning swimmer is exactly 150 meters north and 50 meters east of Angela Pamerson, as depicted in the following figures. water 14 go 50m ik 14 grass ds 50m 50m 50m water sand grass 50 m 50 m 50 m 50 m The figure on the right is included just in case the geometry in the hand-drawn figure is not clear. Angela Pamerson must figure out the fastest route to the swimmer. That is, she must solve for optimal values of x and y in the figures above. If her speed over grass, sand, and water were exactly the same, then the fastest path would be a straight line. However, her speeds differ quite a bit. On grass, she runs at 10 meters per second. On sand, she runs at 5 meters per second. On water, she can swim at 1.5 meters per second. (An excellent pace on both land and sea!) The goal of this is assignment is to find the optimal route and save the day. To do this we will employ Newton's Method for Optimization. NEWTON'S METHOD In its simplest form, Newton's Method can be used to find the roots/zeros of a function. For a function g of one variable, starting at an initial guess xo, we define a sequence of points x iteratively by Xn+1 = Xn where g' is the derivative. Under certain assumptions and if the initial guess xo is close enough to the exact answer, then this process will rapidly converge to a root of the function. Newton's Method can also be used to find a minimum or maximum value of a function. Say that f is a function for which we want to find a minimum. Assume that the first derivative f and second derivative f" exist. The first derivative f' must be zero at a minimum, and we can use the following version of Newton's method f'(xn) Xn+1 = Xn- Under certain assumptions and if the initial guess xo is close enough to the exact answer, then this process will rapidly converge to a point where the minimum occurs. So far, we have described Newton's Method for a function of one variable, but in this assign- ment, you will be solving for a minimum value of a function f(x, y) of two variables. Here, starting with an initial guess (xo. Yo). Newton's Method for Optimization is given by Hf (Xn. Yn) ¹Gf (Xn, Yn) where Xn+1 Yn+1 = Xn yn 25 dxdx Gf(x, y) = 1(x,y) is the gradient of the function f at the point (x, y) and g(xn) g'(xn) 1(x,y) 1(x,y) 2²28 axdy 2²1 aydy |fx(x, y) fy(x, y) Hf(x,y)=f axoy (x,y) 1(x,y) is the Hessian matrix at the point (x, y). Note that Newton's Method uses the inverse of the Hessian matrix. This is just a brief overview of the concept. There are lots of good resources for Newton's Method on the internet and we will provide some links on the Moodle page. fxx(x, y) fxy(x, y) fxy(x, y) fyy(x,y) QUESTIONS And now, back to the problem of Angela Pamerson and the drowning swimmer. Let f(x, y) be the total time it takes Angela Pamerson to reach the swimmer where, as shown in the figure, x is the horizontal component of her travel over grass and y is the horizontal component of her travel over sand. (1) Write a formula for the function f and explain how you arrived at this formula. Note: when writing mathematics or physics, it is generally considered bad form to stick values such as 50 meters directly into a formula, so we suggest you give names such as C= 50m to the constants involved. (2) Calculate formulas for the first-order partial derivatives fx and fy. (3) Calculate formulas for the second-order partial derivatives fxx fxy, fyy- (4) How can we check if these formulas for partial derivatives are correct? Recall that the partial derivative of a function is defined as a limit fx(x, y) = lim f(x+h, y)-f(x,y) h Hence, if his sufficiently small, then (f(x+h, y)-f(x, y)) should be very close in value to fx(x, y). Using the test point (x, y) = (25,35) and h=10³, evaluate both f (x: + h, y₁)-f(xt, yt) h and verify that they are close in value. Do the same for f(x,yt +h)-f(x₁.yt) h and fy(x,yt). (5) Using the same method (and same values x, y, and h), test whether your formulas for fxx fxy, and fyy are accurate. and fx(x₁.yt) (6) Newton's Method requires a reasonable first guess (xo. yo) in order for the resulting points (Xn, yn) to converge to the solution. It doesn't have to be super accurate, but if the initial guess is way off, the method may not converge. Make a choice of initial guess (xo, yo) € R² for the solution and explain why you made that guess. (7) Starting from your inital guess (xo, yo), run one iteration of Newton's Method to compute (x₁, y₁). For this question, explain in detail how you computed (x₁, y₁). (8) Starting from your initial guess (xo, yo), calculate five iterations of Newton's Method. At each step, please tell us • the point (xn. Yn), • the value f(xn. Yn) of the function at that point, • the gradient of f at that point, and • the Hessian matrix of f at that point. For this question, if you have implemented Newton's Method on computer, it is enough to include the output of the program, so long as it provides this information in a clean and concise manner at each iteration. (9) Given a reasonable starting point, the algorithm after five steps should be very close to a solution where the gradient is zero. By analyzing the Hessian matrix at this point, determine whether this point is a local minimum, local maximum, or saddle. (10) For the function f in this assignment, does Newton's method always converge to the correct answer? Either provide some evidence that this is the case, or show for some starting point (xo, yo) € R² that Newton's Method for Optimization fails to converge to a minimum. Angela Pamerson is a world-famous lifeguard. One day after lunch, she is walking back to the beach when she spots a person drowning out in the water. The beach stretches out in an east to west direction and is 50 meters wide along its length. South of the beach is a strip of grass. The drowning swimmer is exactly 150 meters north and 50 meters east of Angela Pamerson, as depicted in the following figures. water 14 go 50m ik 14 grass ds 50m 50m 50m water sand grass 50 m 50 m 50 m 50 m The figure on the right is included just in case the geometry in the hand-drawn figure is not clear. Angela Pamerson must figure out the fastest route to the swimmer. That is, she must solve for optimal values of x and y in the figures above. If her speed over grass, sand, and water were exactly the same, then the fastest path would be a straight line. However, her speeds differ quite a bit. On grass, she runs at 10 meters per second. On sand, she runs at 5 meters per second. On water, she can swim at 1.5 meters per second. (An excellent pace on both land and sea!) The goal of this is assignment is to find the optimal route and save the day. To do this we will employ Newton's Method for Optimization. NEWTON'S METHOD In its simplest form, Newton's Method can be used to find the roots/zeros of a function. For a function g of one variable, starting at an initial guess xo, we define a sequence of points x iteratively by Xn+1 = Xn where g' is the derivative. Under certain assumptions and if the initial guess xo is close enough to the exact answer, then this process will rapidly converge to a root of the function. Newton's Method can also be used to find a minimum or maximum value of a function. Say that f is a function for which we want to find a minimum. Assume that the first derivative f and second derivative f" exist. The first derivative f' must be zero at a minimum, and we can use the following version of Newton's method f'(xn) Xn+1 = Xn- Under certain assumptions and if the initial guess xo is close enough to the exact answer, then this process will rapidly converge to a point where the minimum occurs. So far, we have described Newton's Method for a function of one variable, but in this assign- ment, you will be solving for a minimum value of a function f(x, y) of two variables. Here, starting with an initial guess (xo. Yo). Newton's Method for Optimization is given by Hf (Xn. Yn) ¹Gf (Xn, Yn) where Xn+1 Yn+1 = Xn yn 25 dxdx Gf(x, y) = 1(x,y) is the gradient of the function f at the point (x, y) and g(xn) g'(xn) 1(x,y) 1(x,y) 2²28 axdy 2²1 aydy |fx(x, y) fy(x, y) Hf(x,y)=f axoy (x,y) 1(x,y) is the Hessian matrix at the point (x, y). Note that Newton's Method uses the inverse of the Hessian matrix. This is just a brief overview of the concept. There are lots of good resources for Newton's Method on the internet and we will provide some links on the Moodle page. fxx(x, y) fxy(x, y) fxy(x, y) fyy(x,y) QUESTIONS And now, back to the problem of Angela Pamerson and the drowning swimmer. Let f(x, y) be the total time it takes Angela Pamerson to reach the swimmer where, as shown in the figure, x is the horizontal component of her travel over grass and y is the horizontal component of her travel over sand. (1) Write a formula for the function f and explain how you arrived at this formula. Note: when writing mathematics or physics, it is generally considered bad form to stick values such as 50 meters directly into a formula, so we suggest you give names such as C= 50m to the constants involved. (2) Calculate formulas for the first-order partial derivatives fx and fy. (3) Calculate formulas for the second-order partial derivatives fxx fxy, fyy- (4) How can we check if these formulas for partial derivatives are correct? Recall that the partial derivative of a function is defined as a limit fx(x, y) = lim f(x+h, y)-f(x,y) h Hence, if his sufficiently small, then (f(x+h, y)-f(x, y)) should be very close in value to fx(x, y). Using the test point (x, y) = (25,35) and h=10³, evaluate both f (x: + h, y₁)-f(xt, yt) h and verify that they are close in value. Do the same for f(x,yt +h)-f(x₁.yt) h and fy(x,yt). (5) Using the same method (and same values x, y, and h), test whether your formulas for fxx fxy, and fyy are accurate. and fx(x₁.yt) (6) Newton's Method requires a reasonable first guess (xo. yo) in order for the resulting points (Xn, yn) to converge to the solution. It doesn't have to be super accurate, but if the initial guess is way off, the method may not converge. Make a choice of initial guess (xo, yo) € R² for the solution and explain why you made that guess. (7) Starting from your inital guess (xo, yo), run one iteration of Newton's Method to compute (x₁, y₁). For this question, explain in detail how you computed (x₁, y₁). (8) Starting from your initial guess (xo, yo), calculate five iterations of Newton's Method. At each step, please tell us • the point (xn. Yn), • the value f(xn. Yn) of the function at that point, • the gradient of f at that point, and • the Hessian matrix of f at that point. For this question, if you have implemented Newton's Method on computer, it is enough to include the output of the program, so long as it provides this information in a clean and concise manner at each iteration. (9) Given a reasonable starting point, the algorithm after five steps should be very close to a solution where the gradient is zero. By analyzing the Hessian matrix at this point, determine whether this point is a local minimum, local maximum, or saddle. (10) For the function f in this assignment, does Newton's method always converge to the correct answer? Either provide some evidence that this is the case, or show for some starting point (xo, yo) € R² that Newton's Method for Optimization fails to converge to a minimum. Angela Pamerson is a world-famous lifeguard. One day after lunch, she is walking back to the beach when she spots a person drowning out in the water. The beach stretches out in an east to west direction and is 50 meters wide along its length. South of the beach is a strip of grass. The drowning swimmer is exactly 150 meters north and 50 meters east of Angela Pamerson, as depicted in the following figures. water 14 go 50m ik 14 grass ds 50m 50m 50m water sand grass 50 m 50 m 50 m 50 m The figure on the right is included just in case the geometry in the hand-drawn figure is not clear. Angela Pamerson must figure out the fastest route to the swimmer. That is, she must solve for optimal values of x and y in the figures above. If her speed over grass, sand, and water were exactly the same, then the fastest path would be a straight line. However, her speeds differ quite a bit. On grass, she runs at 10 meters per second. On sand, she runs at 5 meters per second. On water, she can swim at 1.5 meters per second. (An excellent pace on both land and sea!) The goal of this is assignment is to find the optimal route and save the day. To do this we will employ Newton's Method for Optimization. NEWTON'S METHOD In its simplest form, Newton's Method can be used to find the roots/zeros of a function. For a function g of one variable, starting at an initial guess xo, we define a sequence of points x iteratively by Xn+1 = Xn where g' is the derivative. Under certain assumptions and if the initial guess xo is close enough to the exact answer, then this process will rapidly converge to a root of the function. Newton's Method can also be used to find a minimum or maximum value of a function. Say that f is a function for which we want to find a minimum. Assume that the first derivative f and second derivative f" exist. The first derivative f' must be zero at a minimum, and we can use the following version of Newton's method f'(xn) Xn+1 = Xn- Under certain assumptions and if the initial guess xo is close enough to the exact answer, then this process will rapidly converge to a point where the minimum occurs. So far, we have described Newton's Method for a function of one variable, but in this assign- ment, you will be solving for a minimum value of a function f(x, y) of two variables. Here, starting with an initial guess (xo. Yo). Newton's Method for Optimization is given by Hf (Xn. Yn) ¹Gf (Xn, Yn) where Xn+1 Yn+1 = Xn yn 25 dxdx Gf(x, y) = 1(x,y) is the gradient of the function f at the point (x, y) and g(xn) g'(xn) 1(x,y) 1(x,y) 2²28 axdy 2²1 aydy |fx(x, y) fy(x, y) Hf(x,y)=f axoy (x,y) 1(x,y) is the Hessian matrix at the point (x, y). Note that Newton's Method uses the inverse of the Hessian matrix. This is just a brief overview of the concept. There are lots of good resources for Newton's Method on the internet and we will provide some links on the Moodle page. fxx(x, y) fxy(x, y) fxy(x, y) fyy(x,y) QUESTIONS And now, back to the problem of Angela Pamerson and the drowning swimmer. Let f(x, y) be the total time it takes Angela Pamerson to reach the swimmer where, as shown in the figure, x is the horizontal component of her travel over grass and y is the horizontal component of her travel over sand. (1) Write a formula for the function f and explain how you arrived at this formula. Note: when writing mathematics or physics, it is generally considered bad form to stick values such as 50 meters directly into a formula, so we suggest you give names such as C= 50m to the constants involved. (2) Calculate formulas for the first-order partial derivatives fx and fy. (3) Calculate formulas for the second-order partial derivatives fxx fxy, fyy- (4) How can we check if these formulas for partial derivatives are correct? Recall that the partial derivative of a function is defined as a limit fx(x, y) = lim f(x+h, y)-f(x,y) h Hence, if his sufficiently small, then (f(x+h, y)-f(x, y)) should be very close in value to fx(x, y). Using the test point (x, y) = (25,35) and h=10³, evaluate both f (x: + h, y₁)-f(xt, yt) h and verify that they are close in value. Do the same for f(x,yt +h)-f(x₁.yt) h and fy(x,yt). (5) Using the same method (and same values x, y, and h), test whether your formulas for fxx fxy, and fyy are accurate. and fx(x₁.yt) (6) Newton's Method requires a reasonable first guess (xo. yo) in order for the resulting points (Xn, yn) to converge to the solution. It doesn't have to be super accurate, but if the initial guess is way off, the method may not converge. Make a choice of initial guess (xo, yo) € R² for the solution and explain why you made that guess. (7) Starting from your inital guess (xo, yo), run one iteration of Newton's Method to compute (x₁, y₁). For this question, explain in detail how you computed (x₁, y₁). (8) Starting from your initial guess (xo, yo), calculate five iterations of Newton's Method. At each step, please tell us • the point (xn. Yn), • the value f(xn. Yn) of the function at that point, • the gradient of f at that point, and • the Hessian matrix of f at that point. For this question, if you have implemented Newton's Method on computer, it is enough to include the output of the program, so long as it provides this information in a clean and concise manner at each iteration. (9) Given a reasonable starting point, the algorithm after five steps should be very close to a solution where the gradient is zero. By analyzing the Hessian matrix at this point, determine whether this point is a local minimum, local maximum, or saddle. (10) For the function f in this assignment, does Newton's method always converge to the correct answer? Either provide some evidence that this is the case, or show for some starting point (xo, yo) € R² that Newton's Method for Optimization fails to converge to a minimum. Angela Pamerson is a world-famous lifeguard. One day after lunch, she is walking back to the beach when she spots a person drowning out in the water. The beach stretches out in an east to west direction and is 50 meters wide along its length. South of the beach is a strip of grass. The drowning swimmer is exactly 150 meters north and 50 meters east of Angela Pamerson, as depicted in the following figures. water 14 go 50m ik 14 grass ds 50m 50m 50m water sand grass 50 m 50 m 50 m 50 m The figure on the right is included just in case the geometry in the hand-drawn figure is not clear. Angela Pamerson must figure out the fastest route to the swimmer. That is, she must solve for optimal values of x and y in the figures above. If her speed over grass, sand, and water were exactly the same, then the fastest path would be a straight line. However, her speeds differ quite a bit. On grass, she runs at 10 meters per second. On sand, she runs at 5 meters per second. On water, she can swim at 1.5 meters per second. (An excellent pace on both land and sea!) The goal of this is assignment is to find the optimal route and save the day. To do this we will employ Newton's Method for Optimization. NEWTON'S METHOD In its simplest form, Newton's Method can be used to find the roots/zeros of a function. For a function g of one variable, starting at an initial guess xo, we define a sequence of points x iteratively by Xn+1 = Xn where g' is the derivative. Under certain assumptions and if the initial guess xo is close enough to the exact answer, then this process will rapidly converge to a root of the function. Newton's Method can also be used to find a minimum or maximum value of a function. Say that f is a function for which we want to find a minimum. Assume that the first derivative f and second derivative f" exist. The first derivative f' must be zero at a minimum, and we can use the following version of Newton's method f'(xn) Xn+1 = Xn- Under certain assumptions and if the initial guess xo is close enough to the exact answer, then this process will rapidly converge to a point where the minimum occurs. So far, we have described Newton's Method for a function of one variable, but in this assign- ment, you will be solving for a minimum value of a function f(x, y) of two variables. Here, starting with an initial guess (xo. Yo). Newton's Method for Optimization is given by Hf (Xn. Yn) ¹Gf (Xn, Yn) where Xn+1 Yn+1 = Xn yn 25 dxdx Gf(x, y) = 1(x,y) is the gradient of the function f at the point (x, y) and g(xn) g'(xn) 1(x,y) 1(x,y) 2²28 axdy 2²1 aydy |fx(x, y) fy(x, y) Hf(x,y)=f axoy (x,y) 1(x,y) is the Hessian matrix at the point (x, y). Note that Newton's Method uses the inverse of the Hessian matrix. This is just a brief overview of the concept. There are lots of good resources for Newton's Method on the internet and we will provide some links on the Moodle page. fxx(x, y) fxy(x, y) fxy(x, y) fyy(x,y) QUESTIONS And now, back to the problem of Angela Pamerson and the drowning swimmer. Let f(x, y) be the total time it takes Angela Pamerson to reach the swimmer where, as shown in the figure, x is the horizontal component of her travel over grass and y is the horizontal component of her travel over sand. (1) Write a formula for the function f and explain how you arrived at this formula. Note: when writing mathematics or physics, it is generally considered bad form to stick values such as 50 meters directly into a formula, so we suggest you give names such as C= 50m to the constants involved. (2) Calculate formulas for the first-order partial derivatives fx and fy. (3) Calculate formulas for the second-order partial derivatives fxx fxy, fyy- (4) How can we check if these formulas for partial derivatives are correct? Recall that the partial derivative of a function is defined as a limit fx(x, y) = lim f(x+h, y)-f(x,y) h Hence, if his sufficiently small, then (f(x+h, y)-f(x, y)) should be very close in value to fx(x, y). Using the test point (x, y) = (25,35) and h=10³, evaluate both f (x: + h, y₁)-f(xt, yt) h and verify that they are close in value. Do the same for f(x,yt +h)-f(x₁.yt) h and fy(x,yt). (5) Using the same method (and same values x, y, and h), test whether your formulas for fxx fxy, and fyy are accurate. and fx(x₁.yt) (6) Newton's Method requires a reasonable first guess (xo. yo) in order for the resulting points (Xn, yn) to converge to the solution. It doesn't have to be super accurate, but if the initial guess is way off, the method may not converge. Make a choice of initial guess (xo, yo) € R² for the solution and explain why you made that guess. (7) Starting from your inital guess (xo, yo), run one iteration of Newton's Method to compute (x₁, y₁). For this question, explain in detail how you computed (x₁, y₁). (8) Starting from your initial guess (xo, yo), calculate five iterations of Newton's Method. At each step, please tell us • the point (xn. Yn), • the value f(xn. Yn) of the function at that point, • the gradient of f at that point, and • the Hessian matrix of f at that point. For this question, if you have implemented Newton's Method on computer, it is enough to include the output of the program, so long as it provides this information in a clean and concise manner at each iteration. (9) Given a reasonable starting point, the algorithm after five steps should be very close to a solution where the gradient is zero. By analyzing the Hessian matrix at this point, determine whether this point is a local minimum, local maximum, or saddle. (10) For the function f in this assignment, does Newton's method always converge to the correct answer? Either provide some evidence that this is the case, or show for some starting point (xo, yo) € R² that Newton's Method for Optimization fails to converge to a minimum. Angela Pamerson is a world-famous lifeguard. One day after lunch, she is walking back to the beach when she spots a person drowning out in the water. The beach stretches out in an east to west direction and is 50 meters wide along its length. South of the beach is a strip of grass. The drowning swimmer is exactly 150 meters north and 50 meters east of Angela Pamerson, as depicted in the following figures. water 14 go 50m ik 14 grass ds 50m 50m 50m water sand grass 50 m 50 m 50 m 50 m The figure on the right is included just in case the geometry in the hand-drawn figure is not clear. Angela Pamerson must figure out the fastest route to the swimmer. That is, she must solve for optimal values of x and y in the figures above. If her speed over grass, sand, and water were exactly the same, then the fastest path would be a straight line. However, her speeds differ quite a bit. On grass, she runs at 10 meters per second. On sand, she runs at 5 meters per second. On water, she can swim at 1.5 meters per second. (An excellent pace on both land and sea!) The goal of this is assignment is to find the optimal route and save the day. To do this we will employ Newton's Method for Optimization. NEWTON'S METHOD In its simplest form, Newton's Method can be used to find the roots/zeros of a function. For a function g of one variable, starting at an initial guess xo, we define a sequence of points x iteratively by Xn+1 = Xn where g' is the derivative. Under certain assumptions and if the initial guess xo is close enough to the exact answer, then this process will rapidly converge to a root of the function. Newton's Method can also be used to find a minimum or maximum value of a function. Say that f is a function for which we want to find a minimum. Assume that the first derivative f and second derivative f" exist. The first derivative f' must be zero at a minimum, and we can use the following version of Newton's method f'(xn) Xn+1 = Xn- Under certain assumptions and if the initial guess xo is close enough to the exact answer, then this process will rapidly converge to a point where the minimum occurs. So far, we have described Newton's Method for a function of one variable, but in this assign- ment, you will be solving for a minimum value of a function f(x, y) of two variables. Here, starting with an initial guess (xo. Yo). Newton's Method for Optimization is given by Hf (Xn. Yn) ¹Gf (Xn, Yn) where Xn+1 Yn+1 = Xn yn 25 dxdx Gf(x, y) = 1(x,y) is the gradient of the function f at the point (x, y) and g(xn) g'(xn) 1(x,y) 1(x,y) 2²28 axdy 2²1 aydy |fx(x, y) fy(x, y) Hf(x,y)=f axoy (x,y) 1(x,y) is the Hessian matrix at the point (x, y). Note that Newton's Method uses the inverse of the Hessian matrix. This is just a brief overview of the concept. There are lots of good resources for Newton's Method on the internet and we will provide some links on the Moodle page. fxx(x, y) fxy(x, y) fxy(x, y) fyy(x,y) QUESTIONS And now, back to the problem of Angela Pamerson and the drowning swimmer. Let f(x, y) be the total time it takes Angela Pamerson to reach the swimmer where, as shown in the figure, x is the horizontal component of her travel over grass and y is the horizontal component of her travel over sand. (1) Write a formula for the function f and explain how you arrived at this formula. Note: when writing mathematics or physics, it is generally considered bad form to stick values such as 50 meters directly into a formula, so we suggest you give names such as C= 50m to the constants involved. (2) Calculate formulas for the first-order partial derivatives fx and fy. (3) Calculate formulas for the second-order partial derivatives fxx fxy, fyy- (4) How can we check if these formulas for partial derivatives are correct? Recall that the partial derivative of a function is defined as a limit fx(x, y) = lim f(x+h, y)-f(x,y) h Hence, if his sufficiently small, then (f(x+h, y)-f(x, y)) should be very close in value to fx(x, y). Using the test point (x, y) = (25,35) and h=10³, evaluate both f (x: + h, y₁)-f(xt, yt) h and verify that they are close in value. Do the same for f(x,yt +h)-f(x₁.yt) h and fy(x,yt). (5) Using the same method (and same values x, y, and h), test whether your formulas for fxx fxy, and fyy are accurate. and fx(x₁.yt) (6) Newton's Method requires a reasonable first guess (xo. yo) in order for the resulting points (Xn, yn) to converge to the solution. It doesn't have to be super accurate, but if the initial guess is way off, the method may not converge. Make a choice of initial guess (xo, yo) € R² for the solution and explain why you made that guess. (7) Starting from your inital guess (xo, yo), run one iteration of Newton's Method to compute (x₁, y₁). For this question, explain in detail how you computed (x₁, y₁). (8) Starting from your initial guess (xo, yo), calculate five iterations of Newton's Method. At each step, please tell us • the point (xn. Yn), • the value f(xn. Yn) of the function at that point, • the gradient of f at that point, and • the Hessian matrix of f at that point. For this question, if you have implemented Newton's Method on computer, it is enough to include the output of the program, so long as it provides this information in a clean and concise manner at each iteration. (9) Given a reasonable starting point, the algorithm after five steps should be very close to a solution where the gradient is zero. By analyzing the Hessian matrix at this point, determine whether this point is a local minimum, local maximum, or saddle. (10) For the function f in this assignment, does Newton's method always converge to the correct answer? Either provide some evidence that this is the case, or show for some starting point (xo, yo) € R² that Newton's Method for Optimization fails to converge to a minimum. Angela Pamerson is a world-famous lifeguard. One day after lunch, she is walking back to the beach when she spots a person drowning out in the water. The beach stretches out in an east to west direction and is 50 meters wide along its length. South of the beach is a strip of grass. The drowning swimmer is exactly 150 meters north and 50 meters east of Angela Pamerson, as depicted in the following figures. water 14 go 50m ik 14 grass ds 50m 50m 50m water sand grass 50 m 50 m 50 m 50 m The figure on the right is included just in case the geometry in the hand-drawn figure is not clear. Angela Pamerson must figure out the fastest route to the swimmer. That is, she must solve for optimal values of x and y in the figures above. If her speed over grass, sand, and water were exactly the same, then the fastest path would be a straight line. However, her speeds differ quite a bit. On grass, she runs at 10 meters per second. On sand, she runs at 5 meters per second. On water, she can swim at 1.5 meters per second. (An excellent pace on both land and sea!) The goal of this is assignment is to find the optimal route and save the day. To do this we will employ Newton's Method for Optimization. NEWTON'S METHOD In its simplest form, Newton's Method can be used to find the roots/zeros of a function. For a function g of one variable, starting at an initial guess xo, we define a sequence of points x iteratively by Xn+1 = Xn where g' is the derivative. Under certain assumptions and if the initial guess xo is close enough to the exact answer, then this process will rapidly converge to a root of the function. Newton's Method can also be used to find a minimum or maximum value of a function. Say that f is a function for which we want to find a minimum. Assume that the first derivative f and second derivative f" exist. The first derivative f' must be zero at a minimum, and we can use the following version of Newton's method f'(xn) Xn+1 = Xn- Under certain assumptions and if the initial guess xo is close enough to the exact answer, then this process will rapidly converge to a point where the minimum occurs. So far, we have described Newton's Method for a function of one variable, but in this assign- ment, you will be solving for a minimum value of a function f(x, y) of two variables. Here, starting with an initial guess (xo. Yo). Newton's Method for Optimization is given by Hf (Xn. Yn) ¹Gf (Xn, Yn) where Xn+1 Yn+1 = Xn yn 25 dxdx Gf(x, y) = 1(x,y) is the gradient of the function f at the point (x, y) and g(xn) g'(xn) 1(x,y) 1(x,y) 2²28 axdy 2²1 aydy |fx(x, y) fy(x, y) Hf(x,y)=f axoy (x,y) 1(x,y) is the Hessian matrix at the point (x, y). Note that Newton's Method uses the inverse of the Hessian matrix. This is just a brief overview of the concept. There are lots of good resources for Newton's Method on the internet and we will provide some links on the Moodle page. fxx(x, y) fxy(x, y) fxy(x, y) fyy(x,y) QUESTIONS And now, back to the problem of Angela Pamerson and the drowning swimmer. Let f(x, y) be the total time it takes Angela Pamerson to reach the swimmer where, as shown in the figure, x is the horizontal component of her travel over grass and y is the horizontal component of her travel over sand. (1) Write a formula for the function f and explain how you arrived at this formula. Note: when writing mathematics or physics, it is generally considered bad form to stick values such as 50 meters directly into a formula, so we suggest you give names such as C= 50m to the constants involved. (2) Calculate formulas for the first-order partial derivatives fx and fy. (3) Calculate formulas for the second-order partial derivatives fxx fxy, fyy- (4) How can we check if these formulas for partial derivatives are correct? Recall that the partial derivative of a function is defined as a limit fx(x, y) = lim f(x+h, y)-f(x,y) h Hence, if his sufficiently small, then (f(x+h, y)-f(x, y)) should be very close in value to fx(x, y). Using the test point (x, y) = (25,35) and h=10³, evaluate both f (x: + h, y₁)-f(xt, yt) h and verify that they are close in value. Do the same for f(x,yt +h)-f(x₁.yt) h and fy(x,yt). (5) Using the same method (and same values x, y, and h), test whether your formulas for fxx fxy, and fyy are accurate. and fx(x₁.yt) (6) Newton's Method requires a reasonable first guess (xo. yo) in order for the resulting points (Xn, yn) to converge to the solution. It doesn't have to be super accurate, but if the initial guess is way off, the method may not converge. Make a choice of initial guess (xo, yo) € R² for the solution and explain why you made that guess. (7) Starting from your inital guess (xo, yo), run one iteration of Newton's Method to compute (x₁, y₁). For this question, explain in detail how you computed (x₁, y₁). (8) Starting from your initial guess (xo, yo), calculate five iterations of Newton's Method. At each step, please tell us • the point (xn. Yn), • the value f(xn. Yn) of the function at that point, • the gradient of f at that point, and • the Hessian matrix of f at that point. For this question, if you have implemented Newton's Method on computer, it is enough to include the output of the program, so long as it provides this information in a clean and concise manner at each iteration. (9) Given a reasonable starting point, the algorithm after five steps should be very close to a solution where the gradient is zero. By analyzing the Hessian matrix at this point, determine whether this point is a local minimum, local maximum, or saddle. (10) For the function f in this assignment, does Newton's method always converge to the correct answer? Either provide some evidence that this is the case, or show for some starting point (xo, yo) € R² that Newton's Method for Optimization fails to converge to a minimum.
Expert Answer:
Answer rating: 100% (QA)
1 The function f represents the total time it takes Angela Pamerson to reach the swimmer The function is made up of the time it takes to ... View the full answer
Related Book For
Cornerstones of Financial and Managerial Accounting
ISBN: 978-1111879044
2nd edition
Authors: Rich, Jeff Jones, Dan Heitger, Maryanne Mowen, Don Hansen
Posted Date:
Students also viewed these accounting questions
-
An earthmover must go north 350 m and then west 275 m to avoid a pipeline hazard. What distance would it travel if it could go directly to the endpoint?
-
A lifeguard has to jump in to save a swimmer in trouble at the lake at Possum Park an average of 2 times a week, according to a Poisson distribution. a. What is the probability that he will save more...
-
A particle of mass m moves along a straight line with constant speed in the x direction, a distance b from the x axis (Fig. P13.14). Show that Keplers second law is satisfied by showing that the two...
-
9) The mole (Avogadro number N) is defined as the number of atoms in exactly 12 grams of 2C, calculate the: a) number of atoms in 2 g of C b) number of atoms in 5 g of C
-
Which medium currently enables the fastest data communications?
-
Whispering Industries purchased $8,100 of merchandise on February 1, 2025, subject to a trade discount of 10% and with credit terms of 3/15, n/60. It returned $2,100 (gross price before trade or cash...
-
True or False. The element mass matrices are always singular.
-
Using the data in Table 10.2, a. What was the average dividend yield for the SP500 from 20022011? b. What was the volatility of the dividend yield? c. What was the average annual return of the SP500...
-
3. In the figure below, a laser beam shines along the surface of a block of transparent material. Half of the beam goes straight to a detector, while the other half travels through the block and then...
-
You are working on a free-form Packet Tracer challenge activity as seen in Figure 1, you have been given the London Railways network.' The purpose of this EMA question is to build upon each of the...
-
Many companies sponsor local sporting teams and event. What data is least likely to be part of the decision to sponsor that event
-
Brewster Park, LLC, is a business that owns, maintains, and leases residential housing in Bridgeport, Connecticut, and Trumbull, Connecticut. The LLC has two members, Michael Weinshel and Joyce...
-
Clarett sought summary judgment on the merits of his antitrust claim. The NFL asserted that Clarett lacked antitrust standing and, as a matter of law, that the eligibility rules were immune from...
-
In July 2013, Desmond Schacht opened joint checking and savings accounts with his father Kenneth at Alaska USA Federal Credit Union. Desmond signed Alaska USAs Master Joint Account Agreement as the...
-
Pittsburgh Glass Works, LLC (PGW) manufactures automotive glass in Harmarville, Pennsylvania. In 2008, the automobile industry began to falter. PGW engaged in several reductions in force (RIFs) to...
-
In January 2013, Wesley Erik Hawley met Denise T. Reed. The two became romantically involved in March 2013 and eventually were engaged to be married. Mr. Hawley was a widower and a thoroughbred horse...
-
A. (10 points) Explain the concept of globalization and how it is measured. In addition, briefly discuss whether globalization is better measured using flow or stock variables, or both. Do you think...
-
Which one of the following anhydrous chloride is not obtained on direct heating of its hydrated chloride? (A) BaCl2 (B) CaClz (C) MgCl2 (D) SrCl2
-
Peachtree Corporation acquired 100 percent of the outstanding common stock of Standard Company in a business combination. Immediately before the business combination, the two businesses had the...
-
Listed below are items that may appear on a classified balance sheet. 1. Land 2. Amounts due from customers 3. Office building 4. Truck 5. Goods held for resale 6. Amounts owed to suppliers 7. Patent...
-
Multiple Choice Questions 1. As a result of a stock split, a. Stockholders equity is increased. b. The par value of the stock is changed in the reverse proportion as the stock split. c. The...
-
You are the senior partner of a large, local audit firm. In reviewing the work of a junior staff member on a compilation engagement for Greasemonkey's Delight Inc., a local autoparts store (in which...
-
The chapter discussed three issues to consider when obtaining evidence using a sample-based audit procedure: a. The number of transactions or items to examine b. The actual transactions or items to...
-
Compare and contrast statistical and non-statistical (judgmental) sampling. Include in your discussion conditions that might make one approach to sampling more desirable than the other.
Study smarter with the SolutionInn App