Minerva CS164 Optimization Methods

Logistics (Fall 2024)

• Pre-requisites: Minerva CS113 Linear Algebra (Spring 2023), Minerva CS111 Single and Multivariable Calculus (Fall 2022)
• Syllabus
  • Textbook: Kochenderfer, M. J., & Wheeler, T. A. (2019). Algorithms for optimization
• My collection of code: Github

Concept Notes

Unit 1 Introduction

• Session 1 What and Why to Optimize
  • mathematical optimization
  • objective function
  • feasible region

Unit 2: Unconstrained optimization

Find the solution to the unconstrained problem

• Session 2 Taylor series and numerical approximation
  • Review gradient, Hessian matrix, numerical approximation method
  • Taylor series
  • Taylor polynomial
  • linear approximation
  • quadratic approximation
• Session 3 Quadratic forms
  • Review critical points, quadratic approximation, Hessian matrix
  • quadratic form
• Session 4 Tests for Positive Definiteness
  • Review determinant, symmetric matrix, diagonal matrix, eigenstuff, the Spectral Theorem, quadratic form
  • positive definite
  • critical point
  • Enrichment: Sylvester’s criterion
• Session 5 Bracketing
  • Review intermediate value theorem
  • bracketing method
  • bisection method
• Session 6 Introduction to descent
  • Review bisection method and step size
  • descent method
  • line search
    • exact line search
    • inexact line search
      • Wolfe conditions
• Session 7 Gradient descent
  • backtracking line search
  • termination conditions for descent method
  • gradient descent
• Session 8 Conjugate gradient
  • Review gradient descent
  • conjugate gradient
• Session 9 Momentum and Noisy Descent
  • Review gradient descent
  • noisy gradient descent
  • momentum-based gradient descent
• Session 10 Newton’s method
  • Review quadratic approximation
  • Newton-Raphson method
  • quasi-Newton method
• Session 11 Unconstrained Review
  • Most important review: positive definite, gradient descent
  • Review constrained optimization
  • Schur complement

Unit 3: Constrained Convex Optimization

Find the solution to the unconstrained problem

• Session 12 Equality Constraints with Lagrange Multipliers
  • Review Lagrange multipliers
  • bordered Hessian
• Session 13: Convex Sets, Cones, and Functions
  • convexity
  • concavity
  • half space
  • Pre-class Work, Main Workbook
• Session 14: Inequality Constraints: the KKT Conditions
  • convex optimization
  • KKT conditions (extension of Lagrange multipliers)
  • Pre-class Work, Main Workbook Debrief
• Session 15: Applying & Interpreting the KKT Conditions
  • KKT conditions
  • Pre-class Work (Explore tab), Main Workbook
• Session 16: Linear Programming
  • Review convex optimization and convexity for PCW
  • Review norm for class activity
  • linear programming
  • convex polyhedron
  • Pre-class Work
  • Main Workbook
    • Q3 and Q5 has wrong signs: and
• Session 17: Duality
  • Review KKT conditions
  • slack variable
  • simplex method
  • dual problem
• Session 18: Integer Programming
  • integer programming
    • binary programming
    • traveling salesman problem, knapsack problem
    • branch and bound method
• Session 19: Mixed-Integer Programming
  • mixed-integer programming
    • big-M method
• Session 20: Quadratic Programming
  • quadratic programming
• Session 21: LMIs
  • Review vector space, subspace, convexity
  • linear matrix inequality
• Session 22: Semidefinite Programming
  • semidefinite programming
  • Review linear matrix inequality, Schur complement
  • CS164 MUW S22 semidefinite programming
• Session 23: Newton’s Method with Linear Equality Constraints
  • Newton’s method for linear equality constraints
• Session 24: Barrier Methods
  • interior point method
  • penalty method
• Session 25: Course synthesis