Summary of the project
A real univariate polynomial is hyperbolic whenever all its roots are real or, in other words, if it equals the characteristic polynomial of a real symmetric matrix.
This property can be extended to the multivariate case via the classical algebraic tool of symmetric determinantal representations. By the way, not every multivariate
hyperbolic polynomial admits such a representation/certificate. Hyperbolic Programming (HP) is the natural convex optimization problem asking to minimize
a linear function over the hyperbolicity cone of a multivariate hyperbolic polynomial. HP generalizes Linear (LP) and Semidefinite Programming (SDP), central
problems in mathematics and its applications. The goal of this project is to contribute to the following two research directions:
(1) the development of symbolic-numerical algorithms and implementations for the general HP problem, and
(2) efficient computation of hyperbolicity certificates such as symmetric determinantal representations.
The two questions above are highly related since when a polynomial has a symmetric determinantal representation or, more generally, when its hyperbolicity cone
is a section of the cone of positive semidefinite matrices, then the associated HP problem reduces to a SDP problem.
Period
2018-2021 and 2019-2022
Associate members
Simone Naldi — Université de Limoges (Principal Investigator)
Mario Kummer — Technische Universität Dresden (collaborator)
Daniel Plaumann — Technische Universität Dortmund (collaborator)
Rainer Sinn — Universität Leipzig (collaborator)
Timo de Wolff — Technische Universität Braunschweig (collaborator)
Funding
This project has received a grant from Fondation Hadamard under the Programme Gaspard Monge pour l'Optimisation (PGMO)
Publications
The following papers acknowledge support from this PGMO project
- A divide-and-conquer algorithm for computing Gröbner bases of syzygies in finite dimension (with V. Neiger) — Proc. ACM ISSAC, Kalamata, GRE (2020)
- Conic programming: infeasibility certificates and projective geometry (with R. Sinn) — J. Pure Appl. Algebra 225(7), 2021 — AAA conference Special Issue.
- Spectrahedral representations of plane hyperbolic curves (with M. Kummer and D. Plaumann) — Pac. J. Math. 303-1 (2019), 243--263
-
Exact algorithms for semidefinite programs with degenerate feasible set (with D. Henrion and M. Safey El Din) — Proc. ACM ISSAC, NY, USA (2018) — See also the extended version published at J. Symb. Comput. (104) 942--959, 2021