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
-
Calculate the bond equivalent yields and the equivalent annual returns for the repurchase agreements described in Problem 14. a. Calculate the yield on the repo if it has a 7-day maturity. b....
-
What impact do you think the policy change had on Power Assets suppliers?
-
Using the approach described in Example 2.6, derive the expressions for all the averaged stiffnesses for the planar isotropic lamina in terms of invariants. Use these results to find the...
-
Match each situation with the fraud triangle factor (opportunity, financial pressure, or rationalization) that best describes it. (a) An employees monthly credit card payments are nearly 75% of their...
-
7.33 moles of a diatomic gas are at a temperature of 317 K. What is the internal energy of the gas?
-
The general ledger of Zips Storage at January 1, 2024, includes the following account balances: Accounts Debits Credits Cash $26,300 17,100 Accounts Receivable Prepaid Insurance Land 15,400 165,000...
-
On 1/1/2023 a bond was authorized to issue at Face value of 6,000,000 Stated interest rate: 5% Interest Payments: Semi-annually on January 1 and July 1 Mature in 10 years, year-end at December 31...
-
A new study comes out revealing the chiropractic visits are less effective at improving health than initially believed. Table 4 details the changes in participant demand and supply schedules which...
-
Explore the role of principal components in machine learning algorithms, such as principal component analysis (PCA) and linear discriminant analysis (LDA). How do these dimensionality reduction...
-
What is the runtime of the following code? Show your work (justify your answer). 1 void translate(char *str) { 1234567 7 } = for (int i if (str[i] 'e' || str[i] str[i] 'a'; 0; str[i] != '\0'; ++i) {...
-
From the concept of Human Resource Management, draw a conceptual framework from Input to process and Output
-
The following is a list of items that could be included in the intangible assets section of the balance sheet. (a) Indicate which items on the list below would generally be reported as intangible...
-
4 Guns LA W Multiple Choice Butter If the economy was producing at point X and moved to point Y, it would have moved from where the economy operates most of the time to a severe recession. it would...
-
on 8 For the following set of lengths 130, 170, 160, 160, 150, 190 Third quartile is: et red d out of Select one: O a. 160 a question O b. 145 O c. 175 O d. 180
-
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...
-
Explain any four types of statistical analysis and their underlying statistical concepts. Describe how each of them has a unique role in the data analysis process.
-
Located in Tokyo, Japan, Sony Mobile Communications is a prominent competitor in the worldwide electronics equipment market. Because of stagnant sales in its ultra HD TVs, that division has decided...
-
Cory Rogers of CMG Research was happy to call Nick Thomas to inform him that Auto Concepts survey data were collected and ready for analysis. Of course, Cory had other marketing research projects and...
Study smarter with the SolutionInn App