Computational methods in optimization

David Gleich

Purdue University

Spring 2012

Course number CS 59000-OPT

Tuesday and Thursday, 3:00-4:15pm

Lawson B134

Homework 1

$\newcommand{\eps}{\varepsilon} \newcommand{\kron}{\otimes} \DeclareMathOperator{\diag}{diag} \DeclareMathOperator{\trace}{trace} \DeclareMathOperator{\rank}{rank} \DeclareMathOperator{\minimize}{minimize} \DeclareMathOperator{\subjectto}{subject to} \newcommand{\mat}[1]{\boldsymbol{#1}} \renewcommand{\vec}[1]{\boldsymbol{\mathrm{#1}}} \newcommand{\vecalt}[1]{\boldsymbol{#1}} \newcommand{\conj}[1]{\overline{#1}} \newcommand{\normof}[1]{\|#1\|} \newcommand{\onormof}[2]{\|#1\|_{#2}} \newcommand{\MIN}[2]{\begin{array}{ll} \minimize_{#1} & {#2} \end{array}} \newcommand{\MINone}[3]{\begin{array}{ll} \minimize_{#1} & {#2} \\ \subjectto & {#3} \end{array}} \newcommand{\OPTone}{\MINone} \newcommand{\itr}[2]{#1^{(#2)}} \newcommand{\itn}[1]{^{(#1)}} \newcommand{\prob}{\mathbb{P}} \newcommand{\probof}[1]{\prob\left\{ #1 \right\}} \newcommand{\pmat}[1]{\begin{pmatrix} #1 \end{pmatrix}} \newcommand{\bmat}[1]{\begin{bmatrix} #1 \end{bmatrix}} \newcommand{\spmat}[1]{\left(\begin{smallmatrix} #1 \end{smallmatrix}\right)} \newcommand{\sbmat}[1]{\left[\begin{smallmatrix} #1 \end{smallmatrix}\right]} \newcommand{\RR}{\mathbb{R}} \newcommand{\CC}{\mathbb{C}} \newcommand{\eye}{\mat{I}} \newcommand{\mA}{\mat{A}} \newcommand{\mB}{\mat{B}} \newcommand{\mC}{\mat{C}} \newcommand{\mD}{\mat{D}} \newcommand{\mE}{\mat{E}} \newcommand{\mF}{\mat{F}} \newcommand{\mG}{\mat{G}} \newcommand{\mH}{\mat{H}} \newcommand{\mI}{\mat{I}} \newcommand{\mJ}{\mat{J}} \newcommand{\mK}{\mat{K}} \newcommand{\mL}{\mat{L}} \newcommand{\mM}{\mat{M}} \newcommand{\mN}{\mat{N}} \newcommand{\mO}{\mat{O}} \newcommand{\mP}{\mat{P}} \newcommand{\mQ}{\mat{Q}} \newcommand{\mR}{\mat{R}} \newcommand{\mS}{\mat{S}} \newcommand{\mT}{\mat{T}} \newcommand{\mU}{\mat{U}} \newcommand{\mV}{\mat{V}} \newcommand{\mW}{\mat{W}} \newcommand{\mX}{\mat{X}} \newcommand{\mY}{\mat{Y}} \newcommand{\mZ}{\mat{Z}} \newcommand{\mLambda}{\mat{\Lambda}} \newcommand{\mPbar}{\bar{\mP}} \newcommand{\ones}{\vec{e}} \newcommand{\va}{\vec{a}} \newcommand{\vb}{\vec{b}} \newcommand{\vc}{\vec{c}} \newcommand{\vd}{\vec{d}} \newcommand{\ve}{\vec{e}} \newcommand{\vf}{\vec{f}} \newcommand{\vg}{\vec{g}} \newcommand{\vh}{\vec{h}} \newcommand{\vi}{\vec{i}} \newcommand{\vj}{\vec{j}} \newcommand{\vk}{\vec{k}} \newcommand{\vl}{\vec{l}} \newcommand{\vm}{\vec{l}} \newcommand{\vn}{\vec{n}} \newcommand{\vo}{\vec{o}} \newcommand{\vp}{\vec{p}} \newcommand{\vq}{\vec{q}} \newcommand{\vr}{\vec{r}} \newcommand{\vs}{\vec{s}} \newcommand{\vt}{\vec{t}} \newcommand{\vu}{\vec{u}} \newcommand{\vv}{\vec{v}} \newcommand{\vw}{\vec{w}} \newcommand{\vx}{\vec{x}} \newcommand{\vy}{\vec{y}} \newcommand{\vz}{\vec{z}} \newcommand{\vpi}{\vecalt{\pi}}$

Please answer the following questions in complete sentences in a typed manuscript and submit the solution to me in class on January 24th, 2012.

Homework 1

Problem 1: Some quick theory

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

Problem 2: Optimization software

We’ll be frequently using software to optimize functions, this question will help familiarize you with two pieces of software: Poblano and the Matlab optimization toolbox.

The function we’ll study is the Rosenbrock function:

$$f(x) = 100(x_2 - x_1^2)^2 + (1-x_1)^2.$$

1. Show a contour plot of this function

2. Write the gradient and Hessian of this function.

3. By inspection, what is the minimizer of this function? (Feel free to find the answer by other means, e.g. looking it up, but make sure you explain why you know that answer must be a global minimizer.)

4. Explain how any optimization package could tell that your solution is a local minimizer.

5. Use Poblano to optimize this function starting from a few different points. Be adversarial if you wish. Does it always get the answer correct? Show your code to use Poblano.

6. Read about Matlab’s fminunc function and determine how to provide it with Hessian and Gradient information. Use this toolbox to optimize the function starting from a few different points. Show your code to use this function.

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?

• 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.

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

1. Modify the raptorchase.m 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 in four dimensions. (Or if you are feeling ambitious, solve it in 4d, and discuss would might be a problem in 5d.)

Problem 4: Convexity

Convex functions are all the rage these days, and one of the interests of students in this class. Let’s do some matrix analysis to show that a function is convex. Solve problem 2.7 in the textbook, which is:

Suppose that $f(x) = x^T Q x$, where $Q$ is an $n \times n$ symmetric positive semi-definite matrix. Show that this function is convex using the definition of convexity, which can be equivalently reformulated:

$$f(y + \alpha(x-y)) - \alpha f(x) - (1-\alpha) f(y) \le 0$$

for all $0 \le \alpha \le 1$ and all $x, y \in \RR^{n}$.

This type of function will frequently arise in our subsequent studies, so it’s an important one to understand.