Continuous optimization

o   Form groups of three on Moodle before lecture in week 2 if you have preferences, and we will propose random assignments to complete groups where needed.

o   HW is done in groups, but I highly recommend that you all learn all aspects of the assignments.

o   Expect 3 homework assignments.

o   You get ~3-4 weeks for each. They are a lot of work: get to them early.

o   First one distributed in week 2 (tbc).

Break

So far, for constrained optimization, we have only discussed one algorithm: projected gradient descent. That is fine if the constraint set S is convex and easy-to-project-to, but that leaves a lot to be desired.

For a few weeks now, we have discussed the case where S is described by equality and inequality constraints (h(x) = 0 and g(x) <= 0). Can we design algorithms that would handle those?

The answer is yes, but it is a bit subtle. We will discuss two different methods: a first, fairly obvious one; then a second, more advanced one that tries to address the shortcomings of the obvious idea.

• Lecture 12a, Quadratic penalty methods, 27 minutes
  
• Lecture 12b, A basic theorem for penalty methods, 20 minutes
  
• Lecture 12c, What's wrong with quadratic penalties?, 21 minutes
  
• Lecture 12d, Augmented Lagrangian methods, 20 minutes
  

This week, we consider a few different optimization software packages for Matlab. The lecture is an interactive software demo, and the exercise session gives you a chance to explore that software.

If you want to try things out for yourself during lecture, it's useful if you install the following ahead of time:

CVX: http://cvxr.com/cvx/download/  :  unzip then run cvx_setup

Manopt: https://www.manopt.org/downloads.html  :  unzip then run importmanopt

Example scripts are below.

Basics of semidefinite programming, and illustration with Max-Cut.