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

Course Topics: Numerical methods for nonlinear optimization
Instructor: Prof. Michael Holst (5739 AP&M, mholst@math.ucsd.edu; Office Hours: Wed 1-2p)
Term: Spring 2015
Lecture: 12-12:50p MWF, Peterson 102
TA: Francesca Grogan (5760 AP&M, fgrogan@ucsd.edu; Office Hours: 3-4p W, 11a-12p Th)
Discussion: Contact the TA for details.
Main Class Webpage: http://ccom.ucsd.edu/~mholst/teaching/ucsd/171b_s15/index.html
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/24, Peterson 102): 20% of grade Midterm #2 (In class week 8, FRI 5/22, Peterson 102): 20% of grade Final (11:30a-2:30p, WED 6/10, Peterson 102) 40% of grade

Here are some other important dates:

 First lecture: MON 3/30 Last lecture: FRI 6/5 Finals week: MON-FRI, 6/8-6/12 Holiday: MON 5/25 (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.
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.)

MAGICAL CHALK: If you recall, toward the end of the quarter I brought in a piece of what I referred to as "magical chalk", which is a type of chalk that is rummored to be "so powerful that mathematics practically writes itself; a chalk so amazing that no incorrect proof can be written using this chalk". (If I recall, that was the one lecture where I did not make any mistakes...) The chalk is made by a company called Hagoromo in Japan. Mathematicians around the world have been buying this chalk from Hagaromo for more than 80 years to give themselves an edge, similar to how competitive athletes go to great lengths to give themselves an edge using performance enhancing substances. Sadly, the company is going out of business, and mathematicians around the world are in a panic, and are hoarding this chalk. (I managed to score a single box for \$17 in late May; that same box is now selling for \$69, shipped from Japan.) Here is an article on Gizmodo.com about this amazing chalk, and the implications for mathematics when it is no longer available.

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(3/30-4/3) Topics: Chapter 1. Week 2(4/6-4/10) Topics: Chapter 2. Homework 1 due FRI 4/10. Week 3(4/13-4/17) Topics: Chapter 2. Week 4(4/20-4/24) Topics: Chapter 2, Review, and Midterm. Homework 2 due WED 4/22. Midterm 1 given in class on Friday 4/24. Covers: Homeworks 1 and 2 (Chapters 1-2). Week 5(4/27-5/1) Topics: Chapter 3. Week 6(5/4-5/8) Topics: Chapter 3. Homework 3 due FRI 5/8. Week 7(5/11-5/15) Topics: Chapter 3. Week 8(5/18-5/22) Topics: Chapter 3, Review, and Midterm. Homework 4 due WED 5/20. Midterm 2 given in class on Friday 5/22. Covers: Homeworks 3 and 4 (Chapter 3). Week 9(5/25-5/59) Topics: Chapter 4. Week 10(6/1-6/5) Topics: Chapter 4 and Review for Final. Homework 5 due FRI 6/5. FinalDATE: WED 6/10TIME: 11:30a-2:30pPLACE: Peterson 102 Final Exam: Covers Homeworks 1-5 (Chapters 1-4).

HOMEWORKS ASSIGNMENTS: The following are the five homework assignments. Each homework consists of exercises listed below.

Homework 1 Exercises (Midterm 1 is based on these problems):
• Homework 1 can be found [ here ].
• Homework 1 solutions are posted [ here ].

Homework 2 Exercises (Midterm 1 is based on these problems):
• Homework 2 can be found [ here ].
The MATLAB m-file you need for the homework is [ here ].
• Homework 2 solutions are posted [ here ].
A working implementation of Newton's Method with backtracking is [ here ].

Homework 3 Exercises (Midterm 2 is based on these problems):
• Homework 3 can be found [ here ].
• Homework 3 solutions are posted [ here ].
A working implementation of Steepest Descent (with backtracking) is [ here ].

Homework 4 Exercises (Midterm 2 is based on these problems):
• Homework 4 can be found [ here ].
• Homework 4 solutions are posted [ here ].
A working implementation of Modified Newton is [ here ].

Homework 5 Exercises (Final is based on these problems as well as being cummulative):
• Homework 5 can be found [ here ].
The MATLAB m-file you need for the homework is ``newbat.m'' from HW2 posted above.
(Or, you can modify ``newmod.m'' from HW4, also posted above.)
• Homework 5 solutions are posted [ here ].