Fall 2005
Department of Computing Science
University of Alberta
Instructor: Dale Schuurmans, Ath409, x2-4806, dale@cs.ualberta.ca
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)
Newsgroup: ualberta.courses.cmput.670
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.
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 |