Welcome to the second week! In Week 2, we will encounter our first iterative optimization algorithm, gradient descent. We discuss the notion of descent direction, how to choose a good step length, and how to evaluate the speed of an algorithms through the notion of rates of convergence.

The first problem sheet has also been released and can be found under Assignments. As mentioned before, it contains a Part A which is discussed in the tutorial class, and a Part B for you to work at home. Programming tasks are for enhancing your understanding and to help you develop some practical skills, but will not feature in the exam or the midterm test. The Jupyter notebook version of the problem sheet contains some space in which you can insert your solutions if you like.

Learning outcomes

  • Understand the concept of an iterative descent algorithms and strategies for step length selection.
  • Understand gradient descent in the special case of a quadratic function.
  • Be familiar with the notion of rates of convergence.

Tasks and Materials

  • Try to work on the problems from the new problem sheet (to be found under Assignments)

Further reading

  • Lecture 3: Section 3.1 from (2), Section Section 9.1 from (1)
  • Lecture 4: Section 3.3 from (2), Section 1.2.3 from (3)

Literature

  1. Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
  2. Jorge Nocedal and Stephen J.Wright. Numerical Optimization. Springer, 2006.
  3. Yuri Nesterov. Introductory Lectures on Convex Optimization. A basic course. Springer, 2004.
  4. Aaron Ben-Tal and Akadi Nemirovski. Lectures on Modern Convex Optimization. 2013.