Announcements

• 5 Jan. We will be using Piazza for all course announcements and discussions. Register for Piazza using this access code (available only from the ubc.cs domain).

• 4 Jan. First lecture. See you in ICCS 206, 2–3:30. If you have trouble registering online for the course, bring registration waiver forms to the first lecture. Auditors welcome.

Class meetings

• Monday and Wednesday, 2:00–3:30 in ICCS 206

• Term 2 of 2011-2012

Instructor

Michael P. Friedlander, CS 221, (mpf@cs.ubc.ca). Office hours TBD.

Course overview

The main algorithms for the numerical solution of unconstrained and constrained optimization problems. Emphasis on the computational aspects of solving large-scale problems that arise in practice. Unconstrained optimization, linear and quadratic programs, least-squares (including regularization), nonlinearly constrained optimization. Optimality conditions. Newton and quasi-Newton, sequential quadratic programming, penalty function and interior-point methods.

Topics covered

• Background. Optimization problems and classes, convex sets and functions, optimality conditions for unconstrained and constrained problems.

• Unconstrained optimization. Steplength algorithms, steepest descent, Newton and quasi-Newton methods, trust-region methods.

• Linear programming: LP duality, logarithmic-barrier function, primal-dual interior methods.

• Quadratic programming.

• Linearly constrained minimization. Reduced gradient methods, augmented systems.

• Convex optimization. Lagrangian duality,

• Nonlinearly constrained optimization: penalty function methods, sequential quadratic programming (SQP) methods, merit functions

• Software. Implementations, optimization modeling languages (e.g., Ampl and CVX)

• Other topics (time permitting): Lagrangian duality, semidefinite programming: formulation and examples

Prerequisites

No official prerequisites. Students are expected to have a solid background in linear algebra and have to have taken a standard sequence of calculus courses. Please talk to me if you are in doubt.

Texts

No official textbook. These are useful references:

• Boyd & Vandenberghe (2004). A free PDF is available online: Optimization

• Bertsekas (2002), Nonlinear Programming

• Nocedal & Wright (2006), Numerical Optimization

Homework and exams

The homeworks, midterm exam, and final project will contribute equally to your final grade.

• There will be regular homework assignments throughout the term. You are encouraged to collaborate with other students in the course, but you must hand in your own assignments.

• Midterm exam. A closed-book examination near the middle of the term.

• Project. A final project and possible in-class presentation will be due at the end of the term. There are no set rules; the only requirement is that it must involve a substantial application of numerical optimization. You are free to choose your own project. Please see me to discuss your project, or if you need help in choosing one.