MS&E 114/214: Applied Optimization

Aut 2024-25

Tu, Th 1:30-2:50pm
Hewlett Teaching Center 201

INSTRUCTOR
Ashish Goel
ashishg@stanford.edu, 650 814 1478
Office Hours: Wed 5-6 pm in person (Huang 203), 7-8 pm on Zoom.

TEACHING ASSISTANTS
Mohak Goyal
mohakg@stanford.edu
Office Hours: Monday 5-6:30 pm, Shriram SB33.

Annie Wang
jingyi.annie.wang@stanford.edu
Office Hours: Wed 9-10 am, on Zoom.


Problem Sessions: Fri 1:30-2:30 (optional; the TAs will solve one or two example problems). Location: on Zoom.

Week 10 Updates; extra OH and Problem Sessions

• Mohak will hold extra OH on Sunday, Dec 1, from 6-7 pm on Zoom.
• Ashish will hold extra OH on Monday, Dec 2, from 2-4 pm on Zoom.
• Ashish will hold extra OH on Sunday, Dec 8, from 4-6 pm on Zoom.
• The problem session on Friday, Dec 6, will be in two parts; 1:30 - 2:30 pm with Annie and 3-4 pm with Mohak. It will be recorded.

IMPORTANT NOTES

• We will not have Office hours or problem sessions in the first week of class. There will no instructor zoom hours in the second week.
• Unless an email is confidential for the instructor, or has very specific request for one person, please send it to msande214-aut2425-staff@lists.stanford.edu so we can track internally. Emails sent to only one person sometimes get lost.
• Class forum: We will use Ed Stem as a discussion forum, and Gradescope for assignments. Sign up link available here. We will not use Canvas for anything other than posting solutions and occasional supplementary videos.
• Auditors: please sign on to the mailman list msande214-aut2425-guests and let the class staff know.
• 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.

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, and Social Choice and Welfare. While we will also provide a rigorous introduction to many of these techniques, the focus will be on applications. There will be several hands-on assignments that will require you to deal with large and complex data sets. Hands-on work will be in both Python and Microsoft Excel Solver, but no prior knowledge will be assumed. Prerequisite: CME 100, MATH 51, or equivalent.

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.

1. Introductory techniques. 1.5 weeks. Review of Linear Programming and Duality, A quick introduction to Quadratic Programming, Convex Optimization, KKT conditions, dynamic programming, stochastic programming. This module will not be contiguous; rather techniques will be introduced as needed. Most techniques will be used at least twice.
2. 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.
3. Optimization in Machine Learning. 2 weeks. Regression; Support Vector Machines; gradient descent and neural networks; Markov Decision Processes and decision making under uncertainty.
4. Finance and Decentralized Finance. 2 weeks. Portfolio optimization using Quadratic Programming; replication and arbitrage; Cryptocurrency exchanges.
5. Matching Markets, computational advertising, and logistics. 2 weeks. Driver assignment for Uber; adword optimization; revenue management; examples from supply chains.
6. Class wrap-up and special topic. 1 week.

REQUIREMENTS

• There will be 5 regular HWs (45% of class grade), and one HW that you don't have to submit (practice problems). HWs will be handed out Oct 2, 9, 16, and Nov 6 and 18, and due on Oct 11, 18, 25, Nov 15, Dec 3. Practice problems for the final will be handed out Dec 3.
• There will one midterm in class on Oct 29 (20%)
• There will be one final exam (20%) on Dec 10 at 3:30 (with an early exam option on Dec 8)
• There will be a takehome lab exam (15%). The take home lab exam can be taken in any two hour window from Dec 5 at 4pm to Dec 6 at 11am.
• There will also be a 10 minute oral exam (you will have a choice of slots from Dec 11 to Dec 13) that will ask you to explain your takehome lab exam and perhaps explain how you would make a minor modification to your solution; this will be a big part of grading your takehome final.
• All HWs and takehome lab exams will be open book, open Internet, and will allow for AI assistants.
• The majority of the problems on the midterm and the final will be minor variants of HW problems to make sure that even if you used AI assistants, you understand your own solutions sufficiently well to adapt and modify them.
• The final will be comprehensive, that is, it will include the entire curriculum.
• We will allow two late days total for the HWs, at most one for each HW.
• If you opt to take the early final, please be forewarned that the handing out of solutions to practice problems as well as office hours will be timed for the regular exam, and it is very possible that this might put you at a disadvantage. To be very clear, we are not intentionally going to make your life hard, but we will optimize the timing for the regular exam.
• The final letter grades will be assigned separately for 114 and 214, and there will sometimes be an extra problem or a harder problem for 214.
• There will occasionally be extra credit work assigned. This will be used to possibly bump up your grade, at our discretion.

HANDOUTS
The handouts will be constantly updated. You can look at last year's class for an example of the problems and the curriculum, though this year will be a little different.