CS 52000 Syllabus

Course information

Spring 2023
MWF 1:30-2:20pm
Lawson 1106
http://www.cs.purdue.edu/homes/dgleich/cs520-2023

Instructor

David F. Gleich
Lawson 1207
dgleich@purdue.edu
https://www.cs.purdue.edu/homes/dgleich

Office hours

Monday 11am-noon. On Zoom or in-person (Lawson 1207) which varies by week.

Teaching Assistant

Shu Li li3916@purdue.edu

Office Hours

Friday 10-11 am in HAAS 115.

Electronic Sites

We will use Gradescope for homework submission and grading.

We will use Brightspace in more limited capacities.

We will use either Piazza or Campuswire for class discussions and questions.

Description

This course is a introduction to optimization for graduate students in any computational field.
It will cover many of the fundamentals of optimization and is a good course to prepare those who wish to use optimization in their research and those who wish to become optimizers by developing new algorithms and theory. Selected topics include:

Newton, quasi-Newton, and trust region methods for unconstrained problems
Linear programming
Constrained least squares problems
Convex optimization

If there is interest, we may cover limited aspects of how optimization is used in ML, such as stochastic gradient descent. Although optimization in ML tends to be more practically oriented compared with theory. (There is good theory, but this isn't the class for that!)

Prerequisites

This class is a graduate lecture class. Students should have taken a _graduate level numerical linear algebra or matrix analysis class__ that covers: QR factorizations, the singular value decomposition, null-spaces, and eigenvalues. David will assume you know this stuff, or can learn it yourself, if you take this class. He will also assume an undergraduate level understanding of mathematical analysis, i.e. limits, convergence sequences, sub-sequences. Multi-dimensional Taylor series will also play a large role in the class.

Goals and objectives

Optimization is an incredibly rich and deep field. This graduate class only scratches the surface to show how to use optimization to solve problems, and peeks at the details of how optimization algorithms work.

When we reach the end of the class, you, the student, will:

Understand why optimization is so hard.
Learn to convert written descriptions into optimization problems.
Learn to solve optimization problems using black-box software.
Understand many of the fundmental optimization algorithms, such as quasi-newton methods and linear programming.
Learn about constrained optimization.
Understand why convex optimization is an important development.

Requirements

The formal requirements and percentage of the total course grade are:

In-class quizzes & participation -- 5%
Homeworks -- 40%
Midterm -- 25%
Final project -- 30%

You must meaningfully participate in each of the three components (homeworks, midterm, and final project). Lack of participation in one area may result in a failing grade for the class or a multiple letter grade reduction. (That is, someone who gets a 65% average on the exams and doesn't do any homework might be able to get a D; this policy would reduce their grade to an F; someone who aced both homeworks and the midterm but skipped the final could have gotten a B-, this would reduce them to a C or D. )

Quizzes

Initial policy: These will be worth 5% of the total grade and are graded as taken/missed. Students can miss up to 7 quizzes with no penalty. Make sure you contact the instructor (David) if you anticipate missing more than 5 quizzes due to any absenses as there may be some accommodation in special circumstances. Note that this is an all-or-nothing grade.

Updated policy after week 12: On week 12, we switched to a flipped classroom model for the last four weeks. (Week 13, 14, 15, 16). But one week was spring break. So for 11/15 weeks, we had the above policy.

Consequently, we will reduce the number of "missed" days to 5 under the previous policy, (this corresponds to approximately scaling the days to the length of the class).

For the flipped classroom weeks, the policy will be that you need to participate in class once a week. You can miss one week. You participate by handing in a question relating to the lecture material at the start of class with your name on it. You need to submit one question during the week to get credit for it.

This grade remains all or nothing. So you could miss up to 5 quizzes with no penalty for the first 11 weeks of class, and then miss one week of participation in the flipped classroom.

References

The following textbook (available online) will also be used heavily:

Numerical Optimization. Jorge Nocedal and Stephen J. Wright. 2nd edition. Springer, 2006. Available online for Purdue students!
doi:10.1007/978-0-387-40065-5

Another text book that is used is:

Algorithms for Optimization Mykel Kochenderfer and Tim A. Wheeler. MIT Press, 2019.

I also highly recommend

Linear and Nonlinear Optimization. Igor Griva, Stephen G. Nash, Ariela Sofer SIAM, 2009.

See also the reading list online for additional references.

Officially, the Algorithms for Optimization book is the required one. The required textbook is the best reflection of a textbook that encapsulates a future reference for what is covered in this course. The course can be successfully completed reading Nocedal and Wright instead without purchasing Algorithms for Optimization.

Policies

Conduct and Courtesy

Students are expected to maintain a professional and respectful classroom environment. In particular, this includes:

silencing personal electronics
arriving on time and remaining throughout the class
do not insult or deride others for any reason (even in jest)
be on time for class
please leave class promptly and wait to ask me questions in the hall, unless they pertain to material on the blackboard.

You may use any non-disruptive personal electronics during class. One exception is during in-class quizzes and tests, for which personal electronics are prohibited.

Announcements

We will have an announcement system -- likely I will enter your email address into a list I maintain. This will send an email message to your purdue email address and you are expected to check this account for information related to the class. We will verify that everyone in the class is receiving these messages early on.

Correspondence

The best way to correspond in this class is to post a note on Piazza or Campuswire (whichever we decide to use).

Please feel free to email me with any questions, but please prefix all email titles with the string CS-52000: to aid in filtering email. Also, consider using a private note on Piazza instead.

I will make every effort to respond promptly, however, replies could be delayed due to circumstances outside of my control. In particular, do not rely on a response between the hours of 8pm and 8am.

Please do not attempt to call, google chat, skype, facebook, or tweet with me without prior arrangement.

Assignment clarity

I expect all assignments to be legible and well-written.
Mathematical derivations alone are insufficient and you must explain your reasoning in sentences. For this, I will suggest using a computer with LaTeX to prepare all submitted materials.

If you do not plan to use a computer and LaTeX to prepare solutions to homeworks, you must let me know.

Also, using LaTeX can increase the temptation to share answers. All LaTeX must be written individually.

Missing or late work

The past two years, the class has selected the following policy among a range of options. To be more efficient, this year, I am preselecting the same option.

(Guidance) Homeworks will be posted by Monday night.
Homeworks will be due by Friday at 5pm.
Everyone gets an extension until Monday at 5pm with no penalty.
After Monday at 5pm, Homeworks will be late.
A late homework must be submitted to a different location on blackboard to track the number of late days used.
Everyone gets one free extension day. (But this goes into effect immediately after a late homework.)
A second extension day costs 10 points
A third extension day costs 25 points
A fourth extension day costs 50 points

This policy does not apply on a per-homework basis but on a per-course basis. That is, if you turn in Homework 1 about 5 minutes after the deadline, then you have used your 1 free day. If you then turn in homework 2 about 5 minutes after the deadline, you will lose 10 points (because you have used two extension days, one for HW 1 and one for HW2). If you then turn in homework 3 about 5 minutes after the deadline, you will lose 25 points. If you then turn in homework 4 about 5 minutes after the deadline, you will lose 50 points! (That's almost the value of a homework.)

Note that under this policy, there will be no extensions given for common scenarios including interviews, conferences, minor illnesses, etc.
(There may be extensions for any of the reasons discussed below including grief, etc.) You are expected to manage your time.

Why do we have to have a late work policy?

In order to discuss solutions in class.
In order to return graded homework.
So that class can run smoothly for everyone who is taking it.

Other choices for homework late policies we could reconsider if there is strong student-led momentum.

Policy 1 (Flexible, communicative, and ambiguous policy):

Homeworks can be turned in within a reasonable time-span of the deadline.
If you expect that is impossible, you are responsible for setting a new reasonable deadline (e.g. I'm leaving on an interview, I will get it in...), which will be the new deadline. We have the right to overrule any such deadline if if it is unreasonable in our view.
6 hours would probably always be reasonable (except, perhaps, before an exam.)
12 hours is getting a little unreasonable.
You will be required to agree that the professor and TAs judgement of reasonable is final and will not be negociated.

Policy 2 (Reasonably extended deadlines, prescribed penalty):

(e.g. All homeworks will be due ~5am Monday.)
Everyone gets one free extension day. (But this goes into effect immediately after a late homework.)
A second extension day costs 10 points
A third extension day costs 25 points
A fourth extension day costs 50 points

This policy does not apply on a per-homework basis but on a per-course basis. That is, if you turn in Homework 1 about 5 minutes after the deadline, then you have used your 1 free day. If you then turn in homework 2 about 5 minutes after the deadline, you will lose 10 points. If you then turn in homework 3 about 5 minutes after the deadline, you will lose 25 points. If you then turn in homework 4 about 5 minutes after the deadline, you will lose 50 points! (That's almost the value of a homework.)

Note that under this policy, there will be no extensions given for common scenarios including interviews, conferences, etc.

The last time I taught this, we had Policy 2. But we will take a vote this time.

Here is more detail on policy 2.

(Guidance) Homeworks will be posted by Monday night.
Homeworks will be due by Friday at 5pm.
Everyone gets an extension until Monday at 5pm with no penalty.
After Monday at 5pm, Homeworks will be late.
A late homework must be submitted to a different location on blackboard to track the number of late days used.
Everyone gets one free extension day. (But this goes into effect immediately after a late homework.)
A second extension day costs 10 points
A third extension day costs 25 points
A fourth extension day costs 50 points

Policy 3: (My preference) Except as discussed below, and or by prior arrangement, missing or late work will be counted as a zero.

Policy 4

I expect students to meaningfully attempt the homework problems before the due date.
I want you to make CS 520 homework a regular part of your week.
I expect students to work on and submit HW on time, even if its incomplete or there are unsolved problems.
Problems are scored in two categories: meaningfully attempted, and not attempted.
For any problem that is meaningfully attempted, we will add 100 HW points to the total of such points, up to the total limit of points for HW questions that were meaningfully attempted.

Your HW grade would then be computed by the formula:

    min(your correct points + 100, 
        your total meaningfully attempted points)
    / total homework points

Example: You tried on every problem, but they were hard. So you got around 75% of the homework points (usually around 600). But because you attempted everything, we'd give you (0.75*600 + 100)/600 = 92% instead.

We used this policy in classes in 2020, 2021, and 2022. The idea is to take stress off of you and encourage you to start early and keep working.

Collaboration

Collaboration on homework is allowed and indeed encouraged.
This is a hard class! The final assignments must contain a list of all collaborators. However, students must prepare solutions individually. As an example of the ideal scenario, the following situation is permissible:

A group of students meets to develop the solution to a problem on a white board. Each student records individual notes from this problem solving meeting. All students then prepare solutions individually and without further collaboration. These solutions list the names of all members in the initial group.

The final assignments must contain a list of all collaborators, regardless of if they are in the class or not. Failure to list collaborators will result in a zero on any homework, you must write ``I did not collaborate with anyone on this homework'' if you worked on the homework entirely alone.

Examples of collaborations that are not allowed include, but are not limited to:

Sharing pieces of any written solution
Sharing source code or any other computer programs
Reviewing final written solutions

Collaboration on the project is not encouraged, but students (you!) should feel free to make a case if you think it's a good idea.
Be prepared to justify why collaboration will result in a better project.

Computer codes

The assignments will involve producing computer codes. These need to be documented and written in accordance with best software engineering practices. Failure to follow this advice may result in solutions receiving zero points. Moreover, these should be prepared individually. Groups may discuss implementation strategies, algorithms, and approaches; but codes, like written homework solutions, must be prepared separately.

Debugging

What to do about debugging? That's right, you've gotten the ideas down. You think you have the algorithm right, you coded it. And yet, it still doesn't work. But you can't ask a friend because you can't share code, right? Here is what you should do. Spend 30 minutes working with that code to try and make it work. Write down what you did. If, after that, it still doesn't work. Then spend 15 minutes explaining what your problem is to a friend without looking at the code.

Grading

The anticipated grade ranges are:

A -- 85-100%
B -- 65-85%
C -- 50-65%
D -- 40-50%
F -- 0-40%

These may be adjusted downward by up to 10% to achieve a reasonable grade distribution. They also may be minor upward adjustments.

COVID and Illness

Please do not come to class if - you know you have COVID or influenza or any other respiratory disease - you have a fever - you have a bad cough or extremely runny nose

Please do wear a mask if you choose to come class in any of the scenarios above. Masks work extremely well for source control.

It is my intention to post video recordings of the lectures so you will be able to see the material.

University standard policies

Academic integrity

Behavior consistent with cheating, copying, and academic dishonesty is not tolerated. Depending on the severity, this may result in a zero score on the assignment or exam, and could result in a failing grade for the class.

Academic integrity is one of the highest values that Purdue University holds. Individuals are encouraged to alert university officials to potential breaches of this value by either emailing integrity@purdue.edu or by calling 765-494-8778. While information may be submitted anonymously, the more information that is submitted provides the greatest opportunity for the university to investigate the concern.

Purdue prohibits "dishonesty in connection with any University activity. Cheating, plagiarism, or knowingly furnishing false information to the University are examples of dishonesty." (Part 5, Section III-B-2-a, University Regulations) Furthermore, the University Senate has stipulated that "the commitment of acts of cheating, lying, and deceit in any of their diverse forms (such as the use of substitutes for taking examinations, the use of illegal cribs, plagiarism, and copying during examinations) is dishonest and must not be tolerated. Moreover, knowingly to aid and abet, directly or indirectly, other parties in committing dishonest acts is in itself dishonest." (University Senate Document 72-18, December 15, 1972)

You are expected to read both Purdue's guide to academic integrety and Prof. Gene's Spafford's guide as well. You are responsible for understanding their contents and how it applies to this class.

Course materials

The course materials (homeworks, slides, lecture notes, etc.) are materials that bear my copyright. These materials may not be posted, shared, redistributed to others who are not registered for this class without my express written permission.

Also, the notes you take in class are "considered to be 'derivative works' of the instructor's presentations and materials, and they are thus subject to the instructor's copyright in such presentations and materials." As such, they also cannot be sold or bartered without my express written permission.

Attendance

Students are expected to be present for every meeting of the classes in which they are enrolled. Only the instructor can excuse a student from a course requirement or responsibility. When conflicts or absences can be anticipated, such as for many University sponsored activities and religious observations, the student should inform the instructor of the situation as far in advance as possible. For unanticipated or emergency absences when advance notification to an instructor is not possible, the student should contact the instructor as soon as possible by email, or by contacting the main office that offers the course. When the student is unable to make direct contact with the instructor and is unable to leave word with the instructor's department because of circumstances beyond the student's control, and in cases of bereavement, the student or the student's representative should contact the Office of the Dean of Students.

Grief Absence Policy

Purdue University recognizes that a time of bereavement is very difficult for a student. The University therefore provides the following rights to students facing the loss of a family member through the Grief Absence Policy for Students (GAPS). GAPS Policy: Students will be excused for funeral leave and given the opportunity to earn equivalent credit and to demonstrate evidence of meeting the learning outcomes for misses assignments or assessments in the event of the death of a member of the student's family.

Violent Behavior Policy

Purdue University is committed to providing a safe and secure campus environment for members of the university community. Purdue strives to create an educational environment for students and a work environment for employees that promote educational and career goals. Violent Behavior impedes such goals. Therefore, Violent Behavior is prohibited in or on any University Facility or while participating in any university activity.

Students with Disabilities

Purdue University is required to respond to the needs of the students with disabilities as outlined in both the Rehabilitation Act of 1973 and the Americans with Disabilities Act of 1990 through the provision of auxiliary aids and services that allow a student with a disability to fully access and participate in the programs, services, and activities at Purdue University. If you have a disability that requires special academic accommodation, please make an appointment to speak with me within the first three (3) weeks of the semester in order to discuss any adjustments. It is important that we talk about this at the beginning of the semester. It is the student's responsibility to notify the Disability Resource Center (http://www.purdue.edu/drc) of an impairment/condition that may require accommodations and/or classroom modifications.

Emergencies

In the event of a major campus emergency, course requirements, deadlines and grading percentages are subject to changes that may be necessitated by a revised semester calendar or other circumstances beyond the instructor’s control. Relevant changes to this course will be posted onto the course website or can be obtained by contacting the instructors or TAs via email. You are expected to read your @purdue.edu email on a frequent basis.

Emergency Preparedness

Emergency notification procedures are based on a simple concept:

if you hear a alarm inside, proceed outside.
if you hear a siren outside, proceed inside.

Indoor Fire Alarms are mean to stop class or research and immediately evacuate the building. Proceed to your Emergency Assembly Area away from building doors. Remain outside until police, fire, or other emergency response personnel provide additional guidance or tell you it is safe to leave.

All Hazards Outdoor Emergency Warning sirens mean to immediately seek shelter (Shelter in Place) in a safe location within the closest building. "Shelter in place" means seeking immediate shelter inside a building or University residence. This course of action may need to be taken during a tornado, a civil disturbance including a shooting or release of hazardous materials in the outside air. Once safely inside, find out more details about the emergency. Remain in place until police, fire, or other emergency response personnel provide additional guidance or tell you it is safe to leave.

In both cases, you should seek additional clarifying information by all means possible: Purdue Home page, email alert, TV, radio, etc. Review the Purdue Emergency Warning Notification System multi-communication layers at http://www.purdue.edu/ehps/emergency_preparedness/warning-system.html

Emergency Response Procedures https://www.purdue.edu/emergency_preparedness/flipchart/index.html
Please review the evacuation routes, exit points, emergency assembly area and shelter in place procedures and locations for our building.
Video resources is a 20-minute active shooter awareness video that illustrates what to look for and how to prepare and react to this type of incident. See http://www.purdue.edu/securePurdue/news/2010/emergency-preparedness-shots-fired-on-campus-video.cfm

Mental health

Purdue University is committed to advancing the mental health and well-being of its students. If you or someone you know is feeling overwhelmed, depressed, and/or in need of support, services are available. For help, such individuals should contact Counseling and Psychological Services (CAPS) at (765)494-6995 and http://www.purdue.edu/caps/ during and after hours, on weekends and holidays, or by going to the CAPS office of the second floor of the Purdue University Student Health Center (PUSH) during business hours.

Nondiscrimination

Purdue University is committed to maintaining a community which recognizes and values the inherent worth and dignity of every person; fosters tolerance, sensitivity, understanding, and mutual respect among its members; and encourages each individual to strive to reach his or her own potential. In pursuit of its goal of academic excellence, the University seeks to develop and nurture diversity. The University believes that diversity among its many members strengthens the institution, stimulates creativity, promotes the exchange of ideas, and enriches campus life.

Purdue University prohibits discrimination against any member of the University community on the basis of race, religion, color, sex, age, national origin or ancestry, marital status, parental status, sexual orientation, disability, or status as a veteran. The University will conduct its programs, services and activities consistent with applicable federal, state and local laws, regulations and orders and in conformance with the procedures and limitations as set forth in Executive Memorandum No. D-1, which provides specific contractual rights and remedies.

Schedule

A tentative list of lectures follows. This list may evolve throughout the course. See the web-page for an up-to-date list of lectures, under the "readings" section.

Intro (3-5 lectures) -- Intro (1 lec), Sequences (1-2 lec), Opt. Software (1-2 lec)
Basic optimization (8-9 lectures) -- Unconstrainted (3 lec); Equality constraints (3 lec); Lagrange Multipliers and Gradient Descent (3 lec)
Linear Programs (5-6 lectures)
Line Search Methods (4-6 lectures) and Stochastic Gradient Descent

Midterm

Post-midterm is a slew of topics. This all builds on the tolls above.

Interior Pt. Methods (2 lectures)
Newton + Quasi-Newton (3 lectures)
Trust region + Nonlinear Equations (3 lectures)
Large scale (2 lectures)
Derivative free (2-3 lectures)
Nonlinear progrmaming (2-3 lectures)
Global optimization + stochastic (2-3 lectures)

Instructor absence

David (your instructor) has a few planned absenses this term. We will hold class as usual with another instructor, your TA, or a video lecture.

Makeup classes

If we need to reschedule additional classes, we will do so on an as-needed basis. Our plan is to use video lectures to supplement for any missing class periods.

Changes

This syllabus is subject to change. Updates will be posted on the course website and announced via email.

Initial version: 2023-01-08
Added new late policy choice: 2023-01-09, Fixed number of days of missing
Added Shu's office hours: 2023-01-13
Added participation policy for flipped classroom: 2023-04-12

Computational Methods in Optimization

David Gleich

Purdue University

Spring 2023

Course number CS-52000

Monday, Wednesday, Friday, 1:30-2:20pm

Location Lawson 1106