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

Project

The final project structure is inspired by EE227BT at UC Berkeley and CS6789 at Cornell.

Projects can have two different formats:

• Option 1: Literature review: describe in detail a set of 3-5 papers and reproduce numerical experiments. In this option, you don't need to produce new results. Instead, you need to prepare a detailed review around a particular topic (based on a set of 3-5 papers), and furthermore, you need to reproduce typical numerical results in one of those papers (i.e., implement the algorithms/methodologies and test them in some problem instances from those papers).

• Option 2: Design methodology: design a new SDP/SOS methodology to address a particular problem (e.g., from your own research or a problem you are interested in). In this option, you need to propose Something New (small or big) that does not exist in the literature. New ideas may emerge from reading those papers. So you may want to start with a set of 3-5 papers, then think critically of their methods, and ask questions during your reading (why this, how about that, etc.). You may be able to introduce a variant of the existing methods that can improve upon them. This can be a good choice for the second option.

A few project ideas are listed at the bottom of this page.

Proposal (5%)

We will use the L4DC LaTex format. Your proposal should be 2 pages maximum (not including references) and should include title, team members, abstract, related works, problem formulation, and goals.

Presentation (10%)

• Each team has 12 minutes + 3 minutes Q & A

• It is good to tell a complete story (you may want to include: background/motivation, main challenges, technical approaches, proof ideas, numerical experiments, conclusion and future work, etc.); A simple yet good guideline for giving presentations is Giving a Presentation by Prof. Dennis Bernstein;

• It is even better to let every audience to learn at least a piece of good message from your presentation;

• It is perfect to let yourself know the topics better after you give the presentation.

Final Report (15 %)

Due by 5:00 pm on March 14. We will use the L4DC LaTex format. Your report should be 10 pages maximum (not including references and appendix; it is likely that I will not read your appendix though). Your final report will be evaluated by the following criteria:

• Merit: Is your problem statement and solution strategy well motivated? Have you justified the approach(es) for the problem?

• Technical depth: How technically challenging was what you did? Did you prove the main results? Did you use a package or write your own code for the implementation?

• Presentation: How well did you explain what you did, your results, and interpret the outcomes? Did you use good graphs and visualizations? How clear was the writing? Did you justify your approach?

Project ideas

We provide a few project ideas below. They can be used for either Option 1 or Option 2. You are welcome to propose your own project idea or use a new set of papers, but please discuss with the instructors.

Theories

• Different inner/outer approximation of SDPs and their approximation quality. Conduct a survey on recent approximation techniques on positive semidefinite matrices and their approximation quality, e.g., [Ahmadi and Majumdar 2017]; [Zheng et al., 2019]; [Blekherman et al., 2020]; [Song and Parrilo, 2021]

• Facial reduction techniques for semidefinite optimization. Conduct a survey on facial reduction techniques that allow us to derive an equivalent and smaller semidefinite problem, e.g., [Waki and Muramatsu 2013]; [Permenter and Parrilo 2018]; [Zhu et al. 2019]

• Sparsity-exploiting techniques for SOS optimization. Conduct a survey on typical sparsity-exploiting techniques for SOS optimization, e.g., [Waki et al., 2006];[Permenter and Parrilo, 2014]; [Waki and Muramatsu. 2010]; [Zheng et al., 2018].

• Sparse matrix decomposition and their applications in SDP/SOS optimization, e.g., [Kakimura, 2010], [Zheng and Fantuzzi, 2020], [Zheng et al. 2021]

• Semidefinite representation of convex sets, e.g., [Helton and Nie, 2010]; [Helton and Nie, 2009];

Algorithms

• First-order algorithms for large-scale SDPs. Conduct a survey on recent first-order algorithm design for solving large-scale semidefinite optimization, e.g., [Wen et al., 2010]; [Zhao et al., 2010]; [O’Donoghue et al., 2016]; [Garstka et al., 2019]

• Iterative approximating techniques for SDPs, such as basis pursuit or column generation techniques, e.g., [Ahmadi and Hall 2015]; [Ahmadi et al., 2017]; [Bertsimas and Cory-Wright, 2019]

• First-order algorithms for polynomial optimization, e.g., [Nie & Wang 2012];[Zheng et al., 2017]; [Yang et al., 2021].

• Non-symmetric interior-point algorithms for sparse SDP or SOS optimization, e.g., [Skajaa & Ye, 2015];[Papp and Yildiz, 2019]; [COEY et al. 2020];

Applications

• Semidefinite relaxation for neural network verifications. Conduct a survey on recent semidefinite relaxation methods for neural network verification, e.g., [Raghunathan et al., 2018], [Fazlyab et al., 2019], [Zhang 2020], [Batten et al., 2021]. Can you propose a new method based on your reading?

• Semidefinite and SOS optimization for Lipschitz constant estimation. Conduct a survey on recent semidefinite/SOS methods for estimating the Lipschitz constant of neural networks, e.g., [Fazlyab et al., 2019], [Jordan and Dimakis, 2020], [Chen et al. 2020].

• SDP/SOS optimization for sensor location problem, e.g., [So & Ye, 2007]; [Kim et al., 2009]; [Nie 2009]

• SOS optimization for geometric perception tasks, e.g., [Yang & Carlone, 2020]; [Yang & Carlone, 2021]; [Chen et al., 2020]

• SOS optimization for nonlinear system analysis, e.g., [Anderson & Papachristodoulou, 2015];

• SDP/SOS techniques for optimal power flow problems, e.g., [Lavaei & Low, 2011]; [Molzahn & Hiskens, 2014]; [Kocuk et al., 2016]

• SDP/SOS techniques for nonlinear systems with neural network in the loop, e.g., [Ferrari 2009]; [Yin et al., 2020]; [Yin et al., 2021];

• Semidefinite optimization for rank minimization problems, e.g., [Fazel et al., 2001]; [Recht et al., 2007]; [Chandrasekaran et al., 2009];

• Semidefinite optimization for robust control problems, e.g., [Gahinet & Apkarian, 1994]; [Scherer et al., 1997]; [Oliveira et al., 2002]; [Zheng et al., 2021]

• Semidefinite optimization for mixed traffic systems, e.g., [Zheng et al., 2018];[Wang et al., 2020]; [Mousavi et al., 2021].

• SDP/SOS techniques for PDE control/analysis, e.g., [Goluskin and Fantuzzi, 2019]; [Ahmadi et al., 2016]; [Marx et al., 2020]; [Valmorbida et al., 2015]; [Chernyavsky et al., 2021];

• SDP/SOS techniques for fluid dynamics analysis, e.g., [Chernyshenko et al., 2014]; [Fantuzzi et al., 2021]; [Fantuzzi et al., 2018]; [Fantuzzi and Wynn, 2016]; [Huang et al., 2015]; [Fuentes et al., 2019]; [Ahmadi et al., 2018]; [Lakshmi et al., 2020].