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 2

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

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: 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:

  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 Optim.jl (or Poblano for Matlab, or Scikit.learn for python) 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.

Problem 2: Optimization theory

Suppose that (i.e. is univariate) and is four times continuously differentiable. Show that the following conditions imply that is a local minimizer.

i.
ii.
iii.
iv.

Problem 3: Optimization software

Repeat all the steps for problem 1 for the Himmelbrau function

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 , where is an symmetric positive semi-definite matrix. Show that this function is convex using the definition of convexity, which can be equivalently reformulated: for all and all .

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