Brainstorming days on measure and polynomial optimization


Tuesday 30 November 2021, 10h Zheng Qu

Title: On the exactness of Lasserre's relaxation for polynomial optimization with equality constraints
slides
Abstract: We study exactness condition for Lasserre's relaxation for polynomial optimization with n polynomial equality constraints, where n is the number of variables. Under the assumption that the quotient ring has dimension equal to the product of the degrees of the polynomials defining the feasible set, we show that Lasserre's relaxation is exact for degree larger than or equal to d, where d is the sum of the degrees of the defining polynomials minus the number of variables n. For relaxation of order smaller than d, we describe the exact region as the convex hull of the moment map image of a linear subspace. The convex hull lies in a tubular neighborhood of the moment map image with respect to the relative entropy distance for some universal constant. For relaxation of order equal to d-1, the convex hull coincides with the moment map image of the complexification of a hyperplane, and is diffeomorphic to its amoeba. Based on results from the theory of amoeba, we obtain an explicit description of the exact region for degree d-1 relaxation and its geometric properties, from which we further derive estimation of the degree (d-1)-relaxation error. As an application of our general theory we obtain various results about the exact region of the binary problem.

Tuesday 30 November 2021, 11h Lucas Slot

Title: Sum-of-squares hierarchies for polynomial optimization and the Christoffel-Darboux kernel
slides
Abstract: We consider Lasserre's approximation hierarchies for the problem of minimizing a polynomial f over a compact semialgebraic set X in R^n. When X is the unit ball or the standard simplex, we show that the hierarchies based on Schmüdgen-type positivity certificates of degree r converge to the global minimum of f at a rate in O(1/r^2), matching recently obtained convergence rates for the hypersphere and hypercube [−1,1]^n. For our proof, we establish a connection between Lasserre's hierarchies and the Christoffel-Darboux kernel, and make use of closed form expressions for this kernel derived by Xu.

Monday 22 November 2021, 15h Mauricio Velasco

Title: Harmonic hierarchies for polynomial optimization
slides
Abstract: The cone of nonnegative forms of a given degree is a convex set of remarkable beauty and usefulness. In this talk we will discuss some recent ideas for approximating this set through polyhedra and spectrahedra. We call the resulting approximations harmonic hierarchies since they arise naturally from harmonic analysis on spheres (or equivalently from the representation theory of SO(n)). We will describe theoretical results leading to sharp estimates for the quality of these approximations and will also show a brief demo of our Julia implementation of harmonic hierarchies. These results are joint work with Sergio Cristancho (UniAndes).

Tuesday 9 November 2021, 14h Matias Bender

Title: Polynomial systems, sparsity, and applications
slides
Abstract: Polynomial systems are ubiquitous in computational mathematics and have several applications in science and engineering. In this talk, I will present some linear-algebra-based strategies to compute with them. First, I will focus on solving, symbolically and numerically, structured systems such as sparse and multi-homogeneous. For that, I will merge classical tools, like Gröbner bases and resultants, with Toric geometry. Later, I will present some applications of these techniques in different domains such as differential equations and topological data analysis, among others.

Monday 8 November 2021, 10h Tong Chen

Title: Effective certification of monotone deep equilibrium models
slides
Abstract: A presentation of the paper https://arxiv.org/pdf/2110.08260.pdf, about certification of monotone deep equilibrium models by using zonotopes.

Monday 18 October 2021, 15h Philipp di Dio

Title: Time-dependent moments from the heat equation
slides
Abstract: We present a new connection between the classical theory of moments and the theory of partial differential equations (arXiv:2108.03505). For the classical heat equation we compute the moments of the unique solution. These moments are polynomials in the time variable, of degree comparable to the degree of the moment, and with coefficients satisfying a recursive relation. This allows us to define the polynomials for any sequence. In the case of moment sequences, the polynomials trace a curve (the heat curve) which remains in the moment cone for positive time, but may wander outside for negative times. We also study how the determinacy of a moment sequence behaves along the heat curve. We show that for several other partial differential equations we have access to the time-dependent moments without calculating the solution of the partial differential equation.

Monday 11 October 2021, 16h Julia Lindberg

Title: Polynomial system solving in applications
slides
Abstract: Polynomial systems arise naturally in many applications in engineering and the sciences. This talk will outline classes of homotopy continuation algorithms used to solve them. I will then describe ways in which structures such as irreducibility, symmetry and sparsity can be used to improve computational speed. The efficacy of these algorithms will be demonstrated on systems in power systems engineering, statistics and optimization.

