Workshop on Semidefinite and Polynomial Optimization
CWI, Amsterdam
29 August  2 September, 2022
This workshop is dedicated to recent developments in semidefinite and polynomial optimization, and their applications in combinatorial and continuous optimization, discrete geometry and quantum information.
The program will consist of invited lectures by experts in the field. It will also feature lectures by younger researchers and ample time will be left for free discussions.
You may download the program here.
The workshop takes place in the Euler room, Amsterdam Science Park Congress Center (Science Park 125), located next to CWI.
However, due to the recently planned strikes by employees at the Dutch railway company (NS), disruptions may be expected in train public transport on some days during the duration of the workshp. For this reason we will also offer the possibility to listen to the presentations online.
Zoom link: https://cwinl.zoom.us/j/3723284671?pwd=NDFwU3dkODB0S1dSUHIwbFJ2VXhydz09
Meeting ID: 372 328 4671,
Passcode: 390834
Speakers and Lectures
The list of invited speakers includes (in alphabetic order):
 Aida Abiad (TU Eindhoven)
Title: Eigenvalue bounds for the independence and chromatic number of graph powers
Slides.
Abstract: In this lecture we will present several eigenvalue bounds on the independence number and the distance chromatic number of graph powers. We will see how to use polynomials and mixedinteger linear programming in order to optimize such bounds. Some infinite families of graphs for which the new bounds are tight will also presented.
 Hamza Fawzi (University of Cambridge)
Title: Quantum relative entropy optimization
Slides.
Abstract:
Many problems in quantum information are formulated as optimization problems (convex or nonconvex) involving the quantum relative entropy function. I will discuss various tools to deal with such optimization problems. First, I will present a selfconcordant barrier with optimal parameter for the quantum relative entropy cone. This barrier function can be used with interiorpoint schemes to solve convex optimization problems with the quantum relative entropy function. Second, I will consider nonconvex problems and show how to obtain a hierarchy of semidefinite relaxations using variational formulations of the quantum relative entropy and tools from approximation theory.
Based on joint works with James Saunderson (arXiv:2205.04581) and with Peter Brown and Omar Fawzi (arXiv:2106.13692).
 Sevag Gharibian (Paderborn University)
Title: Approximating quantum constraint satisfaction problems via noncommutative SDP hierarchies (I)
Slides.
Abstract:
SDPs are the goto method for approximating NPcomplete Boolean constraint satisfaction problems (CSPs). Quantumly, the generalization of CSPs is the fundamental klocal Hamiltonian problem, which asks: Given a manybody quantum system, what energy level does the system relax into when cooled to near absolute zero? In this work, we formally introduce the klocal Hamiltonian problem, and discuss various SDP approaches for giving nontrivial approximations. For example, how well can general quantum CSPs be approximated? How about CSPs where the constraints take a very specific, physically motivated, form? No quantum background is required, though naturally some background is always helpful!
 Sander Gribling (IRIF, Université de Paris)
Title: Mutually unbiased bases: polynomial optimization and symmetry
Slides.
Abstract:
Two orthonormal bases of C^d are called mutually unbiased
if the squared modulus of the inner product of any two vectors
in distinct bases is equal to 1/d. A natural question is for which pairs (d,k) there
exist k mutually unbiased bases in dimension d.
The (wellknown) upper bound d+1 is attained when d is a power
of a prime. For all other dimensions it is an open problem whether the
bound d+1 can be attained. Navascués, Pironio, and Acín showed how to
reformulate the existence question in terms of the existence of a certain
C^*algebra. This naturally leads to a noncommutative polynomial
optimization problem and an associated hierarchy of semidefinite programs.
The problem has a symmetry coming from the wreath product of the symmetric groups S_d
and S_k.
We exploit this symmetry (analytically) to reduce the size of the
semidefinite programs making them (numerically) tractable. A key step is a
novel explicit decomposition into irreducible modules of the space C^{dk} under the action of the above wreath product.
We present numerical
results for small d,k and low levels of the hierarchy. In particular, we
obtain sumofsquares proofs for the (wellknown) fact that there do not
exist d+2 mutually unbiased bases in dimensions d=2,3,4,5,6,7,8.
This is based on joint work with Sven Polak.
 Krystal Guo (University of Amsterdam)
