Spring 2022

If you are enrolled in this course 100% remotely and are not a Go Local/Study Away student

for NYU Paris, please make sure that you’ve completed the online academic orientation via

Brightspace so you are aware of site specific support structure, policies and procedures.

Please contact [email protected] if you have trouble accessing the Brightspace

site.

Syllabus last updated on: December 13, 2021

Instructors: This class will be taught by Professor Alfred Galichon ([email protected]). The teaching assistant is Andrew D. Lipnick ([email protected]).

Professor Galichon will hold an office hour Monday 5:15-6:15pm Paris time; use the link you'll find in NYU Classes to join him (the meeting ID is different from the one we use for lectures and recitations).

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  nonlinear  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 unconstrained optimization (eg gradient descent, stochastic gradient descent,  Newton's  method,  and  quasi-Newton  methods)  and  selected  techniques  for constrained optimization (eg using penalty methods and barriers). Applications will be drawn from many areas, but will emphasize economics (eg two-person zero-sum games, matching and assignment problems), 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:   multivariable   calculus   and   linear   algebra.   The   multivariable   calculus prerequisite is satisfied by MATH-UA 123 (Calculus III) or MATH-UA 129 (Honors Calculus III) or MATH-UA 213 (Math for Economics III) with a grade of C or better. The linear algebra prerequisite is satisfied by MATH-UA 140 (Linear Algebra) or MATH-UA 148 (Honors Linear Algebra) with  a grade of  C or  better. The  prerequisites  can also  be  met  by equivalent coursework elsewhere.

Units earned: 4

Course Details

Lectures MW 4:00-5:15 (Paris time), Recitations W 5:30-7:00 (Paris time)

Location: Rooms will be posted in Albert before your first class.

Zoom links: Our lectures, recitations, and lab sessions will all be hybrid. They will not be recorded. You'll find links for each session in the the Zoom section of the NYU Classes site. All lectures, recitations, and lab sessions will use the same meeting ID.

Gradescope: We will use Gradescope for homework, quizzes and exams. You'll find Gradescope in the Lessons section of the NYU Classes site. We will inform you each time we post something on Gradescope.

Class materials: All class material (for example pdf versions of any handwritten notes created during lectures) will be available in the Resources section of the NYU Classes site. We will also maintain a table on the front page of the NYU Classes site, providing a summary of the materials available (with links).

Regarding the  NYU Spring 2022 calendar:  Our first class  is Wed  1/26.  Monday, February 21 is a holiday in NY, but not in Paris, and our class still meets as usual. Monday, April 18 is a holiday in Paris and our class does not meet -- it meets on Friday April 22 instead. Our last class is May 5/9.

●   COVID-related details:In the interest of protecting the NYU Paris community, we are closely following CDC guidance around COVID-19 and adjusting our recommendations and policies accordingly. Your health and well-being is our top priority.

○   If you are attending in person, you will be assigned a seat on the first day and are expected to use that seat for the entire semester due to NYU COVID-19 safety  protocol.  Please  note that you  are  expected to  attend  every  class meeting in-person; however, this may change during the drop/add period if in- person student registration increases significantly or at any point during the semester if local COVID-19 regulations require additional physical distancing.

Course Objective

Our material has two related but distinct threads, namely linear programming (for which we'll mainly use Vanderbei's book) and nonlinear optimization (for which we'll mainly use the book of Luenberger & Ye). These threads will be developed in parallel over the course of the semester -- alternating between them in segments (each two or three lectures long).               As stated in the course description, the class will emphasize connections with and applications to economics and data science. These are sometimes conceptual (such as the use of linear programming to solve two-person zero-sum games) and sometimes quite practical (such as the use of stochastic gradient descent to tune neural networks -- in effect, minimizing a nonlinear and nonconvex function of many variables). As we discuss various optimization techniques, we will focus on the technique's essential character,  power,  and  limitations; computing with python will permit us to do examples, bringing the methods to life and applying them.

We expect to cover the following topics (in approximately this order):

-      Introduction to linear programming; geometry of the simplex method (Vanderbei, chapters 1-3)

-      Introduction to nonlinear optimization; gradient descent and stochastic gradient descent (Luenberger & Ye, chapter 8)

-      Duality in linear programming (Vanderbei, 5.1-5.5) and its application to game theory (Vanderbei, chapter 11).

-     Some applications of linear programming to data science (Vanderbei, chapter 12).

-      Newton's method, and quasi-Newton methods (drawing from Luenberger & Ye 10.1- 10.4)

-      Linear programming applied to network problems, and to matching and assignment problems (Vanderbei chapters 14 & 15, with additional sources for matching and     assignment problems)

-      Interior point methods for linear programming, and barrier & penalty methods for   nonlinear optimization with constraints (drawing from Luenberger & Ye chapters 5 and 13)

-      Dynamic programming -- shortest paths in networks; resource planning; prediction with expert advice (not in our textbooks -- additional sources will be provided)

Assessment Components and Requirements You are expected to attend class in person or remote synchronously. Failure to submit or fulfill any required component may result in failure of the class, regardless of grades achieved in other assignments.

The course requirements are

Homework: There will be approx 7 homework assignments, roughly one every two weeks. (HW1 will be an exception -- it will be due at the end of week 2.) Each        assignment will count equally toward your grade (regardless of the max possible    points). Taken together, the homework will be worth 35% of your grade.

Exams: The midterm exam and the final exam will each be worth 25% of your grade.

Quizzes: There will be weekly quizzes. They will be short and you'll be able to do

them quickly, provided you are up to date on the material. The quizzes will help make sure you don't forget about this class during the periods when no lectures are              scheduled; in particular, they'll help you remember to stay up to date. They will            usually be posted on Thursday (thus: after the week's lectures are finished) with a       completion deadline just before the following week's first lecture (which is usually on   Monday). Each quiz will count equally. Taken together, the quizzes will account for     15% of your grade.

Required Texts and Resources

Textbooks: We will use the following two books as texts. Each is available to members of the NYU community as a free pdf download from SpringerLink, and a paperback copy can be purchased at a very low cost from the book's SpringerLink page; for access, find the book in Bobcat (or use the permalink given below) then click on SpringerLink.

(1) Robert Vanderbei, Linear Programming -- Foundations and Extensions, 5th edition, Springer, 2020; permalink:

https://bobcat.library.nyu.edu/permalink/f/1c17uag/nyu\_aleph007821893

(2) David Luenberger and Yinyu Ye, Linear and Nonlinear Programming, 4th edition, Springer-Verlag, 2015; permalink:

https://bobcat.library.nyu.edu/permalink/f/1c17uag/nyu\_aleph006561000

We will, of course, cover only selected parts of each book. For a few topics that aren't covered well by these books, additional notes or readings will be made available.

Computing: While no prior experience in programming is expected, the required coursework will  include  numerical  implementations,  including  some  programming.  Students  will  be introduced to the python programming language through the jupyter  platform, along with the numpy library and the gurobi linear programming solver early in the semester. Note that using the jupyter platform and basic python programming will be an essential and obligatory part of this course.

Information about downloading and installing jupyter and gurobi will be distributed during the first  week  of  classes.  The  first  two  recitations  (Jan  26  and  Feb  2)  will  be  devoted  to python/jupyter tutorials, to help you get started using these computational tools. Students are strongly urged to attend the python/jupyter tutorials in person, to make sure they have access to our computational tools.

Supplemental Texts (not required to purchase)

Additional books: This course will emphasize applications to economics and data science. The following books, while not suitable for use as textbooks for this class, are rich with applications to those areas:

(a) Rakesh Vohra, Advanced Mathematical Economics, Routledge, 2005; permalink:

https://bobcat.library.nyu.edu/permalink/f/1c17uag/nyu\_aleph006302959

This book is downloadable for free via Bobcat (use the permalink then choose online   access). Its scope is broader than just optimization, and its level is more advanced      than this class. But the first 115 pages are pretty accessible, and the topics they          cover are within the scope of this class. The book is full of applications to economics - - far more than we'll have time for.

(b) Gilbert Strang, Linear Algebra and Learning from Data, Wellesley Cambridge Press, 2019. Like Vohra, this book's level is more advanced than our class; moreover its     focus isn't mainly on optimization (in fact, the emphasis is on tools from linear           algebra). But the book is nevertheless worth mentioning, since it offers a broad         perspective on how optimization, linear algebra, and related tools are used in data    science. Unfortunately, it isn't available electronically. The book's website https://math.mit.edu/~gs/learningfromdata offers links to several sellers, and             Professor Strang's website http://www-math.mit.edu/~gs has links to youtube and    MIT OCW sites where you'll find lectures from a 2018 course based on a draft of the book.

er from their regular class schedule]

Classroom Etiquette

Please make you sur read and acknowledge the information regarding this section on the NYU Paris Resources site on Brightspace.

Academic Policies

Grade Conversion

Your lecturer may use one of the following scales of numerical equivalents to letter grades:

Collaboration on homework

Students are welcome -- and even encouraged -- to discuss the homework problems with others. However, for both  numerical and pencil/paper type questions, each student must implement and present his or her own solutions (this is an important part of the learning process).  Direct copying of another student's solution is not permitted -- both because it amounts to cheating, and because it defeats the entire purpose of the homework (which is to gain familiarity with new concepts and techniques).

Attendance Policy

Studying at Global Academic Centers is an academically intensive and immersive experience, in which students from a wide range of backgrounds exchange ideas in discussion-based seminars. Learning in such an environment depends on the active participation of all students. And since classes typically meet once or twice a week, even a single absence can cause a student to miss a significant portion of a course. To ensure the integrity of this academic experience, class attendance at the centers, or online through NYU Brightspaces if the course is remote synchronous/blended, is expected promptly when class begins. Attendance will be checked  at  each  class  meeting.  If  you  have  scheduled  a  remote  course  immediately preceding/following      an      in-person      class,      you      may      want      to      write      to [email protected] to see if you can take your remote class at the Academic Center.

As soon as it becomes clear that you cannot attend a class, you must inform your professor and/or the  Academics team  by  e-mail  immediately  (i.e.  before the  start  of your  class). Absences are only excused if they are due to illness, Moses Center accommodations, religious observance or emergencies. Your professor or site staff may ask you to present a doctor's note or an exceptional permission from an NYU Staff member as proof. Emergencies or other exceptional circumstances that you wish to be treated confidentially must be presented to staff. Doctor's notes must be submitted in person or by e-mail to the Academics team, who will inform your professors.

Unexcused absences may be penalized with a two percent deduction from the student’s final course grade for every week's worth of classes missed, and may negatively affect your class participation grade. Four unexcused absences in one course may lead to a Fail in that course. Being more than 15 minutes late counts as an unexcused absence. Your professor is entitled to deduct points if you frequently join the class late.

Exams, tests and quizzes, deadlines, and oral presentations that are missed due to illness always require a doctor's note as documentation. It is the student's responsibility to produce this doctor's note and submit it to site staff; until this doctor's note is produced the missed assessment is graded with an F and no make-up assessment is scheduled. In content classes, an F in one assignment may lead to failure of the entire class.

Regardless of whether an absence is excused or not, it is the student's responsibility to catch up with the work that was missed.

Final exams

Final exams must be taken at their designated times. Should there be a conflict between your final exams, please bring this to the attention of the Academics team. Final exams may not be taken early, and students should not plan to leave the site before the end of the finals period.

Late Submission of Work

(1) Work submitted late receives a penalty of 2 points on the 100 point scale for each day it is late (including weekends and public holidays), unless an extension has been approved (with a doctor's note or by approval of NYU SITE Staff), in which case the 2 points per day deductions start counting from the day the extended deadline has passed.

(2) Without an approved extension, written work submitted more than 5 days (including weekends and public holidays) following the submission date receives an F.