Math 171B (Introduction to Numerical Optimization: Nonlinear Problems)

Course Topics: Numerical methods for nonlinear optimization
Instructor: Prof. Michael Holst (5739 AP&M,; Normal Office Hours: Mon 2-4pm; Finals: Tue (6/12/12) 1-3pm)
Term: Spring 2012
Lecture: 1:00p-1:50p MWF, AP&M B412
TA: Shi (Fox) Cheng (5760 AP&M,; Office Hours: 4:30p-5:30p Tu-Fri)
Discussion: 6:00p-6:50p, B412 AP&M
Main Class Webpage:
Textbook(s): P.E. Gill and M.H. Wright, Numerical Optimization, Available at Soft Reserves.
Printable Syllabus: Can be found [ here ].

CATALOG DESCRIPTION: 171B. Introduction to Numerical Optimization: Nonlinear Problems (4)
Convergence of sequences in Rn, multivariate Taylor series. Bisection and related methods for nonlinear equations in one variable. Newton’s methods for nonlinear equations in one and many variables. Unconstrained optimization and Newton’s method. Equality-constrained optimization, Kuhn-Tucker theorem. Inequality-constrained optimization. Three lectures, one recitation. Knowledge of programming recommended. (Credit not allowed for both Math 171B and Econ 172B.) Prerequisites: Math 171A.

COURSE INFORMATION: Problems in all areas of mathematics, science, and engineering can be posed as optimization problems. An optimization problem begins with a set of independent variables or parameters, and often includes a set of side conditions which define acceptable values of the variables for the particular application. These side conditions are known as constraints. The second component of an optimization problem is a measure of goodness called the objective function, which depends in some way on the constrained variables. The solution of an optimization problem is a (possibly non-unique) set of allowed values of the independent variables for which the objective function reaches its "optimal" (maximal or minimal) value. While Math 171A dealt mainly with linear programming, Math 171B deals mainly with nonlinear programming. This involves the minimization of a nonlinear objective function, possibly subject to nonlinear constraints in the form of equalities or inequalities. For historical reasons, this subject area is often called mathematical programming. The modern terminology for this subject is simply optimization, and the numerical algorithms we study form the subject of numerical optimization.

GRADES, HOMEWORKS, EXAMS, AND IMPORTANT DATES: Course information, such as homework assignments, due dates, and exam dates, will be maintained on the class webpage. Note that I sometimes make minor changes to the homework assignments as the quarter progresses, based on how much I am able to cover in the lectures. Therefore, CHECK THE WEBPAGE FREQUENTLY. The course will be graded on the homework assignments, two midterm examinations and a final examination, according to the following guidelines:

Written and Computer HW (five homeworks): 20% of grade
Midterm #1 (In class week 4, FRI 4/27, AP&M B412): 20% of grade
Midterm #2 (In class week 8, FRI 5/25, AP&M B412): 20% of grade
Final (11:30a-2:29p THU 6/14, AP&M B412) 40% of grade

Here are some other important dates:

First lecture: MON 4/2
Last lecture: FRI 6/8
Finals week: MON-FRI, 6/11-6/15
Holiday: MON 5/28 (Memorial Day -- NO LECTURE)

There will be five homework assignments throughout the quarter. The first midterm will be based on homeworks 1 and 2. The second midterm will be based on homeworks 3 and 4. The final will be cummulative and based on homeworks 1-4, as well as a small amount of new material from homework 5. The following policies regarding homeworks and exams will be applied:
  1. The default plan is to have all HW assignments count towards the final grade in the class.
    UPDATE 06/12/2012: The CAPE response rate has now exceeded our target of 70% (we hit 88.24%). As promised, in return for your help with getting a good sample size for the CAPES, I WILL now drop your single lowest homework score. Your grade for the homework will then be the average of just your four best scores. Thanks again to all of you for helping get a good CAPE response; it helps me improve as an instructor.
  2. In order to receive credit on a homework, you must at least attempt the computer parts of the homework assignments (if there are any).
  3. There will be no make-up exams. If you miss a midterm with an excused absence (i.e., illness with a note from a doctor), the other midterm and the final exam will be weighted accordingly.
  4. You are not allowed (and will not need) to use a calculator on midterms or finals.
  5. You are allowed to bring a single 8x11 sheet of paper containing notes on both sides (formulas, whatever you find useful) to each midterm and to the final. My view is that this allows you to focus on learning how to do the problems and understanding the material, rather than on memorizing formulas.
  6. Hint for Midterms and Final: The questions on all three exams should look very familiar. I will make most of the problems on all three exams look very much like the homework problems; in some cases, they will be exactly the same as some of the homework problems, and in other cases, they will be minor variations of homeworks. (I will put at least one slightly more challenging problem on each exam, which is not just a variation of a homework problem; this ensures that everyone will have some challenge on the exam.)

LECTURES: The lectures will follow the textbook quite closely. Homework assignments will be a combination of theoretical and computer problems; this will require some computer programming using MATLAB. The TA will be able to assist you in accessing your computer accounts as well as MATLAB.

Week Topics Covered
Week 1

Topics: Chapter 1.

Week 2

Topics: Chapter 1-2.
Homework 1 due WED 4/18.

Week 3

Topics: Chapter 2.

Week 4

Topics: Chapters 2-3 and Midterm.
Homework 2 due WED 4/25.
Midterm 1 given in class on Friday 4/27. Covers: Homeworks 1 and 2 (Chapters 1-2).

Week 5

Topics: Chapter 3.

Week 6

Topics: Chapter 3.
Homework 3 due FRI 5/11.

Week 7

Topics: Chapter 3.

Week 8

Topics: Chapters 3-4 and Midterm.
Homework 4 due WED 5/23.
Midterm 2 given in class on Friday 5/25. Covers: Homeworks 3 and 4 (Chapter 3).

Week 9

Topics: Chapter 4.

Week 10

Topics: Chapter 4 and Review for Final.
Homework 5 due FRI 6/8.

SAT 6/9
AP&M B402

Review Session: The TA (Fox Cheng) will be giving a special 1-hour review for the final.
THU 6/14
AP&M B412

Final Exam: Covers Homeworks 1-5 (Chapters 1-4).