ECE 594: Convex Optimization (Fall 2020)

Lectures

Tue/Thu, 12:30-1:45pm, online (Blackboard Collaborate)
The class will be taught synchronously to promote real-time interaction. Lectures will be recorded.

Instructor

Shuo Han (hanshuo@uic.edu)
Office hours: Mon, 3:00-5:00pm, online (see instructions)

Teaching Assistant

Lubna Shibly Mokatren (lshibl2@uic.edu)

Course Description

This graduate-level course covers three main aspects of convex optimization: theory, applications (e.g., machine learning, signal/image processing, controls), and algorithms. After taking the course, students should be able to recognize convexity and use convex optimization to model and solve problems that arise in engineering applications. Students will also gain a basic understanding of how convex optimization problems are solved algorithmically so as to determine whether a given problem can be solved using off-the-shelf solvers.

Prerequisites

Good knowledge of linear algebra (e.g., as in ECE 550 or ECE 531). Exposure to probability (e.g., ECE 341). Familiarity with MATLAB.

Topics

• Introduction (including a review of linear algebra)
• Theory
  • Convex sets
  • Convex functions
  • Convex optimization problems: LP, QP, QCQP, SOCP, SDP, GP, conic programs
  • Duality: dual cones, convex conjugate, dual problems
• Applications
  • Geometric problems: projection, distance, covering
  • Machine learning: regression and classification
  • Data processing: estimation, reconstruction, denoising
  • Decision making under uncertainty: chance-constrained optimization, robust optimization
• Algorithms
  • First-order methods: gradient methods, proximal methods
  • Second-order methods: Newton's method, interior-point methods
• Advanced topics (time permitting)
  • Algorithms for large-scale optimization
  • Convex relaxation of nonconvex problems
  • Sums-of-squares optimization

Course Policy

Grading

• Homework (30%): Homework sets are issued every Thursday and are due the following Thursday by 6pm.
  • There will be about 11 homework sets in total.
  • No homework will be assigned in Weeks 1, 8 (due to the midterm exam) and 15 (due to the final exam).
  • The lowest one will be dropped. Namely, if there are X homework sets in total, then the best X-1 sets will be used towards calculating your total homework grade.

• Midterm exam (30%): Online and open-book/note. The exact date(s) and format will be announced at a later time. It will cover materials from Weeks 1-7 (convex optimization theory) and is likely to take place during Week 9.

• Final exam (40%): Online and open-book/note. The exact date(s) and format will be announced at a later time. In addition to traditional analytical questions, the exam will also involve using CVX (a MATLAB software package that you will learn in this course) to solve convex optimization problems.

• Guaranteed cutoff grades: A-85%, B-75%, C-65%.

Course Logistics

We will use a number of websites/apps throughout this course, each of which has a different purpose.

• This website: course syllabus
• UIC Blackboard: lectures and recordings, viewing grades, midterm and final exams
• Piazza: course announcements, downloading problem sets and course materials, Q&A with the instructor and the TA
• Gradescope: submitting homework and viewing the graded copy
• Zoom + Google Calendar: office hours
• Slack: socializing with other students

Homework Policy

• You are required to submit your homework on Gradescope. You will receive a link to join during Week 2 before Homework 1 is due. Email the instructor if you do not receive the link by then.
• You are encouraged (but not required) to typeset your homework using LaTeX. See the section "LaTeX resources" on this page if you are new to LaTeX. If you choose to write your solution by hand, make sure the submitted copy is legible.
• Collaboration on homework assignments is encouraged. You may consult the lecture notes, the textbook listed below, references mentioned in class, other students, the TA, or the instructor. You may also consult outside references not listed on the course webpage, provided that you cite those references in your homework solutions.
  
• You cannot consult homework solutions from prior years or solution manuals. All solutions that are handed in should be written up individually and should reflect your own understanding of the subject matter at the time of writing.
• MATLAB scripts and plots are considered part of your writeup and should be done individually (you can share ideas, but not code).
  
• Show all your work to receive credits. However, we will deduct points from long needlessly complex solutions, even if they are correct. If you find that your solution to a problem goes on and on for many pages, you should try to come up with a simpler one. One useful way to shorten your solutions is to cite results derived in class or from the textbooks.
  
• Late homework: Late homework will not be accepted without proper supporting documents (e.g., a note from doctor or the Dean).

Academic Integrity

• We treat academic dishonesty seriously. All offenses are reportable to the University.
• For first-time offense in homework, the final letter grade of the offender will be lowered by one tier, e.g., from A to B.
• For cheating in exams or second-time offense in homework, the offender will receive a letter grade of F.
• The penalty applies to all parties involved.
• You can read this page by Jeff Erickson (UIUC) to learn more about academic integrity,

Others

• You should keep the course material (lecture notes, audio recordings, and homework problems and solutions) for personal use only and not post them on public websites (e.g., Course Hero).
• Students who wish to observe their religious holidays should notify instructor by the tenth day of the semester of the date when they will be absent unless the religious holiday is observed on or before the tenth day of the semester. In such cases, the students should notify the instructor at least five days in advance of the date when he/she will be absent. Every reasonable effort will be made to honor the request.

Course Text and References

The required textbooks for the course is:

• [BV04] S. P. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, 2004. Online access

Other references

• [BN01] A. Ben-Tal and A. Nemirovski, Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications, SIAM, 2001. Online access (2020 version)
• [BPT12] G. Blekherman, P. A. Parrilo, and R. R. Thomas (Eds.), Semidefinite Optimization and Convex Alegbraic Geometry, SIAM, 2012. Online access

LaTeX Resources

• Installation: See a list of LaTeX distributions for common operating systems.
• LaTeX editors
  • Because the LaTeX source files are in plain text, you can always use your favoriate text editor.
  • For a WYSIWYG document processor (similar to MS Word) based on LaTeX: LyX
  • Alternatively, you can use an online browser-based LaTeX editor: Overleaf
• LaTeX usage
  • If you are new to LaTeX, the best way to begin is by typsetting using an existing template. You can find a LaTeX template useful for this course on this page. Read template_notes.pdf and use template_notes.tex as a start.
  • For how to compile a PDF from LaTeX source, see this page. We recommend using pdfLaTeX.
  • If you do not know how to type a mathematical symbol, you can get help from Detexify.
  • A comprehensive usage guide is available on the Overleaf website.