Monday 4 October 2021, 16h Mareike Dressler

Title: Signomial Moment Theory and Upper Bounds for Signomial Optimization
slides
Abstract: Signomials are obtained by generalizing polynomials to allow for arbitrary real exponents. This generalization offers great expressive power, but has historically sacrificed the organizing principle of "degree" that is central to polynomial optimization theory. In this talk, I introduce the concept of signomial rings that allows to reclaim that principle. Then I provide a language for and basic results in signomial moment theory that are analogous to those in the rich moment-SOS literature for polynomial optimization. That theory is used to turn (hierarchical) inner-approximations of signomial nonnegativity cones into (hierarchical) outer-approximations of the same. Finally, I explain how any such construction leads to highly structured convex programs which produce bounds that approach the minimum of a signomial from above. This is joint work with Riley Murray.

Monday 4 October 2021, 17h Riley Murray

Title: Theoretical and practical applications of signomial rings to polynomial optimization
slides
Abstract: Signomials generalize polynomials by allowing arbitrary real exponents, at the expense of restricting the resulting function to the positive orthant. This talk concerns a recently proven signomial Positivstellensatz based on "sums of arithmetic-geometric exponentials" (SAGE). The Positivstellensatz applies to compact sets which need not be convex or even basic semi-algebraic. In the first part of the talk, I explain how this result is derived through the newly-defined concept of signomial rings. Then I explain how the same concept leads to a new convex relaxation hierarchy for signomial optimization. These relaxations (which are based on relative entropy programming) can be solved more reliably than those arising from earlier SAGE-based Positivstellensatz. Moreover, this increase in reliability comes at no apparent cost of longer solver runtimes or worse bounds. Numerical examples are provided to illustrate the performance of the hierarchy on problems in chemical engineering and reaction networks. (Joint work with Mareike Dressler.)

Monday 20 September 2021, 15h Andreas Bluhm

Title: Free spectrahedra and quantum information theory
slides
Abstract: In this talk, I will explain how some problems in quantum information theory can be rephrased as inclusion problems of certain free spectrahedra. Free spectrahedra typically arise as matricial relaxations of linear matrix inequalities. A well-known example is the matrix cube. On the quantum side, I will focus on measurement incompatibility: Two quantum measurements are compatible if there exists a third one which implements both measurements at the same time. The best known example of incompatible measurements are the position and the momentum of a particle. Using the connection to free spectrahedra, we can show that inclusion constants correspond to the robustness of measurement incompatibility to white noise.

Monday 28 June 2021, 15h Jared Miller

Title: Bounding distances to unsafe sets
slides
Abstract: We propose an algorithm to bound the minimum distance between points on trajectories of a dynamical system and points on an unsafe set. Prior work on certifying safety of trajectories includes barrier and density methods, which do not provide a margin of proximity to the unsafe set in terms of distance. The distance problem is relaxed to a Monge-Kantorovich type optimal transport problem based on existing occupation-measure methods of peak estimation. Specialized programs may be developed for polyhedral norm distances (e.g. L1 and Linfinity) and for scenarios where a shape is traveling along trajectories (e.g. rigid body motion).

Monday 28 June 2021, 16h Edgar Fuentes Figueroa

Title: Polynomial Optimization Techniques for Energy Network Operation and Design
slides
Abstract: Global solution of the Optimal Power Flow (OPF) problem remains an active research topic. In particular, convex relaxations of the OPF problem based on semidefinite programming have been shown to deliver tight lower bounds and are an important tool for proving global optimality. In this category, Lasserre's hierarchy of moment relaxations has been useful to globally solve challenging instances. According to experiments, the second- and third-order moment relaxations are exact for many practical cases. However, realistic networks contain thousands of variables and exploiting the sparsity of the network becomes crucial for solving large-scale instances. Even for moderate-size instances, implementing a full second-order moment relaxation could become intractable. In this talk, we focus on introducing the OPF problem remarking the term sparsity structure of the quadratic constraints of the problem. To continue, we discuss some ideas found in the literature that allow to apply moment-like relaxations to OPF instances with up to 4000 variables.

Monday 14 June 2021, 15h Nicolas Augier

