Math 164: Optimization
Math 164: Optimization
Instructor: Katy Craig, MS 7354, katy•craig•math at gmail • com
Teaching Assistant: Tyler Arant, MS 2361, tylerarant at math • ucla • edu
Lecture/Section/Office Hours: Times and Locations
Textbook: I. Griva, S. Nash, and A. Sofer, Linear and Nonlinear Optimization, second edition.
Other Recommended References:
D. Luenberger and Y. Ye, Linear and Nonlinear Programming. (Free, if you download from the campus network)
S. Boyd and L. Vandenberghe, Convex Optimization. (Free)
Exams: There will be two midterms and one final exam. The examinations will be closed book and closed note. There will be no retaking or rescheduling of exams under any circumstances, as the grading scheme allows you to drop your lowest midterm score.
First Midterm: Wednesday, April 29th, 8:00-8:50AM
Second Midterm: Wednesday, May 27th, 8:00-8:50AM
Final Exam: Friday, June 12th, 11:30AM-2:30PM
Grading Scheme: homework: 10%, highest midterm score: 40%, final: 50%
If you have questions about the grading of any assignment or exam, you have one week after it is handed back to request a regrade.
Prerequisites: Math 115A
Outline of Course:
Part 1: linear optimization Part 2: nonlinear optimization
• fundamentals of optimization • unconstrained optimization
• geometry of linear programming • linear (in)equality constraints
• the simplex method • Lagrange multipliers
• duality • nonlinear (in)equality constraints
Syllabus:
read by today topic
1 Mar 30 (M): 1.1-1.5 Optimization: applications and the need for theory
2 Apr 1 (W): 2.2 Feasibility and optimality
3 Apr 3 (F): 2.3 (without 2.3.1) Convexity, part 1
4 Apr 6 (M): - Convexity, part 2
5 Apr 8 W): 3.1 Linear constraints and the geometry of the feasible region
6 Apr 10 (F): 4.1 Geometry of linear programming
7 Apr 13 (M): 4.2 Standard form
8 Apr 15 (W): 4.3 Basic solutions and extreme points, part 1
9 Apr 17 (F): - Basic solutions and extreme points, part 2
10 Apr 20 (M): 4.4 Representation of solutions, part 1
11 Apr 22 (W): - Representation of solutions, part 2
12 Apr 24 (F): 5.2 The simplex method, part 1
13 Apr 27 (M): - The simplex method, part 2
14 Apr 29 (W): - First midterm, covering lectures 1-12
15 May 1 (F): - The simplex method, part 3
16 May 4 (M): 6.1, 6.2 The dual linear program, interpretation of the dual
17 May 6 (W): - Duality theory
18 May 8 (F): 6.2.1, 6.2.2 Complementary slackness, part 1
19 May 11 (M): - Complementary slackness, part 2
20 May 13 (W): B.4, 2.3.1, 2.6 Derivatives and convexity
21 May 15 (F): B.7 More derivatives and convexity
22 May 18 (M): 3.2 Null and range spaces
23 May 20 (W): 11.2 Optimality conditions: unconstrained optimization
24 May 22 (F): 14.2 Optimality conditions: linear equality constraints, part 1
25 May 25 (M): - Happy Memorial Day!
26 May 27 (W): - Second midterm, covering lectures 13-24
27 May 29 (F): - Optimality conditions: linear equality constraints, part 2
28 June 1 (M): 14.3 Lagrange multipliers and the Lagrangian, part 1
29 June 3 (W): - Lagrange multipliers and the Lagrangian, part 2
30 June 5 (F): 14.4 Optimality conditions: linear inequality constraints
- June 12 (F): Final exam, covering lectures 1-30, 11:30AM-2:30PM
Homework:
• Homework assignments will be posted on this website and collected Friday during lecture.
• Only the problems marked with an asterisk should be submitted for grading.
• At least one problem on each of the exams will be chosen from the non-asterisked homework problems.
•No late homework will be accepted. (Talk to me if you transfer into the course partway through the quarter, and we’ll work something out.)
•The lowest two homework grades will be dropped and will not count toward the final grade.
Homework 1 (due April 3rd): HW1.pdf
Homework 2 (due April 10th): HW2.pdf
Homework 3 (due April 17th): HW3.pdf
Homework 4 (due April 24th): HW4.pdf, HW4_Corrected.pdf
Here is a practice midterm, based on the midterms I gave in fall 2014:
Your midterm will be a littler harder than this practice one, closer in difficulty to the homework problems. (I gave this midterm before I realized how smart you UCLA kids are!!) The best thing you can do to study for this midterm is to work all of the non-asterisked homework problems (particularly on HW 4.5) and review your class notes. Ignore the last problem on the practice midterm -- we have not covered this yet.
Homework 4.5 (extra practice for midterm, not to be turned in): HW4p5.pdf
Homework 5 (due May 8th): HW5.pdf
Homework 6 (due May 15th): HW6.pdf, HW6_Corrected.pdf In Q7 (a), the constraint in the dual problem should read "yB-yC+yBC>=0", not "yC-yB+yBC>=0".
Homework 7 (due May 22nd): HW7.pdf, HW7_Corrected.pdf
Here is a practice midterm, based on the midterm I gave in fall 2014:
Your midterm will be shorter than the practice one, closer in length to the first midterm. I think it would be very useful for you to work all the problems on this practice midterm. It will also be helpful to work all the non-asterisked homework problems, especially those on HW 7.5.
Homework 7.5 (extra practice for midterm, not to be turned in): HW7p5.pdf
Homework 8 (due June 5th): HW8.pdf
Homework 8.5 (extra practice for final, not to be turned in): HW8_5.pdf, HW8_5_Corrected.pdf
Here is a practice final, based on the final I gave in fall 2015: