Introduction to Optimization

EN 553.361

Spring 2021

Instructor:

Zachary Lubberts (he/him)

Department of Applied Mathematics & Statistics

Office: wse.zoom.us/my/lubberts.lectures

Office Hours: Wednesday 2:30-3:30 pm or by appointment

(please email me if you’d like to attend)

Email: [email protected]

TAs:

   Section 1

David Sheng (he/him)

Office/Section: JHUBlueJays.zoom.us/my/davidsheng

Office Hour: Mondays 2-4 pm or by appointment

Email: [email protected]

   Section 2

Logan Donaldson (he/him)

Office/Section: JHUBlueJays.zoom.us/my/logandonaldson

Office Hour: Tuesdays 3-5 pm or by appointment

Email: [email protected]

   Section 3

Isha Rai (she/her)

Office/Section: JHUBlueJays.zoom.us/j/3567878634

Office Hour: Wednesdays 7-9 pm or by appointment

Email: [email protected]

Lecture Hours and Location:

Monday, Wednesday, and Friday, 10- 10:50 am

Lectures are delivered online at wse.zoom.us/my/lubberts.lectures, and recordings are available afterwards (links and annotated slides will be posted on Blackboard).

Section 1 will meet at JHUBlueJays.zoom.us/my/davidsheng Thursdays at 9-9:50 am.

Section 2 will meet at JHUBlueJays.zoom.us/my/logandonaldson Thursdays at 3-3:50 pm.

Section 3 will meet at JHUBlueJays.zoom.us/j/3567878634 Thursdays at 7-7:50 pm.

Content:

• Basics of Optimization

• Linear Programming, Polyhedral Sets, and Simplex Method

• Duality in Linear Programming

• Nonlinear Optimization and the KKT conditions

Prerequisite(s): Calculus I and II (AS.110.109 or equivalent), and Linear Algebra (AS.110.201 or equivalent) required. Calculus III recommended. Numerical examples presented in class will be implemented only in MATLAB.

Textbook: None required.

Online Resources: This course will use Blackboard to distribute homework assignments and other course resources, as well as keeping a record of course grades. Zoom will be used for lectures and office hours.

Evaluation

Daily Assignments: 10 homework assignments, assigned every week except exam weeks, submitted via Blackboard.

Examinations:

Exam 1: Posted Friday, Feb. 26th. Due Monday, Mar. 1 at 10 am.

Exam 2: Posted Friday, Apr. 2nd. Due Monday, Apr. 5 at 10 am.

Final Exam: Posted Thursday, May 6. Due Thursday, May 13 at 12 pm.

Grade Distribution:

Homework: 20%

Exam 1: 25%

Exam 2: 25%

Final Exam: 30%

Letter Grade Distribution in %:

A- /A/A+ :   90.00 - 100.00

B- /B/B+ :   80.00 - 89.99

C- /C/C+ :   70.00 - 79.99

D/D+ :        60.00 - 69.99

F :               0 - 59.99

Course Policies:

• General

– You may use the class lecture notes and your own personal notes while taking exams, but you may not use any internet resources or computational tools besides pen/cil and paper. You may not discuss exams in any way with people besides Professor Lubberts and the TAs during the exam period.

– The lowest homework score will be dropped.

– Make-up exams will be offered in the case of a documented absence consistent with the policies at this link.

• Assignments

– Discussion of homework problems among students is encouraged, but when in doubt, direct your questions to the instructor or the teaching assistants.

– Students should submit individual solutions for the homework sets. Discuss all you like before you start writing up solutions, but your submitted solutions should reflect your own understanding and be stated in your own words.

– Late homework will be accepted for up to one week after the deadline, at a 20% penalty. It will not be accepted after this time It is far better to submit an assignment late or incomplete than not at all.

– Homework assignments and exams should be submitted through Blackboard, formatted as a single, organized file (pdf preferred). If there are programming questions, you should also submit your .m files (this will be indicated on the assignment). Do not include printouts of intermediate computations unless specifically requested, and in these cases, limit the amount to the first few and last few iterations.

• Attendance

– Attendance is encouraged whenever possible, but annotated slides and lecture videos will be made available as soon as possible after the lecture for those unable to attend.

