Course: MATH 164, Optimization, Lecture 3, Fall 2016
Prerequisite: Math 115A. Not open for credit to students with credit for Electrical Engineering 136.
Course Content: Fundamentals of optimization. Linear programming: basic solutions, algorithms (simplex method, ellipsoid method, interior point methods). Gradient descent, Newton's Method, Conjgate Gradient methods. Least squares. Unconstrainted optimization. Semidefinite programming. Calculus of variations.
Last update: 15 October 2016

Instructor: Steven Heilman, heilman(@-symbol)
Office Hours: Wednesdays 10AM-11AM, Fridays 11AM-12PM, MS 5634
Lecture Meeting Time/Location: Monday, Wednesday and Friday, 1PM-150PM, Geology 6704
TA: Brent Woodhouse,
TA Office Hours: Mondays 11AM-12PM, 2PM-3PM, MS 6153
Discussion Session Meeting Time/Location: Tuesdays, 1PM-150PM, TBD
Recommended Textbook: Chong and Zak, An Introduction to Optimization, 4th Edition, Wiley. (I will never require you to read this book, and I will never assign exercises from this book. So, you could get through the course without buying this book.)
Other Textbooks (not required): Boyd and Vandenbergh, Convex Optimization. (Available Online)
Nocedal and Wright, Numerical Optimization (This book is more advanced, more comprehensive, and more rigorous than the Chong and Zak book.)
Grothschel, Lovasz and Schrijver, Geometric Algorithms and Combinatorial Optimization. (This book is a bit more advanced and a bit more specific, but the topics that it discusses are covered fairly comprehensively.) Also, it might be helpful to the read the introduction of the following article about semidefinite programming: Vandenberghe and Boyd, Semidefinite Programming. (Available Online)
First Midterm: Monday, October 17, 1PM-150PM, Geology 6704
Second Midterm: Wednesday, November 9th, 1PM-150PM, Geology 6704
Final Exam: Tuesday, December 6, 1130AM-230PM, Geology 3656
Other Resources: An introduction to mathematical arguments, Michael Hutchings, An Introduction to Proofs, How to Write Mathematical Arguments
Email Policy:

Exam Procedures: Students must bring their UCLA ID cards to the midterms and to the final exam. Phones must be turned off. Cheating on an exam results in a score of zero on that exam. Exams can be regraded at most 15 days after the date of the exam. This policy extends to homeworks as well. All students are expected to be familiar with the UCLA Student Guide to Academic Integrity. If you are an OSD student, I would encourage you to discuss with me ways that I can improve your learning experience; I would also encourage you to contact the OSD office to confirm your exam arrangements at the beginning of the quarter.
Exam Resources: Here, here and here are pages containing practice exams from other 164 classes. Occasionally these exams will cover slightly different material than this class, or the material will be in a slightly different order, but generally, the concepts should be close if not identical.

Homework Policy: Grading Policy:

Tentative Schedule: (This schedule may change slightly during the course.)

Week Monday Tuesday Wednesday Thursday Friday
0 Sep 23: Introduction; Review of Optimization on the Line
1 Sep 26: 2, 3: Review of Linear Algebra Sep 27: Homework 0 (ungraded) Sep 28: 4.3, 4.5: Convex Geometry, Convex Functions Sep 30: 5.5, Review of Lagrange Multipliers
2 Oct 3: 5.6, Taylor Series, Second Derivative Test Oct 4: Homework 1 due Oct 5: 8.1, Gradient Descent Oct 7: 9.1, Newton's Method
3 Oct 10: 10.1, Conjugate Gradient Oct 11: Homework 2 due Oct 12: 12.1, Least Squares Oct 14: 15.5, Linear Programming
4 Oct 17: Midterm #1 Oct 18: Homework 3 due Oct 19: 15.8, Linear Programming Oct 21: 16.4, Linear Programming Algorithms
5 Oct 24: 16.4, Linear Programming Algorithms Oct 25: Homework 4 due Oct 26: 17.1, Linear Programming Duality Oct 28: 17.2, Linear Programming Duality
6 Oct 31: 22.3, Constrained Optimization Nov 1: Homework 5 due Nov 2: NP Hardness and Complexity Nov 4: Semidefinite Programming
7 Nov 7: Semidefinite Programming Nov 8: No homework due Nov 9: Midterm #2 Nov 11: No class
8 Nov 14: Semidefinite Programming Algorithms Nov 15: Homework 6 due Nov 16: Randomized Algorithms Nov 18: Review of Graph Theory
9 Nov 21: MAX-CUT Nov 22: Homework 7 due Nov 23: Calculus of Variations Nov 25: No class
10 Nov 28: Calculus of Variations Nov 29: Homework 8 due Nov 30: Leeway Dec 2: Review of course

Advice on succeeding in a math class:

Homework Exam Solutions Supplementary Notes