The University of Texas at
Austin
Department of Electrical
and Computer Engineering
Fall Semester 2009
Some Basic Information
Instructor:
Constantine Caramanis
Email: caramanis AT mail DOT utexas DOT edu
Phone: (512) 471-9269
Office: ENS 426
Office Hours: TBA
Lectures:
Time: Monday and Wednesday, 2:00-3:30 PM,
Location: ENS 116
Course Overview
Convex Optimization, including techniques, algorithms, and theory,
have been playing an increasing
role in many applications. This is a consequence of the fact that
optimization algorithms have improved dramatically, and computing
speeds have also increased. Techniques from convex optimization have
found applications far beyond convex problems, and currently provide
the basis for most solution-techniques, and algorithms for solving
nonconvex continuous and discrete and combinatorial problems.
The purpose of this class will be to develop the mathematical tools
as well as the concepts and intuition of Convex Optimization. In
addition to this, there will be a big focus on understanding and
appreciating the modeling power, and applicability of a wide array
of special classes of convex optimization problems (LP, SOCP, SDP,
GP, etc). Recognizing these classes of optimization problems in
engineering, and developing an intuition for their complexity, and
successful modeling principles is important, and a key objective of
the class is to provide students the theoretical background
required, and also some experience, so that they may use these
methods and tools in their own engineering research.
The class is organized into three subunits: (I) Convex Analysis,
(II) Convex Optimization, and (III) Applications. These include the
following topics:
- Theory of Convex Analysis: This portion of the class lays
the theoretical framework for the next two sections.
- Geometry of Convex sets, and convex functions;
- Dual spaces, dual cones;
- Convex duality, optimality conditions, Lagrange multipliers,
theorems of the alternative (and applications such as Helly's
theorem).
- Fenchel-Legendre duality. Conjugate functions.
- Geometry of separation. Equivalence of separation and
optimization. Membership oracles.
- Key question: What makes a problem easy or hard? Convexity is
not the end of the story (e.g.: positive definite vs. copositive
matrices).
- Convex Optimization: This portion of the class relies on
the theory developed in part I, to establish the main known and most
commonly used classes of convex optimization.
- Linear programming;
- Second Order Cone and Quadratic;
- Semidefinite, and general convex conic;
- Duality and Robust Optimization;
- Applications and Techniques: This class will largely be
connected to the project component of the class. Unlike parts (I)
and (II), the topics listed below may not all be covered, but rather
may serve as a starting point for a final project. Some of the
topics below fit specifically within some of the categories (SOCP,
SDP, etc) of part (II), and as such will be integrated into the
appropriate sections.
- Combinatorial Optimization: Relaxation techniques, hierarchies
of approximation, including sum-of-squares approaches, and moment
methods, integral gap. Applications.
- Applications of convex optimization to statistical learning
theory, and also graphical models.
- Probabilistic Approaches: Applications of convex optimization
to applied probability, and also application of probabilistic
techniques to optimization (including combinatorial and stochastic
optimization).
- Techniques for very large scale optimization problems.
- Adaptability and multi-stage problems.
- Application Areas: control, wireless communication,
circuit design, signal processing, game theory, computational
geometry, information theory, etc.
Intended audience: This class is structured to be interesting
and relevant to students who are using or plan to use optimization
in their engineering research. It should be of particular interest
to students from Electrical and Computer Engineering, Computer
Science, Operations Research and Industrial Engineering, Mechanical
Engineering, Aero and Astro, and Applied Math. Additionally, the
class may also be of interest to students in Economics and Finance.
Course Prerequisites
The prerequisites for this class include a
course in Real Analysis I, (such as Math 365C, or the equivalent).
In addition, a class in Optimization (such as EE380N, ORI391Q-1,
ORI391Q-5, ORI391Q-10) or independent research experience in
optimization, is strongly recommended, although not a formal
prerequisite. A good background in Linear Algebra (at the level
developed in EE380K) is certainly desirable. Some knowledge of
algorithms and complexity will be useful but is not required.
Some basic knowledge of Matlab will also be needed.
General Note: If you are concerned about the prerequisites
or your background, or what the course will cover, please don't
hesitate to contact me by e-mail, or come by
my office hours.
Homework and Exams
The first part of this class will be the most
technical, and thus there will be weekly problem sets. At the end of the first
section there will be an in-class midterm exam. The remainder of the class will
be paper-driven. In place of homeworks, you will be responsible for submitting
short paper-summaries each week, for the papers we cover. The final component
of the class will be a final project.
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. I have
listed the text book: Convex
Optimization by Stephen Boyd and Lieven Vandenberghe as the main
source, for several reasons: it is quite readable, it covers the theory
with many examples and pictures, it has a broad range of applications,
and also has an entire section on algorithms (which we will likely
not get to in this class). Finally, it is also available on line.
Additional References: Some additional references that may be helpful:
- 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.) On reserve at the
PMA library.
- 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). On reserve at the
PMA library.
- 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.)
On reserve at the PMA library.
- 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).
- 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).
Lecture schedule
Lecture No. | Date | Homework | Solutions | Assigned Reading | Scribed Notes
|
1 | Wed Aug 26 | --- | --- | --- | ---
|
2 | Mon Aug 31 | --- | --- | --- | ---
|
3 | Wed Sep 2 | Problem Set #1 | Solution Set #1 | Relative Interior | ---
|
4 | Wed Sep 9 | Problem Set #2 | Solution Set #2 I,II | --- | ---
|
5 | Mon Sep 14 | --- | --- | --- | ---
|
6 | Wed Sep 16 | --- | --- | --- | ---
|
7 | Mon Sep 21 | --- | --- | --- | ---
|
8 | Wed Sep 23 | Problem Set #3 | --- | Complexity Handout | ---
|
9 | Mon Sep 28 | --- | --- | --- | ---
|
10 | Wed Sep 30 | --- | --- | --- | ---
|
11 | Mon Oct 5 | --- | --- | --- | ---
|
12 | Wed Oct 7 | --- | --- | --- | ---
|
13 | Mon Oct 12 | --- | --- | --- | ---
|
14 | Wed Oct 14 | --- | --- | --- | ---
|
15 | Mon Oct 19 | --- | --- | --- | ---
|
16 | Wed Oct 21 | --- | --- | --- | ---
|
MIDTERM | Mon Oct 26 | --- | --- | --- | ---
|
17 | Wed Oct 28 | --- | --- | --- | ---
|
18 | Mon Nov 2 | --- | --- | --- | ---
|
19 | Wed Nov 4 | --- | --- | --- | ---
|
20 | Mon Nov 9 | --- | --- | --- | ---
|
21 | Wed Nov 11 | --- | --- | --- | ---
|
22 | Mon Nov 16 | --- | --- | --- | ---
|
23 | Wed Nov 18 | --- | --- | --- | ---
|
24 | Mon Nov 23 | --- | --- | --- | ---
|
25 | Wed Nov 25 | --- | --- | --- | ---
|
26 | Mon Nov 30 | --- | --- | --- | ---
|
27 | Wed Dec 2 | --- | --- | --- | ---
|
No Final Exam | --- | --- | --- | --- | Final
|
Homeworks
Homeworks are due Wednesday at the beginning of class.
Early assignments (e.g. Monday in class) are fine, but no late
homeworks will be accepted. You are allowed to drop one (1) homework.
Homework #1:
Concepts from convexity, relative interior, and the asymptotic cone.
Homework #2:
Concepts from convexity, projection, separation, and Helly's theorem.
Homework #3:
Concepts from projection, separation, and conjugacy.
2007 Midterm:
The old midterm.
Solutions
Solutions to Homework 1: Solutions #1
Solutions to Homework 2: I,II
Scribed Lecture Notes
Since this class does not closely follow any single textbook, lecture notes
will serve in its stead. The lectures are primarily drawn from three books, although
material comes from all the books listed in the references for this course. The
three main books from which the lectures draw, are: Fundamentals of Convex Analysis,
by Hiriart-Urruty and Lemar\'echal, Convex Analysis by Rockafellar, and Convex Analysis and
Optimization, by Bertsekas, Ozdaglar, and Nedic.
Lecture notes should be typed up using Latex. Please
download and use this
style file and this
template file. Scribed lecture notes should contain not only a
record of what we covered in class, but also should fill in missing details required
either to clarify a point, or to complete a proof. A first draft should be completed
on the Monday after the class being scribed, so that after some iteration with me, we
can have a nice version posted by at most 2 weeks after the class.
Paper-Reading Portion of the Class
The next part of the class will have no problem sets, and will not follow
any book or notes, but will be paper-based. Instead of homework, I expect
a before-and-after write up of the papers below that have been marked as
required. The "before" write up should be done before we discuss
the paper in class, and the "after" write up should be done after the
discussion. My expectations for these write-ups are as follows:
- The main goal is for you to think about the paper critically,
try to understand and extract the main points and key ideas. It is not
for you to provide a summary of the abstract and introduction. These
write ups don't need to contain any information about the background, etc.
- A successful writeup should express the fact that you've done this.
It should show an attempt to understand the crux of the paper.
- The write up can be handwritten, it can contain less-than-precise
statements, whose aim is to get across intuition about the key aspects of
the paper. Try to separate the essential ideas of the paper, from the
detail-oriented work that has to go into any paper to make it clean and
correct (you want to focus on the former!). For example, some questions
to think about might include: What is the main result? What is the key proof
technique or proof idea? Which hypotheses are critical to the intuitive
reason the proof works? And so on.
Many more papers are listed for those who are interested in a particular
area, but those papers are not required reading.
Course Project
There are a few different types of course projects that would work for this course.
They are listed below in no particular order. Each kind has the potential to be useful
and interesting for you and for me.
- Survey work: One avenue for the course project is to write an expository paper on some
special topic of interest to you. While the research results will not be new, the exposition
should be. This kind of project expects more than merely a summary of some paper. Rather, it
will ideally discuss a few papers, pointing out connections and common trends in a way that
is interesting and useful to the reader. I would expect this kind of project to be quite common.
- Research work:
- A Contribution in Modeling and Formulation.
This kind of project will propose an optimization-based formulation and solution of
some problem in engineering, in a way that has not been considered before. Thus, in particular,
the formulation here should be novel. In addition to a formulation, the paper should include
discussion about the approximations made, the regimes in which the formulation is accurate. In
addition, the paper should include general algorithmic approaches to the problem,
particularly if the problem is not convex. Some computational examples illustrating
the formulation and solution method can be particularly useful.
- A Theoretical Contribution. This could include new complexity results for some hard problem; etc.
I would expect this kind of project to be less common that the options offered above.
- Computational contribution: This class has not spent too much time discussing algorithms
and complexity, beyond the course level of polynomially solvable vs NP-hard. Nevertheless, if someone
is particularly interested in exploring numerical algorithms or approaches (such as, for example,
parallel or distributed implementations) then such a project would be quite welcome.
Note that such a contribution could also be made in the context of a new formulation, or an expository
paper.
Potential Project Topics: below are listed some potential topics, particularly for the expository-paper option.
This list is in no way expected to be exhaustive, rather it should be just a point to help you get started
thinking about the project. Also, the links provided below are, naturally, not meant to be exhaustive or authoritative
in any way -- rather, they are only meant to provide a starting point.
- Sum of Squares applications. See web pages of: Parrilo,
Lasserre, Lall,
Boyd, and for a (even) more algebraic angle,
see Sturmfels. A place to start is with the papers to be
discussed in class in Lectures 22 and 23.
- Polyhedral combinatorics. See web pages of: Goemans,
Laurent, Schrijver,
Lovasz.
- Other SDP applications to combinatorics and combinatorial optimization.
See the web pages given above for the previous two topics.
- Applications to Control. See this paper,
and also the web pages of Boyd, Lall,
Vandenberghe, Dullerud,
and also Parrilo.
- Applications to distributed optimization. See web pages of: Tsitsiklis,
Bertsekas, Ozdaglar,
and Nedic. For more towards recent work
in consensus propagation, and belief propagation, see Van Roy,
Moallemi, Wainwright,
and for more focus on discrete problems, see Shah.
- Applications to Graphical Models. See web pages of: Wainwright,
Jordan, Willsky.
- Metric Embeddings. See course notes here, and
references therein. Also see the book: Cuts and Metrics by Deza and Laurent.
- Statistical Machine Learning. See web pages of Jordan,
Lanckriet, Mannor,
Dhillon, Ghosh.
- Applications to Communications, Signal Processing. See web pages of
Z.Q. (Tom) Luo, Giannakis,
and Tsitsiklis.
- Applications to circuits. Boyd.
Other Engineering Applications: For example, for other Log-Det problems in
geometry, statistics, system id, etc., see this
paper. LDPC decoding (more related to LP relaxations and polyhedral combinatorics).
- Game Theory and Networks. See web pages of Ozdaglar
and Johari and Mannor.
- Robust and Stochastic Optimization: See web pages of: Ben-Tal, Melvyn Sim, D. Morton, Shapiro, Nemirovski. Also
of interest: work of Calafiore and Campi.
Additional online sources:
Other Potential Topics:
- Perturbation of Optimization Problems.
- Random projections.
- Infinite dimensional problems. (E.g., Luenberger).
- Random methods in optimization, randomized algorithms.
- Online optimization. Regret minimization.
- Hyperbolic polynomials.
Announcements
- Wed. August 26: Welcome to EE381V. I have posted a tentative lecture, homework, and exam
schedule above. If you have any questions about the class, please feel free to e-mail me, or to
drop by my office (ENS 426)
if you prefer.
Questions, Comments, Answers
If you have questions/comments, I encourage you to e-mail me.
I will post questions/comments/answers that might be useful to the entire
class here.