Math 479/560: Optimization

Prof. Andrew Ross

Fall Semester 2022

Basic Information

Note: this syllabus is temporary, and may change up to the first day of class.
This version posted on: 2022-08-30

The official course title is "Introduction to Optimization Theory". However, we will try to split our time evenly between applications/modeling, theory, and methods.

Mathematical optimization is the science (and sometimes art) of finding the best (lowest cost, most lives saved, least risk, or best-fitting) solution to a given minimization or maximization problem. Often, we also try to prove that it is the best, or that it is within some small percentage of the best solution. Some common examples are:

Since you have had the prerequisite courses, you are familiar with finding the minimum or maximum of a function using derivatives (like in first-semester calculus), and finding the minimum or maximum of a function of two or three variables (like in third-semester calculus). In this course, we will be working with thousands of variables--real applications can use millions of variables. Of course, we don't solve problems like that by hand. In our course, we will learn the methods people have developed for computers to solve such large problems.

Official Course Catalog Entry

An introduction to various aspects of optimization theory, including linear and nonlinear programming, primal dual methods, calculus of variations, optimal control theory, sensitivity analysis and numerical methods.

Prerequisites

Completion of courses in elementary linear algebra/matrix algebra and multivariable calculus is assumed.
Some experience using Excel, and Python, Mathematica, Maple, or Matlab/Octave/SciLab will also be very helpful, but it is not strictly a prerequisite.

Follow-up courses: Math 436 Numerical Analysis, Math 419W/519 Stochastic Math Models, various statistics classes.

Related courses:

  • Convex Optimization lecture videos from Stanford

    Class Meetings

    Our class is online/asynchronous, so there are no required class meetings. I will hold a video chat/collaborative-work/office-hour session every Tuesday and Thursday at 4:00. Some of these will also be student project presentations, which you should either attend live online or watch the recordings.
    Other class info:Math 479 CRN 13523; Math 560 CRN 14322"
    3 credit hours.

    Instructor information

    Professor Andrew Ross
    Pray-Harrold 515L
    andrew.ross@emich.edu
    http://emunix.emich.edu/~aross15/
    (734) 487-1658, but I strongly prefer e-mail instead of phone contact. During the coronavirus shutdown, my office phone number will just always go to voicemail.
    Math department main office: Pray-Harrold 515, (734) 487-1444

    Office Hours and other help

    In-Person: Tue/Thu 3:30-5:30 except I might be Zooming with other students from my office during some of that.

    You can also make an appointment to meet me on Zoom; I'll send out a link for that.

    I am also happy to make appointments if you cannot come to the general office hours. Please send me e-mail to arrange an appointment. It can even be in the evening or on a weekend.

    Many assignments in this course will be in the form of papers, which I want to be well written. Please consult with The Writing Center for help in tuning up your writing.

    Required materials

    We will be using pieces from the following textbooks, which are ELECTRONICALLY FREELY AVAILABLE to EMU students through our campus library:

    Other suggested (not required) textbooks are "Operations Research: Applications and Algorithms (4th revised edition)" by Wayne Winston (2004), and "Introduction to Operations Research, 10th edition" by Hillier and Lieberman. These are more undergraduate-level texts, which provide a gentler introduction to the subject but can get stuck in by-hand calculations. The high cost is why they are suggested but not required.

    We will also be using software. At least one of the following, and possibly more, is required:

    As of Fall 2016, brand-name Microsoft Excel is available free to EMU students. The University's campus license also allows students, faculty, and staff to install Microsoft Office (Windows, Mac and mobile device versions) at no cost. To obtain the software, login to https://portal.office.com (Links to an external site.) using your EMU email address (username@emich.edu) and NetID password and then follow the instructions on the page to download and install the application.

    Course Web Page

    We will use the EMU Canvas system. You are expected to keep an eye on your scores using the system, and get extra help if your scores indicate the need.

    Supplementary Materials

    Here are some handy web sites: Here are some other optimization books: Other books related to optimization, but not really our main focus: Books on Optimization Models:

    Blogs

    Here are some of the blogs that relate to our class:

    Course Content

    Course Goals

    Our primary goal is to teach you to be a good (or great!) optimizer. To be a good optimizer, you need:

    Our department list of Student Learning Outcomes for Math 560 is: 

    Upon successfully completing MATH 560 Introduction to Optimization Theory, students will be able to

