CISC371, Nonlinear Optimization: Lectures


These lectures are approximately aligned with classes in the course notes. There may be differences between the notes and the videos because these evolve over time.

Prerequisite material is overviewed in a series of videos that are available under the "Prerequisites" topic in the navigation bar, which is to the left of this text.

The lectures were produced using technology that is described in this video:

No. PDF Video
Week   1
1 Class #01 Introduction To Optimization
1a Course Overview
1b Examples: Fermat's Problem
1c Open Sets; Interior And Boundary Points
1d Minimizers and Minima
2 Class #02 Minimizing By Approximation
2a Approximation Of Data
2b Polynomial Models
2c Vandermonde Matrix For Quadratics
2d Quadratic Examples
3 Class #03 Minimizing By Approximation
3a Stationarity
3b Conditions for Stationarity
3c Convexity; Strict Convexity
3d Gradient Inequality And Convexity
Week   2
4 Class #04 Scalar Minimization
4a Searching For A Scalar Minimizer
4b Searching With A Fixed Stepsize
4c Searching With a Variable Stepsize
4d Armijo Backtracking
5 Class #05 Functions With A Vector Argument
5a Functions of Multiple Variables
5b The 1-Form as Linear Algebra
5c Directional Derivative and the Chain Rule
5d Gradient 1-Form And Jacobian Matrix
5e Linear Forms And Quadratic Forms
5f Level Curves
6 Class #06 Stationary Points
6a Stationarity Example
6b Conditions For Stationarity
6c Second Derivative And Hessian Matrix
6d Eigenvalues Of A Hessian Matrix
Week   3
7 Test #1 Basic Scalar Optimization
8 Class #08 Methods Using Steepest Descent
8a Introduction To Descent
8b Descent Directions
8c Fixed-Stepsize Descent
8d Backtracking Descent
9 Class #09 Newton's Method
9a Scaling Methods
9b Manual Scaling
9c Newton's Method
9d Damped Newton's Method
Week   4
10 Class #10 Nonlinear Least Squares
10a GPS As Vector Optimization
10b Descent Methods for NLS Problems
10c The Levenberg-Marquardt Algorithm
10d Fermat-Weber Problems
11 Class #11 Linear Algebra For Neural Networks
11a New Matrix New Products
11b Quantization And The Heaviside Function
11c Vectorization Of Matrices
11d Kronecker Product
11e Layer With Two Neurons
11f Hadamard Product
12 Class #12 Single Artificial Neuron
12a Terms And Symbols For Neural Networks
12b Activation Functions
12c Steepest Descent For One Observation
12d Batches Of Data
Week   5
13 Test #2 Adaptive Vector Optimization
14 Class #14 Artificial Neural Networks
14a Simple Neural Network
14b Network Formulation
14c Network Vectorization
14d Steepest Descent For Simple Network
14e Batches Of Data And Exclusive-Or Example
15 Class #15 Back-Propagation Of Scale Factors
15a Fundamental Algorithm Of Neural Networks
15b Hadamard Product For Simplification
15c Chain Rule And Back-Propagation
15d Example Computations
Holiday Special
Week   6
16 Class #16 Convexity And Level Sets
16a Monotonicity And Convexity
16b Convex Functions
16c Convex Sets
16d Level Sets
16e Gradient Inequality
17 Class #17 Constrained Optimization
17a Constraint Properties For A Minimizer
17b Linear Constraints
17c Linear Objective Functions
17d Convex Problems
18 Class #18 Lagrange Multipliers
18a Objective Gradient And Property Gradient
18b Quadratic Objective And Quadratic Constraint
18c Linear Objective And Non-Convex Constraint
18d Existence Of Lagrange Multipliers
Week   7
19 Class #19 The Lagrange Equations
19a Single Linear Constraint
19b Quadratic Objective With Linear Constraints
19c Example Mechanical System
19d Matrix Form Of Quadratic Problems
20 Class #20 Dual Formulation of Lagrange Equations
20a Primal Form And Feasible Set
20b Min-Max And Max-Min Expressions
20c Closed Form For Minimization Step
20d Dual Formulation For Quadratic Problems
21 Class #21 Quadratic Examples Of Dual Formulation
21a Dual Formulation And Smaller Matrices
21b Squared-Norm Objective Function
21c Example Mechanical System
21d 3D Example
21e Extra: Hessian Matrix
Week   8
22 Test #3 Nonlinear Least Squares and Neural Networks
23 Class #23 KKT Conditions For Constrained Optimization
23a Linear Inequality Constraints
23b Examples Of Linear Inequalities
23c KKT Background And Examples
23d Definition Of A KKT Point
24 Class #24 Geometry At KKT Points
24a Algebraic Interpretation Of Lagrange Multipliers
24b KKT Geometry Of Inactive Linear Inequalities
24c KKT Geometry Of Active Linear Inequalities
24d KKT Geometry Of Linear Equality
Week   9
25 Class #25 Constrained Least Squares
25a Ordinary Least Squares Problem
25b Constrained Least Squares Problem
25c KKT Conditions For Constrained Least Squares
26 Class #26 Tikhonov Regularization
26a Objective With Quadratic Constraint
26b Parameters For Tikhonov Regularization
26c Discrete Total Variation Problem
26d Tikhonov Regularization For Denoising
27 Class #27 The Lasso And Related Regularization
27a Regularization For Standardized Data
27b Ridge Regression And Lasso Regularization
27c Lasso Selects Variables And Constrains Regression
27d Elastic Net Blends Ridge Regression And Lasso
Week   10
28 Test #4 KKT Conditions and Constrained Least Squares
29 Class #29 The Support Vector Machine (SVM)
29a Hyperplane Classification
29b Hyperplane Optimization Using Support Vectors
29c Hyperplane Margins
29d Primal Formulation Of SVM
30 Class #30 Primal And Dual Formulations Of The SVM
30a Design Matrix And Label Matrix
30b Vectorization Of SVM Primal Formulation
30c Dual Formulation Of SVM
Week   11
31 Class #31 Slack Variables And Dual Formulations
31a Separable Data Not Linearly Separable
31b Slack Variables And Inequality Constraints
31c Slack Variables In SVM Primal Formulation
31d Slack Variables In SVM Dual Formulation
32 Class #32 Gram Matrix For Nonlinear SVM
32a Nonlinearly Separable Data
32b Kernel Functions
32c Gram Matrix And The Kernel Trick
33 Class #33 The Kernel Trick For SVM
33a Convex Problem For Lagrange Multipliers
33b Classifying Observations And The Kernel Trick
33c Examples Using Gaussian Kernels
Week   12
34 Test #5 The Lasso and Support Vector Machines
35 Class #35 Course Summary
Symbols Symbols used in these notes

Queen's University is situated on traditional Anishinaabe and Haudenosaunee Territory.

Last updated