ECE 594: Convex Optimization (Fall 2021)

Lectures

Mon/Wed, 4:30-5:45pm, Lecture Center A7

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.

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 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 letter-sized double-sided "cheat sheet" during the exam. The cheat sheet may contain formulas, facts, definitions, and theorems. However, your cheat sheet may not contain worked examples. You must hand in your cheat sheet along with your completed exam. No calculators/computers are allowed in the exam.
  • The exams are likely to take place during Week 5 and Week 10, 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 of submission is December 5, 2021.
• 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 hardcopy 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.
• 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 textbook 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 without proper supporting documents (e.g., a note from doctor or the Dean).

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 assignements, the zero grade will not be dropped in 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) to learn more about academic integrity,

COVID-19 Special Policies

The following policies are from the official guidance provided by the University:

• Face Masks: Masks covering both the mouth and nose must be worn at all times by all students, faculty, and staff while inside any campus building regardless of vaccination status. If you do not wear a mask, you will be asked to leave the classroom and will not be allowed back in class unless or until you wear a mask. If you have forgotten your mask, you may pick one up from one of the student information desks on campus during the first two weeks of campus. Students who do not comply with the mask-wearing policy will be reported to the Dean of Students. Eating and drinking are not allowed in classrooms.
• On-Campus Exams: This course will require students to be on campus for in-person exams. If you are a student who is not coming to campus to attend classes, you will be required to adhere to the campus COVID-19 testing requirements and have a saliva test prior to coming to campus to take the exam. Saliva testing must be completed at UIC not earlier than 48 hours and not more than 72 hours ahead of the exam date, so that the test result is available (and negative) by the date of the examination. For example, if you have an in-person exam at 3:00 p.m. on Thursday, you must complete your saliva testing no later than 3:00 p.m. on Tuesday but no earlier than 3:00 p.m. on Monday. You must be prepared to present your UIC Daily Pass at the examination site. Note that the Saliva Testing Badge AND the Healthcheck Badge must be “green” to sit for the examination.

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 (2021 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 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 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.
  • Comprehensive usage guides are available on the following websites:
    • Overleaf LaTeX documentation
    • Wikibooks LaTeX guide