MATP6640 / ISYE6770 Linear and Conic Optimization
Spring 2020
Course outline.
Grades, software, notes, and other material will be posted on
LMS.
Office hours: In Amos Eaton 325 On Webex Meetings
on Mondays 24pm, Wednesdays 11am1pm, or by appointment.
Material
on reserve in the library.
Scores are available on LMS
 Totals on homeworks 14 out of 210:
209
207
205
203
203
198
198
196
194
186
183
170
167
161
 Scores on the midterm (mean 81, median 82, stdev 12):
99
98
90
87
87
87
82
82
77
77
69
69
64
60
Projects:
Midterm Exam:
In class on Thursday, March 19.
It will cover everything seen in class through Monday, March 16
(Lecture 16).
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.
Here are the robust ampl
model
and
run file,
where you can just change the seed.
Here are the robust ampl
model
and
run file,
which require the use of a
data file
containing the matrix A.
Your graded exam should be availale on LMS.
Old exams:
Homework:
Information about
AMPL.
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.
 Lecture 2: Basic feasible solutions, degeneracy:
handout,
slides,
ipad.
 Lecture 3: Duality.
 Lecture 4: The simplex algorithm.
 Lecture 5:
 Revised simplex, resolution.
 Lecture 6:
 Lecture 7:
 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.
 Lecture 14:
 Lecture 15:
 Lecture 16:
 Interior point methods.
 Lecture 18: The primal affine method:
 Lecture 19:
 Lecture 20:
 Lecture 21:
 Lecture 22:
 SDP and SOCP.
 Lecture 23:
 Lecture 24:
 Lecture 25:
 Lecture 26:
SDP and SOCP.
Lecture 28:
Pages 35/72 to 53/72 and 67/72 to 69/72 from this
talk
on interior point cutting plane methods should be covered.
It is based on a
paper.
The book
Convex Optimization,
by Boyd and Vandenberghe, contains a wealth of material on SDP, SOCP,
and conic programming.
The material on linear programs with complementarity constraints
in Lecture 28 is from two talks:
slides 4/54 to 14/54 from
this one
and slides 12/41 to 24/41 from
this one.
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.