Linear and Nonlinear Optimization

Catalog description

Formerly numbered MATH-UA 253; the content has not changed. 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).