ECE 520/MATH 520 Lecture and Homework Schedule, Spring 2019 | Version: January 2, 2019 |
|||

Session |
Date |
Topic | Chapter |
Homework Due |

1 | 1/22 | Introduction. Examples. Math preliminary: Notation, real vector spaces, linear independence, matrices. | 1,2 | |

2 | 1/24 | 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 | |

3 | 1/29 | Definition of optimization problem and types of solutions. Quadratic problems. FONC. | 6 | |

4 | 1/31 | SONC and SOSC. Basic iterative algorithms: form, basic properties, line search. | 6 | |

5 | 2/5 | 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 |

6 | 2/7 | Multi-dimensional algorithms. Gradient methods: form, steepest descent, convergence. | 8 | |

7 | 2/12 | Gradient methods: convergence of fixed step size algorithm, steepest descent algorithm. Order of convergence. | 8 | |

8 | 2/14 | Newton's method: form, order of convergence. Properties of general algorithms. | 9 | |

9 | 2/19 | 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 |

10 | 2/21 | Quasi-Newton methods: form, properties, rank one formula. | 11 | |

11 | 2/26 | Quasi-Newton methods: DFP and BFGS. | 11 | |

12 | 2/28 | Least squares problems: basic properties, grammian, examples. | 12 | |

13 | 3/5 | RLS. Parameter identification. | 12 | 10.1, 10.7, 10.10, 11.1, 11.13 |

14 | 3/7 | Exam 1 | ||

15 | 3/12 | Randomized search. Simulated annealing. Genetic algorithm: Intro, representation schemes, selection. | 14 | |

16 | 3/14 | Genetic algorithm: evolution (crossover & mutation). Algorithms for constrained problems: projection, penalty method. | 14,23 | |

17 | 3/26 | 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) |

18 | 3/28 | Linear programming: converting to standard form. Linear equations, elementary row operations, basic solutions. | 15,16 | |

19 | 4/2 | Basic feasible solutions. Fundamental theorem of LP. Pivoting, changing bases and canonical augmented matrix. | 16 | |

20 | 4/4 | Moving from one BFS to an adjacent BFS. Reduced cost coefficients. Simplex algorithm. Matrix form of simplex. | 16 | |

21 | 4/9 | 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 |

22 | 4/11 | Weak duality lemma, duality theorem, duality and Simplex algorithm, complementary slackness. Equivalence of feasibility and LP problems. | 17 | |

23 | 4/16 | General equality constraints: basic form, example. Lagrange condition for scalar equality constraint. | 17,20 | |

24 | 4/18 | Exam 2 | 20 | |

25 | 4/23 | General multivariable Lagrange condition. Tangent and normal space. | 20 | 17.3, 17.8, 17.13, 20.8a, 20.14, 20.15a, 20.20a |

26 | 4/25 | Minimizing quadratic subject to linear constraint (quadratic programming). Simple linear quadratic regulator problem. Second order conditions. | ||

27 | 4/30 | General equality and inequality constraints: form, example. KKT condition with only inequality constraints. Examples. | 21 | |

28 | 5/2 | KKT condition for equality and inequality constraints. SONC. | 21 | |

29 | 5/7 | SOSC. Convex optimization problems. | 21,22 | 20.8b,c, 20.15b,c, 20.20b, 21.11, 21.12, 21.17, 22.3, 22.14 |

30 | 5/9 | Exam 3 | 22 | |