ECE 273
Convex Optimization and Applications
Spring 2015
Practical Information
Course load
4 units
Lectures
Wednesday 5:00-7:50pm and 8:30-9:50pm, WLH 2111
Instructor
Gert Lanckriet
Email: gert@ece.ucsd.edu
Office: 5604 Jacobs Hall
Office hours: Tuesday 3:30-3:55pm / Wednesday 3:45-4:50pm
TA
Ning Ma
Email: nima@eng.ucsd.edu
Office: Jacobs Hall, Room 2321
Office hours: Monday 12:00PM - 1:30PM, Friday 10:50AM - 11:50AM, 4:00PM - 5:00PM.
Grading
Homework: 20%
Midterm: 50%
Project: 30%
Back
Updates and Announcements
- 05/16/15: Project abstract is now due on 05/24/15.
- 05/16/15: HW3 is now due on 5/27/15.
- 05/12/15: HW3 has been posted.
- 05/07/15: It is likely that there will be no lectures next week (5/13). Final conformation, one way or the other, will be posted closer to the date.
- 05/07/15: Solutions to HW2 have been posted.
- 04/30/15: Ning changed his office hours.
- 04/24/15: HW2 has been posted.
- 04/24/15: Solutions to HW1 have been posted.
- 04/21/15: Ning changed his office hours location to Jacobs Hall, Room 2321. We hope this will be more convenient for everyone!
- 04/07/15: Ning set up an account for the class on piazza.com: https://piazza.com/ucsd/spring2015/ece273/home. The main purpose of this piazza is to facilitate student-to-student discussion.
- 04/05/15: HW1 has been posted.
- 04/05/15: There will be no lectures on Wednesday, April 8th.
- 04/01/15: 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/27/15. The midterm is closed-book but you are permitted to bring in one page of notes (letter size, both front and back allowed, hand-written).
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 with your current research interests.
- Project proposal (1 page abstract) due: 05/24/15 (email abstract to instructor)
- Report due: 06/09/15, 3pm (email report to 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