ECE 508: Convex Optimization (Fall 2024)

Lectures

Mon/Wed, 4:30-5:45pm, TH 215 (Taft Hall)

Instructor

Shuo Han (hanshuo@uic.edu)
Office hours: Mon, 3:00-4:00pm, 1110 SEO

Teaching Assistant

N/A

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 or Python.

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 (20%): Homework sets are issued every Wednesday and are due 8pm the following Wednesday.
  • Homework will be graded on a scale from 0 to 4 based on effort and completion.
  • The lowest one will be dropped towards calculating your total homework grade. Namely, if there are X homework sets in total, then the best X-1 sets will be used.
  • There will be about 11 homework sets in total.
  • No homework will be assigned in Weeks 1 and 15, and the weeks of midterm exams.
• Two midterm exams (25% + 25%): In-class, closed-book, and closed-notes.
  • You may use a single handwritten letter-sized double-sided "cheat sheet" during the first midterm exam, and two for the second midterm exam. The cheat sheets may contain formulas, facts, definitions, and theorems. However, your cheat sheets may not contain worked examples. You must hand in your cheat sheets along with your completed exam. No calculators/computers are allowed in the exam.
  • The exams will likely take place around Week 7 and Week 13, respectively. The exact date(s) will be announced later.
• Final report (30%): You are expected to independently solve 10 problems of your choice from a given set of problems. Your solutions should be typed up (preferably in LaTeX) as a single report and submitted on Gradescope. You will be asked to give a brief oral presentation of one problem chosen by the instructor during Week 15. The deadline for submitting the final report is December 8, 2024.
• There will be no make-up exams or substitutions.
• Incomplete grades are given according to the UIC policy. For this course, "satisfactory progress" means that you are currently receiving a grade of C or better at the time of requesting an incomplete grade.
  
• Guaranteed cutoff grades: A-85%, B-75%, C-65%.

Course Logistics

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

• This website: course syllabus
• UIC Blackboard: viewing grades
• Piazza: course announcements, downloading problem sets and course materials, Q&A
• Gradescope: submitting homework and the final report

Homework Policy

• You are required to submit your homework on Gradescope. 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, we ask that you digitize it using a high-quality scanner (as opposed to taking photos), which is available and free at the Daley Library. This will ensure that the submitted copy is legible.
• You may consult the lecture notes, the textbooks listed below, references mentioned in class, other students (see the "Collaboration" section below), 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.
• Show all your work to receive credits. We prefer correct and concise solutions. 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 in any circumstances. The policy of dropping the lowest grade in homework assignments is meant to cover emergencies. Use it wisely.

Collaboration

• Collaboration on homework assignments is encouraged. All solutions handed in should be written up individually and reflect your own understanding of the subject matter at the time of writing. Notes taken during the discussions cannot be used at the time of writing your own solutions.
• MATLAB scripts and plots are considered part of your writeup and should be done individually (you can share ideas, but not code).
  
• You are not allowed to collaborate on any problems in the final report.
• If you have collaborated with others, include their names, the problems you have collaborated on, and to what extent. Also, be explicit that you have written your solution on your own and that you have not shared code. No statement will be treated as no collaboration.
  • Example: "I collaborated with [names] on Problems 1 and 3, discussing related concepts and solution strategies. The solutions that I submit reflect my own understanding at the time of writing. I have not shared my code with others."

Academic Integrity

• We treat academic dishonesty seriously. All offenses are reportable to the University.
• For any violation of the course policy in homework or the final report, the homework assignment or the report will receive a grade of zero, and a warning will be issued to the offender. For homework assignments, the zero grade will not be dropped when calculating the letter grade.
• For two violations of the course policy, the final letter grade of the offender will be lowered by one tier, e.g., from A to B.
• For more than two violations of the course policy, 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) and UIC's official page 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 the 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 they will be absent. Every reasonable effort will be made to honor the request.
• UIC is committed to full inclusion and participation of people with disabilities in all aspects of university life. To receive accommodations, you will need to disclose the disability to the Disability Resource Center (DRC), complete an interactive registration process with the DRC, and provide me with a Letter of Accommodation (LOA). Upon receipt of an LOA, I will gladly work with you and the DRC to implement approved accommodations.

Course Text and References

The required textbook 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 (2022 version)
• [BPT12] G. Blekherman, P. A. Parrilo, and R. R. Thomas (Eds.), Semidefinite Optimization and Convex Algebraic 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 favorite 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 typesetting 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.
  • Comprehensive usage guides are available on the following websites:
    • Overleaf LaTeX documentation
    • Wikibooks LaTeX guide