**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)ucla.edu

**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, bwoodhouse729@gmail.com

**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:**

- My email address for this course is heilman(@-symbol)ucla.edu
- It is your responsibility to make sure you are receiving emails from heilman(@-symbol)ucla.edu , and they are not being sent to your spam folder.
- Do NOT email me with questions that can be answered from the syllabus.

- Late homework is not accepted.
- If you still want to turn in late homework, then the number of minutes late, divided by ten, will be deducted from the score. (The time estimate is not guaranteed to be accurate.)
- The lowest two homework scores will be dropped. This policy is meant to account for illnesses, emergencies, etc.
- Do not submit homework via email.
- There will be 8 homework assignments, assigned weekly on Tuesday and
turned
in at the
**beginning**of the discussion section on the following Tuesday. - A random subset of the homework problems will be graded each week. However, it is strongly recommended that you try to complete the entire homework assignment.
- You may use whatever resources you want to do the homework, including computers, textbooks, friends, the TA, etc. However, I would discourage any over-reliance on search technology such as Google, since its overuse could degrade your learning experience. By the end of the quarter, you should be able to do the entire homework on your own, without any external help..
- All homework assignments must be
**written by you**, i.e. you cannot copy someone else's solution verbatim. - Homework solutions will be posted on Friday after the homework is turned in.

- The final grade is weighted as the larger of the following two schemes. Scheme 1: homework (15%), the first midterm (20%), the second midterm (25%), and the final (40%). Scheme 2: homework (15%), largest midterm grade (35%), final (50%). The grade for the semester will be curved. However, anyone who exceeds my expectations in the class by showing A-level performance on the exams and homeworks will receive an A for the class.
- We will use the MyUCLA gradebook.
- If you cannot attend one of the exams, you must notify me within the first two weeks of the start of the quarter. Later requests for rescheduling will most likely be denied.
- You must attend the final exam to pass the course.

** 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:**

- Review the relevant course material
**before**you come to lecture. Consider reviewing course material a week or two before the semester starts. - When reading mathematics, use a pencil and paper to sketch the calculations that are performed by the author.
- Come to class with questions, so you can get more out of the
lecture. Also, finish your homework at
least
**two days**before it is due, to alleviate deadline stress. - Write a rough draft and a separate final draft for your homework. This procedure will help you catch mistakes. Also, consider typesetting your homework. Here is a template .tex file if you want to get started typesetting.
- If you are having difficulty with the material or a particular homework problem, review Polya's Problem Solving Strategies, and come to office hours.