Title: Transversal polynomial of graphs
Slides.
Abstract:
We explore the interplay between algebraic combinatorics and
some algorithmic problems in graph theory. We define a polynomial with
connections to correspondence colouring, a recent generalization of
listcolouring, and the Unique Games Conjecture. Like the chromatic
polynomial of a graph, we are able to evaluate this polynomial at r+1
modulo r^n, despite the complexity of computing this polynomial. This
is based on joint work with Chris Godsil and Gordon Royle.
 Etienne de Klerk (Tilburg University)
Title: Recent advances in semidefinite programming performance estimation
Slides.
Abstract:
Semidefinite programming performance estimation is a technique for the worstcase analysis of iterative algorithms. It was pioneered by Drori and Teboulle in 2014, and has since been applied successfully to a variety of methods, including (stochastic) gradient descent, accelerated gradient descent, the convexconcave procedure (DCA), the alternating direction method of multipliers (ADMM), etc. In this talk I will discuss some recent developments in this area. My talk will cover joint work with Hadi Abbaszadehpeivasti and Moslem Zamani, performed as part of the NWO ENWGROOT project Optimization for and with Machine Learning (OPTIMAL).
 David de Laat (TU Delft)
Title: The Lasserre hierarchy for equiangular lines with a fixed angle
Slides.
Abstract:
In ndimensional Euclidean space, the equiangular lines problem asks for the maximum number of lines through the origin which are pairwise separated by the same angle. For the case of a fixed angle arccos(1/(2r1)), a recent breakthrough by Jiang, Tidor, Yao, Zhang, and Zhao shows that for sufficiently high dimensions this maximum is linear in the dimension with slope r/(r1). The Delsarte LP bound and kpoint SDP bounds can also be used to obtain upper bounds for this problem, but they fail to recover this linear behaviour in high dimensions.
In this talk I will explain how the Lasserre hierarchy can be formulated for this problem, and how we can compute the second and third levels (the first level is identical to the Delsarte LP bound). For this we use a beautiful connection found by Gelbart and made explicit by Gross and Kunze between the representations of the general linear group and invariant subspaces of representations of the orthogonal group. We can use this to obtain much improved bounds in intermediate dimensions, and I will present surprising numerical data that indicates the second level of the hierarchy is linear in the dimension. Finally, I will discuss conjectures that could lead to a proof of this linear behaviour.
Joint work with Fabrício Machado and Willem de Muinck Keizer.
 JeanBernard Lasserre (LAASCNRS, Toulouse)
Title: On the Christoffel function for data analysis and optimization
Slides.
Abstract:
In this talk we briefly describe the ChristoffelDarboux (CD) kernel and the Christoffel function (CF),
wellknown tools from the theory of approximation. We next describe some of
their recent applications as a simple and easy to use tool for
 approximating the graph of a function,
 interpolation of a function from finitely many values,
 detection of outliers.
Finally we will also exhibit a simple and perhaps surprising connexion with
optimization and sumsofsquares.
 Victor Magron (LAASCNRS, Toulouse)
Title: Trace polynomial optimization with applications in quantum information
Slides.
Abstract:
Motivated by recent progress in quantum information theory, this talk
aims at presenting how to optimize over trace polynomials, i.e.,
polynomials in noncommuting variables and traces of their products.
A novel Positivstellensatz certifying positivity of trace polynomials
subject to trace constraints is presented, and a hierarchy of
semidefinite relaxations converging monotonically to the optimum of a
trace polynomial subject to tracial constraints is provided.
This hierarchy is applied to bound violations of polynomial Bell
inequalities as well as to detect entanglement in multipartite Werner
states. This is joint work with Felix Huber, Igor Klep and Jurij Volcic.
 Fernando de Oliveira Filho (TU Delft)
Title: A 3point bound for distanceavoiding sets on the sphere
Slides.
Abstract:
Witsenhausen's problem asks: what is the maximum measure of a subset of
the (n1)dimensional unit sphere having no orthogonal points? Only
lower and upper bounds for this maximum measure are known for n >= 3.
The best known upper bound is given by Kalai's doublecap conjecture,
which states that the maximum is achieved by two open antipodal
45degreeradius spherical caps.
An upper bound for the maximum measure can be obtained from a suitable
extension of the Lovász theta number. I will discuss a 3point bound
for this problem, based on copositive programming, which improves on the
best known upper bounds.
Joint work with Bram Bekker, Olga Kuryatnikova, and Juan Vera.
 Ojas Parekh (Center for Computing Research, Sandia National Laboratories)
