MATH 171A - Introduction to Numerical Optimization:
Linear Programming - Winter 2020


Lecture: Tu Th 3:30 pm - 4:50 pm at CENTR 115
Instructor: Mareike Dressler
eMail: mdressler@ucsd.edu
Office: AP&M 6444
Office Hours: Tu Th 10:00 am - 11:00 am at AP&M 6444

Discussion: A01: W 5:00 pm - 5:50 pm at HSS 1315, Chuqing
A02: W 6:00 pm - 6:50 pm at HSS 1315, Chuqing
A03: W 7:00 pm - 7:50 pm at HSS 1315, Jiajie
A04: W 8:00 pm - 8:50 pm at HSS 1315, Jiajie
Teaching Assistant:     Chuqing Shi
eMail: chs139@ucsd.edu
Office Hours: Tu 5:00 pm - 6:00 pm and F 9:00 am - 10:00 am at AP&M 1240
Teaching Assistant:     Jiajie Shi
eMail: jis254@ucsd.edu
Office Hours: F 2:00 pm - 4:00 pm at AP&M 1131
Credit Hours:    4 (Credit not allowed for both MATH 171A and ECON 172A.)
Prerequisites:    MATH 18 or MATH 20F or MATH 31AH, and MATH 20C. Students who have not completed listed prerequisites may enroll with consent of instructor.
Course description: Math 171A is an upper-division course introducing students to the field of mathematical optimization, in particular, the area of linear optimization (historically known as linear programming). Topics covered in this course include the geometry of linear programming, optimality conditions, the simplex method, duality theory.

Some homework assignments will require the use of the package Matlab, although no prior knowledge of Matlab is assumed. Matlab enables the student to concentrate on the fundamental ideas of linear programming without becoming distracted by the rigors of mental arithmetic.

The aim of the class is for students to
  • recognize different formulations of problems,
  • understand the basic theory and methods for linear optimization problems,
  • determine whether a problem has a solution or not, and
  • gain practical experience by utilizing state-of-the-art tools.
Textbook: There is no required textbook for this course. A copy of "Linear Programming Notes" by Philip E. Gill, Walter Murray, and Margaret H. Wright will be made available to enrolled students. Please do not distribute these notes.
Syllabus:    This website acts as our syllabus.

Exams:  There will be three exams in the class:

There will be no make-up exams! I.e., you must take your midterms on the scheduled dates at the scheduled times; they will not be offered at an alternate time. It is your responsibility to ensure that you do not have a schedule conflict involving the final exam; you should not enroll in this class if you cannot sit for the final exam at its scheduled time.

⭢ You may use one 8.5 x 11 inch sheet of handwritten notes (which may be written on both sides, no photocopies!). No books, calculators, phones, or other aids may be used during exams.

Homework:  Homework will be assigned weekly, and is due on Fridays at 11:00 am, starting in Week 2. Homework problems will be uploaded on Canvas and Gradescope. There will be nine (9) homework assignments in total.
The lowest homework grade will be dropped.

Homework and late homework policy:

Homework philosophy and collaboration policy:

Canvas:  We will use Canvas for class announcements and additional material uploaded for your convenience and help.

Gradescope:  Your midterm exams and final will be scanned and uploaded using an online tool called Gradescope and will be graded within it. As a consequence, exams will not be returned to the students. Instead, a digital version of your exams will be made available after the grading has been completed. An email will be sent from Gradescope when the exams are made available.

Piazza:  We will use Piazza for class discussions. Post on Piazza whenever you're confused about homework, the lecture, course logistics, or anything relevant to the course. Do not let yourself be silenced by the fear of looking stupid. Your classmates, the TAs, and I will answer. You are strongly encouraged to post messages on Piazza instead of emailing me or the TAs directly.

Grading Information

There are two methods to determine your course grade. Your grade will be determined using both methods and then the best grade will be used.

After your weighted average is calculated, letter grades will be assigned based on the following grading scale:

A+ A A- B+ B B- C+ C C-
979390878380777370

The scale may be adjusted to be more lenient (depending on the performance of the class). While the scale may be adjusted to be more lenient, the grade corresponding to a given percentage is guaranteed not to be lower than specified by the above scale.

Notes

Course Calendar

The following is a tentative plan and is subject to change or revision. Content covered will be added/updated below as the course progresses.

Week Monday Tuesday Wednesday Thursday Friday
1
  Jan 07

Overview of the Class:
Introduction to Optimization
Jan 08

Discussion
Jan 09

Properties of Linear Constraints and Geometry of the Feasible Region
 
2
  Jan 14

Properties of the Feasible Region and of the Objective Function
Jan 15

Discussion
Jan 16

Two Methods for Toy Linear Programs,
Full-Rank Systems of Linear Equations
Jan 17

Homework 1 due
3
Jan 20

Martin Luther King, Jr. Holiday
Jan 21

Full-Rank Systems cont'd,
Properties of Incompatible Equations
Jan 22

Discussion
Jan 23

Prop's of Incompatible Equations cont'd,
Linear Programming with Equality Constraints
Jan 24

Homework 2 due
4
  Jan 28

Midterm I
Jan 29

Discussion
Jan 30

Optimality Conditions for Equality Constraints,
Feasible Directions for Inequality Constraints
Jan 31
Homework 3 due
Last Day to Drop w/o 'W'
5
  Feb 04

Vertices, Finding a Vertex
Feb 05

Discussion
Feb 06

Optimality Conditions for Linear Programming
Feb 07

Homework 4 due
6
  Feb 11

Farkas' Lemma and its Implications
Feb 12

Discussion
Feb 13

The Simplex Method
Feb 14
Homework 5 due
Last Day to Drop w/o 'F'
7
Feb 17

Presidents' Day
Feb 18

Degenerate Constraints,
Mitigating the Ill-Effects of Degeneracy
Feb 19

Discussion
Feb 20

Finding a Feasible Point
Feb 21

Homework 6 due
8
  Feb 25

Midterm II
Feb 26

Discussion
Feb 27

LPs with Mixed Constraint Types
Feb 28

Homework 7 due
9
  Mar 03

LPs in Standard Form,
Simplex Method for Standard-Form LPs
Mar 04

Discussion
Mar 05

Linear Programming Duality Theory
Mar 06

Homework 8 due
10
  Mar 10

More Duality Theory,
Complexity of Simplex Method
Mar 11

Discussion
Mar 12

Other techniques for solving LPs,
Applications of Linear Programming,
Recap
Mar 13

Homework 9 due
11   Mar 17
space
Final Exam
3:00pm-6:00pm
     

Study Resources

MATLAB Resources

Etiquette: Etiquette includes things like giving credit where credit is due, and treating your peers respectfully in class. In addition, here are a few of our expectations for etiquette in and out of class.

Academic Integrity:  Academic integrity is highly valued at UCSD and academic dishonesty is considered a serious offense. Students involved in an academic integrity violation will face an administrative sanction which may include suspension or, in very serious cases, expulsion from the university. Your integrity has great value: Cultivate and protect your academic integrity. Click here for more information on academic integrity and its value.
Academic Accomodations:  Students needing academic accommodations must register with the Office for Students with Disabilities (OSD). The student must provide the appropriate accommodation documentation to the instructor no later than the end of the first week of classes.