ECE 273
Convex Optimization and Applications
Spring 2008
Practical Information
Course load
4 units
Lectures
Tuesday & Thursday 2:00-3:20pm, CSB 004
Instructor
Gert Lanckriet
Email: gert@ece.ucsd.edu
Office 5604 EBU1
Office hours: Tuesday & Thursday, 12:30-1:30pm
TA
Mehrdad Yazdani
Email: myazdani@ucsd.edu
Office Cafe Roma
Office hours: Monday 4:30-5:30pm, Wednesday 7:00-8:00pm
Grading
Homework: 40%
Midterm: 30%
Project: 30%
Back
Updates and Announcements
- 06/07/08: Projects can voluntarily be presented during the Cosmal Spring 2008 Poster session which will be held on Wednesday June 11th, from 4pm till 6pm, in the EBU3b lobby and/or room 1202.
- 06/03/08: HW4 solutions have been posted.
- 05/28/08: The due date for HW4 has been adjusted.
- 05/22/08: HW4 and solutions to HW3 have been posted.
- 05/07/08: HW3 has been posted.
- 05/01/08: HW2 solutions have been posted.
- 04/23/08: HW2 and solutions to HW1 have been posted.
- 04/09/08: HW1 has been posted.
- 04/01/08: First class.
Back
Course Description
Convex optimization relates to a class of nonlinear optimization problems where the objective to be minimized and the constraints are both convex. Convex optimization problems are attractive because a large class of these problems can now be efficiently solved. However, the difficulty is often to recognize convexity: convexity is harder to recognize than say, linearity. Moreover, it is possible to address certain hard, non-convex problems (combinatorial optimization, integer programming) using convex approximations that are more efficient than classical linear ones.
This course covers some convex optimization theory and algorithms, and will concentrate on formulating/recognizing and solving convex optimization problems in applications arising in a variety of field (e.g., analysis, design and control of complex systems, machine learning, applied statistics, financial engineering, communication theory, signal processing, circuit design, combinatorial optimization, computational geometry, computational biology and mechanical engineering).
Objectives
- present the basic theory of convex optimization, concentrating on results that are useful for practical applications and computation
- providing tools and training to recognize convex optimization problems that arise in engineering
- give some understanding of how such problems are solved: convexity is not always the "end of the story"
- gain experience required to use these methods in your own research or engineering work
Intended Audience
Students interested in scientific and engineering problems where optimization plays a role. Related departments/fields include: bioengineering, civil and environmental engineering, electrical engineering (signal and image 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 and structure engineering (robotics, control, structural analysis, optimization and design), scientific computing and computational mathematics, statistics (model fitting and selection; experimental design), finance, economics.
Outline
Theory
- linear algebra background
- convex sets and functions
- convex optimization problems
- cones and conic programming
- linear, quadratic, second-order cone programming
- semidefinite programming
- geometric programming
- Lagrange duality theory
- optimality conditions
- theorems of the alternative
Algorithms
- first second order optimization methods (gradient and descent methods)
- second order optimization methods (Newton's method and variants, barrier and interior-point methods)
Applications
- convex relaxations of non-convex problems
- robust optimization of problems with uncertain parameters
- applications of convex optimization in finance, machine learning, control, engineering, etc.
Required background
Basic linear algebra (matrices, eigenvectors, symmetric matrices, positive-definite matrices). Prior exposure to optimization (e.g., linear programming) helps but is not necessary.
Textbook and optional references
The textbook for this course is Convex Optimization (S. Boyd & L. Vandenberghe, Cambridge University Press 2004). The book is available online at http://www.stanford.edu/~boyd/cvxbook/ or at http://www.ee.ucla.edu/~vandenbe/cvxbook/.
Other useful references:
Back
Homework
Homework is assigned every other week and due the following week. You are allowed, even encouraged, to work on the homework in small groups, but you must write up your own homework to hand in. Indicate with whom you discussed homework problems. Late homework will not be accepted.
Back
Midterm
A midterm will be held in class on 05/22/08. The midterm is closed-book but you are permitted to bring in one page of notes (letter size, both front and back allowed).
Back
Project
There will be a project instead of a final, involving independent work on a topic of choice. You are welcome to choose a project that intersects as much as possible with your current research interests. Course projects will be presented in an informal poster session at the end of the quarter and the work will be summarized in a write-up. Advise will be given to further develop promising projects and submit them for publication. Both individual and group projects (2 persons) are allowed.
- Project proposal (1 page abstract) due: 05/22/08
- Report due: 06/11/08, 11am (send the report per email to the instructor)
Back
Software
Here are a couple of Matlab tutorials that you might find helpful: http://www.math.ufl.edu/help/matlab-tutorial/ and http://www.math.mtu.edu/~msgocken/intro/node1.html.
There are various types of publicly-available packages that may be useful to you:
- Mosek is a general purpose solver for various types of convex programs (a temporary license can be obtained at http://www.mosek.com/trial/).
- SeDuMi is specialized for semidefinite programs, including LPs and SOCPs
- For semidefinite programming: http://plato.asu.edu/ftp/sdplib.html provides a nice comparison of available codes
- To develop convex optimization code, some high-level packages might be useful: YALMIP, CVX (containing many examples).
Back