The University
of Texas at Austin
Department of Electrical and
Computer Engineering
Fall Semester 2012
Some Basic Information
Instructors: Constantine Caramanis
/ Sujay Sanghavi
Email: caramanis/sanghavi AT mail DOT utexas DOT edu Phone: (512)
471-9269 Office: ENS 427/429 Constantine's Office Hours:
Tuesday 2:00 pm Sujay's Office Hours: Monday 2:00 pm
TA: Dohyung Park
Email: dhpark AT utexas DOT edu
Office: ENS 138
Office Hours: Wednesday 2 - 4 pm
Lectures:
Time: Tuesday and Thursday, 12:30-2:00 PM, Location: RLM 6.104
Course Overview
This is the first course in a two-course sequence
on Large-Scale Optimization and Learning.
While the first course will focus on optimization and the
second on learning, we will draw examples from
learning throughout the first course.
The first
course in the sequence will focus on Convex Optimization including basic material from convex
geometry, convex analysis and convex optimization.
It will cover basic modeling, and understanding
how to find and exploit convexity, both for theoretical analysis, and also for developing
algorithms.
Intended audience: This class is structured to be interesting and
relevant to students who are using or plan to use optimization in their research, and are interested
in solving large-scale optimization problems.
The target audience is quite broad: graduate students
from ECE, CS, OR, Math, DSSC, and
related disciplines.
Course Prerequisites
This class does not assume previous exposure to optimization.
(However, if you have previously taken
courses such as Linear Programming, there should be minimal
overlap with this class.) Good familiarity
with Liner Algebra (at the level of, e.g., EE380K) is
important, as we will freely use concepts, tools and techniques from linear algebra.
Some basic
knowledge of Matlab will also be needed, although basic familiarity with programming should be
sufficient.
General Note: If you are concerned about the prerequisites or your background, or
what the course will cover, please don't hesitate to contact us by e-mail, or come by office hours.
Grading: Homeworks, Exams and Scribing
The grade for the course will be determined by
three components: Problem sets (15%), Scribing (5%),
a Midterm Exam (35%) and a Final Exam (45%).
Problem sets will be given out approximately weekly. The midterm and final
will be in-class
closed-book exams.
Scribing: Each student is expected to scribe a lecture in
latex. The scribing will be done in groups of two or three students. The goal
is to produce a
high-quality, complete record of the material covered in class. Students that scribe a Tuesday
lecture are expected to submit a high-quality,
polished and complete draft to Constantine and Sujay
by Friday of the same week. Students scribing a Thursday lecture should submit this by Monday. This
leaves time for some
iteration if required, with the goal of posting the scribed notes within a week
of the class scribed.
You can find the necessary scribing templates here.
Please reference completely and fully, as if you were writing a paper to submit. Also, as with any paper, all the writing should be your own.
Policy on Collaboration: Discussion of homework questions is encouraged. Please be sure to
submit your own independent homework solution. This includes any matlab code required for the
assignments. Late homework assignments will not be accepted.
Text and References
The course will be taught from a collection of sources. The primary
reference is the book: Convex Optimization by Stephen Boyd and Lieven Vandenberghe. Note
that this book is available on line.
Additional References: Some additional references that may be helpful:
Convex and Nonlinear Optimization:
- Nonlinear Programming by D.P. Bertsekas. (This book is a must-have. It covers algorithms and theory for convex and nonlinear optimization.)
- Numerical Optimization by J. Nocedal and S. Wright. (This book covers both theory and algorithms for convex optimization, and is an excellent supplement to what we
will cover in this course. Note: The UT Library offers this book electronically to students.).
- Linear and Nonlinear Programming by D.G. Luenberger and Y. Ye. (A recently -- and heavily -- revised classic, this is another excellent reference for all the analysis and
algorithms we cover.)
- Applied Optimization Formulation and Algorithms
for Engineering Systems by Ross Baldick. (Of the books on this
list, this is probably the best for
giving concrete ideas of
formulation and application to real-world problems. Additionally, it also
does an excellent job of reviewing much of the theory discussed here).
- Linear
Optimization by D. Bertsimas and J.N. Tsitsiklis.
(This book is a great book on the theory and
algorithms of linear optimization. It does not have much on more general
optimization formulations).
Convex Analysis:
- Fundamentals of Convex Analysis by
Hiriart-Urruty and Lermar\'echal. (This book is a condensed version of a two-volume set by the same
authors, and is a nice, readable overview of the basic theory of convex analysis.)
- Convex
Analysis by T.J. Rockafellar. (This book is a classic in the field, but considered more of a
reference for the intiated, than a first point of contact with the subject).
- A Course in
Convexity by A. Barvinok. (This book focuses more on optimization than the previous two books
listed. It covers a broad array of quite theoretical problems, discrete and continuous.)
-
Optimization via Vector Spaces by D. Luenberger. (This book is also a classic, and it sets
optimization in the infinite dimensional setting.)
- Convex Optimization by D. Bertsekas,
A. Ozdaglar, and A. Nedic. (This is another book with a combination of convex analysis, convex
optimization, and algorithms. It has many nice motivating pictures that help illustrate the theory.
In addition, this book has an extensive development of Lagrange multipliers, something that the
other books listed here do not have. We do not discuss strong duality extensively in this course, but this book has one
of the most clear developments of the proof of strong duality, and constraint qualifications.)
Lecture schedule (tentative)