Recognize the assumptions that are made in developing a model and how to modify the assumptions to refine the model
Do a project, roughly on the scale of COMAP's Mathematical Contest in Modeling (MCM), and communicate its results
Formulate common Linear, Integer, and Nonlinear programs in software and symbolically
Explain basic solution methods for Linear, Integer, and Nonlinear Programs, including speed considerations
Explain the role of convexity in Nonlinear Programs
Explain meta-heuristics such as Evolutionary methods and Simulated Annealing
Explain duality and sensitivity analysis for LPs and NLPs
Explain other optimization topics such as Constraint Programming, Stochastic Programming, Robust Programming, Dynamic Programming, Calculus of Variations, and Optimal Control
    Undergrads enrolled in Math 479 do not need to achieve the same level of ambition in their projects as graduate students in Math 560, and similarly do not need to develop as deep an understanding of some of the solution methods. Here is an idealized, pie-in-the-sky list of more detailed Student Learning Outcomes for this course: Students will be able to:
    1. Formulate common LPs in software and symbolically
    2. Explain the Fundamental Theorem of LP
    3. Formulate common IPs in software and symbolically
    4. Explain other optimization topics: Constraint Programming, Stochastic Programming, Robust Programming, Dynamic Programming, Calculus of Variations, Optimal Control
    5. Explain classic unconstrained NLP solution methods: line search, Steepest Descent, Newton, Quasi-Newton
    6. Explain the roles of convexity in NLPs
    7. Explain meta-heuristics: Evolutionary, Simulated Annealing, and perhaps others
    8. Explain the Simplex Method
    9. Explain duality and sensitivity analysis for LPs; column generation
    10. Explain Lagrange Multipliers/the KKT conditions and sensitivity analysis for constrained NLPs
    11. Explain constrained NLP solution methods
    12. Explain interior-point methods for LP
    13. Explain branch-and-bound for IPs; tight formulations, symmetry-breaking; branch-and-cut
    14. Consider factors affecting speed of unconstrained NLP solution: Conditioning, use of derivatives, algorithm convergence order/rate, etc.
    15. Take an optimization project from initial concept to formulation(s) and solution(s) including algorithmic concerns, and report/presentation.
    and we will take them in that order, mostly.

    Outline/schedule

    Many classes in optimization theory start with linear problems and solution methods, then proceed to nonlinear problems, because linear problems and solution methods are simpler. Other classes start with nonlinear, because then linear is just a special case. We will start with mostly nonlinear problems and solution methods because then you will have a wide base of ideas to do the first (mid-semester) project. See the day-by-day schedule in the file containing All The Homework (or, this direct google doc link in case the bitly link fails) 
    








     Grading Policies 
    


     Attendance 
    


    


    

    
My lectures and discussions mostly use the document camera, along with
demonstrations in Excel and other mathematical software.  I do not
usually have PowerPoint-like presentations, and thus cannot hand
out copies of slides.

    


     Homework 
    

    
Homework will be assigned about once a week.  All homework should
be typed unless notified otherwise.

    


     Homework papers should be submitted on-line via EMU Canvas unless otherwise noted in the assignment.

    


     Exams 
    

    
There will be no exams, unless the class demonstrates an unwillingness
to be motivated any other way.  

    

     Project(s) 
    

    
Instead of exams, we will have two projects.
Your results for each will reported in a paper and a presentation to
the class.  You may work by yourself or in a team of 2 people, but no
groups larger than 2 will be allowed.  You may switch project partners
at your will.  Your project grades will each be split into roughly:
10 percent for the project proposal (due 2 weeks before the project),
80 percent for the written paper and actual work, and
10 percent for the presentation
(subject to change).  The presentations for the second project will be made during the
time slot reserved for the final exam.

    



     Overall Grades 
    

     There is no systematic system for dropping scores like "the lowest 2 homeworks".
