MS&E 214: Optimization Via Case Studies

Spring 2023-24

Tu, Th 1:30-2:50pm
Turing Auditorium

INSTRUCTOR
Ashish Goel
ashishg@stanford.edu, 650 814 1478
Office Hours: Monday 5-6 pm, Huang 305

TEACHING ASSISTANT
Sahasrajit Sarmasarkar
sahasras@stanford.edu
Office Hours: Friday 9-10 am, on Zoom. Link available here.

Class forum: We will use ed stem as a discussion forum, and Gradescope for assignments. Sign up link available here.

Auditors: please sign on to the mailman list msande214-spr2324-guests and let the instructor know.

DESCRIPTION
This class will illustrate applications of optimization principles such as linear and non-linear programming, decision making under uncertainty, and dynamic programming in several important real-world scenarios, including Machine Learning, Market Design, Logistics and Revenue Management, Centralized and Decentralized Finance, Recommendation Systems, and Participatory Budgeting. The focus will be on applying the techniques, and in addition to the modeling, there will also be several hands-on assignments that will require you to deal with large and complex data sets. Prerequisites: Linear programming at the level of MS&E 111; proficiency in some programming language (preferably python).

OBJECTIVE
To enable students to apply optimization in complex real-world settings. Expose students to how optimization works in conjunction with data science and product management. Expose students to specific domains from the social sciences, technology, finance, and business where optimization plays a key role.

DETAILED PLAN
This class will be structured in multiple modules, each revolving around an applied area, and each involving a substantial HW, and a guest lecture. We will assume familiarity with basic linear programming and basic python, but we will also review linear programming at the beginning of the class in sufficient detail for a mathematically well-prepared student to pick it up, and we will also provide basic templates for linear programming in python. The focus of the class will be on applications, and not on theorem proving or getting very deep into techniques. The list of modules is given below.

Introductory techniques. 1.5 weeks. Review of Linear Programming and Duality, A quick introduction to Quadratic Programming, Convex Optimization, KKT conditions.
Social Choice and welfare. 2 weeks. Participatory Budgeting, Representational Robustness, Ordinal vs cardinal social choice, cake cutting and rent division (Walrasian equilibrium), Nash welfare and fair resource allocation.
Optimization in Machine Learning. 2 weeks. Regression; Support Vector Machines; gradient descent and neural networks; use of massively parallel architectures such as CUDA and Map Reduce.
Finance and Decentralized Finance. 2 weeks. Portfolio optimization using Quadratic Programming; replication and arbitrage; Cryptocurrency exchanges.
Matching Markets, computational advertising, and logistics. 2 weeks. Driver assignment for Uber; adword optimization; revenue management; examples from supply chains.
Class wrap-up and special topics. 1 week.

REQUIREMENTS
There will be 4 HWs (50% of class grade), a project (25% of class grade), and a final take home exam (25% of class grade) that will also have a hands-on component.
Attendance is mandatory (in that the class is not recorded, and anything covered in class is part of the curriculum), but we will not track it.
We will allow two late days total, at most one for each HW.
HW1 will be handed out on Fri week 3 and due Thu week 5.
HW2 will be handed out on Thu week 5 and due Tue week 7.
HW3 will be handed out on Tue week 7 and due Fri week 9.
HW4 will be handed out on Fri week 8 and due Thu week 10.
Project topics will be handed out at the end of week 4; topics must be selected by Thu week 6; preliminary report due end of week 9; final report due Mon week 11.
Preliminary report: at least 4 pages, clear articulation of approach to be taken and partial progress (at least half the work completed).
Exam: Sat June 8 noon to Sun June 9 8pm; three hour window; take home.

HANDOUTS