CSC466-2305 Numerical Methods for Optimization Problems

Winter 2024 Bulletin board for csc466-2305 Winter 2024 -- course outline -- MarkUs

Course information for current students:

Textbook web page (see educational modules)

Material to be covered in the course (with textbook sections in parentheses) 

2024-01-09 (2 hours)
1.   Introduction
1.1  Scope of the course
1.2  Vectors and matrices [N+W A.1]
1.3  Eigenvalues and eigenvectors [N+W A.1]
2024-01-11 (1 hour)
1.4  Norms and inner products [N+W A.1]
     Condition number of a matrix [N+W A.1]
2024-01-16 (2 hours)
1.5  Rate of convergence of sequences [N+W A.2]
1.6  Convexity [N+W Ch 1]
1.7  Gradient, Hessian, Jacobian, directional derivative, steepest descent direction [N+W A.2]
1.8  Mean Value Theorem, Taylor's Theorem [N+W A.2]
1.9  Global, local, etc, minimizers, conditions for optimality [N+W 2.1]
2024-01-18 (1 hour)
1.10 Finite difference approximations to derivatives [~N+W 8.1]
1.11 O(h) and O(n) notations, convergence of a discretization method [N+W A.2]

2024-01-23 (2 hours)
2.1  Optimization problems and methods (general) [N+W Ch 1]
2.2  1D opt: Golden section search method [Heath 6.4]
2.3  1D opt: Successive parabolic interpolation [Heath 6.4]
2.4  1D opt: Newton's [Heath 6.4]
2024-01-25 (1 hour)
2.5  Optimization methods in multiple dimensions (general) [N+W 2.2]
2.6  multi-dim opt: Steepest descent direction [N+W 2.2]
2.7  multi-dim opt: Descent directions [N+W 2.2]
2.8  multi-dim opt: Newton's direction [N+W 2.2]
2.9  multi-dim opt: Quasi-Newton's directions, and approximations to Hessian inverse [N+W 2.2]
2024-01-30 (2 hours)
2.9  multi-dim opt: Quasi-Newton's directions, and approximations to Hessian inverse [N+W 2.2] (end)
2.10 multi-dim opt: Conjugate gradient direction [N+W 2.2]
2.11 Quadratic function, gradient, Hessian and linear system

3.1  Line-search methods - picking a stepsize [N+W 3.1]
3.2  The Wolfe conditions, sufficient decrease and curvature [N+W 3.1]
3.3  The strong Wolfe conditions [N+W 3.1]
     Existence of intervals of stepsizes satisfying the (strong) Wolfe conditions
2024-02-01 (1 hour)
3.4  The Goldstein conditions [N+W 3.1]
3.5  Simple backtracking algorithm for stepsize [N+W 3.1]
2024-02-06 (2 hours)
3.6  Convergence of line-search methods [N+W 3.2]
     Zoutendjik theorem
3.7  Steepest descent with exact line search [N+W 3.3]
     Rate of convergence
3.8  Newton's convergence and rate [N+W 3.3]
3.9  Quasi-Newton methods' convergence and rate [N+W 3.3]
2024-02-08 (1 hour)
3.10 Newton's: modifications to Hessian [N+W 3.4]
     Eigenvalue modification
     Diagonal shift
     Modified Cholesky factorization
     Modified symmetric indefinite factorization
2024-02-13 (2 hours)
3.11 More on backtracking algorithms for calculating the stepsize [N+W 3.5]
     Initial condition
     Algo to satisfy the Wolfe conditions

4.1  Trust region methods [N+W 4.0]
     Validity of model and region, generic algorithm
4.2  Constrained minimization of quadratic - complementarity problem [N+W 4.0]
4.3  Constrained minimization of quadratic - Cauchy point [N+W 4.1]
4.4  Constrained minimization of quadratic - Dogleg method [N+W 4.1]
4.5  Constrained minimization of quadratic - two-dim subspace minimization [N+W 4.1]
4.6  Convergence of trust region - reduction by Cauchy point and other [N+W 4.2]
2024-02-15 (1 hour)
A1 discussion

reading week

2024-02-27 (2 hours)
term test
2024-02-29 (1 hour)
4.6  Convergence of trust region - reduction by Cauchy point and other [N+W 4.2]
4.7  Convergence of trust region to stationary points [N+W 4.2]
4.8  Constrained minimization of quadratic - complementarity problem [N+W 4.3]
4.9  Convergence of trust region (rate) [N+W 4.4]
4.10 Other (scaling, norms) [N+W 4.5]

2024-03-05 (2 hours)
5.   Conjugate gradient method [N+W 5.]
5.1  Intro and motivation
5.2  Conjugate direction method
5.3  Gram-Schmidt orthogonalization
5.4  Properties of conjugate direction methods
2024-03-07 (1 hour)
5.5  Conjugate gradient method
     first version of CG algorithm
     efficient/practical version of CG algorithm
     convergence of CG method (rate)
     comparison with steepest descent
     convergence of CG method: eigenvalues
2024-03-12 (2 hours)
5.6  Preconditioning
     ILU, IC, SSOR
5.7  Preconditioned conjugate gradient (PCG) algorithm
5.8  Nonlinear conjugate gradient methods
     Fletcher-Reeves, Polak-Ribi`ere, PR+, FR-PR,
     Hestenes-Stiefel, Y. Dai - Y. Yuan, W. W. Hager - H. Zhang
     Restarts and quality control
5.9  FR convergence, PR+, FR-PR, DY, HZ
     PR convergence and non-convergence

2024-03-14 (1 hour)
6.   (more on) Quasi-Newton methods
6.1  The DFP method -- derivation of update
6.2  The BFGS method -- update, algorithm, initialization, pitfalls
2024-03-19 (2 hours)
6.2  The BFGS method -- update, algorithm, initialization, pitfalls (cont)
6.3  The damped BFGS update
6.4  The SR1 method -- update, properties
6.5  The Broyden class methods -- update, restricted class, properties
6.6  Convergence of BFGS -- restricted Broyden, rate

2024-03-21 (1 hour)
7.   Large-scale optimization
7.1  Inexact Newton methods
7.2  Convergence of inexact Newton, rate
7.3  Line search Newton-CG (truncated Newton) method
7.4  Hessian-free computation
2024-03-26 (2 hours)
7.5  Trust region Newton-CG (CG-Steihaug) method
7.6  Limited memory quasi-Newton methods: L-BFGS, two-loops recursion
7.7  Relation between L-BFGS and nonlinear CG (Hestenes-Stiefel)
7.8  Sparse quasi-Newton updates
7.9  Partially separable functions

2024-03-28 (1 hour)
9.   Derivative-free optimization
9.1  Model-based methods
9.2  Simplex-based methods: Nedler-Mead method
no more classes!

Notes and handouts:
Note on use of notes: Notes will be available when the course starts. While it may be convenient to study for the course by reading the notes, it should be made clear that the notes are not there to substitute the textbook or any relevant book. Notes are always more condensed and give less overall information than books.
Notes with math notation, etc, are difficult to read online. It may be preferable for some of you to print out the 4-page style notes on paper (preferably double-sided).

Access to the data below requires that you type in your CDF (teaching labs) username (same as UTorId) and last 5 digits of your student number as password. This password (for accessing the website) cannot be reset.

Lecture notes

Assignments Other