ECE285, Fall 2026 – Semidefinite and Sum-of-squares Optimization

Project

Each project should consist of two team members (in exceptional cases, we may allow individual projects, but please talk with the instructor to get an approval first). For each assignment, please briefly describe the role of each member. Both team members will receive the same grade.

The goal of the course project is to develop a deeper understanding of a particular topic in semidefinite optimization, polynomial optimization, or convex optimization more generally. The emphasis is on careful reading, clear explanations, and numerical exploration. You are expected to understand the main ideas and technical details of your chosen topic, but you are not required to produce new research results.

Projects can take one of two formats:

Option 1: Literature review and numerical reproduction: prepare a detailed review of 2 (or 3) closely related papers on a particular topic (You may read additional relevant papers as needed, but you are not expected to review them in depth). Explain the problem being studied, the main ideas and results, and the connections and differences among the papers. In addition, reproduce representative numerical results from one of the papers by implementing the relevant algorithms and testing them on selected problem instances. Explain your implementation and discuss how your results compare with those reported in the paper.

Option 2: Literature review and exploratory extension: Start with a review of 2 (or 3) closely related papers, then explore a question motivated by your reading or your own research. For example, you might investigate a variant of an existing method, examine the role of an assumption, or apply a method to a different problem. Explain the motivation for your exploration and support your observations with mathematical analysis or numerical experiments. New theoretical results or improved performance are welcome but are not required.

AI policy. The course AI policy also applies to the project. All project assignments, including the proposal, presentation, and final report, must be completed by the team members and reflect your own understanding and intellectual effort. Each team member is expected to develop a thorough understanding of the project and be able to explain its main ideas, technical details, and results.

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 (15%)

Each team has 18 minutes + 2 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;
You need to demonstrate that you have a geniue understanding of the topic.
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 (20 %)

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? How well did you explain the main results, their assumptions, and the key proof ideas? How carefully did you implement the methods and analyze the numerical results?
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 topic or use a different set of papers, but please discuss your plan with the instructor.

Choose a focused question and a set of 2 (or 3) closely related papers. For long surveys, select the sections most relevant to your topic. For Option 1, reproduce representative numerical results from one of your chosen papers. You are not required to produce new research results.

Theory and structure

Strict complementarity, error bounds, and quadratic growth in SDPs: Study the relationships between strict complementarity, quadratic growth, and error bounds in semidefinite optimization. For numerical exploration, study small SDPs with known solutions and illustrate the relationship between objective gaps and distances to the solution set, comparing examples with and without strict complementarity. Suggested readings: [Ding and Udell, 2023]; [Liao et al., 2024]; and [Ding and Udell, 2021].

Exploiting sparsity in SDP and SOS optimization: Study how chordal decomposition or term sparsity reduces the size of SDP and SOS formulations. Focus on one mechanism and compare dense and sparse formulations on a small family of problems. Explain whether the structural simplification preserves the original relaxation or changes its strength. Suggested readings: [Zheng et al., 2021] (and the references therein); [Wang et al., 2021].

Approximating the PSD and SOS cones: Study inner and outer approximations of the positive semidefinite cone and their implications for SOS optimization. Topics include diagonally dominant, scaled diagonally dominant, and block factor-width approximations, as well as theoretical limits on the approximation quality achievable using smaller semidefinite constraints. For numerical exploration, compare SOS, SDSOS, and DSOS lower bounds on small polynomial problems, examining the tradeoff between bound quality and computation time. Suggested readings: [Ahmadi and Majumdar, 2019]; [Zheng et al., 2023]; [Song and Parrilo, 2023].

Algorithms

