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
General Information
- Theme/Domain : Algorithmics, Computer Algebra and Cryptology
- Town/city : Sophia Antipolis
- Inria Center : Centre Inria d'Université Côte d'Azur
- Starting date : 2023-10-01
- Duration of contract : 1 year
- Deadline to apply : 2023-12-30
Warning : you must enter your e-mail address in order to save your application to Inria. Applications must be submitted online on the Inria website. Processing of applications sent from other channels is not guaranteed.
Instruction to apply
Defence Security :
This position is likely to be situated in a restricted area (ZRR), as defined in Decree No. 2011-1425 relating to the protection of national scientific and technical potential (PPST).Authorisation to enter an area is granted by the director of the unit, following a favourable Ministerial decision, as defined in the decree of 3 July 2012 relating to the PPST. An unfavourable Ministerial decision in respect of a position situated in a ZRR would result in the cancellation of the appointment.
Recruitment Policy :
As part of its diversity policy, all Inria positions are accessible to people with disabilities.
Contacts
- Inria Team : AROMATH
-
Recruiter :
Mourrain Bernard / Bernard.Mourrain@inria.fr
The keys to success
Candidates must hold a Ph.D. in Mathematics or Computer Sciences. Candidates must also show evidence of research productivity (e.g. papers, conference presentations, etc.) at the highest level.
We prefer candidates who have strong mathematical background (on computer algebra, optimisation or scientific computing) and in general are keen on using mathematics to model real problems and get insights. The candidate should also be knowledgeable on software development and have good programming skills. Previous experiences with Julia is a plus.
The position is for 12 months, renewable for one more year, for a total of 24 months.
About Inria
Inria is the French national research institute dedicated to digital science and technology. It employs 2,600 people. Its 200 agile project teams, generally run jointly with academic partners, include more than 3,500 scientists and engineers working to meet the challenges of digital technology, often at the interface with other disciplines. The Institute also employs numerous talents in over forty different professions. 900 research support staff contribute to the preparation and development of scientific and entrepreneurial projects that have a worldwide impact.