University of California at Berkeley
Dept. of Electrical Engineering & Computer Science
Dept. of Statistics

EE227A / STAT 260
Nonlinear and Convex Optimization

Fall Semester 2004



Practical information

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

Volume: 3 units

Lectures: Cory Hall 241, Tues-Thurs 2--3:30pm .

Grading: Homework, Inclass Midterm and no Final Exam.

Project: There will be a project instead of a final.  Students are welcome to choose a project that intersects as much as possible with their current research interests.  

Instructor: Martin Wainwright

Office Hours: Mon. 1--2pm (485 Cory Hall); Wed. 3--4pm (421 Evans Hall)
Email: wainwrig AT eecs DOT berkeley DOT edu
Phone: 643-1978
Offices: 485 Cory Hall or 421 Evans Hall

Course assistant: Donna Ko

Email: donnako AT eecs DOT berkeley DOT edu

Back to top

Course description

Overview: Problem formulations and techniques from nonlinear optimization play a central role in a wide range of scientific and engineering fields. An important subclass of optimization problems are convex programs, in which both the objective function to be minimized and the associated constraint set are convex. One attractive feature of convex programs is that a large class can be solved very efficiently. Convex programs also arise frequently as approximations or relaxations of inherently non-convex problems (e.g., integer programming and combinatorial optimization). This 3-unit course will address both theoretical and algorithmic aspects of nonlinear and convex optimization. In addition, various applications will be explored, drawn from a range of fields such as communication theory, signal processing, circuit design, control theory, combinatorial optimization, statistics, and machine learning.

Intended audience: Students interested in scientific and engineering problems in which optimization-based formulations play a role. Relevant and/or related departments/fields include: Electrical Engineering (signal processing; CAD; communication; control), Computer Science (computer graphics; machine learning and artificial intelligence; algorithms and complexity); Statistics (model fitting and selection; experimental design); Bioengineering; Civil and Environmental Engineering (structure optimization and control); Industrial Engineering and Operations Research; Mechanical Engineering; Scientific Computing and Computational Mathematics; Finance; Economics.

Required background: Basic linear algebra such as matrices, eigenvectors, symmetric matrices, positive-definite matrices; advanced calculus and basic notions of analysis; and some degree of mathematical maturity. Prior exposure to optimization (e.g., linear programming) is helpful but not necessary.

Back to top

