MATH-UA 9253 Linear and nonlinear optimization Spring 2022
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Linear and nonlinear optimization
MATH-UA 9253
Instruction Mode: Blended
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:
US Letter Grade |
US numerical |
French numerical |
|
A |
94-100 or 4.0 |
15-20 |
Excellent |
A- |
90-93 or 3.7 |
14 |
Very Good |
B+ |
87-89 or 3.3 |
13 |
Good |
B |
84-86 or 2.7 |
12 |
Good |
B- |
80-83 or 2.7 |
11 |
Satisfactory |
C+ |
77-79 or 2.3 |
10 |
Sufficient |
C |
74-76 or 2.0 |
9 |
Sufficient |
C- |
70-73 or 1.7 |
8 |
Sufficient |
D |
65-66 or 1.0 |
5-7 |
Poor |
F |
below 65 or 0 |
1-4 |
Fail |
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.
(3) Assignments due during finals week that are submitted more than 3 days late (including weekends and public holidays) without previously arranged extensions will not be accepted and will receive a zero. Any exceptions or extensions for work during finals week must be approved by Academic Affairs ([email protected]).
(4) Students who are late for a written exam have no automatic right to take extra time or to write the exam on another day.
(5) Please remember that university computers do not keep your essays - you must save them elsewhere. Having lost parts of your essay on the university computer is no excuse for a late submission.
2022-01-26