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 4

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: Log-barrier terms

The basis of a class of methods known as interior point methods is that we can handle non-negativity constraints such as by solving a sequence of unconstrained problems where we add the function to the objective. Thus, we convert into

  1. Explain why this idea could work. (Hint: there's a very useful picture you should probably show here!)

  2. Write a matrix expression for the gradient and Hessian of in terms of the gradient vector and the Hessian matrix of .

Problem 2: Inequality constraints

Draw a picture of the feasible region for the constraints:

Problem 3: Necessary and sufficient conditions

Let .

  1. Write down the necessary conditions for the problem:

  2. Write down the sufficient conditions for the same problem.

  3. Consider the two-dimensional case with Determine the solution to this problem by any means you can, and justify your work.

  4. Produce a Julia or hand illustration of the solution showing the function contours, and gradient. What are the active constraints at the solution? What is the value of in ?

Problem 4: Constraints can make a non-smooth problem smooth.

Show that

can be reformulated as a constrained optimization problem with a continuously differentiable objective function and both linear equality and inequality constraints.