a logo for the course

Computational Methods in Optimization

David Gleich

Purdue University

Spring 2017

Course number CS-52000

Tuesday and Thursday, 1:30-2:45pm

Location Lawson B134

Homework 1

Please answer the following questions in complete sentences in submit the solution on Blackboard by the due date there.

Problem 1: Some quick theory

  1. What is when ? What is the limit of the sequence as ?

  2. Show, using the definition, that the sequence converges superlinearly to .

Problem 2: Convergence theory

Consider the function defined by . Show that the sequence of iterates defined by: satisfies for . Show that every point on the unit circle is a limit point for .

Problem 3: Raptors in space

Mr. Munroe (the xkcd author) decided that trapping you with raptors in the plane was too easy for someone that has taken this class.
After all, you did come up with the solution that you should climb a tree to escape them, didn't you?
Your new problem is to solve the generalized raptor problem:

Suppose raptors are positioned at the vertices of a k-dimensional regular simplex. You are at the center 20 m away from the vertices. One of the raptors has a bum leg. Which direction should you run to maximize your survival time?

Checkout wikipedia http://en.wikipedia.org/wiki/Simplex about how to find the coordinates of the raptors in a general space, or just adapt this Matlab code to Julia and use it. http://people.sc.fsu.edu/~jburkardt/m_src/simplex_coordinates/simplex_coordinates1.m

  1. Modify the the Raptor chase example function to compute the survival time of a human in a three-dimensional raptor problem. Show your modified function, and show the survival time when running directly at the slow raptor.

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

  3. Discuss the major challenge for solving this problem with the current strategy in four dimensions.
    (Or if you are feeling ambitious, solve it in 4d, and discuss would might be a problem in 5d.)