Workshop on Semidefinite and Polynomial Optimization

CWI, Amsterdam

29 August - 2 September, 2022

Webpage under construction


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 (under construction) 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.

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

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: TBA

- Sevag Gharibian (Paderborn University)
Title: Approximating quantum constraint satisfaction problems via non-commutative SDP hierarchies (I)

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

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

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

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: TBA ]

- Jean-Bernard Lasserre (LAAS-CNRS, Toulouse)
Title: On the Christoffel function for data analysis and optimization

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

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

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)

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

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

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 Bregués (Leiden University)
Title: TBA

Abstract:

- Frank Vallentin (Universität zu Köln)
Title: A semidefinite program for least distortion embeddings of flat tori into Hilbert spaces

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 (Carnegie Mellon University, CWI)
Title: Accelerated first-order methods for a class of semidefinite programs

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

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).

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.

Registration

Participation is free, but registration is mandatory since the workshop has a limited capacity. Please register here.

Location

CWI, room TBA

CWI, Science Park 123, 1098 XG Amsterdam.

Accomodation

Interested participants may make a hotel reservation at Hotel Casa . 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.