Sujets de recherche - POP

Dynamical systems with algebraic data

Originally designed to address static polynomial optimization problems, the Moment-SOS hierarchies have been extended to optimal control problems whose description (vector field, and state/control constraints) is done through polynomials (and even semi-algebraic functions).

We are now investigating similar extensions to stochastic polynomial optimal control and control of systems described by non-linear partial differential equations arXiv:1807.02306, arXiv:1804.07565

Christoffel-Darboux (CD) kernels

The CD-kernel is an old and well known tool in theory of approximation and orthogonal polynomials. It turns out that it can provide an efficient and easy to use tool to address some problems in data analysis (e.g., outlier detection, support inference, density approximation, etc.) where the measure of interest is discrete (its support is the cloud of data points to analyse). In addition it can also be used in other applications:

• Interpolate functions from a sample of its values;

• Recover a function from moments of the measure supported on its graph (which is typically the information obtained as output of the Moment-SOS hierarchy in dynamical systems).

Finally, the CD-kernel is also involved in an interpretation of the Moment-SOS Hierarchy in polynomial optimization arXiv:2011.08566 as well as in results on its rate of convergence arXiv:2001.11289.
 

Noncommutative polynomial optimization

There is a plethora of prior research in quantum information theory involving reformulating problems as optimization of noncommutative polynomials.
One famous application is to characterize the set of quantum correlations and to investigate entanglement.
Noncommutative analogs of the Lasserre's hierarchy have been introduced by experts from real algebraic geometry (Helton and McCullough) and from quantum physics (Navascues, Pirionio, Acin).
So far, prior research in quantum information theory focused intensively on reformulating problems as eigenvalue optimization of noncommutative polynomials.
Motivated by certain quantum information problems, including polynomial Bell inequalities and Werner witnesses, the team is also interested in deriving hierarchies to optimize over trace polynomials, i.e., polynomials in noncommuting variables and traces of their products, as well as noncommutative analogs of Christoffel-Darboux kernels.

Koopman operators, data-driven control

In this research direction we develop the Koopman operator framework for control of complex nonlinear dynamical systems. In this framework, a nonlinear dynamical system is equivalently represented by an infinite-dimensional linear operator whose spectrum provides information about the properties of the underlying system and whose finite-dimensional truncations allow one to use linear techniques to analyze the nonlinear system. The principal open problem that we tackle is the use of this framework for control within an optimization-based scheme such as model predictive control (MPC) while guaranteeing end-to-end convexity and fully data-driven design. First works on this topic inlcude arXiv:1611.03537 and arXiv:1810.08733. The second principal direction tackled is that of structure exploitation within the Koopman operator framework with the aim of improving the scalabiltiy and decreasing the data-requirements of the approach; the first work on this topic is arXiv:2112.10887.

Connections between tropical geometry and positivity certificates

In recent years, tools from tropical geometry have been used to study fundamental problems in linear and semidefinite programming. The team is investigating how tropical techniques can be used to provide new insights about other problems from polynomial optimization. Two examples of such problems are the tropicalization of the hyperbolic programming and of the Moment-SOS hierarchy. Another research direction consists in studying the connections between tropical geometry and alternative positivity certificates such as SONC/SAGE. The team is also interested in using tropical tools to develop new noncommutative analogues of the positivity certificates.

Structure exploitation

On the practical side, there is no free lunch and polynomial optimization methods usually encompass severe scalability issues.
The underlying reason is that for optimization problems involving polynomials in n variables of degree at most d, the size of the matrices involved in the Moment-SOS hierarchy of convex relaxations is proportional to n^d (at fixed d).
The team has invested a lot of recent efforts to tackle these issues.
Fortunately, for many applications, we can look at the problem in the eyes and exploit the inherent data structure arising from the cost and constraints describing the problem, in particular sparsity or symmetries:

• correlative sparsity, occurring when there are few correlations between the variables of the input polynomials;

• term sparsity, occurring when there are a small number of terms involved in the input polynomials by comparison with the fully dense case;

• invariance of all input polynomials under the action of a subgroup of the general linear group.

In all cases, the properties on the original optimization problem induce specific sparsity/symmetry structures on the matrices arising in the convex relaxations.
Such schemes have been used for important applications arising from various fields, including roundoff error bounds (computer arithmetic), robustness of deep networks (machine learning), entanglement (quantum information), AC optimal power-flow (energy networks), and sphere packing (discrete geometry).
The team is also willing to extend these frameworks in the context of noncommutative optimization, set approximation and analysis of dynamical systems.

Algebraic methods for validated optimization

An important challenge when considering the continuous increase of cyber-physical  systems complexity is to propose a corresponding increase in the capability of designing fault-free systems, maintaining the very high level of security and safety already achieved in existing systems with unaltered performances.
The team proposes several algorithmic solutions to various problems for optimization and control of such systems.
We are typically interested in proposing algorithms that are numerically robust and which rely on efficient, reliable and safe numerical methods.
In this context, the problem of validated computations and certification of the developed numerical algorithms constitutes a natural extension of the historical research themes of the team.
The goal of validated/rigorous computing is to benefit from the speed of numerical approximate computations, yet to be able to bound all rounding or method errors involved, see arXiv:1811.10062.
A complementary strategy is to develop exact optimization algorithms as in arXiv:1508.03715.

Application fields

1. Quantum systems: quantum games, e.g., number of mutually unbiased bases,  ground state energy of many body Hamiltonians, inflation for quantum correlations in networks, device independent quantum key distribution, entanglement witnesses for multi-partite Werner states, polynomial Bell inequalities, analysis/control of Hamiltonian systems;

2. Deep learning: robustness of neural networks, stability of dynamical systems controlled by neural networks, classification and explainability with Christoffel-Darboux kernels, training with optimal transport and optimal control;

3. Energy networks: alternative current-optimal power flow problems, stability of large-scale power systems, analysis/control of systems governed by nonlinear  delay/stochastic/partial differential equations.