University of Chicago

Winter 2013

This course covers the fundamentals of convex optimization. Students are expected to have a solid grounding in multivariate calculus and linear algebra, and will be expected to complete several programming exercises (using CVX, SeDuMi, SDPT3, or SDPA) during the course.

General topics covered will include basic convex geometry and convex analysis, KKT condition, self-concordance, Fenchel and Lagrange duality theory. The main focus of the course will be the various types of convex optimization problems and their applications to science, medicine, and engineering problems. These include linear programming, geometric programming, second-order cone programming, semidefinite programming, linearly and quadratically constrained quadratic programming.

In the last part of the course we will examine the generalized moment problem — a singularly powerful technique that allows one to encode all kinds of problems (in probability, statistics, control theory, financial mathematics, signal processing, etc) and solve them or their relaxations as convex optimization problems.

- 03/14/13: Homework 5 posted.
- 03/12/13: Lecture as usual on Thu, Mar 14.
- 03/06/13: Homework 4 posted.
- 02/17/13: Homework 3 posted.
- 02/14/13: Second make-up lecture 3:30–5:30pm, Wed, Feb 27 in Eckhart 133.
- 02/14/13: No lectures next Tue and Thu, Feb 19 and 21.
- 02/11/13: TA's office hour on Tue, Feb 12 moved to 4:30–5:30PM in Eckhart 132.
- 02/04/13: Homework 2 posted.
- 02/01/13: First make-up lecture 3–5pm, Wed, Feb 13 in Eckhart 133.
- 02/01/13: No classes on Feb 19 and 21.
- 01/18/13: Homework 1 posted.
- 01/08/13: Check back regularly for announcements.

**Location:** Eckhart Hall,
Room 117

**Times:** 3:00–4:20pm on Tue/Thu.

**Instructor:**
Lek-Heng
Lim

Office: Eckhart
122

`lekheng(at)galton.uchicago.edu`

Tel: (773) 702-4263

**Office hours:** Weds 1:30-3:30 PM

**Course Assistant:** Lian
Huan Ng

Office: Eckhart 131

`lhng(at)galton.uchicago.edu`

**Office hours:** Tues 12:00-1:00 PM

Problem set will be assigned biweekly. Collaborations are permitted but you will need to write up your own solutions.

- Problem Set 5: Excercises 5.27, 5.28, 5.30 in the book and Exercises 4.3, 4.5, 4.14 in extra exercises (posted: Mar 14; due: Mar 22)

- Problem Set 4: Excercises 4.21, 4.28, 4.29, 4.33, 4.41, 5.3, 5.5 in the book and Exercises 3.8, 3.10 and 3.12 in extra exercises (posted: Feb 28; due: Mar 14)

- Problem Set 3: Excercises 3.36, 3.37, 3.38, 4.5, 4.8, 4.9, 4.13, 4.22, 4.23, 4.24 in the book (posted: Feb 17; due: Mar 5)

- Problem Set 2: Excercises 3.4, 3.13, 3.20, 3.24, 3.25, 3.52, 3.54, 3.55, 3.56 in the book (posted: Feb 4; due: Feb 14)

- Problem Set 1: Excercises 2.11, 2.13, 2.15, 2.16, 2.19, 2.20, 2.26, 2.31, 2.32, 2.35, 2.36 in the book, and Exercise 1.5 in extra exercises (posted: Jan 18; due: Jan 31)

**Bug report** on the problem sets or the solutions:
`lekheng(at)galton.uchicago.edu`

**Grade composition:** No in-class examination. Grade based entirely
on five take-home problem sets.

- F. Alizadeh, D. Goldfarb, "Second-order cone programming,"
*Math. Program.*,**95**(2003), no. 1, pp. 3–51.

- S. Boyd, S.-J. Kim, L. Vandenberghe, A. Hassibi,
"A tutorial on geometric programming,"
*Optim. Eng.*,**8**(2007), no. 1, pp. 67–127.

- Examples of how Fenchel conjugate is used in:

- Probability: R. Cerf and P. Petit, "A short
proof of Cramér's theorem in
**R**"*Amer. Math. Monthly*,**118**(2011), no. 10, pp. 925–931.

- Statistics: L. Brown, Chapter 6: The dual to the maximum likelihood
estimator, pp. 174–207 in
*Fundamentals of Statistical Exponential Families with Applications in Statistical Decision Theory*, IMS, Hayward, CA, 1986 (Thanks to Steve Lalley for the pointer).

- Course homepage from Winter 2011.

- S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004.

- J. Lasserre, Moments, Positive Polynomials and their Applications, Imperial College Press, 2010.