CMPUT 670 - Numerical Optimization: Theory and Algorithms

Fall 2005
Department of Computing Science
University of Alberta

Instructor: Dale Schuurmans, Ath409, x2-4806,
Room: AF 1-13
Time: TR 11:00-12:30
Office hours: W 1:15-2:00, R 12:30-1:30 (or by appointment)


Optimization is a central problem in computing science.

Obviously it is good to do things optimally. However, doing so effectively requires algorithms for solving well posed problems. A good example of the pervasiveness of optimization in computing science is machine learning, where almost every problem involves optimization at its core---be it training neural networks, support vector machines, decision trees, or solving Markov decision processes. However, optimization problems arise in every area of computing science, including networking (routing), databases (query optimization), computer vision (matching, recognition), computer games---you name it. In fact, optimization forms one of the core topics of theoretical computing science, both in terms of complexity and approximation analysis, and in terms of algorithm design (although much, but not all, work in theoretical computing science is focused primarily on discrete optimization).

This course will cover the fundamental concepts and key algorithms of continuous optimization. Although it might seem peculiar to focus on continuous optimization in a computing science course, these problems are pervasive in most areas of applied computing, and moreover, form the foundation for many key ideas in discrete optimization. (Plus, the algorithms are very powerful, and problems you can solve with them are amazingly cool.) The goal of this course is to provide a familiarity with the key algorithmic ideas of continuous optimization, with a particular emphasis on convex methods that have been developed in the past decade. Topics covered include the basics, like gradient descent, convergence, and higher-order (Newton) methods, but emphasis will be placed on more advanced topics like global optimization and constrained optimization---including linear, quadratic, semidefinite and general convex programming. (Some attention will be paid to discrete optimization problems as the course progresses.) Covering algorithmic ideas effectively also requires attention to be paid to the efficiency and accuracy of the various techniques.

Although there are no formal prerequisites for this course, much of the material is necessarily based on multivariable calculus and linear algebra, but I fully expect to fill in this background as the course proceeds. Nevertheless, a willingness to re-acquire linear algebra and calculus concepts, particularly when it becomes obvious that they will be extremely useful, will be most helpful.

Course work:
3 Assignments 20% each Assignment 1 (updated 13/10/2005) (data1.mat) (data1-v4.mat for older versions of Matlab)
Assignment 2 (updated 30/10/2005) (data2.mat) (data2-v4.mat for older versions of Matlab) (a2test.mat)
Assignment 3 (updated 24/11/2005) (data3.mat) (data3-v4.mat for older versions of Matlab)
Project 40% Project handout
Link to Yuxi's project description


There will be no official text for this course. Most of the material will be covered in lecture notes and supplementary excerpts that will be provided.

Supplementary References:

Linear and Nonlinear Programming, 2nd Edition, by David Luenberger
On reserve in Cameron library

Nonlinear Programming, by Dimitri Bertsekas
On reserve in Cameron library

Convex Optimization, by Stephen Boyd and Lieven Vandenberghe
Free on the web

Numerical Optimization, by Jorge Nocedal and Stephen Wright

Linear Programming: Foundations and Extensions, by Robert Vanderbei

An Introduction to Linear Programming, by Michael Goemans

Background References:

The Mathematics of Nonlinear Programming, by A. Peressini, F. Sullivan and J. Uhl Jr.
Available in the bookstore

Introduction to Probability Models, by S. M. Ross.

Course outline

Lecture 1 Introduction Thur Sep 8
Lecture 2 1-dimensional optimization Tues Sep 13
Part 1 Unconstrained Optimization
Lecture 3 Quadratic optimization Thur Sep 15
Lecture 4 Convexity Tues Sep 20
Lecture 5 Convex optimization Thur Sep 22
Lecture 6 Local optimality and local optimization Tues Sep 27
Lecture 7 Convergence analysis, time complexity Thur Sep 29 A1 out
Lecture 8 Convexification Tues Oct 4
Part 2 Global Optimization
Lecture 9 Simulated annealing, convergence Thur Oct 6
Lecture 10 Deterministic annealing, homotopy, continuation Tues Oct 11
Lecture 11 Adversarial perturbation, GAs Thur Oct 13 A1 due
Lecture 12 Bayesian methods Tues Oct 18 A2 out
Dan's noisy function optimization lecture
Part 3 Constrained Optimization
Lecture 13 Lagrange multipliers, equilibrium, KKT conditions Thur Oct 20
Lecture 14 Linear equality constraints Tues Nov 1 A2 due
Lecture 15 Linear programming Thur Nov 3
Yuxi's linear programming lecture
Lecture 16 Quadratic programming Tues Nov 8
Lecture 17 Interior point, barrier methods Thur Nov 10
Lecture 18 Semidefinite programming Tues Nov 15 A3 out
Lecture 19 Geometric programming, SOCPs, QCQPs Thur Nov 17
Lecture 20 Non-convex programming Tues Nov 22
Part 4 Integer Optimization
Lecture 21 Integer programming, branch and bound, relaxation Thur Nov 24
Lecture 22 Integer linear, quadratic programming Tues Nov 29 A3 due
Lecture 23 General integer optimization Thur Dec 1
Tues Dec 6 Project due