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://cwi-nl.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 mixed-integer 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 non-convex) involving the quantum relative entropy function. I will discuss various tools to deal with such optimization problems. First, I will present a self-concordant barrier with optimal parameter for the quantum relative entropy cone. This barrier function can be used with interior-point schemes to solve convex optimization problems with the quantum relative entropy function. Second, I will consider non-convex 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 non-commutative SDP hierarchies (I)
Slides.
Abstract: SDPs are the go-to method for approximating NP-complete Boolean constraint satisfaction problems (CSPs). Quantumly, the generalization of CSPs is the fundamental k-local Hamiltonian problem, which asks: Given a many-body quantum system, what energy level does the system relax into when cooled to near absolute zero? In this work, we formally introduce the k-local Hamiltonian problem, and discuss various SDP approaches for giving non-trivial 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 (well-known) 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 sum-of-squares proofs for the (well-known) 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 list-colouring, 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 worst-case 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 convex-concave 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 ENW-GROOT 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 n-dimensional 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/(2r-1)), 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/(r-1). The Delsarte LP bound and k-point 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.

- Jean-Bernard Lasserre (LAAS-CNRS, Toulouse)
Title: On the Christoffel function for data analysis and optimization
Slides.
Abstract: In this talk we briefly describe the Christoffel-Darboux (CD) kernel and the Christoffel function (CF), well-known 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 sums-of-squares.

- Victor Magron (LAAS-CNRS, 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 3-point bound for distance-avoiding sets on the sphere
Slides.
Abstract: Witsenhausen's problem asks: what is the maximum measure of a subset of the (n-1)-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 double-cap conjecture, which states that the maximum is achieved by two open antipodal 45-degree-radius 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 3-point 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 non-commutative 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 QMA-hard 2-LH instance to illustrate our approach, in the same vein that Max Cut is a model 2-CSP 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 2-LH. Although approximating 2-LH bears similarity to approximating 2-CSP, the former does take some unexpected turns.

- Franz Rendl (Klagenfurt University)
Title: Stable-Set and Coloring bounds based on k-ones 0-1 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 0-1 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átal-Gomory Procedure for Integer Semidefinite Programs
Slides.
Abstract: The Chvátal-Gomory (CG) cutting-plane procedure is considered to be among the most celebrated results in integer programming. We extend the Chvátal-Gomory (CG) cutting-plane 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átal-Gomory cuts and strengthened Chvátal-Gomory 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 branch-and-cut 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 branch-and-cut 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 many-body 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 many-body 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, higher-order 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 non-Euclidean 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 first-order methods for a class of semidefinite programs
Slides.
Abstract: In this lecture, we will discuss a new storage-optimal first-order method for solving a special class of semidefinite programs (SDPs) to high accuracy. The class of SDPs that we consider, the "exact QMP-like SDPs" is characterized by low-rank 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 low-dimensional 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 direct-sum 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 direct-sum 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 factor-width k. A globally convergent algorithm due to Sznaier and Roig-Solvas 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/Away-Patterns (HAP) for round robin tournaments on 2n teams ¿ represented as 2n x (2n-1) 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 n-level correlations
Slides.
Abstract: It is conjectured that all non-trivial 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 long-standing 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 block-diagonalization 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 well-performing 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 theta-number and related problems for highly symmetric graphs
Slides
Abstract: Determining the chromatic number and independence number of a graph are two widely studied, NP-hard 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 Nordhaus-Gaddum 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 (CP-rank) of a matrix. The CP-rank of an n x n matrix A, denoted by cp-rank(A), is the smallest integer r such that A=BB^T for some n x r nonnegative matrix B. Matrices with a finite CP-rank are called completely positive (CP) and have exciting links to optimization. Our approach relies on the moment method and yields a hierarchy of semidefinite-based lower bounds that converges to a natural convexification of the combinatorial parameter cp-rank(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 sum-of-squares 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 sum-of-squares 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 co-NP-complete problem. These hardness results motivate investigating certificates that make evident that a matrix is copositive. We say that a copositive matrix M is SOS-certifiable 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 SOS-certifiable. Moreover, we show examples of copositive matrices that are not SOS-certifiable for size n \ge 6. In addition, we show a family of copositive matrices indexed by graphs that are SOS-certifiable, 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.