Computational Methods in Optimization

David Gleich

Purdue University

Spring 2023

Course number CS-52000

Monday, Wednesday, Friday, 1:30-2:20pm

Location Lawson 1106

Homework 1

Please answer the following questions in complete sentences in a clearly prepared manuscript and submit the solution by the due date on Gradescope.

Remember that this is a graduate class. There may be elements of the problem statements that require you to fill in appropriate assumptions. You are also responsible for determining what evidence to include. An answer alone is rarely sufficient, but neither is an overly verbose description required. Use your judgement to focus your discussion on the most interesting pieces. The answer to "should I include 'something' in my solution?" will almost always be: Yes, if you think it helps support your answer.

Problem 0: List your collaborators

Please identify anyone, whether or not they are in the class, with whom you discussed your homework. This problem is worth 1 point, but on a multiplicative scale.

Problem 1: Some quick, simple theory

1. What is $1/\sqrt(x)$ when $x = 10^9$? What is the limit of the sequence $1/\sqrt(x)$ as $x \to \infty$? What type of convergence is this?

2. Show, using the definition, that the sequence $1 + k^{-k}$ converges superlinearly to $1$.

3. Suppose we have a sequence $x_{k+1} = \sqrt{x_k}$. Show that this sequence converges for all positive inputs $\vx_0$_. What is the the rate of convergence.

4. Let $z = 9$. Consider the sequence $$x_{k+1} = (1/2) x_k (3 - z x_k^2), x_0 = 1/2.$$ Show that this converges and give the convergence type (algebra, linear, quadratic, etc.)

5. (A little more interesting, note that I haven't yet worked out the answer to this one; it may be well-known in other areas, etc. Don't feel obliged to compute a full solution, but for full points you must show your investigation. ) Suppose we have a sequence $x_{k+1} = |\log{x_k}|$. Does this converge for any input? For all inputs? For some? What else can you say about it? Are there limit points?

Problem 2: Angled raptors

Mr. Munroe (the xkcd author) decided that running in a single direction was unrealistic. Your new problem is to solve the generalized raptor problem where you can turn twice. Once at 0.25 seconds. A second time at 0.75 seconds. Otherwise the problem is the same.

• Ignore all acceleration, like we did in class.
• The slow raptor runs at 10 m/s
• The fast raptors run at 15 m/s
• You run at 6 m/s
• A raptor will catch you if you are within 20 centimeters.
• You can turn instantaneously.

There are three parts.

1. Modify the the Raptor chase example function to compute the survival time of a human in a raptor problem where you switch direction at 0.25 seconds and 0.75 seconds. Show your modified function, and show the survival time when running directly at the slow raptor (up to time 0.25) and then reversing your direction and running away from it.

2. Utilize a grid-search strategy to determine the best angles for the human to run to maximize the survival time. Show the angles.

3. Discuss the major challenge for solving this problem with the current strategy if we added a fourth angle at 0.5 seconds. (Or do so!) And a fifth angle at 0.75 seconds. (Or if you are feeling ambitious, solve these and see where you start running into trouble and discuss why that is!