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
-
Saunders Corp. has current liabilities of $435,000, a quick ratio of .95, inventory turnover of 6.2, and a current ratio of 1.6. What is the cost of goods sold for the company?
-
As stated in the chapter, the Congressional Budget Office (CBO) estimates that the federal budget deficit was $1,294 billion in 2010. For each of the interest rates given in problem 1.8, calculate...
-
Describe or define the following terms: 1. Asset 2. Liability 3. Shareholders equity 4. Revenue 5. Expense Discuss how the five terms relate to one another.
-
1. Which of the following taxpayers may not deduct their educational expense? a. A CPA who attends a course to review for the real estate agents exam b. A corporate president who attends a management...
-
This question needs you to engage with your Tutor Group Forum ( the forum that is moderated by your own tutor not in any wider TM 2 5 5 forum ) on a regular basis throughout Block 1 . It is important...
-
Salazar Company is a job-order costing firm that uses activity-based costing to apply overhead to jobs. Salazar identified three overhead activities and related drivers. Budgeted information for the...
-
I ran Bubble Sort, Merge Sort, and Quick Sort under the following inputs: List of 1000 numbers drawn from 0--9 . List of 1000 numbers drawn from 0--99 . List of 1000 numbers drawn from 0--999 . List...
-
Quantitative Problem: Bellinger Industries is considering two projects for inclusion in its capital budget, and you have been asked to do the analysis. Both projects' after-tax cash flows are shown...
-
An initial investment of $800 grows in value at a continuous rate of 5.9% per year. What is the doubling time for the investment? Give an exact value, not a decimal approximation.
-
1. A box that weighs 2000N is accelerated uniformly over a horizontal surface at a rate of 8.00 m/s. The opposing force of friction between the box and the surface is 27.4 N. a. Draw a labeled,...
-
During 2024, a company sells 389 units of inventory for $94 each. The company has the following inventory purchase transactions for 2024: Number of Unit Date January 1 May 5 Transaction Beginning...
-
Using the information in the image below, how do I set up a linear programming model for the project plan with these parameters Show how time and cost estimates play into the specification. In...
-
1. DOES AN ACCELERATING OBJECT COVER THE SAME DISTANCE EVERY SECOND THAT IT TRAVELS? EXPLAIN WHY OR WHY NOT.. 2. MAKE TWO SKETCHES (SETS OF DOTS) FOR THE FOLLOWING: A. MARK THE LOCATION OF AN OBJECT...
-
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...
-
Ratios Analyzing Long-Term Firm Solvency The following information is available for Rae Company: Calculate the following: a. 2019 debt-to-equity ratio b. 2019 times-interest-earned ratio c. 2019...
-
Jason Corporation has only common stock outstanding. The firm reported earnings per share of \(\$ 4.00\) for the year. During the year, Jason paid dividends of \(\$ 0.85\) per share. At year end, the...
-
The following information from Buchanan Company's current operations is available: Required a. Prepare a multiple-step income statement. Disregard earnings per share. b. Prepare a single-step income...
Study smarter with the SolutionInn App