Computation of the distance to semi-algebraic sets

Département Mathématiques Appliquées et Analyse Numérique, Centre National d'Études Spatiales, 18 avenue E. Belin, 31401 Toulouse Cedex 4, France; Christophe.Ferrier@cnes.fr.

Received: 23 September 1998
Revised: 1 October 1999

Abstract

This paper is devoted to the computation of distance to set, called S, defined by polynomial equations. First we consider the case of quadratic systems. Then, application of results stated for quadratic systems to the quadratic equivalent of polynomial systems (see [5]), allows us to compute distance to semi-algebraic sets. Problem of computing distance can be viewed as non convex minimization problem: , where u is in . To have, at least, lower approximation of distance, we consider the dual bound m(u) associated with the dual problem and give sufficient conditions to guarantee m(u) = d(u,S). The second part deal with numerical computation of m(u) using an interior point method in semidefinite programming. Last, various examples, namely from chemistry and robotic, are given.

Résumé

Dans cet article nous nous intéressons au calcul de la distance à un ensemble S défini par des équations polynomiales. Nous considérons d'abord le cas quadratique. Le passage au cas polynomial se fait ensuite grâce aux équivalents quadratiques des systèmes polynomiaux développés dans [5]. Le calcul de la distance peut être vu comme un problème de minimisation non convexe où . Pour obtenir, au moins un minorant de cette distance, nous considérons la borne duale m(u) issue de la résolution du problème dual. De plus, nous donnons des conditions suffisantes pour avoir m(u) = d(u,S). La seconde partie de cet article est consacrée au calcul de m(u) en utilisant une méthode de points intérieurs en programmation semi-définie positive. Pour finir, nous donnons des exemples d'applications issus notamment de la chimie et de la robotique.