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

Course Learning Objectives (CLO)

 

Students successfully completing the course will be able to...

1. Analyze optimization problems to determine appropriate solution methods, including applying analytical and numerical methods.

2. Apply necessary conditions and sufficient conditions for optimality.

3. Analyze optimization algorithms in terms of properties including descent, convergence, and order of convergence.

4. Make precise statements about optimization problems and their solutions.

 

 

 

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

Version: February 25, 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