Math 484: Nonlinear Programming (Spring 2019)

Mikhail Lavrov


Archiving note

This is an archived version of a class I taught at the University of Illinois Urbana-Champaign. For a while after I left, it remained on UIUC's website, but it was taken down when some subdomains got shuffled around. I think these are pretty okay lecture notes, and I know some people found them useful later, so I've decided to archive them on my personal webpage. If you spot any mistakes, please let me know.


Location

Grading

The course grade will be calculated as follows, out of 660 points total:

You can check your grades via Moodle.

Your grade total will be converted to a letter grade according to the following scale:

A+ ≥ 630 B+ ≥ 520 C+ ≥ 450 D+ ≥ 380
A ≥ 570 B ≥ 490 C ≥ 420 D ≥ 350
A- ≥ 540 B- ≥ 470 C- ≥ 400 D- ≥ 330

It is possible to take the course for 4 credits rather than 3, at the cost of extra homework questions and more difficult exams. If you want to do this, you need to register at the math office in Altgeld Hall soon after the start of the course.

Homework

There will be 10 homework assignments, to be turned in at the beginning of class the day they are due. Of these homework assignments, the top 8 homework scores will determine your grade. Each assignment is graded out of 20 points, for a total of 160.

If you cannot attend class, you can submit a scanned copy or a photo of your homework as a PDF file by e-mail before class begins. Please avoid doing this unless it's necessary, since it is more work for the grader.

If the homework assignment is received after class on the due date, but before the next class, it will be accepted as late, for a 2-point penalty. Homework will not be accepted after the next class for any reason.

Exams

There will be three evening midterm exams: Wednesday 2/6, Wednesday 3/6, and Wednesday 4/10 from 7pm to 8:30pm in 241 Altgeld Hall. Correspondingly, three lectures will be canceled, not necessarily in the same week as the midterm exams. The first of these is already marked in the syllabus below.

The final exam will be Thursday 5/9 from 7pm to 10pm in 347 Altgeld Hall (our usual classroom).

Detailed syllabus

The course follows the textbook The Mathematics of Nonlinear Programming by A. Peressini, F. Sullivan and J. Uhl. The syllabus below will initially describe a tentative plan for what parts of the textbook will be covered when. As the semester progresses, I will update the syllabus with information about what actually happened in class, adjustments to my plans for the future, and links to homework assignments.

Date Chapter Details Homework/Exams
Mon January 14 Chapter 1
Calculus
Section 1.1: 1D Optimization
Wed January 16 Section 1.2: Geometry of ℝn
Fri January 18 No class
Mon January 21 MLK Day: no class
Wed January 23 Section 1.2: Critical points in ℝn
Fri January 25 Section 1.3, 1.5: Positive definite matrices HW 1 due
Mon January 28 Section 1.3: Sylvester's criterion
Wed January 30 "Local minimizer" day: no class
Fri February 1 Section 1.4: Closed and bounded sets
Mon February 4 Chapter 2
Convex Functions
Section 2.1: Convex sets HW 2 due
Wed February 6 Section 2.3: Convex functions Exam: 7pm in 241 AH (Topics)
Fri February 8 Section 2.3: Building convex functions
Mon February 11 Section 2.3: Jensen's inequality
Wed February 13 Section 2.4: AM-GM inequality
Fri February 15 Section 2.5: Geometric programming HW 3 due
Mon February 18 Section 2.5: Solving the dual GP
Wed February 20 Chapter 4
Least Squares
Section 4.1: Interpolation and best-fit lines
Fri February 22 Section 4.2: Least-squares fit and projections HW 4 due
Mon February 25 Section 4.1: Orthogonal matrices
Wed February 27 Section 4.3: Minimum-norm solutions
Fri March 1 Section 4.4: Generalized inner products HW 5 due
Mon March 4 Chapter 5
The KKT Theorem
Section 5.1: The obtuse angle criterion
Wed March 6 Section 5.1: The separation theorem Exam: 7pm in 241 AH (Topics)
Fri March 8 No class
Mon March 11 Section 5.1: The support theorem; subgradients
Wed March 13 Section 5.2: Convex programming
Fri March 15 Section 5.2: The KKT theorem HW 6 due
Mon March 18Spring break: no class
Wed March 20
Fri March 22
Mon March 25 Chapter 5
Convex Programming
Section 5.2: KKT, gradient form
Wed March 27 Section 5.4: KKT duality
Fri March 29 Section 5.3: Finding dual constraints HW 7 due
Mon April 1 Section 5.3: Geometric programming, again
Wed April 3 Chapter 6
Penalty Methods
Section 6.1: Intro to penalty methods
Fri April 5 Section 6.2: Guaranteeing optimality HW 8 due
Mon April 8 Section 6.2: More on coercive functions
Wed April 10 Section 6.3: KKT and the penalty method Exam: 7pm in 241 AH (Topics)
Fri April 12 Equality constraints
Mon April 15 Chapter 3
Iterative Methods
Section 3.1: Newton's method
Wed April 17 Section 3.1: Newton's method in ℝn
Fri April 19 Section 3.2: The steepest descent method HW 9 due
Mon April 22 Section 3.3: More general descent methods
Wed April 24 Section 3.3: Using descent methods
Fri April 26 Section 3.4: Broyden's method
Mon April 29 Other stuff KKT for local minimizers HW 10 due
Wed May 1 Exam review (optional)
Thu May 9 Final Exam (Topics)

Last updated May 1, 2019. Mikhail Lavrov <misha.p.l@gmail.com>