Math 171B (Mathematical Programming)

Course Topics: Numerical methods for nonlinear optimization
Instructor: Prof. Michael Holst (5739 AP&M, mholst@math.ucsd.edu; Office Hours: MW 1-2pm)
TA: Daniel Robinson (VOLUNTEER; 5748 AP&M, drobinso@math.ucsd.edu; Office Hours: W 12:30pm-2:00pm)
Term: Spring 2005
Lecture: 10:00a-10:50a MWF, HSS 1305; Discussion: TBA
Textbook(s): P.E. Gill and M.H. Wright, NUMERICAL OPTIMIZATION, Available at Soft Reserves.
Main Class Webpage: http://ccom.ucsd.edu/~mholst/teaching/ucsd/171b_s05/index.html
Homework Webpage: http://ccom.ucsd.edu/~mholst/teaching/ucsd/171b_s05/hw/index.html



READING AND HOMEWORK SCHEDULE
  • Week 1: (Chapter 1)
    • Mon 3/28:
      • Outline; Motivating 1D examples from calculus; Linear Algebra Review: Vector spaces; linear operators and matrices (rectangular and square); eigenvalues/eigenvectors; various special properties of symmetric matrices.
    • Wed 3/30:
      • Linear Algebra + Calculus: normed spaces and inner-product spaces; convergent and cauchy sequences in R and Rn; continuity of functions in R and Rn.
    • Fri 4/1:
      • Advanced Calculus: Convergence rates of sequences in R and Rn; continuity and differentiation in R and Rn; gradient, Jacobian, and Hessian; Taylor's Theorem and the Taylor Remainder Formula.
      • HW 1 DUE at 5pm Today: Covers Chapter 1. This HW can be found here.
  • Week 2: (Chapter 2)
    • Mon 4/4:
      • Finding zeros of functions of one variable; Newton's method; Finding zeros of functions of several variables; Newton's method in Rn.
    • Wed 4/6:
      • Convergence properties of Newton's method in Rn; some examples;
    • Fri 4/8:
      • General convergence proof for Newton's method in Rn.
  • Week 3: (Chapter 2)
    • Mon 4/11:
      • Making Newton's method more robust: Backtracking and damping.
    • Wed 4/13:
      • Making Newton's method more efficient: approximate Jacobians, the inexact-Newton method.
    • Fri 4/15:
      • Backtracking and damping for inexact Newton; review for Midterm 1.
      • HW 2 DUE at 5pm Today: Covers Chapter 2. This HW can be found here.
      • The MATLAB file newton.m that you need for HW2 can be found here.
  • Week 4: (Chapter 3)
    • Mon 4/18:
      • MIDTERM 1 in Class Today: Covers Chapters 1-2 and Homeworks 1-2.
    • Wed 4/20:
      • Unconstrained optimization: minimization and optimality conditions in one variable.
    • Fri 4/22:
      • Minimization and optimality conditions in several variables; model-based methods for functions of several variables.
  • Week 5: (Chapter 3)
    • Mon 4/25:
      • The quadratic model.
    • Wed 4/27:
      • Convergence of steepest descent and condition numbers.
    • Fri 4/29:
      • (Local) convergence of Newton's method.
  • Week 6: (Chapter 3)
    • Mon 5/2:
      • Fixing Newton via Hessian modification and linesearch.
      • HW 3 DUE at 5pm Today: Covers first half of Chapter 3. This HW can be found here.
      • NOTE: The due date written on HW 3 is 4/29; please ignore this and just have it in by 5/2.
    • Wed 5/4:
      • Review of some matrix theory: spectral decomposition.
    • Fri 5/6:
      • Line-search methods: intro to backtracking.
  • Week 7: (Chapter 3 and first part of Chapter 4)
    • Mon 5/9:
      • Line-search methods: Goldstein-Armijo via linear model
    • Wed 5/11:
      • Line-search methods: Modified Newton; spectral decomposition
    • Fri 5/13:
      • Optimization with equality constraints: Feasible paths, constraints c(x), and constraint jacobian Jc(x).
      • HW 4 DUE at 5pm Today: Covers second half of Chapter 3. This HW can be found here.
  • Week 8: (Chapter 4)
    • Mon 5/16:
      • Tangent cone, Null(Jc), constraint qualification, Karush-Kuhn-Tucker (KKT) conditions.
    • Wed 5/18:
      • The Lagrangian and the method of Lagrange multipliers.
    • Fri 5/20:
      • Quadratic problems w/ equality constraints; optimality conditions; review for Midterm 2.
  • Week 9: (Chapter 4)
    • Mon 5/23:
      • MIDTERM 2 in Class Today: Covers Chapter 3 and Homeworks 3-4.
    • Wed 5/25:
      • Linear equality constraints.
    • Fri 5/27:
      • No Lecture (to be made up in 10th week).
  • Week 10: (Chapter 4 and Review)
    • Mon 5/30:
      • Memorial Day (NO LECTURE).
    • Wed 6/1:
      • Optimization with inequality constraints.
      • HW 5 DUE at 5pm Today: Covers Chapter 4. This HW can be found here.
      • The MATLAB file newbat.m that you need for HW5 can be found here.
    • Fri 6/3:
      • Cummulative Review: Chapters 1-4 and Homeworks 1-5.
[an error occurred while processing this directive]