– If you are unable to regularly attend lecture, I strongly encourage you to set a specific time each day where you will watch the previous lecture, and to attend either my or the TAs’ office hours. Remember that you can request an appointment if the standard time does not work for you.

• Exceptional Circumstances

– It’s been a strange couple of years. If significant issues arise which are affecting your ability to learn the material or submit assignments, please contact me as soon as possible so that we can adjust accordingly.

Tentative Course Outline and Schedule:

The following course schedule reflects the order in which material will be presented, but may undergo small changes based on implementation.

Day	Date	Topic	Notes
Mon.	Jan. 25	Introduction and Review
Wed.	Jan. 27	Review; Basic Topology
Thurs.	Jan. 28	Discussion Section
Fri.	Jan. 29	Optimality Conditions
Mon.	Feb. 1	Intro to Linear Programming
Wed.	Feb. 3	Polyhedral Sets and Geometry
Thurs.	Feb. 4	Discussion Section
Fri.	Feb. 5	Polyhedral Sets and Geometry	Homework 1 Due
Mon.	Feb. 8	Characterizing Solutions to LPs
Wed.	Feb. 10	Characterizing Solutions to LPs
Thurs.	Feb. 11	Discussion Section
Fri.	Feb. 12	Characterizing Solutions to LPs	Homework 2 Due
Mon.	Feb. 15	Simplex Method
Wed.	Feb. 17	Simplex Method
Thurs.	Feb. 18	Discussion Section
Fri.	Feb. 19	Simplex Method	Homework 3 Due
Mon.	Feb. 22	Simplex Method
Wed.	Feb. 24	Simplex Method Odds and Ends
Thurs.	Feb. 25	Discussion Section
Fri.	Feb. 26	Simplex Methods Odds and Ends	Homework 4 Due; Exam 1 Posted
Mon.	Mar. 1	Duality for Linear Programming	Exam 1 Due
Wed.	Mar. 3	Duality for Linear Programming
Thurs.	Mar. 4	Discussion Section
Fri.	Mar. 5	Duality for Linear Programming
Mon.	Mar. 8	Complimentary Slackness
Wed.	Mar. 10	Complimentary Slackness
Thurs.	Mar. 11	Discussion Section
Fri.	Mar. 12	Duality and Slackness	Homework 5 Due
Mon.	Mar. 15	Dual Simplex Method
Wed.	Mar. 17	Dual Simplex Method
Thurs.	Mar. 18	Discussion Section
Fri.	Mar. 19	Linear Programming Wrap-Up	Homework 6 Due
Mon.	Mar. 22	Spring Break Day	No Class
Wed.	Mar. 24	Selections of Multi-D Calculus
Thurs.	Mar. 25	Discussion Section
Fri.	Mar. 26	Selections of Multi-D Calculus	Homework 7 Due
Mon.	Mar. 29	Optimizing Convex Functions
Wed.	Mar. 31	Optimizing Convex Functions
Thurs.	Apr. 1	Discussion Section
Fri.	Apr. 2	Optimizing Convex Functions	Homework 8 Due; Exam 2 Posted
Mon.	Apr. 5	Newton’s Method	Exam 2 Due
Wed.	Apr. 7	Steepest Descent
Thurs.	Apr. 8	Discussion Section
Fri.	Apr. 9	Farkas’ and Gordon’s Theorems
Mon.	Apr. 12	Nonlinear Programming
Wed.	Apr. 14	Spring Break Day	No Class
Thurs.	Apr. 15	Discussion Section
Fri.	Apr. 16	Characterizing Solutions to NLPs	Homework 9 Due
Mon.	Apr. 19	Characterizing Solutions to NLPs
Wed.	Apr. 21	Characterizing Solutions to NLPs
Thurs.	Apr. 22	Spring Break Day	No Discussion Section
Fri.	Apr. 23	KKT Conditions	Homework 10 Due
Mon.	Apr. 26	Implications of KKT
Wed.	Apr. 28	Implications of KKT
Thurs.	Apr. 29	Discussion Section
Fri.	Apr. 30	Spring Break Day	No Class
Thurs.	May 13	Final Exam Due	Final Exam Due 12 pm

Course Goals

Specific outcomes for this course are as follows:

• Students will learn how to model industrial and real-life optimization problems in a mathematical framework.

