MATH 435 Linear Optimization
MATH 535 Optimization I
Instructor: Hemanshu Kaul
Office: Rettaliata Engg Cntr 125C.
E-mail: kaul [at] iit.edu
Time: 1:50pm-3:05pm, Tuesday and Thursday.
Place: Hermann Hall 003.
Office Hours: Tuesday at 12:30pm-1:30pm, and Thursday at 4:30pm-5:30pm. And by appointment in-person or through Zoom (send email).
TA Office Hours: Alaittin Kirtisoglu, Wednesday 2pm-5pm at RE 129 or through Math Tutoring Center.
|Course Information|
|Advice|
|Announcements|
|Examinations|
|Weekly Class Log & HW|
|Supplemental Readings|
Course Information:
This course develops the theory and algorithms of Linear Optimization from a linear algebraic and geometric perspective. It focuses on developing the rigorous foundations of linear optimization algorithms based on linear algebra. In addition to the properties of the Simplex Method, it delves in some depth into topics like duality theory in both Linear and Integer programs, sensitivity analysis, decomposition techniques for large scale optimization including applications to stochastic programming, integer and combinatorial optimization.
The Course Information Handout has extensive description of the course - topics, textbook, student evaluation policy, as well as other relevant information. Read it carefully!
What is this course really about? Required reading.
The official MATH 435/ 535 course topics.
Advice for students:
Excellent advice by Francis Su on good mathematical writing.
Why do we have to learn proofs? by Josh Cooper.
On a more abstract note, here is a discussion of Language and Grammar of Mathematics - which is what you are learning in a course like this.
Excellent advice for mathematics students, especially those planning to go on to or are already in graduate school, by Terry Tao, 2006 Fields medallist. Excellent reading.
Read this book on a variety of experiences in the journey to learn mathematics:
Living Proof
Some of the primary sources of information/discussion for careers in Mathematical Sciences:
MAA - Careers
SIAM - Careers
INFORMS - Careers
AMS - Careers
Class Announcements:
- Thursday, 1/15 : This webpage will be updated every Thursday unless otherwise announced.
- Tuesday, 1/13 : Check this webpage regularly for homework assignments, announcements, etc.
Examinations:
- Exam #1 : TBA . Syllabus: Based on topics, examples, and problems corresponding to HWs #1-#5.
- Exam #2 : TBA . Syllabus: Based on topics, examples, and problems corresponding to HWs #6-#10.
- Final Exam : TBA by university . Syllabus: All topics covered during the semester.
Weekly Class Log with HW:
- Homework #0
Linear Algebra Background : Read and understand the Linear Algebra background (MATH 332 or its equivalent is a pre-requisite for this course) from Section 1.5 within the first 10 days of the semester.
You need to be familiar with topics like - System of linear equations, Row operations for solving systems of linear equations, R^n as a vector space, Subspaces, Span, Linear Independence, Basis, Dimension, Nullspace of a matrix, Matrix rank, Affine subspaces.
You can pick up any standard undergraduate linear algebra textbook from the IIT library, like Anton, Elementary Linear Algebra, 9th/ 10th ed. or Lay, Linear Algebra and its applications, 3rd ed., and follow along the topics covered in my IIT course at
Math 332.
Another option is to use the MIT linear algebra site and study at least the lectures 1-11 as given under video lectures.
Of course, feel free to consult with me on any of these topics that you have difficulty with. Stop by during my office hours.
- Week #1 : 2 Lectures.
- Topics and Readings: Discussion of the course; Linear Optimization as a tool for general-purpose modeling and general purpose optimization algorithms - Max Flow Problem as LP; Logistics and setting up the Transportation/ Min Cost Network Flow problem as an LP; Linear Program and its various forms, Basic terminology, Matrix and vector forms for setting up an LP, How to convert any LP into standard form. (From Sections 1.1, 1.2, and elsewhere)
- Homework:
The homeworks listed below are from the course textbook unless otherwise noted.
Follow the detailed instructions and rules for HWs given in the Course Information Handout and through emailed comments.
- Reading HW:
Read and understand Examples from Section 1.2.
Read the discussion on page 18 (Section 1.3).
- Homework #1 for submission [PDF]. Due Thursday, 1/22, by 11pm in Canvas. Submit a single PDF file through Canvas Assignment.
Questions? Ask on Canvas Discussion Forum. Or, Ask for help during the instructor and TA office hours, or through email to the instructor.
- Week #2 : 2 Lectures.
- Topics and Readings: Why standard form? its relation to general solution of system of m linear equations in n variables, and the related concepts of Null space of A, nullity, rank, etc., When are two LPs (or optimization problems) equivalent? Converting an optimization problem with a piecewise linear objective function into an LP, Removing absolute value function from an optimization problem - two methods. Geometric method of solution using family of parallel lines perpendicular to c, the cost vector, Different possible solutions for an LP based on different cost functions. (From Sections 1.2, 1.3, 1.4, 1.5, and elsewhere)
- Homework:
The homeworks listed below are from the course textbook unless otherwise noted.
Follow the detailed instructions and rules for HWs given in the Course Information Handout and through emailed comments.
- Reading HW:
Read the discussion on page 18 (Section 1.3).
Read Section 1.8.
Read the initial few pages of Section 2.1.
- Homework #2 for submission. Due Thursday, 1/29, by 11pm in Canvas. Submit a single PDF file through Canvas Assignment.
BT 1.4, BT 1.5ab, BT 1.6, BT 1.14.
[Comment for 1.14: You should show a sketch in your solution to illustrate/justify the answer for part(c).]
[Comment for 1.5b: Proving the following two statements is enough to finish the proof. You need to submit the proof of only ONE of these two statements. Below, P0 refers to the given optimization problem, P1 refers to the first reformulation, and P2 refers to the second reformulation.
(i) Given a feasible solution of P0, find a feasible solution of P1 with cost no more than the cost in P0.
And, given a feasible solution of P1, find a feasible solution of P0 with cost no more than the cost in P1.
(ii) Given a feasible solution of P0, find a feasible solution of P2 with cost no more than the cost in P0.
And, given a feasible solution of P2, find a feasible solution of P0 with cost no more than the cost in P2. ]
Questions? Ask on Canvas Discussion Forum. Or, Ask for help during the instructor and TA office hours, or through email to the instructor.
Supplemental Reading:
For an alternate point-of-view and for additional applications, refer to the following books:
- LP book by Vanderbei
- H.P. Williams, Model Building in Mathematical Programming, Fifth Edition.
- Hillier and Lieberman, Introduction to Operations Research, 7th edition onwards.
Links for Additional Information:
HOME