Course plan for Optimization in Physical and ICT Systems

The lectures will be held over a period of 7 weeks (Q1).

The lecture plan below is tentative and changes may be made during the course. (White => 2015 version, Dark gray => updated 2016 version)

Note, [CZ] refers to either 3. edition or 4. edition, the text is the same. [CZ 3e]  refers to 3. edition and [CZ 4e] refers to the 4. edition.  

 

Course plan Optimization in Physical and ICT Systems

Lecture Date Week Topic Reading Homework Assigned
1 30/8 1/35 Introduction to Optimization
  • Introduction and course outline
  • Math preliminaries
  • Matrix Games
TXT1
[CZ]: Chap. 1,
[CZ]: Chap. 2,
[Lay]: Sec. 9.1

Powerpoint Lecture 1

Intersting lecture:
How We Teach Computers to Understand Pictures | Fei Fei Li | TED Talk.: https://www.youtube.com/watch?v=40riCqvRoMs
HW1
[Lay] Sec 9.1: 1, 7, 9, 15, 19.
The following 2 exercises are extras, you may need results from [CZ], Chap. 3 to solve 2.6/2.8.
 [CZ, 3e]: 1.5, 2.6
[CZ, 4e]: 1.5, 2.8(Theory covered in [CZ], Chap. 3)
Solutions HW1
2 2/9 1/35 Linear programming
  • Geometric method
  • Simplex method
TXT2
[Lay]: Sec. 9.2,9.3
(also covered in
[CZ]: Sec. 15.1-15.3, 15.5-15.8
[CZ]: Sec. 16.1-16.4, 16.7)

MatLab Demos

PowerPoint Lecture 2
HW2
[Lay] Sec. 9.2: 3, 5, 15, 16
[Lay] Sec. 9.3: 3, 9, 10

Solutions HW2
3 6/9 2/36 Linear programming
  • Simplex Method
  • Duality
TXT3
[Lay]: Sec. 9.3, 9.4,
(also covered in
[CZ]: Chap. 17)

MatLab Demos

PowerPoint Lecture 3
HW3
[Lay] Sec. 9.2: 11
[Lay] Sec. 9.4: 11, 21

Solutions HW3

Extra assigment  and solution, HW3, LP
9/9 2/36 Unconstrained optimization
      
Basics of set-constrained and unconstrained  optimization
  • Mathematical preliminaries
  • First and second order conditions
TXT4
[CZ]: Chap. 5 (not Sec. 5.1)
[CZ]: Chap. 6

MatLab Demos

PowerPoint Lecture 4
HW4
[CZ, 3e]: 5.8, 5.9 a., b.
[CZ, 4e]: 5.9, 5.10 a., b. 
[CZ, 3e]: 6.2, 6.7, 6.8, 6.9, 6.18, 6.21
[CZ, 4e]: 6.3, 6.8, 6.10, 6.11, 6.20, 6.23
Quadratic forms exercises 10, 11, 12

Solutions HW4, v3

Solutions to "Quadratic forms exercises 9, 10, 11, 12
5 13/9 3/37

Unconstrained optimization
     1D search methods

  • Golden section search
  • Fibonnaci search
  • Newtons method
TXT5
[CZ, 3e]: Chap. 7 (skip pp. 110-113)
[CZ, 4e]: Chap. 7 (skip pp. 112m - 116 122m-124m, 125-126)

MatLab Demos

PowerPoint Lecture 5

Taylor polynomial applet


(Nice paper using Line Search)
HW5
[CZ 3e]: 7.2 a., b., 7.3, 7.9
[CZ 4e]: 7.2 a., b., 7.3, 7.10


Solutions HW5


Extra assigment and solution, HW5, Golden Search
6 16/9 3/37 Unconstrained optimization
Gradient methods
  • The method of steepest descent
  • Analysis of gradient methods
TXT6
[CZ]: Chap.8. In section 8.3 we skip details in proofs, we focus on the results stated in Thm. 8.2, Thm. 8.3, Thm 8.4.

Review of linear algebra: eigenvalues and quadatic forms.
[CZ]: Sec. 3.1, 3.2,
[CZ, 3e]: p. 29 upper half.
[CZ, 4e]: p. 31 upper half.
[CZ]: Thm. 3.7.
[CZ, 3e]: pp. 36-37 Rayleigh's Ineq.
[CZ, 4e]: pp. 38-39 Rayleigh's Ineq.

MatLab Demos

PowerPoint Lecture 6

 
HW6
[CZ, 3e]: 8.7, 8.15, 8.20, 8.24, 8.25
[CZ, 4e]: 8.8, 8.16, 8.21, 8.25, 8.26
[CZ]: 3.15, 3.18

