ECE 508: Convex Optimization (Fall 2023)

Lectures

Mon/Wed, 4:30-5:45pm, LH 202 (Lincoln Hall)

Instructor

Shuo Han (hanshuo@uic.edu)
Office hours: Mon, 2:30-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 the following Wednesday in class.
  • 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 are likely to take place around Week 7 and Week 13, respectively. The exact date(s) will be announced at a later time.
• 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. The deadline for submission is December 3, 2023.
• 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 the final report

Homework Policy

• You are required to submit a hard copy of your homework in class. If you are unable to attend the lecture, you need to email me at least one day prior to the due date for approval of electronic submission (usually I will say yes unless you are doing it many times), after which you can email your homework to me by the due date. If you are writing your solution by hand, we recommend that you digitize it using a high-quality scanner (as opposed to taking photos), which is available and free at the Daley Library. This ensures that your writing remains legible after we print out your electronic submission.
• Make a copy of your homework prior to submission. You will be asked to provide your copy for any claims of missing homework.
• 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.
• 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. 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 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 that are handed in should be written up individually and should 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 and the problems that 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 in the calculation of 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 he/she will be absent. Every reasonable effort will be made to honor the request.

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