ECE 520/MATH 520 Course Learning Objectives, and Lecture/Homework Schedule

ECE 520/MATH 520 Lecture and Homework Schedule, Spring 2020

Version: September 09, 2020

Session

Date

Topic

Chapter

Homework Due

CLO

1

1/21

Introduction. Examples. Math preliminary: Notation, real vector spaces, linear independence, matrices.

1,2

1,4

2

1/23

Math preliminary: Inner product, norm. Eigenvalues and eigenvectors, quadratic forms, calculus of several variables, chain rule, Taylor series, gradient, level sets, directional derivative.

3,5

4

3

1/28

Definition of optimization problem and types of solutions. Quadratic problems. FONC.

6

1,2,4

4

1/30

SONC and SOSC. Basic iterative algorithms: form, basic properties, line search.

6

2,3

5

2/4

One-dimensional search methods: Golden section search, Newton's method, secant method.

7

1.5, 2.9, 3.6, 3.17a, 5.6, 5.9, 5.10, 6.3, 6.8, 6.19, 6.29

3

6

2/6

Multi-dimensional algorithms. Gradient methods: form, steepest descent, convergence.

8

3

7

2/11

Gradient methods: convergence of fixed step size algorithm, steepest descent algorithm. Order of convergence.

8

3

8

2/13

Newton's method: form, order of convergence. Properties of general algorithms.

9

3

9

2/18

Conjugate direction methods: form, properties, conjugate gradient formulas.

10

7.2a,b,d, 8.1, 8.6, 8.18, 8.24, 9.1, 9.4

3

10

2/20

Quasi-Newton methods: form, properties, rank one formula.

11

3

11

2/25

Quasi-Newton methods: DFP and BFGS.

11

3

12

2/27

Least squares problems: basic properties, grammian, examples.

12

1.3,4

13

3/3

RLS. Parameter identification.

12

10.1, 10.7, 10.10, 11.1, 11.13

3,4

14

3/5

Randomized search. Simulated annealing. Genetic algorithm: Intro, representation schemes, selection.

14

1,3

15

3/10

Exam 1

16

3/12

Genetic algorithm: evolution (crossover & mutation). Algorithms for constrained problems: projection, penalty method.

14,23

1,3

17

3/24

Constrained optimization: basic form with equality and inequality constraints. Intro to linear programs, geometric view, standard form.

15

12.3, 12.10, 12.12, 12.14, 12.15, 23.11a (Hint: solution is A^T(A.A^T)^{-1}.b; see Section 12.3)

1,4

18

3/26

Linear programming: converting to standard form. Linear equations, elementary row operations, basic solutions.

15,16

3

19

3/31

Basic feasible solutions. Fundamental theorem of LP. Pivoting, changing bases and canonical augmented matrix.

16

3

20

4/2

Moving from one BFS to an adjacent BFS. Reduced cost coefficients. Simplex algorithm. Matrix form of simplex.

16

3

21

4/7

Artificial problem and feasibility. Two phase algorithm. Duality: form, example.

16,17

15.1, 15.7, 15.10, 16.3, 16.4, 16.13, 16.14

3,4

22

4/9

Weak duality lemma, duality theorem, duality and Simplex algorithm, complementary slackness. Equivalence of feasibility and LP problems.

17

1,4

23

4/14

General equality constraints: basic form, example. Lagrange condition for scalar equality constraint.

17,20

2,4

24

4/16

Exam 2

20

25

4/21

General multivariable Lagrange condition. Tangent and normal space.

20

17.3, 17.8, 17.13, 20.8a, 20.14, 20.15a, 20.20a

1,2,4

26

4/23

Minimizing quadratic subject to linear constraint (quadratic programming). Simple linear quadratic regulator problem. Second order conditions.

2,4

27

4/28

General equality and inequality constraints: form, example. KKT condition with only inequality constraints. Examples.

21

2,4

28

4/30

KKT condition for equality and inequality constraints. SONC.

21

2

29

5/5

SOSC. Convex optimization problems.

21,22

20.8b,c, 20.15b,c, 20.20b, 21.11, 21.12, 21.17, 22.3, 22.14

1,2,4

30

5/7

Exam 3

22