EECS 127/227A | Optimization Models in Engineering

Fall 2020

Schedule

ATTENTION: This schedule is tentative and subject to change.
The course youtube channel can be found here
Week Date Lecture Topic Reading Section Homework
0
08/27 Th Logistics & Introduction, Vectors, Matrices, Functions, and Linear Algebra review
(Webcast)
C-EG: Ch. 1, Ch. 2 Homework 0
Due 09/04 Fr
(PDF) (Sols)
1
09/01 Tu Vectors, Matrices, Functions, and Linear Algebra review
(Webcast)
C-EG: Ch. 2, Ch. 3 Section 1, Linear Algebra
(Dis) (Sol) (Druv's slides) (Recording)
Homework 1
Due 09/11 Fr
(PDF) (Sols)
(Self Grade)
09/03 Th Vectors, Matrices, Functions, and Linear Algebra review
(Webcast)
C-EG: Ch. 2, Ch. 3
2
09/08 Tu Symmetric matrices, PSD matrices, and PCA
(Webcast)
C-EG: Ch. 4 Section 2
(Dis) (Sol) (Druv's Slides) (Recording)
Homework 2
Due 09/18 Fr
(PDF) (Sols)
(Self Grade)
09/10 Th Singular Value Decomposition
(Webcast)
C-EG: Ch. 5
3
09/15 Tu Singular Value Decomposition, Least Squares and variants
(Webcast)
C-EG: Ch. 5, Ch. 6 Section 3
(Dis) (Sol) (Druv's Slides)
Homework 3
Due 09/25 Fr
(PDF) (Sols)
(Self Grade)
09/17 Th Least Squares and Variants
(Webcast)
C-EG: Ch. 6, 13.1-13.4
4
09/22 Tu Convex sets and functions
(Webcast)
C-EG: Ch. 8.1, 8.2; B-V: Ch. 2.1, 2.2, 2.3, 2.5 Section 4
(Dis) (Sol) (Walkthrough) (Recording)
Homework 4
Due 10/02 Fr
(PDF) (Sols)
(Self Grade)
09/24 Th Convex sets and functions
(Webcast)
C-EG: Ch. 8.1, 8.2; B-V: Ch. 3.1, 3.2
5
09/29 Tu Convex conjugate duality
(Webcast)
B-V: Ch. 3.3 Section 5
(Dis) (Sol) (Druv's Slides) (Walkthrough) (Recording)
Homework 5
Due 10/09 Fr
(PDF) (Sols)
(Self Grade)
10/01 Th Convex optimization problems; Lagrangian
(Webcast)
C-EG: Ch. 8.3, 8.4, 8.5; B-V: Ch. 4.1, 4.2-4.2.4
6
10/06 Tu Duality in convex optimization, Weak/Strong Duality
(Webcast)
C-EG: Ch. 8.4, 8.5; B-V: Ch. 5.1, 5.2 Section 6
(Dis) (Sol) (Druv's Slides) (Walkthrough) (Recordings)
Homework 6
Due 10/16 Fr
(PDF) (Sols)
(Self Grade)
10/08 Th KKT conditions, Slater's condition
(Webcast)
C-EG: Ch. 8.4, 8.5; B-V: Ch. 5.3, 5.4, 5.5
7
10/13 Tu Linear programming
(Webcast)
C-EG: Ch. 9.1, 9.2, 9.3; B-V: Ch. 4.3 Section 7
(Dis) (Sol) (Recordings)
10/15 Th LP, QP, QCQP, duality
(Webcast)
C-EG: Ch. 9.3, 9.4; B-V: Ch. 4.3, 4.4
8
10/20 Tu LP, QP, QCQP, GP, duality
(Webcast)
C-EG: Ch. 9.5, 9.6, 9.7; B-V: Ch. 4.3, 4.4, 4.5 Section 8
(Dis) (Sol) (Walkthrough)
Homework 7
Due 10/30 Fr
(PDF) (Sols)
(Self Grade)
10/22 Th Midterm day - No lecture
9
10/27 Tu QCQP, SOCP, Support Vector Machines (SVM)
(Webcast)
C-EG: Ch. 9.6, 10.1, 13.3, 13.4; B-V: Ch. 4.4.2 Section 9
(Dis) (Sol) (Walkthrough)
Homework 8
Due 11/06 Fr
(PDF) (Sols)
(Self Grade)
10/29 Th Geometric programming (GP)
(Webcast)
C-EG: Ch. 9.7; B-V: Ch. 4.5
10
11/03 Tu SDP
(Webcast)
C-EG: Ch. 11.1, 11.2; B-V: Ch. 4.6.2, 4.6.3 Section 10
(Dis) (Sol) (Walkthrough)
Homework 9
Due 11/13 Fr
(PDF) (Sols)
(Self Grade)
11/05 Th SDP, SDP duality
(Webcast)
B-V: Ch. 4.6.2, 4.6.3, Ex 5.11
11
11/10 Tu SDP examples
(Webcast)
C-EG: Ch. 11.4, 15.3 Section 11
(Dis) (Sol) (Walkthrough)
Homework 10
Due 11/22 Su
(PDF) (Sols)
(Self Grade)
11/12 Th SDP Ex, Algs for unconstrained min
(Webcast)
C-EG: Ch. 11.4, 15.3, 12.1-12.2; B-V: Ch. 9.1-9.2
12
11/17 Tu Descent methods for unconstrainted opt.
(Webcast)
C-EG: Ch. 12.1-12.2; B-V: Ch 9.1-9.4 Section 12
(Dis) (Sol) (Recordings) (Walkthrough)
Homework 11
Due 11/29 Su
(PDF) (Sols)
11/19 Th Descent methods & Newton's method
(Webcast)
C-EG: Ch. 12.1-12.2; B-V: Ch 9.1-9.5
13
11/24 Tu Newton's method, steepest descent, conjugate gradient method
(Webcast)
C-EG: Ch 12.1-12.2; B-V: Ch 9.1-9.5 Section 13
(Dis) (Sol) (Walkthrough) (Recordings)
11/26 Th Thanksgiving Holiday (No Lecture)
14
12/01 Tu Barrier methods for constrained optimization
(Webcast)
C-EG: Ch 12.3.1; B-V: Ch 9.6, 11.1, 11.2, 11.3 Section 14
12/03 Th Class review
(Webcast)
15
12/08 Tu RRR Week
Section 15
12/10 Th RRR Week
16
12/15 Tu Final Exam at 8:00 am
Section 16

Calendar

Course Staff

Instructors


Venkat Anantharam
ananth@eecs.

GSIs


Dominic Carrano
Head TA
dcarrano@

Hari Prasanna Das
Head Content TA
hpdas@

Wilson Wu
Content TA
wilswu99@

Matteo Ciccozzi
Content TA
mcicco@

Deepshika Dhanasekar
Discussion TA
ddhanasekar@

Joey Hejna
Discussion TA
jhejna@

Hermish Mehta
Discussion TA
hermish@

Daniel Jing
Discussion TA
daniel.jing@

Druv Pai
Discussion TA
druvpai@

Akash Velu
Discussion TA
akashvelu@

Albert Wilcox
Reader
albertwilcox@

Yong Song
Reader
yongsong@

Hamza Qadeer
Reader
hamza.qadeer@

Harshayu Girase
Reader
harshayugirase@

Varun Dashora
Reader
vdashora@




Please add berkeley.edu to the end of all emails, unless otherwise specified.

Policies

Course Info

Course Title: Optimization Models in Engineering

Units: 4

Course Format: 3 hours of lecture, 1 hour discussion

Instructors: Venkat Anantharam

Contact Information:ananth@eecs.berkeley.edu, eecs127227fa20@gmail.com (This email is for course matters and is viewed by the Professor as well as the head TA)

Prerequisites: EECS 16A & EECS 16B OR Math 54, CS 70, Math 53

Online resources: Piazza, Gradescope (9RJR7Z), course website, and bcourses.

Course Description

This course offers an introduction to optimization models and their applications, ranging from machine learning and statistics to decision-making and control, with emphasis on numerically tractable problems. We will appreciate the role of duality in optimization. We will encounter several widely used classes of convex optimization problems, such as LP, QP, GP, SOCP and SDP. (4 Units.)

Course Objectives

  1. Develop a practical understanding of the applications and limitations of optimization as a solution approach to engineering analysis and design.
  2. Develop an ability to use rapid prototyping software to guide optimization solutions.

Desired Course Outcome:

By the end of the term, students having taken Optimization Models in Engineering are expected to be able to:

  1. Understand the basic concepts of linear algebra: vectors, matrices, rank, projections; symmetric matrices, positive semidefinite matrices, eigenvalues; singular value decomposition and principal component analysis.
  2. Learn about basic optimization models such as least-squares, linear programming, quadratic programming, SOCP and SDP, and develop an understanding of the more general convex optimization.
  3. Become aware of the wide-ranging applications where optimization models are useful, such as learning, control, finance and engineering design.
  4. Be able to use prototyping software to develop optimization-based solutions in concrete applications.

Course Content

The course content will roughly follow the outline posted on the website, but is subject to change and evolve throughout the semester.

  • Linear Algebra
    1. Vectors, projection theorem, matrices, symmetric matrices
    2. Linear equations, least-squares and minimum-norm problems
    3. SVD, PCA and related optimization problems
  • Convex Optimization
    1. Convex sets, convex functions, convex optimization problems
    2. KKT optimality conditions, duality (weak and strong), Slater's condition.
    3. Special convex models: LP, QP, GP, SOCP, SDP
    4. Regularization and LASSO
  • Algorithms
    1. Gradient descent, Newton's method
  • Applications
    1. Learning from data, control, finance, engineering design

Discussion

There will be one discussion worksheet per week. You can choose to attend any of the discussion sessions on either Wednesday or Friday. All the discussion sections will cover the same material but you are welcome to attend more than one.

The discussion schedule is posted on the calendar section above. This section is still being updated, more information discussion sections, such as zoom links and other details, will be available later in the month.

Homework

There will be 10 mandatory homeworks, one optional diagnostic homework (Homework 0) and one terminal homework (Homework 11) which is not to be submitted. Homeworks will be released on Fridays at 12:00 p.m. according to the posted schedule. You will be responsible for submitting the homework by 11:59 pm on Friday according to the posted schedule, with an optional grace period of 48 hours. This means that you can submit your homework until 11:59pm on the Sunday after it is assigned, giving you a total of 9 days to work on the homework. Homework solutions will be made available on Monday at 10:00 a.m. according to the posted schedule.

GSIs will be under no obligation to answer homework questions on Piazza after the Friday 11.59 p.m. deadline for the homework, so please be aware that is the real deadline.

Homeworks will be self-graded, the self-grades are due at 11:59 pm on Friday, according to the posted schedule, with an optional grace period of 48 hours. This means you can submit your self-grades as late as 11:59 pm of the Sunday after the self-graded homework deadline.

Each week, some parts of the homework (roughly 20%) will be actually graded by the readers (separate from self-grading). When the self-graded homework is submitted, the readers will compare the self- grade on the part that is actually graded with the grade that the reader assigned to that part and determine the overall score on the basis of these two scores.

Homeworks or self-grades submitted past their deadlines (after the grace period) will be assigned a score of 0 with no exceptions.

After the HW deadline, official solutions will be posted online. You will then be expected to read them and use the self-grade link generator, posted on the website under the homework section for that week, and enter your own scores and comments for every part of every problem in the homework on a simple coarse scale.

0 = Didn't attempt or very very wrong,
2 = Got started and made some progress, but went off in the wrong direction or with no clear direction,
5 = Right direction and got half-way there,
8 = Mostly right but a minor thing missing or wrong,
10 = 100% correct.

Note: You must justify self-grades of 2, 5 or 8 with a comment. Grades of 0 and 10 do not need to be justified. If you are really confused about how to grade a particular problem, you should post on Piazza. This is not supposed to be a stressful process.

For your actual homework write-ups LaTeX is preferred, but not required -- we'll also accept neatly handwritten solutions. If you're really unsure about what "neatly" means you can make a private Piazza post, but we believe everyone has a pretty good sense of where the line is on legibility.

Exam Policies

You will have a midterm and a final exam, information on what they will cover will be released closer to the exam dates.
Midterm Date: Thursday October 22nd, with two available times, see piazza for details.
Final Exam Date: Tuesday December 15th, with two available times, see piazza for details.

Grading Breakdown

  • Homeworks: 30% (10 homeworks. The grade will be based on the top 8 homeworks, dropped homework counts for 0 for this.)
  • Max(Midterm, Final): 42%
  • Min(Midterm, Final): 28%

DSP

Hermish is in charge of managing DSP accommodations. Please reach out to him at hermish@ if you need accommodations.

Course Communication

The instructor will post homeworks, discussions, homework solutions, discussion solutions, recordings of the lectures and other course-related documents on bCourses. An email broadcast will be sent out whenever something new is posted on bCourses by the instructor. The TAs will post announcements, clarifications, hints, etc. on Piazza. You must check the EECS127/227A bCourses page and the EECS127/227AT Piazza page frequently throughout the term.

If you have a question, your best option is to post a message there. The staff will check the forum regularly, and other students will be able to help you too. When using the forum, please avoid off-topic discussions, and please do not post answers to homework questions before the homework is due. Also, always look for a convenient category to post the question to (for example, each homework will have its own category, so please post there). That will ensure you get the answer faster.

If your question is personal or not of interest to other students, you may mark your question as private on Piazza, so only the instructors will see it. If you wish to talk with one of us individually, you are also welcome to come to our office hours. Please reserve email for the questions you can't get answered in office hours, in discussion sections, or through the forum.

It can be challenging for the instructors to gauge how smoothly the class is going. We always welcome any feedback on what we could be doing better. If you would like to send any feedback, you can do so here.

Collaboration

We encourage you to work on homework problems in study groups of two to four people; however, you must always write up the solutions on your own. Similarly, you may use books or online resources to help solve homework problems, but you must always credit all such sources in your writeup, and you may never copy material verbatim. Using previous homework and exam solutions is strictly prohibited, and will be considered academic dishonesty. This is not how you want to start your career as an engineer.

We expect that most students can distinguish between helping other students and cheating. Explaining the meaning of a question, discussing a way of approaching a solution, or collaboratively exploring how to solve a problem within your group is an interaction that we encourage strongly. But you should write your homework solution strictly by yourself so that your hands and eyes can help you internalize the subject matter. You should acknowledge everyone whom you have worked with, or who has given you any significant ideas about the homework. This is good scholarly conduct.

Don't Be Afraid to Ask for Help

Are you struggling? Please come talk with us! The earlier we learn about your struggles, the more likely it is that we can help you. Waiting until right before an exam or the last few weeks of the semester to let us know about your problems is not an effective strategy - the later it is, the less we will be able to help you.

Even if you are convinced that you are the only person in the class who is struggling, please overcome any feelings of embarrassment or guilt, and come ask for help as soon as you need it – we can almost guarantee you're not the only person who feels this way. Don't hesitate to ask us for help – we really do care that you thrive!

Advice

The following tips are offered based on our experience.

Do the homework! The homework is explicitly designed to help you to learn the material as you go along. There is usually a strong correlation between homework scores and final grades in the class.

Keep up with lectures! Discussion sections, labs and homework all touch on portions of what we discuss in lecture. Students do much better if they stay on track with the course. That will also help you keep the pace with your homework and study group.

Take part to discussion sections! Discussion sections are not auxiliary lectures. They are an opportunity for interactive learning. The success of a discussion section depends largely on the willingness of students to participate actively in it. As with office hours, the better prepared you are for the discussion, the more you are likely to benefit from it.

Come to office hours! We love to talk to you and do a deep dive to help you understand the material better.

Form study groups! As stated above, you are encouraged to form small groups (two to four people) to work together on homework and on understanding the class material on a regular basis. In addition to being fun, this can save you a lot of time by generating ideas quickly and preventing you from getting hung up on some point or other. Of course, it is your responsibility to ensure that you contribute actively to the group; passive listening will likely not help you much. Also recall the caveat above, that you must write up your solutions on your own. We strongly advise you to spend some time on your own thinking about each problem before you meet with your study partners; this way, you will be in a position to compare ideas with your partners, and it will get you in practice for the exams. Make sure you work through all problems yourself, and that your final write-up is your own. Some groups try to split up the problems ("you do Problem 1, I'll do Problem 2, then we'll swap notes"); not only is this a punishable violation of our collaboration policies, it also ensures you will learn a lot less from this course.