Title: Approximating quantum constraint satisfaction problems via noncommutative SDP hierarchies (II)
Slides.
Abstract:
The local Hamiltonian (LH) problem serves as a natural quantum generalization of classical constraint satisfaction problems (CSP). We leverage this connection to generalize classical approximation algorithms for CSP, based on semidefinite programming hierarchies, to the quantum LH case. We employ the recently introduced Quantum Max Cut (QMC) problem as a model QMAhard 2LH instance to illustrate our approach, in the same vein that Max Cut is a model 2CSP that has driven development of classical approximation and hardness results for CSPs. We will discuss many recent results on approximation and hardness for QMC and more general instances of 2LH. Although approximating 2LH bears similarity to approximating 2CSP, the former does take some unexpected turns.
 Franz Rendl (Klagenfurt University)
Title: StableSet and Coloring bounds based on kones 01 quadratic
optimization
Slides.
Abstract:
The Lovász Theta function provides a well studied
tool to get bounds for the stability number and the
chromatic number of graphs.
It is the optimal value of a semidefinite program
in matrices of order n having m equality constraints
plus possibly some additional sign constraints.
Here n denotes the number of vertices and m the number
of edges of the underlying graph.
The number m of equations may be of order quadratic in n
which limits the practical use of the Theta function.
We introduce a new way to obtain bounds which is derived
from a quadratic 01 optimization problem having exactly
k variables equal to 1. This allows us to move the m
equality constraints into the objective function, leaving
a semidefinite program with only 2n equality constraints
independent of the number m of edges.
Surprisingly, this relaxation is closely related to
Schrijver's refinement of the Theta function for the
stability number, and to Szegedy's strengthening of the
Theta function in the coloring case.
We propose a further tightening of this bound using
the exact subgraph idea in a new way. Rather than
looking at subgraphs with a small number of vertices
which should be contained in the respective polytope,
we now consider subgraphs where
the stability number is small (but could have a large
number of vertices) and require them to be contained
in the corresponding polytope. Computational results
on a series of graphs from the literature show the
strong potential of this approach.
 Renata Sotirov (Tilburg University)
Title: The ChvátalGomory Procedure for Integer Semidefinite Programs
Slides.
Abstract:
The ChvátalGomory (CG) cuttingplane procedure is considered to be among the most celebrated results in integer programming. We extend the ChvátalGomory (CG) cuttingplane procedure to integer semidefinite programs (ISDPs). We present an explicit formulation of the elementary closure of spectrahedra that relies on the data matrices of the ISDP. This formulation enables us to introduce ChvátalGomory cuts and strengthened ChvátalGomory cuts for ISDPs. We also show how to derive a polyhedral description of the elementary closure for a specific class of spectrahedra based on the SDP equivalent of total dual integrality.
In the second part of the talk, we show how to exploit (strengthened) CG cuts in a branchandcut framework for ISDPs.
Different from existing algorithms for solving ISDPs, the separation routine in our approach exploits both the semidefinite and the integrality constraints. We derive separation routines for common classes of binary SDPs resulting from combinatorial optimization problems. We also demonstrate the practical strength of the CG cuts in a branchandcut algorithm, which outperforms alternative ISDP solvers.
This is joint work with F. de Meijer
 Jordi Tura Brugués (Leiden University)
