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



                             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 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.

  1. 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.)

  2. 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: