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

Contract type : Fixed-term contract

Renewable contract : Yes

Level of qualifications required : PhD or equivalent

Fonction : Post-Doctoral Research Visit

Level of experience : From 3 to 5 years

About the research centre or Inria department

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.

Context

Team AROMATH (https://team.inria.fr/aromath/), Inria at Université Côte d'Azur; team leader: Bernard Mourrain.

Research topics: computational algebraic geometry;  efficient algorithms for solving the non-linear problems, exploiting algebraic structures, stable against numerical perturbation; high order geometric modeling exploiting algebraic representations, for the accurate description of shapes.

Contact:
  Bernard Mourrain (http://www-sop.inria.fr/members/Bernard.Mourrain/)

Beside carrying out high quality research, we expect the postdoc to participate to the activities of the EU network TENORS on tensors and optimisation, which will start in January 2024.

The postdoc will also have the opportunity to collaborate with PhD students working on related topics.

 

Assignment

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.

Main activities

The research activity will follow a classical path: literature review, exchange, brain storming, development of new results ...
Software development (for instance with Julia Language) and experimentation can be considered to validate new methods. The collaboration will be conducted through regular meetings with the advisors.
The post-doctoral fellow will have the opportunity to bring his/her own expertise and will be encouraged to open up his/her own research avenues. 
He/she will benefit from the rich enviornement and expertise in effective algebraic geometry and computer algebra at the AROMATH team and at the University Côte d'Azur, from seminars and workshops and from our network of collaborators.

 

 

Skills

 

The following skills are desired for this position:

  • a strong research background in the domain of the project (or at least in a specific area such as computer algebra, geometry, optimisation or scientific computing)
  • good communication and reporting skills, and an interest in collaborative work
  • proficiency in English

Benefits package

  • 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)

Remuneration

Gross Salary: 2746 € per month