EE109 Convex Optimization Syllabus - Spring 2019

PDF version:

Syllabus

  1. Introduction to optimization: Role of optimization, Convexity, Examples

  2. Review of mathematical analysis and linear algebra

  3. Convex sets and convex functions: Operations that preserve convexity, Conjugate function, conjugate sets, Separating hyper-plane theorem

  4. Convex optimization problems: Definition and examples, Linear programming, Quadratic programming, Geometric programming, Semi-definite programming

  5. Duality theory: Lagrangian dual function, Lagrange dual problem, weak and strong duality, Interpretation of dual variables, KKT optimality conditions.

  6. Methods and algorithms: Descent methods, Newton methods, Sub-gradient method, Barrier interior point method, Primal-dual interior point methods.

  7. Advanced topics: First-order methods, Schur convexity (as time allows)

Assessment

Breakdown:

  • 20% homework

  • 20% midterm exam

  • 25% project

  • 35% final exam

We reserve the right to change these weights based on performance of the entire class.

  1. The course will have biweekly homework in the first three quarters of the semester, and a project in the last quarter.

  2. Course project should be carried out individually. If you intend to perform the project in a group of two, special permission from the instructor is needed – a group project is only allowed if the project has a big enough scope, and the group must have no more than 2 students. For the project, each student needs to formulate an optimization problem, analyze the optimal solutions or conditions for optimality, and implement a numerical algorithm to solve the problem. The problem can be students's own research (advisor's consent is required), or can be a reproduction of existing results in other papers; if a reproduction, a new algorithmic aspect or new analysis must be developed. The project involves a proposal in mid-semester and a class presentation at the end of semester. More information will be given in the project description.

  3. The final is a 24 or 48 hour take-home exam. The midterm exam format is to be determined.

Textbook

References (these are optional)

  1. Ben-Tal and Nemirovski, Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications, MPS-SIAM Series on Optimization, 2001.

  2. Nesterov, Introductory Lectures on Convex Optimization: A Basic Course, Springer, 2003.

  3. David G. Luenberger, Optimization by Vector Space Methods, Wiley, 1997.

  4. R. Tyrell Rockafellar, Convex Analysis, Princeton University Press., 1996

Prerequisites

  • Vector calculus, linear algebra. Students should be comfortable with mathematical formulations and analysis. Prior Matlab or other programming experience is useful.