Solutions HW6, v2

Another solution of [CZ, 4e] 8.25
7 20/9 4/38 Unconstrained optimization
Newtons method
  • Newtons method in nD
  • Analysis of Newton's method
  • Levenberg-Marquards modification
  • Newton's method for nonlinear least square
TXT7
[CZ]: Chap. 9

MatLab Demos

Powerpointslides Lecture 7

Examples on Gauss Newton form the lecture (sse also demos)
HW7
[CZ]: 9.1 a., b. and c., 9.3, 9.4
Get the Levenberg-Marquardt algorithm working for example 9.3 in[CZ] (generate your own data set). Matlab code is available for the LM algortime in the toolbox immoptibox form dtu (marquardt and smarquardt). You can download the toolbox and manual here.

Solutions HW7
8 23/9 4/38 Unconstrained optimization
Conjugate directions methods and  Quasi-Newton methods
  • The conjugate direction algorithm
  • The conjugate gradient algorithm
  • quasi-newton methods
TXT8
[CZ]: Chap. 10 (skip proof).
[CZ, 3e]: Section 11.1, Rank one algorithm pp. 192-193, DFP algorithm pp. 196-197.
[CZ, 4e]: Section 11.1, Rank one algorithm pp. 198-199, DFP algorithm pp. 202-203.


Some of you may find it helpful to complement your reading with the following (not part of the curriculum:
Painless-conjugate-gradient

In "Introduction to Optimization and Data Fitting", by K. Madsen and H.B. Nielsen, you will find a nice section on Quasi-Newton methods (section 3.3).

Top 10 Algorithms

Powerpointslides Lecture 8

HW8
[CZ, 3e]: 10.5, 10.9
[CZ, 4e]: 10.5, 10.10
Study the gui demo in the demo folder CZ, Chap 10, Conjugate Direction Methods

[CZ]: 11.2


Solutions HW8




9 27/9 5/39

Solving Linear equations
Examples and basic properties

  • Examples and basic properties
  • Least-square analysis
  • Recursive least squares algorithms
  • Kaczmarz's algorithm
TXT9
[CZ]: Sec. 12.1, 12.2, 12.3, 12.4 (only The Kaczmarz algortim, i.e. 1. page in sec. 12.4), Theorem 12.6 (p. 235 in [CZ, 3e], p. 242 in [CZ, 4e]).

Leon sec. 7.4

MatLab Demos

Powerpointslides Lecture 9

HW9
[CZ]: 12.2, 12.4

Soultions HW9

10 30/9 5/39 Global search algorithms
  • Simulated annealing
  • Particle Swarm Optimization
TXT10
[CZ]: Sect.14.1, 14.3, 14.4

MatLab demos

Powerpointslides Lecture 10

Udacity, AI in Robotics : https://www.udacity.com/course/artificial-intelligence-for-robotics--cs373

I showed you the trailer, and 1:25 min in the video in the intro. section on particle filters.

ParticlesDIY (bring PC with MatLab )
HW10
[CZ]: 14.2, 14.3

Solutions HW10

Extra assigment and solution, HW10, PSO



Compulsory assignment, Fall2016

11 4/10 6/40 Global search algortihms
  • Genetic algorithms
TXT11
[CZ]: Sect. 14. 5  (no proofs in analyses section, only interpretation of Lemma 14.1 and Thm. 14.1)

MatLab demos

Powerpointslides Lecture 11

Examples from the class:
http://rogeralsing.com/2010/02/14/genetic-programming-code-smarter-than-you/

Eureqa

Eureqa data
HW11
[CZ]: 14.12 (any programming language will do)

Solutions HW11 (download ga_demo)

12 7/10 6/40 Nonlinear constrained optimization
  • Lagrange multiplies
TXT12
[CZ, 3e]: Chap 19. In section 19.5 only Thm. 19.4 (no proof), 19.5 (no proof).
[CZ, 4e]: Chap 20, in section 20.5 only Thm. 20.4 (no proof), 20.5 (no proof).


Powerpointslides Lecture 12

Jurgen Schmidhuber
http://people.idsia.ch/~juergen/
http://people.idsia.ch/~juergen/deeplearningwinsMICCAIgrandchallenge.html

HW12
[CZ, 3e]: 19.1, 19.4.
[CZ, 4e]: 20.2, 20.6

Solutions HW12
13 11/10 7/41 Summing up

Please mail suggestions for the summery lectures to: hka@eng.au.dk.  
*

Powerpointslides Lecture 13

Compulsory assignment, Fall2016
Draft of soultion to compulsory assignment, Fall2016

Written exam 2015

Summery exercises
14 14/10 7/41 Summing up *


Updated 27-10-16, by HKa