Post-Doctoral Research Visit F/M Primal-Dual relaxations for Non-Linear Problems

The Inria centre at Université Côte d'Azur includes 37 research teams and 8 support services. The centre's staff (about 500 people) is made up of scientists of different nationalities, engineers, technicians and administrative staff. The teams are mainly located on the university campuses of Sophia Antipolis and Nice as well as Montpellier, in close collaboration with research and higher education laboratories and establishments (Université Côte d'Azur, CNRS, INRAE, INSERM ...), but also with the regiona economic players.

With a presence in the fields of computational neuroscience and biology, data science and modeling, software engineering and certification, as well as collaborative robotics, the Inria Centre at Université Côte d'Azur  is a major player in terms of scientific excellence through its results and collaborations at both European and international levels.

Non-Linear Equations are ubiquitous in domains such as geometric modelling, scientific computing, data analysis, . . . . Finding their solutions is an instance of non-linear optimisation problems. A classical approach to tackle these non-linear problems is to use local methods, such as Newton method or gradient descent methods. This family of methods is widely used in practice, but it only provides local extrema with no guaranty for a global solution. Moreover, it is very sensitive to the choice of the initial point.
Alternative algebraic approaches such as Grobner basis have been developed over the last decades to compute all the solutions of polynomial equations [2]. They involve direct computations with the polynomial equations, but are not numerically stable. Border basis [6], which have been developed more recently for robustness purposes, also involves primal polynomial computations.
At the turn of this century, an innovative approach has been proposed by J.B. Lasserre, to approximate global optima [4]. It involves primal convex cones of sums of squares of polynomials and their dual cones of pseudo-moment sequences. The core of the approach is to approximate positive polynomials by sums of squares and moments of measures by positive pseudo-moment sequences. These primal-dual relaxations allow to recover the optimal value and all the solutions of the optimization problem.
The objective of the project is to explore new types of primal-dual relaxations, which lead to efficient methods for solving global non-linear problems.
The first part of the project will be dedicated to the study of non-linear problems with a finite number of solutions, based on linear primal and dual relaxations. We will investigate new methods extending the Truncated Normal Form (TNF) approach [5] for solving non-linear constraints.
In a second part, we will consider non-linear optimisation problems defined on general basic semi-algebraic sets. We will investigate new primal and dual convex relaxations for other types of functions such as splines, polynomial exponential functions [3], or network functions used in Machine Learning for data fitting. We aim at analysing the capacity of approximation of these relaxations [1], their potential to recover the optimizers of the global optimization problem and their practical performance through their use in illustrative applications.

References

• [1] Lorenzo Baldi and Bernard Mourrain. On the Effective Putinar’s Positivstellensatz and Moment Approximation. Mathematical Programming, Series A, 2022.
• [2] David A. Cox, John Little, and Donal O’Shea. Ideals, Varieties, and Algorithms. Undergraduate Texts in Mathematics. Springer.
• [3] Mareike Dressler, Sadik Iliman, and Timo de Wolff. A Positivstellensatz for Sums of Nonnegative Circuit Polynomials. SIAM Journal on Applied Algebra and Geometry, 1(1):536–555, 2017.
• [4] Jean B. Lasserre. Global Optimization with Polynomials and the Problem of Moments. SIAM Journal on Optimization, 11(3):796–817, 2001.
• [5] Bernard Mourrain, Simon Telen, and Marc Van Barel. Truncated normal forms for solving polynomial systems: Generalized and efficient algorithms. Journal of Symbolic Computation, 102:63–85, 2021.
• [6] Bernard Mourrain and Philippe Trébuchet. Stable normal forms for polynomial system solving. Theoretical Computer Science, 409(2):229–240, December 2008.

• Subsidized meals
• Partial reimbursement of public transport costs
• Leave: 7 weeks of annual leave + 10 extra days off due to RTT (statutory reduction in working hours) + possibility of exceptional leave (sick children, moving home, etc.)
• Possibility of teleworking and flexible organization of working hours
• Professional equipment available (videoconferencing, loan of computer equipment, etc.)
• Social, cultural and sports events and activities
• Access to vocational training
• Contribution to mutual insurance (subject to conditions)

Gross Salary: 2746 € per month