7 January 2021 in SIAM Journal on Optimization
This paper is concerned with polynomial optimization problems. We show how to exploit term (or monomial) sparsity of the input polynomials to obtain a new converging hierarchy of semidefinite progr...
12 January 2021 in SIAM Journal on Optimization
This work is a follow-up and a complement to [J. Wang, V. Magron and J. B. Lasserre, preprint, arXiv:1912.08899, 2019] where the TSSOS hierarchy was proposed for solving polynomial optimization pro...
2 January 2017 in ACM Transactions on Mathematical Software
Roundoff errors cannot be avoided when implementing numerical programs with finite precision. The ability to reason about rounding is especially important if one wants to explore a range of potential representations, for instance, for FPGAs or custom hardware implementations. This problem becomes challenging when the program does not employ solely linear operations as non-linearities are inherent to many interesting computational problems in real-world applications. Existing solutions to reasoning possibly lead to either inaccurate bounds or high analysis time in the presence of nonlinear correlations between variables. Furthermore, while it is easy to implement a straightforward method such as interval arithmetic, sophisticated techniques are less straightforward to implement in a formal setting. Thus there is a need for methods that output certificates that can be formally validated inside a proof assistant. We present a framework to provide upper bounds on absolute roundoff errors of floating-point nonlinear programs. This framework is based on optimization techniques employing semidefinite programming and sums of squares certificates, which can be checked inside the Coq theorem prover to provide formal roundoff error bounds for polynomial programs. Our tool covers a wide range of nonlinear programs, including polynomials and transcendental operations as well as conditional statements. We illustrate the efficiency and precision of this tool on non-trivial programs coming from biology, optimization, and space control. Our tool produces more accurate error bounds for 23% of all programs and yields better performance in 66% of all programs.
27 July 2021 in Computational Optimization and Applications
11 July 2024 in Physical Review X
A ubiquitous problem in quantum physics is to understand the ground-state properties of many-body systems. Confronted with the fact that exact diagonalization quickly becomes impossible when increasing the system size, variational approaches are typically employed as a scalable alternative: Energy is minimized over a subset of all possible states and then different physical quantities are computed over the solution state. Despite remarkable success, rigorously speaking, all that variational methods offer are upper bounds on the ground-state energy. On the other hand, so-called relaxations of the ground-state problem based on semidefinite programming represent a complementary approach, providing lower bounds to the ground-state energy. However, in their current implementation, neither variational nor relaxation methods offer provable bound on other observables in the ground state beyond the energy. In this work, we show that the combination of the two classes of approaches can be used to derive certifiable bounds on the value of any observable in the ground state, such as correlation functions of arbitrary order, structure factors, or order parameters. We illustrate the power of this approach in paradigmatic examples of 1D and 2D spin- Heisenberg models. To improve the scalability of the method, we exploit the symmetries and sparsity of the considered systems to reach sizes of hundreds of particles at much higher precision than previous works. Our analysis therefore shows how to obtain certifiable bounds on many-body ground-state properties beyond energy in a scalable way.
28 January 2021 in Mathematical Programming