• Students will learn methods of solving these optimization problems.

• Students will understand the theory behind these methods of solving optimization problems.

This course will address the following Criterion 3 Student Outcomes:

• An ability to apply knowledge of mathematics, science and engineering (Criteria 3(a))

• An ability to design a system, component, or process to meet desired needs within realistic constraints such as economic, environmental, social, political, ethical, health and safety, manufacturability, and sustainability the design process (Criteria 3(c))

• An ability to design a system, component, or process to meet desired needs within realistic constraints such as economic, environmental, social, political, ethical, health and safety, manufacturability, and sustainability recognition of constraints within design (Criteria 3(c))

• An ability to identify, formulate and solve engineering problems (Criteria 3(e))

• An understanding of professional and ethical responsibility (Criteria 3(f))

• An ability to communicate effectively (writing) (Criteria 3(g))

• The broad education necessary to understand the impact of engineering solutions in a global, economic, environmental and societal context (Criteria 3(h))

• A recognition of the need for and an ability to engage in life-long learning (Criteria 3(i))

• An ability to use the techniques, skills, and modern engineering tools necessary for engineering practice (Criteria 3(k))

Ethics

The strength of the university depends on academic and personal integrity. In this course, you must be honest and truthful. Ethical violations include cheating on exams, plagiarism, reuse of assignments, improper use of the Internet and electronic devices, unauthorized collaboration, alteration of graded assignments, forgery and falsification, lying, facilitating academic dishonesty, and unfair competition. Report any violations you witness to the instructor.

You can find more information about university misconduct policies on the web at these sites:

• For undergraduates: jhu.edu/undergrad-students/student-life-policies/

• For graduate students: jhu.edu/grad-students/student-life-policies/

Disability Accommodations

If you are a student with a disability or believe you might have a disability that requires accommodations, please contact Student Disability Services at 410-516-4720, studentdisabil-[email protected], or in-person at 385 Garland Hall. I work with this office to ensure that students have the accommodations they need to learn and to be fairly evaluated, but this coordination happens best when both parties have sufficient notice of the needed accommo-dations, so please let them and me know as soon as you are able.

Diversity and Inclusion Statement

“Johns Hopkins is a community committed to sharing values of diversity and inclusion in order to achieve and sustain excellence. We firmly believe that we can best promote excellence by recruiting and retaining a diverse group of students, faculty and staff and by creating a climate of respect that is supportive of their success. This climate for diversity, inclusion and excellence is critical to attaining the best research, scholarship, teaching, health care and other strategic goals of the Health System and the University. Taken together these values are recognized and supported fully by the Johns Hopkins Institutions leadership at all levels. Further, we recognize that the responsibility for excellence, diversity and inclusion lies with all of us at the Institutions: leadership, administration, faculty, staff and students.”

-Johns Hopkins Diversity Leadership Council

Mathematics is a field that in America has historically been quite homogenous, but as with any discipline, it benefits tremendously from the intersection of diverse people and minds: in my own education, several of my research advisors and collaborators belong to various underrepresented groups in the field, and without them my understanding of mathematics would be far less than it is today. In short, no matter who you are, I want to help you learn mathematics.

University Resources

A wealth of university resources may be found at studentaffairs.jhu.edu/resources/.

In particular, the Counseling Center may be found at studentaffairs.jhu.edu/counselingcenter/.

They provide a variety of mental health and crisis management services.

Sexual Misconduct Support

“Johns Hopkins University is committed to promoting a safe and supportive environment for each and every member of our community. If you have been sexually assaulted or a victim of sexual violence, we urge you to reach out for emotional support and medical care. We also stand ready to assist you with a complaint through JHU and/or local law enforcement.”

-Johns Hopkins Sexual Assault Response & Prevention Website

The following website lists several resources for victims of sexual misconduct: sexualas-sault.jhu.edu, and offers a confidential helpline at 410-516-7333.

In the language of the Johns Hopkins SMPP (available here), I am a Responsible Employee, which means that I am required to refer any disclosure of sexual misconduct to the Title IX Coordinator, including any relevant details. While I am available to listen, you should know that I cannot keep the information confidential. Confidential resources are available at sexualassault.jhu.edu, and there is a confidential helpline available at the phone number above, 410-516-7333.