Title: On the ensemble controllability of quantum systems
slides
Abstract: The principal issue that will be developed in this talk is how to control a parameter-dependent family of quantum systems with a common control input, namely, the ensemble controllability problem. Thanks to the study of one-parameter families of Hamiltonians driven by two real controls and their generic spectrum singularities, we will give an explicit adiabatic control strategy when geometric conditions on the spectrum of the Hamiltonian are satisfied, i.e. when the Hamiltonian admits conical or semi-conical intersections of eigenvalues. Then, in order to understand which ensemble controllability properties can be extended to the case where the system is driven by a single real input, we will study the compatibility of the adiabatic with the rotating wave approximations.

Monday 14 June 2021, 16h Pierre-Emmanuel Emeriau

Title: Witnessing Wigner Negativity
slides
Abstract: Quantum Information describes the behavior of information when encoded in degrees of freedoms of particles governed by the laws of quantum physics. It is important to study and better understand non-classical features allowed by the quantum theory. Negativity of the Wigner function is arguably one of the most striking non-classical features of quantum states. Beyond its fundamental relevance, it is also a necessary resource for quantum speedup with continuous variables. As quantum technologies emerge, the need to identify and characterize the resources which provide an advantage over existing classical technologies becomes more pressing. Yet it is quite challenging to detect Wigner negativity experimentally. Here we derive witnesses for Wigner negativity of single mode and multimode quantum states, based on fidelities with Fock states, which can be reliably measured and efficiently estimated using standard detection setups. These witnesses possess a threshold expectation value indicating whether the measured state has a negative Wigner function. Moreover, the amount of violation provides an operational quantification of Wigner negativity. We phrase the problem of finding the threshold values for our witnesses as an infinite-dimensional linear optimisation. By relaxing and restricting the corresponding linear programs, we derive two hierarchies of semidefinite programs, which provide numerical sequences of increasingly tighter upper and lower bounds for the threshold values. We further show that both sequences converge to the threshold value. Moreover, our witnesses form a complete family - each Wigner negative state is detected by at least one witness - thus providing a reliable method for experimentally witnessing Wigner negativity of quantum states from few measurements. From a foundational perspective, our findings provide insights on the set of positive Wigner functions which still lacks a proper characterisation.

Monday 31 May 2021, 15h Victor Magron

Title: Optimizing over trace polynomials
slides
Abstract: Motivated by recent progress in quantum information theory, this article aims at optimizing 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 can be seen as a tracial analog of the Pironio, Navascués and Acín scheme [New J. Phys., 2008] for optimization of noncommutative polynomials. The results obtained are applied to violations of polynomial Bell inequalities in quantum information theory.

Monday 17 May 2021, 15h Corbinian Schlosser

Title: An explicit proof of Vinter's theorem
slides
Abstract: We provide a more elementary proof of Vinter's Theorem which states that optimal control problems with additional convexity properties can be reformulated as linear programs on the space of continuously differentiable functions. The constraints in this linear program are of Hamilton-Jacobi-Bellman (HJB) PDE type and the linear program gives the correct solution even if the optimal cost function is not smooth. We show that the optimal cost function can be approximated by a sequence of smooth functions, arising from relaxed optimal control problems (OCP), such that the HJB inequality that appears in Vinter's Theorem satisfied. Those relaxed OCPs treat the state constraints by penalty functions. This has the advantage that Lipschitz regularity of the optimal cost can be guaranteed and it overcomes the need to take the state constraints into account explicitly.

Monday 3 May 2021, 15h Jared Miller

Title: Analysis and Control of Time-Delay Systems with Occupation Measures
slides
Abstract: The evolution of time delay systems (delay differential equations) depends on present and past values of the state. This dependence on state histories can lead to instabilities, bifurcations, and nonintuitive behaviors which are not found in analogous ODE systems. Some instances of time delay systems with their associated delays include epidemic models (incubation period), population dynamics (gestation time), and fluid modeling (transport time of fluid moving in a pipe). This work presents an occupation measure framework to develop weak solutions over a finite time interval of nonlinear time-delay systems with a finite number of bounded discrete delays. A Liouville equation is formulated with respect to a joint occupation measure supported in delay coordinates. Data consistency in delayed coordinates is enforced by constraining marginals of the joint occupation measure with respect to shifted copies of component measures. Applications of this weak solution include optimal control (including dead-time), peak estimation, and reachable set estimation of time delay systems. This is joint work in collaboration with Milan Korda, Victor Magron, Alexandre Seuret and Mario Sznaier.

Tuesday 6 April 2021, 15h Felix Kirschner