First-order methods for semidefinite and convex optimization: Study first-order algorithms such as projected gradient descent, the alternating direction method of multipliers (ADMM), and the primal-dual hybrid gradient (PDHG) method. Focus on one or two methods, explaining their main ideas, convergence guarantees, and computational cost per iteration. For numerical exploration, implement the selected methods on small problems, such as semidefinite relaxations of Max-Cut. Suggested readings: [Wen et al., 2010]; [Chambolle and Pock, 2011]; [O'Donoghue et al., 2016].

Low-rank factorization methods for semidefinite optimization: Study the Burer-Monteiro factorization, its computational advantages, and the assumptions behind its optimality guarantees. Implement a factorized method for small SDPs and investigate how the factor rank and initialization affect its performance relative to standard convex SDP solvers. Suggested readings: [Burer and Monteiro, 2003]; [Boumal et al., 2020].

Proximal and spectral bundle methods: Study how accumulated subgradient information produces useful models of nonsmooth convex objectives, and how spectral structure can be used in methods for SDPs. Implement a basic proximal bundle method for standard SDPs, and reproduce a small spectral-bundle experiment. Suggested readings: [Diaz and Grimmer, 2023]; [Liao et al., 2026].

Performance estimation of optimization algorithms using SDP: Study how interpolation inequalities and Gram matrices turn the worst-case analysis of a first-order optimization method into an SDP. Derive a small performance-estimation problem, then use PEPit to compare gradient descent and an accelerated method across stepsizes or function classes. Discuss how numerical worst-case bounds relate to analytical convergence guarantees. Suggested readings: [Taylor et al., 2017]; [Goujaud et al., 2024].

Broader convex optimization

Differentiable convex optimization layers: Study how solutions of parameterized convex programs can serve as layers in a learning model. Derive sensitivities through the optimality conditions of a small quadratic program, check them using finite differences, and reproduce a simple learning experiment. Discuss the assumptions needed for differentiability. Suggested readings: [Amos and Kolter, 2017]; [Agrawal et al., 2019].

Distributionally robust optimization: Study how uncertainty about a probability distribution leads to a worst-case optimization problem and, under suitable assumptions, a tractable convex reformulation. For the survey below, select only the sections relevant to your chosen problem. Suggested readings: [Mohajerin Esfahani and Kuhn, 2018]; [Kuhn et al., 2025].

Optimal transport and entropic regularization: Study the linear-programming formulation of discrete optimal transport, entropic regularization, and Sinkhorn iterations. Investigate how the regularization parameter affects transport cost, marginal residuals, and computation time, etc. Suggested readings: [Cuturi, 2013]; [Altschuler et al., 2017].

Convex formulations of two-layer neural-network training: Study a setting in which regularized two-layer ReLU training admits a convex formulation. Explain the roles of activation patterns, network width, and regularization. Use a small one- or two-dimensional regression example to compare a convex formulation with direct nonconvex training under matching loss and regularization choices. Suggested readings: [Pilanci and Ergen, 2020]; [Mishkin et al., 2022].

Applications

Semidefinite relaxations for neural-network verification: Study convex relaxations for bounding the worst-case output of a ReLU network. Compare simple linear bounds with SDP-based bounds for a small network, explaining how coupling between neurons affects tightness. SDP-CROWN provides a recent connection between SDP ideas and scalable bound propagation. Keep numerical experiments small and use the same perturbation set for any direct comparison. Suggested readings: [Raghunathan et al., 2018]; [Batten et al., 2021] [Chiu et al., 2025].

Data-driven control using linear matrix inequalities: Study how feedback controllers can be computed from input-state data through linear matrix inequalities, with particular attention to data richness and noise assumptions. Reproduce a stabilization or LQR example for a small linear system and investigate how the amount of data or a noise bound affects feasibility and closed-loop performance. Suggested readings: [De Persis and Tesi, 2020]; [van Waarde et al., 2022]. Optional reading: [van Waarde et al., 2023].

SOS certificates for nonlinear-system stability: Study how polynomial nonnegativity conditions for Lyapunov functions and regions of attraction are replaced by SOS constraints. Compute polynomial Lyapunov functions or certified inner estimates of a region of attraction for one two-state system, then compare certificate degrees. Explain which optimization steps are convex and which require fixing variables or alternating between SDPs. Suggested readings: [Papachristodoulou and Prajna, 2005]; [Topcu et al., 2008].

Certifiable estimation and geometric perception: Study an SDP relaxation of a geometric estimation problem and explain how primal and dual information can certify a candidate solution. Use a small rotation-synchronization or localization experiment to examine how noise affects relaxation tightness. The second paper also considers the complications caused by anisotropic measurement weights. Suggested readings: [Rosen et al., 2019]; [Holmes et al., 2024].

AI assistance disclosure: ChatGPT was used to help brainstorm and organize the project ideas and polish the descriptions in this section.

You are also welcome to take a look at recent survey papers to identify applications that you're interested in. For example, [Hall 2019]; [Majumdar et al., 2020]; [Zheng et al., 2021]

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