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