Title: Convergence rates of RLT and Lasserre-type hierarchies of the generalized moment problem on the simplex and the sphere
slides
Abstract: The talk is based on the following joint work with Etienne de Klerk arXiv:2103.02924. We consider the generalized moment problem (GMP) over the simplex and the sphere. This is a rich setting and it contains NP-hard problems as special cases, like constructing optimal cubature schemes and rational optimization. Using the Reformulation-Linearization Technique (RLT) and Lasserre-type hierarchies, relaxations of the problem are introduced and analyzed. For our analysis we assume throughout the existence of a dual optimal solution as well as strong duality. For the GMP over the simplex we prove a convergence rate of O(1/r) for a linear programming, RLT-type hierarchy, where r is the level of the hierarchy, using a quantitative version of Polya's Positivstellensatz. As an extension of a recent result by Fang and Fawzi arXiv:1908.05155 we prove the Lasserre hierarchy of the GMP over the sphere has a convergence rate of O(1/r^2).

Monday 29 March 2021, 15h Mateusz Skomra

Title: A machine learning framework for solving high-dimensional mean field games
slides
Abstract: I will present a paper by Ruthotto, Osher, Li, Nurbekyan, and Fung, published in PNAS 2020 117 (17), about solving high-dimensional mean field games (MFG) using an approach based on machine learning. The results of the paper apply to potential MFGs, which can be formulated as infinite-dimensional optimal control problems. In order to solve these problems numerically, the authors propose a framework that consists of two steps. First, they show how to solve the continuity equation using the computation of characteristic curves. This reduces MFG to an unconstrained optimization problem that involves only the potential function. Second, they parametrize the potential using a neural network and transform MFG into a machine learning problem. In particular, this method does not use spatial discretization and is capable of solving problems in high dimensions. In the talk, I will introduce the notion of mean field games, present the framework from the paper, and discuss its applications to optimal transport and crowd motion problems.

Monday 22 March 2021, 15h Enrico Facca

Title: The Dynamical Monge-Kantorovich model. An Optimal Transport Problem tool for applied sciences
slides
Abstract: In this talk we present the Dynamical Monge-Kantorovich (DMK) model, a recent reformulation of the Optimal Transport Problem (OTP). This research field deals with the problem of finding the best strategy of moving resources from one place to another. The DMK model has been successfully applied in the numerical solution of the OTP on 2d, 3d, and surface domains. More recently, the model was applied also on graphs, where the combination of implicit time-stepping scheme with the Newton method resulted in an efficient numerical scheme able to tackle large scale OTP. In this presentation, we give an overview of the OTP and DMK models, with a particular focus on application of OT tools to applied problems.

Monday 8 March 2021, 15h Rodolfo Rios-Zertuche

Title: Long term dynamics of small step algorithms
slides
Abstract: We introduce "closed measures," a statistical method that is helpful in connecting the discrete and the continuous dynamics and revealing the quasi-periodicity of a range of algorithms that share the property that the distance between successive iterations vanishes asymptotically. The area of application includes many of the optimization algorithms used today for training large-scale neural networks, such as the small-step (stochastic) subgradient method, the heavyball algorithm, and Lyapunov function methods, and extends also to subdifferential inclusions and games.

Tuesday 16 February 2021, 15h Ulysse Marteau Ferret

Title: Finding Global Minima via Kernel Approximations
slides
Abstract: We consider the global minimization of smooth functions based solely on function evaluations. Algorithms that achieve the optimal number of function evaluations for a given precision level typically rely on explicitly constructing an approximation of the function which is then minimized with algorithms that have exponential running-time complexity. In this paper, we consider an approach that jointly models the function to approximate and finds a global minimum. This is done by using infinite sums of square smooth functions and has strong links with polynomial sum-of-squares hierarchies. Leveraging recent representation properties of reproducing kernel Hilbert spaces, the infinite-dimensional optimization problem can be solved by subsampling in time polynomial in the number of function evaluations, and with theoretical guarantees on the obtained minimum. The rate is nearly optimal in the case of Sobolev functions and more generally makes the proposed method particularly suitable for functions that have a large number of derivatives. Indeed, when m is in the order of d, the convergence rate to the global optimum does not suffer from the curse of dimensionality, which affects only the worst-case constants (that we track explicitly through the paper).

Tuesday 2 February 2021, 15h Didier Henrion

