University of California at Berkeley
Dept of Electrical Engineering & Computer Sciences

Convex optimization and applications

Fall Semester, 1999-2000

Practical information

See also the UCB On-Line Course Catalog and Schedule of Classes

Volume: 3 units

Lectures: 60 Evans Hall, M/W/F 1:00-2:00.

Instructor:Laurent El Ghaoui

Office Hours: Wed 2:00-4:00.

Grading: Homework 25%, Midterm 30%, Project 45%.

Course description

This new course is on mathematical programming, with emphasis on convex optimization and problems with uncertain data.

Convex optimization relates to a class of nonlinear optimization problems where the objective to be minimized, and the constraints, are both convex. Contrarily to the more classical linear programming framework, convex programs often go unrecognized, and this is a pity since a large class of convex optimization problems can now be efficiently solved. In addition, it is possible to address hard, non convex problems (such as "combinatorial optimization" problems) using convex approximations that are more efficient than classical linear ones. Convex optimization is especially relevant when the data of the problem at hand is uncertain, and "robust" solutions are sought.

The 3-unit course covers some convex optimization theory and algorithms, and describes various applications, with a special emphasis on problems with incomplete/unknown data. A large number of examples arising in a variety of fields will be given, covering analysis, design and control of complex systems, and in various identification, data fitting and estimation problems.

Intended audience: Students interested in engineering problems where decision-making (system analysis and design, engineering trade-offs, risk analysis, etc) has to do with scientific computations. Related departements/fields include: Bioengineering, Civil and Environmental Engineering (structure optimization and control) Electrical Engineering (signal processing, control and communications, robotics, CAD) Computer Science (computer graphics, artificial intelligence and decision theory, data mining, algorithms & complexity, computational geometry), Industrial Engineering and Operations Research, Mechanical Engineering, Scientific Computing and Computational Mathematics, Statistics, Finance, Economics.

Required background: Basic linear algebra such as matrices, eigenvectors, symmetric matrices, positive-definite matrices. A prior exposure to optimization, such as an introductory course on linear programming, helps, but is not necessary.

Tentative syllabus: (Each item is approximately a week, i.e. 3 lectures)

  1. introduction
  2. convex sets and functions
  3. convex optimization problems
  4. duality
  5. unconstrained minimization
  6. interior-point methods
  7. localization methods
  8. some applications in engineering
  9. problems with uncertainty
  10. uncertainty models
  11. robust optimization
  12. applications to data fitting and estimation
  13. applications to control
  14. conclusions



In this course we will use the matlab function lp.m for linear programming, and the software package lmitool for semidefinite programming. For information on how to use it, click here