Title: Bounding the set of classical correlations of a manybody system
Slides.
Abstract:
I will present a method to certify the presence of Bell
correlations in experimentally observed statistics, and to obtain new
Bell inequalities. Our approach is based on relaxing the conditions
defining the set of correlations obeying a local hidden variable model,
yielding a convergent hierarchy of semidefinite programs (SdP's).
Because the size of these SdP's is independent of the number of parties
involved, this technique allows us to efficiently characterize
correlations in manybody systems. As an example, we illustrate our
method with the experimental data presented in [Science 352, 441
(2016)]. I will discuss extensions of this method to derive inequalities
with many outcomes, higherorder correlators, etc. and the pathological
cases that can arise, where the approximation of the set of local
correlations via the convex hull of a semialgebraic set can pose
additional challenges.
 Frank Vallentin (Universität zu Köln)
Title: A semidefinite program for least distortion embeddings of flat tori into Hilbert spaces
Slides.
Abstract:
Least distortion embeddings of flat tori into Hilbert space were first studied by Khot and Naor in 2006. A flat torus is the metric space given by the quotient $R^n / L$ with some $n$dimensional lattice $L$. Khot and Naor showed that these kind of metric spaces can be highly nonEuclidean in the sense that all embeddings of the flat torus into some Hilbert space have distortion at least $\Omega(\sqrt{n})$.
Haviv, Regev (2010) and Agarwal, Regev, Tang (2020) extended these results and constructed excellent embeddings of flat tori having low distortion. One motivation is that studying the Euclidean distortion of flat tori might have applications to the complexity of lattice problems, like the closest vector problem, and might also lead to more efficient algorithms for lattice problems through the use of our metric embeddings.
In this talk I want to add a semidefinite optimization perspective to this story. For finite metric spaces it is known that one can compute least distortion Euclidean embeddings via an SDP. I want to extend this result from finite metric spaces to flat tori. This will yield, via SDP duality, an algorithmic method for proving nonembeddability results. In particular, this leads to new, simple proofs of (strengthenings of) previous results as well as the possibility to find optimal embeddings of given flat tori.
Based on joint work with A. Heimendahl, M. Lücke, M.C. Zimmermann.
 Alex Wang (CWI)
Title: Accelerated firstorder methods for a class of semidefinite programs
Slides.
Abstract:
In this lecture, we will discuss a new storageoptimal firstorder method for solving a special class of semidefinite programs (SDPs) to high accuracy. The class of SDPs that we consider, the "exact QMPlike SDPs" is characterized by lowrank solutions, a priori knowledge of the restriction of the SDP solution to a small subspace, and standard regularity assumptions such as strict complementarity. Crucially, we show how to use a "certificate of strict complementarity" to construct a lowdimensional strongly convex minimax problem whose optimizer coincides with a factorization of the SDP optimizer. From an algorithmic standpoint, we show how to construct the necessary certificate and how to solve the minimax problem efficiently.
 Jeroen Zuiddam (University of Amsterdam)
Title: Shannon Capacity via Real Algebraic Geometry and Strassen's Positivstellensatz
Slides.
Abstract:
Posed by Shannon in 1956, understanding the amount of information that can be transmitted perfectly over a noisy communication channel (the Shannon capacity of graphs) is a longstanding and central open problem in information theory, graph theory and combinatorial optimization. This problem is part of the broader theme of directsum problems, which ask: What is the cost of a task if we have to perform it many times? We will discuss an approach to the study of Shannon capacity (and other directsum problems) via real algebraic geometry, and in particular a Positivstellensatz of Strassen that provides a dual description (called asymptotic spectrum duality) of the Shannon capacity. This realizes a framework that unifies known computational methods and structural theorems, and provides new directions in the study of Shannon capacity (including a new notion of graph limits).
The program will also feature the following lectures by young researchers:
 Felix Kirschner (Tilburg University)
Title: Iterative approximation schemes for semidefinite programs using the factor width cone
Slides.
Abstract: In this lecture we will discuss an iterative approximation scheme for semidefinite programs due to Ahmadi, Majumdar and Hall. The method is based on solving a sequence of optimization problems over cones that are more tractable than the SDP cone. We will be particularly interested in the cone of matrices of factorwidth k. A globally convergent algorithm due to Sznaier and RoigSolvas is presented.
 Roel Lambers (TU Eindhoven)
Title: Orthogonal schedules
Slides.
Abstract:
Scheduling big sports competitions is a major logistic challenge. It is a popular approach to first fix for each team when it plays Home and Away, and then decide upon the exact schedule, i.e. who plays who in which round. Of course, the decisions made in the first phase limits the options of the second phase. We look at Home/AwayPatterns (HAP) for round robin tournaments on 2n teams ż represented as 2n x (2n1) binary matrices  and their compatible schedules; two compatible schedules are orthogonal if no match is planned in the same round in both schedules. We are interested in the HAPs that give rise to orthogonal schedules, and how many different orthogonal schedules can be found on these HAPs. This depends on the values of n, and as it turns out, a unique HAP exists if n=2^k, for which there are n orthogonal schedules.
 Nando Leijenhorst (TU Delft)
Title: Bounding quantities related to zeros of the Riemann zeta function using nlevel correlations
Slides.
Abstract: It is conjectured that all nontrivial zeros of the Riemann zeta function are simple. Assuming the Riemann hypothesis, we give bounds on the percentage of zeros with certain multiplicities to support this. In this talk, I will explain how we optimize these bounds and how this connects to semidefinite programming.
Joint work with F. Goncalves and D. de Laat.
 Sven Polak (CWI)
Title: New lower bounds on crossing numbers of the complete bipartite graph
Slides.
Abstract:
Computing the crossing number of the complete bipartite graph K_{m,n} is a longstanding open problem, going back to Turán in the 1940s. In this talk, we explain how to use semidefinite programming and representation theory to compute new lower bounds on the crossing number of K_{m,n}, extending a method from de Klerk et al. and the subsequent reduction by de Klerk, Pasechnik and Schrijver.
We exploit the full symmetry of the problem by developing a blockdiagonalization of the underlying matrix algebra and use it to improve bounds on the crossing number of K_{m,n} for all m,n at least 10, using a novel decomposition technique. Some of our bounds are computed using a new and wellperforming relaxation of the original semidefinite programming bound, by only requiring one small matrix block to be positive semidefinite.
This is based on joint work with Daniel Brosch (Tilburg University).
 Lennart Sinjorgo (Tilburg University)
Title: On the generalized thetanumber and related problems for highly symmetric graphs
Slides
Abstract: Determining the chromatic number and independence number of a graph are two widely studied, NPhard problems in graph theory. The Lovász theta number, denoted theta(G), is a bound on both of these quantities, and can be computed by solving an semidefinite programming problem (in polynomial time). We study a generalization of the Lovász theta number, induced by an additional integer parameter k, denoted theta_k(G). The generalized Lovász theta number also serves as a bound for the generalized chromatic and independence number of the graph.
We study the parameter theta_k(G) as a function of k, compute it for multiple graph families, and show that it
inherits many elegant properties of the theta parameter. Furthermore, we provide a new NordhausGaddum type inequality on the generalized chromatic number.
This presentation is based on joint work with Renata Sotirov.
 Andries Steenkamp (CWI)
Title: Polynomial optimization bounds for the (sparse) completely positive rank
Slides.
Abstract:
We apply polynomial optimization techniques to lower bound the completely positive rank (CPrank) of a matrix. The CPrank of an n x n matrix A, denoted by cprank(A), is the smallest integer r such that A=BB^T for some n x r nonnegative matrix B.
Matrices with a finite CPrank are called completely positive (CP) and have exciting links to optimization.
Our approach relies on the moment method and yields a hierarchy of semidefinitebased lower bounds that converges to a natural convexification of the combinatorial parameter cprank(A) and lower bounds it. A distinguishing feature is exploiting the
positivity constraint to impose positivity of a polynomial matrix localizing map, the dual notion of the notion of sumofsquares polynomial matrices.
We also show how sparsity can leverage quicker and stronger bounds.
The lecture is based on joint works with S. Gribling, M. Korda, M. Laurent, and V. Magron.
 Luis Felipe Vargas (CWI)
Title: A new result on sumofsquares certificates for copositive matrices
Slides.
Abstract:
A symmetric matrix M is copositive if the form x^TMx is nonnegative on the nonnegative orthant. We denote by COP_n the set of copositive matrices of size n. Optimizing over COP_n is hard as it encodes many hard combinatorial problems such as the Stable Set Problem. Determining whether a matrix is copositive is a coNPcomplete problem. These hardness results motivate investigating certificates that make evident that a matrix is copositive. We say that a copositive matrix M is SOScertifiable if the polynomial (x^2)^TMx^2 (\sum_{i=1}^n x_i^2)^r is a sum of squares for some r. This certificate is based on a work by Parrilo (2000) who defined conic approximations for COP_n based on this certificate. In this talk we show that every copositive matrix of size 5 is SOScertifiable. Moreover, we show examples of copositive matrices that are not SOScertifiable for size n \ge 6. In addition, we show a family of copositive matrices indexed by graphs that are SOScertifiable, partially solving a conjecture proposed by de Klerk and Pasechnik (2002).
This is based in joint works with Monique Laurent and Markus Schweighofer.
Program
The workshop is planned to start on Monday 29 August (first lecture at 9h30) and end on Friday 2 September (around 12h30).
Please see below for details about the program or download this file.
Coffee will be available from 9h00!
Registration
Participation is free, but registration is mandatory since the workshop has a limited capacity. Registration is now closed as the workshop is fully booked. Please contact the organizers in case you like to join.
Location
Amsterdam Science Park Congress Center, Euler Room.
Location next to the entrance of CWI.
Science Park 125, 1098 XG Amsterdam
CWI, Science Park 123, 1098 XG Amsterdam.
Accomodation
Interested participants may make a hotel reservation at Hotel Casa. It may be possible to benefit from
a corporate rate of 110 Eur (incl. breakfast, excl. city tax); for this book using this link and the promotion code CWI2022.
Hotel Casa (Eerste Ringdijkstraat 4, Amsterdam) is conveniently located near Amstel train station and from there you can walk, cycle or take the bus to CWI.
Organizers
Jop Briët (CWI), Monique Laurent (CWI, Tilburg University)
If you have any questions please contact us.
