MAT 168: Optimization
Spring 2008
Instructor
Teaching Assistants
We are fortunate to have two teaching assistants for this course:
- Qiang Wang
- Office: MSB 3151
- Office Hours: Tuesday 3-4 PM
- Rob Gysel
- Office: MSB 3129
- Office Hours: Thu 9-10 AM
Course Time and Place
-
MWF 3:10 - 4:00 PM, 2016 Haring
Grading percentages
- Weekly Homework: 10%
- Programming Projects: 30%
- Midterm: 20%
- Final: 40%
-
The lowest two scores on your homework assignments will be dropped.
Textbook
We will be using Linear Programming: Foundations and Extensions
by R.J. Vanderbei.
`
Feel free to use either the Second or Third edition.
Description and Syllabus
This course is an introduction to optimization. We will
cover both constrained and unconstrained optimization,
but with an emphasis on the former.
Our primary focus will be on linear programming. We will
be discussing the simplex method, duality, interior
point methods, and numerous applications and examples.
We will also discuss unconstrained optimization,
with an introduction to the solution of nonlinear equations
and unconstrained nonlinear least-squares problems
via iterative methods.
A detailed syllabus can be found at
www.math.ucdavis.edu/~bremer/spring2008/mat168/syllabus.pdf
.
News
Take-home Final
A take-home final will be distributed in class on Wednesday,
June 4. A copy can also be found here.
It is due on the date of our final, June 11. It can be
turned in anytime between June 4 and June 11 by putting
it in my box in the MSB building or sliding it
under my office door (MSB 2230).
I will also make it available online, here.
Programming Projects
Three programming projects will be assigned during the semester. Each will
be worth 10% of your grade for the course. Details will be provided in class
and posted here later, but expect the first project to be given out during
the second week of class.
Project one is available here. Its due
Wednesday April 30. The associated data file returns.m can be
downloaded here.
Instruction for submitting project one:
- Put the MATLAB scripts you wrote for the project as well as a text
file (a PLAIN text file with no formatting information) in a single .zip
or .tar archive.
- Make sure that your script "solveall.m" prints out the correct information
for each of the three cases: the value of the constant mu, the solution vector,
and the value of the objective function.
- Email the .zip or .tar archive to the address
ucdavis.mat168.projects@gmail.com.
Make the subject line your full name as you are registered for the course.
- You should receive a confirmation reply email within a few minutes. If you don't,
it means you made a mistake submitting the project (perhaps sending it to the wrong
email address).
- Submissions must be received before midnight on Wednesay April 30, 2008 to
receive creidt.
- If you are having difficulties submitting the projects, I will be in my office
on wednesday afternoon until 5:30 PM. You can come by or email me.
Project two
The due date for project two was extended to June 4, 2008,
as I announced in class.
Please turn it in by emailing a .tar or .zip file with
your code to
ucdavis.mat168.projects@gmail.com.
Project two is available here.. It dues
date has been extended to June 4, 2008.
Here is the file containing headers
for the project 2 functions.
Homework Assignments
- Homework will be collected at the beginning
of class each Wednesday, starting with
the second week of class.
- Remember that the primary purpose of homework assignments
is to test your knowledge of the
course material without the pressure of an exam.
- Late assignments
will not be accepted. All assignments refer
to problems in Vanderbei, 2nd Edition.
- Please make sure all the work you turn in is neat and
legible.
- This is a list of homework exercises which will be collected.
You are encouraged to work other exercises in the book in addition
to these problems.
Due Wednesday, April 9:
Due Wednesday, April 16:
- Chapter 2, problems 2.2,2.5,2.9,2.17, and 2.18.
- Additional Problem: Give an example of an iteration
in the Simplex Method where there is more than one
choice of leaving variable (that is, variable that
changes from independent to dependent).
- Chapter 3, problem 3.2.
Due Wednesday, April 23:
- Chapter 4, problem 4.1, 4.3 (use Matlab and the pivot tool I provided to do
these problems. If you turn these in as a printout, make sure to include
each of the pivot steps).
- Chapter 5, problems 5.1, 5.5.
Due Wednesday, April 30:
- Chapter 6, problems 6.1, 6.6
Due Wednesday, May 7:
- Chapter 7, problems 7.3, 7.8
Due Wednesday, May 21:
- Write down the linear programs for the
newtwork flow problems in problems 14.1
and 14.3 in the book. You do not need to
do those problems or solve the linear programs.
- Let A be an m by n matrix, n > m, of rank m.
Given a vector b of length m, explain why
the equation Ax=b has an infinite number of solutions.
Show that the problem of finding the
vector x with the smallest L^1 norm such that
Ax=b can be solved using linear programming
(i.e., write down a linear program for
solving this problem).
Due Wednesday, May 28:
- Chapter 15, Problem 15.4
- Chapter 15, Problem 15.5
Due Wednesday June 4: