MATH-UA 253 Linear and Nonlinear Optimization
4 points. Fall and Spring terms.
Course Description
Optimization is a major part of the toolbox of the applied mathematician, and more broadly of researchers in quantitative sciences including economics, data science, machine learning, and quantitative social sciences. This course provides an application-oriented introduction to linear programming and convex optimization, with a balanced combination of theory, algorithms, and numerical implementation. While no prior experience in programming is expected, the required coursework will include numerical implementations, including some programming; students will be introduced to appropriate computational tools, with which they will gain experience as they do the numerical assignments. Theoretical topics will include linear programming, convexity, duality, minimax theorems, and dynamic programming. Algorithmic topics will include the simplex method for linear programming, selected techniques for smooth multidimensional optimization (eg Newton's method and the conjugate gradient method), techniques for solving for L1-type optimizations, and stochastic gradient descent. Applications will be drawn from many areas, but will emphasize economics (eg two-person zero-sum games, matching and assignment problems, optimal resource allocation), data science (eg regression, convex-relaxation-based approaches to sparse inverse problems, tuning of neural networks, prediction with expert advice) and operations research (eg shortest paths in networks and optimization of network flows).
Prerequisites
Students must earn grades of C or higher in the following two prerequisite courses:
- MATH-UA 123 Calculus III or MATH-UA 129 Honors Calculus III or MATH-UA 133 Math for Economics III
- MATH-UA 140 Linear Algebra or MATH-UA 148 Honors Linear Algebra