CMPUT 670 - Numerical Optimization: Theory and Algorithms

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

References:

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
www.stanford.edu/dept/MSandE/people/faculty/luenberger/linear.html
On reserve in Cameron library

Nonlinear Programming, by Dimitri Bertsekas
www.athenasc.com/nonlinbook.html
On reserve in Cameron library

Convex Optimization, by Stephen Boyd and Lieven Vandenberghe
www.stanford.edu/~boyd/cvxbook.html
Free on the web

Numerical Optimization, by Jorge Nocedal and Stephen Wright
http://www.ece.northwestern.edu/~nocedal/book/num-opt.html

Linear Programming: Foundations and Extensions, by Robert Vanderbei
www.princeton.edu/~rvdb/LPbook/index.html

An Introduction to Linear Programming, by Michael Goemans
http://www-math.mit.edu/~goemans/notes-lp.ps

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