ECE 174 Intro to Linear & Nonlinear Optimization Ken Kreutz-Delgado ECE Department UCSD2 Contact Information Course Website • Accessible from http://dsp.ucsd.edu/~kreutz Instructor • Ken Kreutz-Delgado [email protected] Office Hour: Wednesday, Noon-1pm, EBU-I 5605 Teaching Assistant (Tutor/Reader) • Sujitha Martin, [email protected] (Office hours TBD) Administrative Assistant • Travis Spackman [email protected] (858) 822-4697, EBU-I 56003 Textbook Matrix Analysis & Applied Linear Algebra Carl D. Meyer, SIAM, 2000 3rd printing is latest Copyright-marked version downloadable from: www.matrixanalysis.com/DownloadChapters.html Supplemental Texts • Linear Algebra, 4th Edition S. Lipschutz & M Lipson Schaum’s Outlines, McGraw-Hill, 2009 • Linear Algebra and its Applications, 4th Edition G. Strang, Brooks Cole, 20054 Course Objectives How to think geometrically in vector-valued signal and data spaces. How to solve linear and nonlinear inverse problems using basic quadratic optimization techniques. • How to use abstract geometric thinking when solving linear and nonlinear inverse problems in signal and data spaces. Become comfortable with the process of moving back-and-forth between abstract mathematical solution techniques and practical engineering problems. • At the end of the quarter students will be able to apply abstract mathematical concepts to practical engineering problems.5 Assumed Course Background It is assumed that students know the material from linear algebra well. As well as basic complex variables and (some) probability. The goal of this course is not to teach fundamental concepts of linear algebra (which you are assumed to already know from Math 20F, or the equivalent). The goal is to ensure that students are comfortable with the underlying geometric concepts associated with linear mappings between inner-product vector spaces and linear inverse problems encountered in many different application domains in engineering and science. Because the students are assumed to already know linear algebra, the course reading and homework will not be assigned in the order of presentation given in the textbook.6 Assumed Programming Skills It is assumed that students know Matlab or an equivalent high-level design-oriented programming language well. Proficiency in Matlab or the equivalent is needed to perform the mandatory computer assignments which will comprise 15% of your total, overall grade.7 Course Performance Evaluation 15% Homework. 15% Computer Projects. 30% Midterm Exam. 40% Final Exam. This breakdown is firm and non-negotiable. • Homework (15%) is graded “A for Actual Effort”. You get full credit merely for turning it in and if it is evident that you worked on all of the problems. You get partial (or even zero) credit if you are missing problems or it is clear that no real good faith effort was expended in attempting to solve the homework problems. You get no credit if you don’t turn in the homework. Note that the individual problems are not corrected or graded. • Computer assignments (15%) are rigorously graded for correctness of content and results, and for quality of the reports. • Midterm (30%) and Final (40%) are rigorously graded for correctness of derivations and results. • Final exam is scheduled for Friday, December 9, 2011, 7-10pm. This date and time is firm and non-negotiable.8 Student Collaboration & Cheating Students are allowed to discuss homework problems. • Individual write-ups must be turned in. • Not understanding homework solutions will hurt you on the midterm and final exams which together comprise 70% of the overall course grade. Computer project reports and coding must be done individually. You are allowed to discuss the projects. • Code and written reports must be turned in. • Identical, or unreasonably similar, overlap of code between two students will be perceived as cheating. Exams are closed notes and closed book. Aggressive administrative action will be taken against students caught cheating. .9 Course Topics - I Overview of (constrained and unconstrained) linear least squares and nonlinear optimization. • Discussion of real-world linear and non-linear inverse problems encountered in engineering drawn from circuit analysis, robotics, GPS, and signal processing. Signal spaces as abstract vector spaces and matrices as representing linear mappings between signal spaces. Under- and over-constrained linear systems of equations and linear inverse problems. • Well-posed and ill-posed linear inverse problems. Constrained and unconstrained quadratic optimization of linear systems (the "linear least squares" problem). .10 Course Topics - II Solutions to the linear least squares problem. • Relationship to the four fundamental subspaces of linear algebra. • The projection theorem, adjoint operators, the normal equation, generalized inverses, & the Moore-Penrose pseudoinverse. The Singular Value Decomposition (SVD) . • SVD and the four fundamental subspaces of linear algebra. • Use of the SVD to solve linear inverse problems and to obtain the Moore-Penrose pseudoinverse. Quadratic forms and weighted least-squares • Use in modeling energy, power, and uncertainty quantities encountered in engineering applications. • The weighted least squares problem and its relationship to the problem of maximum likelihood (MLE) estimation in statistics. .11 Course Topics - III Nonlinear least squares theory. • Vector differentiation and Hessians. • Necessary & sufficient conditions for an optimum to exist. Linearization-based nonlinear optimization techniques. • Iterative optimization techniques, including steepest descent, Gauss's method, and Newton's method. • Constrained nonlinear optimization and the method of Lagrange multipliers (time permitting). .12 Computer Programming Assignments (Two projects) For each assignment students will turn in an “Engineering Technical Report” • You should write these up assuming that you will show them to prospective employers during job interviews. • Students have had positive responses in interviews. Linear least-squares project. • Speech compression via differential coding. Nonlinear least-squares project. • GPS positioning.