The University of Texas at Austin
Department of Electrical and Computer Engineering

EE381V - Convex Optimization: Theory and Applications

Fall Semester 2011



Some Basic Information

Instructor: Constantine Caramanis

Email: caramanis AT mail DOT utexas DOT edu
Phone: (512) 471-9269
Office: ENS 427
Office Hours: Thursday 11 am

TA: Yudong Chen

Email: ydchen AT mail DOT utexas DOT edu
Office Hours: Wednesday 1 - 3 pm
Office: ENS 110

Lectures:

Time: Tuesday and Thursday, 5:00-6:30 PM,
Location: ACA 1.102


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:

  1. Theory of Convex Analysis: This portion of the class lays the theoretical framework for the next two sections.

  2. 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.
  3. 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.
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:



Lecture schedule

Lecture No.

Date

Homework

Solutions

Assigned Reading

Scribed Notes

1

Thu Aug 25

---

---

---

---

2

Tue Aug 30

---

---

---

---

3

Thu Sep 1

Problem Set #1

---

Relative Interior

---

4

Tue Sep 6

---

---

---

---

5

Thu Sep 8

---

---

---

---

6

Tue Sep 13

---

---

---

---

7

Thu Sep 15

Problem Set #2

---

---

---

8

Tue Sep 20

---

---

---

---

9

Thu Sep 22

---

---

---

---

10

Tue Sep 27

---

---

---

---

11

Thu Sep 29

---

---

---

---

12

Tue Oct 4

---

---

---

---

13

Thu Oct 6

---

---

---

---

14

Tue Oct 11

---

---

---

---

15

Thu Oct 13

---

---

---

---

16

Tue Oct 18

Problem Set #3

---

---

---

17

Thu Oct 20

---

---

---

---

18

Tue Oct 25

---

---

---

---

MIDTERM

Thu Oct 27

---

---

---

---

19

Tue Nov 1

---

---

---

---

20

Thu Nov 3

---

---

---

---

21

Tue Nov 8

---

---

---

---

22

Thu Nov 10

---

---

---

---

23

Tue Nov 15

---

---

---

---

24

Thu Nov 17

---

---

---

---

25

Tue Nov 22

---

---

---

---

26

Tue Nov 29

---

---

---

---

27

Thu Dec 1

---

---

---

---

No Final Exam

---

---

---

---

Final


Homeworks

Homeworks are due at the beginning of class on the posted due-date.

  • Problem Set #1

  • Problem Set #2


    Solutions



  • 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:

    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.

    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.

    Additional online sources:

    Other Potential Topics:


    Announcements


    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.