In the unfortunate event of a need, the appropriate grade or
grades may be dropped entirely (at the professor's discretion), rather than giving a make-up.
You are highly encouraged to still complete the relevant assignments and consult with me during office hours to ensure you know the material.

    


Your final score will be computed as follows:

Once final scores are computed, a curve will be applied.
    



     General Caveat 
    

The instructor reserves the right to make changes to this syllabus
throughout the semester.  Notification will be given in class or
by e-mail or both.  If you miss class, it is your responsibility
to find out about syllabus and schedule changes, especially
the due dates and times of projects, assignments, or presentations.


     Advice from previous students 
    

Last time I taught the course, I asked my students to give advice to you, future students, 
based on their experiences in my course. Here are some of the highlights: 



    UNIVERSITY COURSE POLICIES, EXPECTATIONS, AND STUDENT RESOURCES 
    


    Health Screening 
    
If you have symptoms or believe you were exposed to COVID-19, please contact your primary health care provider or the IHA Health Center @ EMU  at 734-896-4110 for patient care management. You MUST also complete the COVID-19 Report Form (See emich.edu/emu-safe/safe-return-to-campus/students).
If you test positive for COVID-19, please complete the COVID-19 Report Form. The Assistant Vice President for Academic & Student Affairs will contact you for verification, support, and notify your instructors. 

    

     Physical Distancing 
    
Physical distancing is one of the most effective strategies to reduce the spread of COVID-19. Whenever practical, all individuals on University grounds must maintain a physical distance of six feet or more from other individuals who are not part of their household. 

    

     Face coverings 
    
Wearing a face covering is one of several essential actions that reduce the spread of COVID-19. Everyone on campus (e.g., students, faculty, staff, and visitors)are required to wear a face-covering that covers both the nose and mouth in or on all university buildings (including classrooms and labs) and grounds.

    

     Hygiene 
    
Hand hygiene practices, as well as appropriate cough etiquette, help reduce the spread of COVID-19. All individuals should regularly wash their hands with soap and water for at least 20 seconds. At a minimum, individuals should wash their hands before eating and after using the restroom, touching anything in a public area, or blowing their nose. Use hand sanitizer when needed (but not in place of handwashing when soap and water are available). Hand sanitizer stations are in all buildings.

    

     Wellness & Community Responsibility 
    
We expect every member of the campus community to follow these standards as part of our community commitment to safety. Students who do not comply with the University’s policy requiring face coverings and physical distancing are subject to the University’s Code of Community Responsibility. Questions regarding enforcement involving students should be directed to the Office of  Wellness & Community Responsibility at emu_owcr@emich.edu or 734-487-2157.

    

In addition to the articulated course specific policies and expectation, students are responsible for understanding all applicable university guidelines, policies, and procedures.  The EMU Student Handbook is the primary resource provided to students to ensure that they have access to all university policies, support resources, and student's rights and responsibilities.  Changes may be made to the EMU Student Handbook whenever necessary, and shall be effective immediately, and/or as of the date on which a policy is formally adopted, and/or the date specified in the amendment.  Electing not to access the link provided below does not absolve a student of responsibility.  For questions about any university policy, procedure, practice, or resource, please contact the Office of the Ombuds: 248 Student Center, 734.487.0074, emu_ombuds@emich.edu, or visit the website at www.emich.edu/ombuds . 

CLICK HERE to access the University Course Policies




     Mental Health Support 
EMU's Counseling and Psychological Services is here to help you with anxiety, depression, and many other difficulties. They are operating online rather than being shut down by the coronavirus.


     Food Pantry 
    
Swoop's Pantry (104 Pierce Hall, emich.edu/swoopspantry, 734 487 4173) offers food assistance to all EMU students who could benefit. Students are able to visit twice per month to receive perishable and non-perishable food items, personal hygiene items, baby items, and more. Students can visit our website for hours of operation and more information. 
If you are in a position to donate to Swoop's, I encourage you to do so!