Updates and Announcements

  • Tues, Dec. 7: The course poster session will be in the Wozniak Lounge, 430 Soda Hall from 1--3pm on Tuesday, Dec 14th. Project writeups are due by 5pm on Thursday Dec 16th, either directly to Martin Wainwright or to Donna Ko in 253 Cory. Note that late write-ups cannot be accepted, due to the deadline of submitting course grades.
  • Fri Nov 27: Please grade problems 6.1, 6.3, 6.4 and 6.6 in Homework #6.
  • Tues, Nov 16: See here for clarification on Homework #6 problems. There will be a talk by M. Chiang on Network Utility Maximization on Friday, Nov 18 in the DSP/Communication seminar that could be of interest.
  • Tues, Nov 9: Homework #6 distributed today; due on Tuesday, November 23. For Homework #5, grade problems 5.1, 5.3, 5.4 and 5.5.
    Reminder that office hours on Wed. 3--4pm are in 421 Evans from now on.
    A talk that could be of interest: LP relaxations for error-control coding , Martin Wainwright, 3108 Etcheverry, 3:30-- 4:30 pm, Monday November 15.
  • Sat, Nov 6: See the updated projects section for an evolving list of papers (survey and otherwise) that may be helpful in exploring project ideas. Note: From now onwards, Wed. 3--4 pm office hours will be held in 421 Evans Hall.
  • Tues, Nov 2: Midterm grades are available during office hours. Please see here for instructions on accessing the course newsgroup for discussion of projects etc.
  • Sun, Oct 31: See here for some corrections to typos in HW #5.
  • Tues, Oct. 26. Reminder of optional midterm review session tonight 7:39 -- 9pm in 285 Cory Hall. HW #5 distributed today.
    In light of possible middle of term burn-out, the due date on HW #5 has been extended to Tues, Nov 9th .
    Please see here for the problem data for Problem 5.5.
  • Sat, Oct 23: HW #4: Grade problems 4.1, 4.2, 4.6, and 4.8.
  • Thurs Oct. 21: Reminder that the midterm exam is on Thursday, October 28 (in-class). An optional midterm review session has been scheduled for Tuesday, October 26 from 7:30--9pm in Cory Hall 285.
  • Tues, Oct 19: Reminders: Homework #4 is due on Thurs, Oct 21. (Problem 4.5 is optional.) The midterm will be in-class on Thurs, Oct 28. One 8.5 X 11 page of notes (both sides) is allowed. Calculators are not allowed. See here for clarification on HW #4 problems.
  • Fri. Oct 15: A more precise description of reading in Chapters 2 and 3: Section 2.1 through end of Section 2.4.1; Section 2.5 through end of Section 2.6.2. Section 3.1 through end of Section 3.3 (excluding 3.2.6).
  • Thurs Oct 14: Problem 4.5 (B & V Exercise 2.37) on HW #4 is optional. You are encouraged to do it, but it will not be graded.
  • Tues, Oct 12: HW #4 distributed; due in class on Thursday, October 21. Reminder that the midterm will be in-class on Thursday, October 28.
  • Thurs. Oct. 7: Problems to be graded on HW #3 are 3.1, 3.2, 3.3, and 3.7. Please see the updated software section of this web page for information on software packages that may be useful.
  • Thurs. Sep. 30: See here for clarifications on HW #3 problems. Problems to be graded on HW #2 are 2.1, 2.3, 2.4, and 2.6.
  • Tues. Sep. 28: HW #3 distributed; due on Thurs, October 7. There will be no office hours on Wed. Sep 29 and no class on Thurs. Sep 30. Office hours for Monday October 4 are rescheduled to 3:30--4:30 on Tuesday October 5.
  • Thurs Sep. 23: See here for a clarification on HW #1 solutions. Also, HW #2 due on Tues, Sep. 28. There will be no class on Thur. Sep 30.
  • Tues. Sep. 21: See here for clarification on HW #2 problems. The EECS distinguished colloquium this week is by Stephen Boyd on convex optimization; the talk is on Wed. Sep 22 at 4pm in Soda Hall 306.
  • Thurs. Sep. 16: Homework #2 distributed; due in class on Tues. Sep. 28. Office hours are 3--4pm Wed., and 1--2pm Mon. in 485 Cory.
  • Thurs. Sep. 16: Please see updated instructions (on webpage) for the homework submission and self-grading procedure. Problems to be graded for Homework #1 are 1.2, 1.4, 1.5, and 1.6.
  • Thurs. Sep. 9: Reminder: midterm scheduled for Thurs, Oct 28. (in class)
  • Tues. Sep. 7: Homework #1 distributed; due in class on Thurs. Sep. 16.
  • Tues. Aug 31: There will be no change in the class time and location.

    • Back to top

    Lecture scribe notes

  • Lecture 1 (Tues Aug 31): Lecture #1 Scribe Notes
  • Lecture 2 (Thurs Sep 2): Lecture #2 Scribe Notes
  • Lecture 3 (Tues Sep 7): Lecture #3 Scribe Notes
  • Lecture 4 (Thurs Sep 9): Lecture #4 Scribe Notes
  • Lecture 5 (Tues Sep 14): Lecture #5 Scribe Notes
  • Lecture 6 (Thurs Sep 16): Lecture #6 Scribe Notes
  • Lecture 7 (Tues Sep 21): Lec. #7 Version A     Lec. #7 Version B
  • Lecture 8 (Tues Sep 26) Lecture #8 Scribe Notes
  • Lecture 9 (Tues Sep 28): Lecture #9 Scribe Notes
  • Lecture 10 (Tues Oct 5) Lecture #10 Scribe Notes
  • Lecture 11 (Thurs Oct 7) Lecture #11 Scribe Notes
  • Lecture 12 (Tues Oct 12): Lec. #12 Version A     Lec. #12 Version B
  • Lecture 13 (Thurs Oct 14) Lecture #13 Scribe Notes
  • Lecture 14 (Tues Oct 19) Lecture #14 Scribe Notes
  • Lecture 15 (Thurs Oct 21) Lecture #15 Scribe Notes
  • Lecture 16 (Tues Oct 26) Lecture #16 Scribe Notes
  • Lecture 17 (Tues Nov 2) Lecture #17 Scribe Notes
  • Lecture 18 (Thurs Nov 4) Lec. #18 Version A     Lec. #18 Version B
  • Lecture 19 (Tues Nov 9) Lecture #19 Scribe Notes
  • Lecture 20 (Tues Nov 16) Lecture #20 Scribe Notes
  • Lecture 21 (Thurs Nov 18) Lecture #21 Scribe Notes
  • Lecture 22 (Tues Nov 23) Lecture #22 Scribe Notes
  • Lecture 23 (Tues Nov 30) Lecture #23 Scribe Notes
  • Lecture 24 (Thurs Dec 2) Lecture #24 Scribe Notes

    • Back to top

    Handouts

  • Lecture 1 (Tues Aug 31): Course information
  • Lecture 2 (Thurs Sep 2): Appendix A Mathematical background, from Nonlinear Programming, D. Bertsekas
  • Lecture 3 (Tues Sep 7): Homework #1 Due in class on Thurs. Sep 16.
  • Lecture 4 (Thurs Sep 9): Gradient methods Section 1.2, from Nonlinear Programming, D. Bertsekas
  • Lecture 6 (Thurs Sep 16): Homework #2 Due in class on Tues. Sep 28.
  • Lecture 9 (Tues Sep 28): Homework #3 Due in class on Thurs. Oct. 7.
  • Lecture 12 (Tues Oct 12): Homework #4 Due in class on Thurs. Oct. 21.
  • Lecture 16 (Tues Oct 26): Homework #5 Due in class on Tues. Nov 9.
  • Lecture 19 (Tues Nov 9): Homework #6 Due in class on Tues. Nov 23.

    Back to top

    Instructions for submitting homeworks

    Due to the absence of a course grader, it will be necessary to follow a somewhat unorthodox approach to grading homeworks.

    Instructions:
  • Please make a photocopy of your homework solutions, with an explicit indication of the total number of pages. Be sure to include both your name and student ID# on the front page of the homework.
  • Hand in one copy and keep the other.
  • Problem set solutions will be distributed in class. They will not be available online; however, extra copies will be available in the box on the door of 485 Cory.
  • Once you have received a copy of the solutions, you will self-grade the specified subset of the problems. For each problem, assign a score of 0,1 or 2. Assign a 2 if you solved the problem correctly and completely; a 1 for a partial solution (at least half of the problem correct); and a score of 0 otherwise. Note: A subset of homeworks will be randomly graded to check that your self-assessment is reasonable.
  • Email your scores to Donna Ko (donnako AT eecs DOT berkeley DOT edu) in the following format:
    Subject line: EE 227 HW #n
    Text body (line 1): Name
    Text body (line 2): ID number
    Text body (line 3): score1, score2, score3, score4
  • In the subject line, #n indicates the problem set number. As an example of line 3 in the text body, a vector of 1, 2, 0, 2 indicates a score of 1 on problem 1, 2 on problem 2, 0 on problem 3, and 2 on problem 4.
    Note: Here problem 1 refers to the first problem in the subset of problems to be graded. This may be different than the first problem in the homework itself.
  • Important: Please send your score report email to Donna within one week of the due date of the homework. (I.e., the following Thursday for a homework due on Thursday; the following Tuesday for a homework due on Tuesday.)

    Back to top

    Homework problems to be graded

  • Homework #1:   Grade problems 1.2, 1.4, 1.5, 1.6. Please see here for clarification on HW #1 solution.
  • Homework #2:   Grade problems 2.1, 2.3, 2.4, and 2.6.
  • Homework #3:   Grade problems 3.1, 3.2, 3.3, and 3.7.
  • Homework #4:   Grade problems 4.1, 4.2, 4.6, and 4.8.
  • Homework #5:   Grade problems 5.1, 5.3, 5.4, and 5.5.
  • Homework #6:   Grade problems 6.1, 6.3, 6.4 and 6.6.
    Back to top

    Scribing materials and instructions

    Lecture scribe notes should be written up in LATEX using the following template and style files:
  • LATEX template file
  • LATEX style file
    • Please send your written notes in PS or PDF format, as well as the original LATEX source, by email to Martin Wainwright with the subject heading Lecture Scribe #N (where N is the lecture number), no later than 4 days after the lecture. I will look over the notes, and indicate whether editing/corrections are required.

    Back to top

    Useful references

  • Convex Optimization Stephen Boyd and Lieven Vandenberghe. On reserve in the Math Library.

  • Nonlinear Programming, Dimitri Bertsekas. On reserve in the Engineering Library.

    • For background on linear algebra:
  • Introduction to linear algebra, G. Strang.

    Other useful materials:
  • Lecture notes on optimization by Pravin Varaiya, UC Berkeley.
  • Lecture notes on optimization by E. Polak, UC Berkeley.