Math 560: Optimization

Fall Semester 2011

Basic Information

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

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 of finding the best (e.g. lowest cost) solution to a 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 (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.


Completion of courses in linear algebra and multivariable calculus is assumed.
Some experience using Excel, 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 419/519 Stochastic Math Models, various statistics classes.

Related courses:

  • Convex Optimization lecture videos from Stanford

    Class Meetings

    CRN 17193: Tue, Thu 4:00pm-5:15pm in Pray-Harrold 520
    Brief schedule: 3 credit hours.

    Class meetings will be mostly interactive lectures and computer lab work, with some time to discuss homework.

    Instructor information

    Professor Andrew Ross
    Pray-Harrold 515m
    (734) 487-1658, but I strongly prefer e-mail instead of phone contact.
    Math department main office: Pray-Harrold 515, (734) 487-1444

    Office Hours and other help

    Here is my complete schedule.
        11:30-12:30 Office hours 
        12:30- 1:20 Math 121 in Pray-Harrold 202
         1:20- 2:20 Office hours 
        11:30-12:30 Office hours in my office
        12:30- 1:20 Math 121 in Pray-Harrold 202
         1:20- 2:00 Office hours in PH 202, proceeding to PH 520
         2:00- 3:15 Math 319 in Pray-Harrold 520
         3:15- 4:00 Office hours in PH 520
         4:00- 5:15 Math 560 in Pray-Harrold 520
      No official office hours, but I'm often on campus.
      E-mail me to make an appointment, or drop by.

    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.

    I am definitely unavailable during the times I teach other classes:

    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

    Our suggested (not required!) textbook is "Operations Research: Applications and Algorithms (4th revised edition)" by Wayne Winston (2004), retail price around $161 (yikes!) The price is why it's suggested but not required. My copy of the book has around 1400 pages (!). I understand that some students like to order international copies, which may have a different number of pages. I would be very suspicious of anything with less than, say, 1000 pages.

    I will also be asking for your feedback at the end of many class meetings, written on a 3-by-5 inch notecard. Please pick up a pack of them (at least 25 cards); this should cost about a dollar.

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

    Course Web Page

    We will use the EMU-Online 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:

    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:

    We have a few secondary goals, which may be more or less applicable to your personal situation:


    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.
    	3 basic models: the diet problem (LP), pricing and production (NLP), shift scheduling (IP)
    	Intro to Excel/Gnumeric and Matlab/Octave/Scilab
    	convexity and concavity of sets and functions in multiple dimensions
    	networks/graph theory concepts
    	Common models:
    		production planning
    		network flows (min cost, max flow, shortest path)
    	Software solutions (Excel/Gnumeric, Matlab/Octave/Scilab)
    	Sensitivity analysis (experimental, not formula-based)
    	Geometry of LPs
    	Linear algebra review: quadratic forms, eigenvalues/vectors
    	Common models:
    		L2 (least-squares) regression
    		maximum likelihood estimators (MLEs)
    		solving differential equations
    		many others
    	Software solutions (Excel/Gnumeric, Matlab/Octave/Scilab)
    	Geometry of NLPs
    	Solution methods for unconstrained problems	
    	Solution methods for constrained problems	
    	Common models:
    		shift scheduling
    		knapsack problems
    		assignment problems
    		travelling salesperson (TSP)
    		vehicle routing problem (VRP)
    		set covering/partitioning/packing
    	Binary Variable techniques:
    		fixed-cost problems
    	Solution via branch-and-bound
    	Cutting Planes
    More LP:
    	L1 or L-infinity regression; Compressive Sensing?
    	Solution via Simplex Method
    	Duality/Sensitivity Analysis (formula-based)
    	Solution via Interior Point Methods
    Heuristic Methods (if any time remains)
    	Simulated Annealing
    	Genetic Algorithms
    	Tabu search
    	Biomimic Algorithms (Ant-colony, etc)
    Dynamic Programming (if any time remains)

    Grading Policies


    Regular attendance is strongly recommended. There will be material presented in class that is not in the textbook, yet will be very useful. Similarly, there are things in the textbook that are might not be covered in class, but are still very useful. If you must miss a class, arrange to get a copy of the notes from someone, and arrange for someone to ask your questions for you.

    My lectures and discussions mostly use the chalkboard, 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 will be assigned about once a week. It will sometimes be a small problem set designed to help you understand the behavior of math models. Other times, it will involve writing up a little paper on an assigned topic. All homework should be typed.

    Homework papers should be submitted on-line, where they might be checked by or a similar service. This is partly to help keep you honest, and partly to help you learn acceptable ways to cite the work of others. A side benefit is that sometimes TurnItIn finds papers relevant to your work that you would not have found otherwise!


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


    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

    No scores will be dropped, unless a valid medical excuse with evidence is given. In the unfortunate event of a medical 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:

    Standard University Policies

    Religious Holy Days

    I support students' right to observe religious holidays without penalty. To the best of my ability, I will schedule exams to not conflict with major religions' holidays. Students are to provide advance notice to the instructor in order to make up work, including examinations that they miss as a result of their absence from class due to observance of religious holidays. If satisfactory arrangements cannot be made, the student may appeal to the head of the department.

    Academic Honesty

    Academic dishonesty, including all forms of cheating and/or plagiarism, will not be tolerated in this class. Penalties for an act of academic dishonesty may range from receiving a failing grade for a particular assignment to receiving a failing grade for the entire course. In addition, you may be referred to the Office of Student Judicial Services for discipline that can result in either a suspension or permanent dismissal. The Student Conduct Code contains detailed definitions of what constitutes academic dishonesty, but if you are not sure about whether something you’re doing would be considered academic dishonesty, consult with the instructor.

    Classroom Behavior

    Students are expected to abide by the Student Conduct Code and assist in creating an environment that is conducive to learning and protects the rights of all members of the University community. Incivility and disruptive behavior will not be tolerated and may result in a request to leave class and referral to the Office of Student Judicial Services (SJS) for discipline. Examples of inappropriate classroom conduct include repeatedly arriving late to class, using a cellular telephone, or talking while others are speaking. You may access the Code online at

    Special Needs Accomodations

    If you wish to be accommodated for your disability, EMU Board of Regents policy #8.3 requires that you first register with the Access Services Office (ASO) in room 203 King Hall. You may contact ASO by telephone at (734) 487-2470. Students with disabilities are encouraged to register with ASO promptly as you will only be accommodated from the date you register with them forward. No retroactive accommodations are possible.

    Student and Exchange VISitors (SEVIS)

    The Student Exchange Visitor Information System (SEVIS) requires F and J students to report the following to the Office of International Students, 229 King Hall within ten (10) days of the event: Prior permission from OIS is needed for the following: Failure to report may result in the termination of your SEVIS record and even arrest and deportation. If you have questions or concerns, contact the OIS at 487-3116, not your instructor. Also, see the EMU SEVIS page.