MATP6640 / ISYE6770 Linear and Conic Optimization
Spring 2022
Course outline.
Grades, software, notes, and other material will be posted on
LMS.
Piazza: the piazza page for the class is
here.
This term we will be using Piazza for class discussion.
The system is highly catered to getting you help fast and efficiently
from classmates, the TA, and myself. Rather than emailing questions to me,
I encourage you to post your questions on Piazza.
If you have any problems or feedback for the developers, email team@piazza.com.
Box:
In addition to LMS,
class material should be posted in this
Box folder.
Instructions to set up your box account are here:
RPI Box account information.
Office hours:
On Webex
on Thursdays 11am1pm, or by appointment.
https://rensselaer.webex.com/meet/mitchj
Material
on reserve in the library.
Scores will be available on LMS
Projects:
Midterm Exam:
In class on Friday, March 18.
It will cover everything seen in class through Tuesday, March 15
(Lecture 15).
You can bring one sheet of handwritten notes, no larger
than 8.5" x 11". You can write on both sides.
Here are the solutions.
Mean: 60.6%, median 65%, StDev 20.3.
Old exams:
Homework:
Information about
AMPL.
The software and instructions are available on LMS and Box.
Notes:
These are typed pdf notes.
Handwritten scanned copies of my notes from previous semesters
can be found here.
 Introduction, basic feasible solutions,
duality, and the simplex algorithm.
 Lecture 1: Introduction.
 Some examples:
handout,
slides,
ipad.
 Standard form:
handout,
slides,
ipad.
 Linear algebra background:
handout,
slides,
ipad.
 Affine sets:
handout,
slides,
ipad.
 Faces:
handout,
slides,
ipad.
on webex.
 Link to the
recorded lecture
 Lecture 2:
Basic feasible solutions, degeneracy:
handout,
slides,
ipad.
Link to the
recorded lecture
 Lecture 3: Duality.
 Lecture 4: The simplex algorithm.
 Lecture 5:
 Revised simplex, resolution.
 Lecture 6:
 Lecture 7:
 Dual simplex method:
handout,
slides,
ipad.
 The KleeMinty cube:
handout,
slides,
ipad.
 FourierMotzkin elimination:
handout,
slides,
ipad.
 Using Farkas to prove strong duality:
handout,
slides,
ipad.
 Resolution:
handout,
slides,
ipad.
 Lecture 8:
The Weyl and Minkowski theorems:
handout,
slides,
ipad.
 Column generation methods.
 Lecture 9:
 Lecture 10:
 Lecture 11:
 Problems on graphs and networks.
 Lecture 12:
 Lecture 13:
 Lecture 14:
 Stochastic programming.
 Interior point methods.
 Lecture 18:
 Lecture 19: The primal affine method:
 Lecture 20:
 Lecture 21:
 Lecture 22:
 SDP and SOCP.
 Lecture 23:
 Lecture 24:
 Lecture 25:
 Lecture 26:
 Lecture 27:
Handouts:
 Linear
algebra. (Lecture 1.)
 Subspaces,
affine sets, convex sets, and cones. (Lecture 1.)
 Dimension, polyhedra, and
faces. (Lecture 1.)

An iteration of the simplex algorithm
and
the algorithm. (Lecture 4.)

Handling upper bounds in
the simplex algorithm. (Lecture 5.)
 The dual simplex
algorithm. (Lecture 6.)
 Extreme points
and extreme rays of polyhedra. (Lecture 8.)
 An example of DantzigWolfe decomposition. (Lecture 9.)
Papers and resources:

An electronic copy of the textbook for the second half of the course is
available for free through the library:
S. Wright, Primaldual Interior Point Methods, SIAM, 1997.
Note: more generally,
SIAM ebooks
are free to RPI students through the library.
In addition,
SIAM membership
is free for RPI students, and SIAM books are
discounted 30%
for members if you buy directly from SIAM.

The book
A
First Course in Linear Optimization, Third Edition, Reex Press, 201317
by
Jon Lee
is available online.
 The book
Convex Optimization,
by Boyd and Vandenberghe, contains a wealth of material on SDP, SOCP,
and conic programming.
 Introduction to
Stochastic Programming by Birge and Louveaux
is available online via the RPI library.

A
computational study of DantzigWolfe decomposition,
the doctoral thesis of James Tebboth.

Issue 87
of the Mathematical Optimization Society newsletter
Optima,
discussing the geometry of polyhedra and simplex pivoting rules.
John Mitchell's homepage.