Computational Methods in Optimization

David Gleich

Purdue University

Spring 2026

Course number CS-52000

Tuesday, Thursday 9:00-10:15

Location Forney B124

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. If you used an LLM on any question, you must explain what you did with the LLM.

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/\log(x)$ when $x = 10^{80}$? What is the limit of the sequence $1/\log(x)$ as $x \to \infty$? What type of convergence is this?

2. I have a child. This individual loves to push the "x^2" key on the calculator repeatedly and see what happens to the number. Let $x_0$ be in $(0,1)$. What is the limit of $x_{k+1} = x_k^2$? Show that this converges quadratically.

3. The other button the child likes to press is \verb#sqrt#. Suppose we have a sequence $x_{k+1} = \sqrt{x_k}$. Show that this sequence converges for all positive inputs $x_0$. What is the rate of convergence.

4. Show, using the definition, that the sequence $1 + k^{-k}$ converges superlinearly to $1$. (To be clear, you need to use the definition to show superlinear convergence.)

5. Ask an LLM about this problem ...

   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?

   Explain what the LLM tells you. Make a plot to illustrate the behavior of this function.

Problem 2: Find the mistake!

The following idea has a critical mistake. Explain what it is.

In class, we developed a way to solve the XKCD raptor problem for a single direction: test a large grid of possible directions and pick the one that is the best.

We expect the XKCD raptor problem to be continuous. If I change the start position of the human, then the optimal angle should continuously change. This idea suggests a strategy to solve the problem. Vary the human starting positions over a grid, then find the optimal direction to run for each of these starting positions. Then, when we need to find the dynamic trajectory, we simply interpolate among these precomputed starting positions, i.e. just look up the nearest starting positions and interpolate the angle to run.

Problem 3: 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 two parts.

1. Modify 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.

OPTIONAL Problem 4:

Work with an LLM to implement a general strategy for raptor problem that finds the actual trajectory.