Title: Moment-SOS hierarchy and exit time of stochastic processes
slides
Abstract: The moment sum of squares (moment-SOS) hierarchy produces sequences of upper and lower bounds on functionals of the exit time solution of a polynomial stochastic differential equation with polynomial constraints, at the price of solving semidefiniteoptimization problems of increasing size. In this talk we use standard results from elliptic partial differential equation analysis to prove convergence of the bounds produced by the hierarchy. We also use elementary convex analysis to describe a super-and sub-solution interpretation dual to a linear formulation on occupation measures. The practical relevance of the hierarchy is illustrated with numerical examples.

Tuesday 19 January 2021, 15h Corbinian Schlosser

Title: Theoretical Foundations for Higher Order Dynamic Mode Decompositions
slides
Abstract: I will talk about Liouville and Koopman operators, as well as reproducing kernel Hilbert spaces for dynamical systems, based on articles by J. Rosenfeld et al: arXiv:1909.11792, arXiv:1910.03977 and arXiv:2101.02646.



First Brainstorming day on measure and polynomial optimization


Friday 11 September 2020, 10h-12h 14h-16h, Salle du Conseil LAAS-CNRS

10h-10h10 Intro

10h10-10h40 Tong Chen

Title: Polynomial optimization for estimating the Lipschitz constant of neural networks
slides
Abstract: The Lipschitz constant of neural networks is useful for several applications in deep learning, such as robustness certification. We first show the semi-algebraic description of the well-known ReLU function and its generalized derivative. Then we introduce a heuristic SDP relaxation to give an upper bound of the Lipschitz constant of multi-layer fully-connected neural networks. This approach can also be applied to give upper bounds of general nearly-dense POPs.

10h40-11h20 Hoang Ngoc Anh Mai

Title: A hierarchy of spectral relaxations for polynomial optimization
slides
Abstract: We show that (i) any constrained polynomial optimization problem (POP) has an equivalent formulation on a variety contained in an Euclidean sphere and (ii) the resulting semidefinite relaxations in the moment-SOS hierarchy have the constant trace property (CTP) for the involved matrices. We then exploit the CTP to avoid solving the semidefinite relaxations via interior-point methods and rather use ad-hoc spectral methods that minimize the largest eigenvalue of a matrix pencil. Efficiency and robustness of this spectral hierarchy is tested against on a sample of randomly generated quadratically constrained quadratic problems.

11h20-11h50 Corbinian Schlosser

Title: Sparse moment-sum-of-squares relaxations for nonlinear dynamical systems with guaranteed convergence
slides
Abstract: This talk will present sparse moment-sum-of-squares relaxations for various problems from nonlinear dynamical systems including maximum positively invariant set, region of attaction or global attractor. We show that these problems admit a sparse relaxation with guaranteed convergence such that the number of variables in the largest sum-of-squares multiplier is given by the longest weighted path of the vector field's sparsity graph. This allows for a significant reduction of the size of the SDP relaxations, thereby allowing to address far larger systems without compromising convergence guarantees. Numerical examples demonstrate the approach.

11h50-14h Lunch break

14h-14h30 Matteo Tacchi

Title: Approximating the region of attraction of a sparse dynamical system
slides
Abstract: Moment-SOS hierarchies are a powerful tool to analyse the stability of nonlinear differential systems by reducing complex problems into semidefinite programs. However, this method is very sensitive to dimensionality and becomes quickly intractable when addressing real life systems. A general solution to use Moment-SOS hierarchies in high dimension consists of exploiting the structure of the problem, e.g. sparsity in its description, as already done for optimization and volume computation. This talk intends to make a first step in the direction of sparse approximation of regions of attraction, with a first encouraging published result and a variety of open questions.

14h30-15h Jie Wang

Title: Exploiting term sparsity in large-scale polynomial optimization
slides
Abstract: Over the past twenty years, the moment-SOS hierarchy has become a powerful tool to tackle polynomial optimization. For large-scale problems, the cost and constraints typically involve only a few amount of terms. It is known that one can exploit correlative sparsity for moment-SOS hierarchies. However, this only takes into account correlations between variables and hence plenty of information hidden in the term level is lost. We show how to exploit the few correlations between terms and propose a novel term sparsity adapted moment-SOS hierarchy. In addition, correlative and term sparsity can be exploited simultaneously. By virtue of these results, we are able to solve polynomial optimization problems, e.g., AC-OPF or noncommutative eigenvalue/trace problems, involving up to several thousand of variables and constraints.

15h-16h Further discussion