ECE285, Winter 2024 – Semidefinite and Sum-of-squares Optimization

(This is the Winter 2024 version of this course. For previous version, click here)

Lectures: Tuesdays/Thursdays 3:30 pm -4:50 pm PST

Location: WLH 2207

Instructors:

• Yang Zheng (zhengy@ucsd.edu)

• Chih-Fan (Rich) Pai (cpai@ucsd.edu)

Office hours:

• Yang Zheng (5:00 pm - 6:30 pm, 3301A FAH)

• Chih-Fan (Rich) Pai (5:00 pm - 6:30 pm, 3301A FAH)

Syllabus: ECE285

Course description

Convex optimization has profound impacts on many problems in control theory, discrete and nonlinear optimization, theoretical computer science, and machine learning. It is a fundamental tool to ensure efficient, resilient, and safe operations of many engineering systems, such as smart power grid, transportation, robotics, and many others. Optimization in these areas often takes the form of conic optimization, especially semidefinite programs. This course will cover semidefinite optimization which is a far-reaching generalization of linear programs. Another emphasis of the course will be on sum-of-squares optimization that deals with optimization problems involving polynomials. Some classical applications in control and recent ones in machine learning will be covered too.

A tentative list of topics that we will cover include

• From linear programming to conic programming. Duality theory.

• Semidefinite optimization and convex relaxations.

• Sum-of-squares and moment problems.

• Applications in control, dynamical systems, and machine learning.

The students are expected to sign up on Piazza and GradeScope. Discussions and important announcements will happen on Piazza. The homework should be turned in and will be graded on GradeScope.

Pre-requisites

This course assumes basic knowledge in linear algebra. Some knowledge of convex optimization will be useful. Mathematical maturity, familiarity with MATLAB, Python, or similar software.

Course grade

• 50% homework (6 problem sets; will drop the lowest score)

• 20% midterm exam (in class; one page of hand-written cheat sheet allowed)

• 30% final project

• Course attendance is mandatory; 5% extra credit for course attendance/participation

These weights are approximate; we reserve the right to change them later.

The due date of each homework and project assignment will be clearly stated. We expect you to turn in all completed problem sets on time. Late submissions and deadline extensions will not be possible because our schedule is very tight.

Collaboration policy: You are encouraged to work with other students on lecture notes, homework sets, general discussions of projects. But please note that the work you turn in should be your own! It is not acceptable to copy a solution that someone else has written. Instances of academic dishonesty will be referred to the Office of Student Conduct for adjudication.

Software

You will use one of YALMIP (Matlab), CVX (Matlab), CVXPY (Python) or CVXOPT (Python), to write simple scripts for homework questions.

References

• Blekherman, G., Parrilo, P. A., & Thomas, R. R. (Eds.). (2012). Semidefinite optimization andconvex algebraic geometry. Society for Industrial and Applied Mathematics.

• Ben-Tal, A., & Nemirovski, A. (2001). Lectures on modern convex optimization: analysis, algorithms, and engineering applications. Society for industrial and applied mathematics.

• Boyd, S. & Vandenberghe, L. (2004). Convex optimization. Cambridge university press.

• Lasserre, J. B. (2009). Moments, positive polynomials and their applications. World Scientific.

• Laurent, M. & Vallentin, F. (2016) Semidefinite optimization, Lecture notes

Academic Integrity

UCSD's Code of Academic Integrity applies to this course. It is dishonest to cheat on exams, copy other people's work, or fake experimental results. An important element of academic integrity is fully and correctly acknowledging any materials taken from the work of others. Instances of academic dishonesty will be referred to the Office of Student Conduct for adjudication.

Acknowledgments

The design of this course is inspired by the following excellent courses

• Topics in Convex Optimisation, University of Cambridge (Lecturer: Hamza Fawzi)

• ORF523:Convex and Conic Optimization, Princeton University (Lecturer: Amir Ali Ahmadi)

• 6.256 Semidefinite Optimization, MIT (Lecturer: Pablo A. Parrilo)