ESAIM: Control, Optimisation and Calculus of Variations (ESAIM: COCV)

Free access article

Issue		ESAIM: COCV Volume 5, 2000
Page(s)		139 - 156
DOI		10.1051/cocv:2000104

DOI: 10.1051/cocv:2000104

ESAIM: COCV, February 2000, Vol. 5, p. 139-156

Computation of the distance to semi-algebraic sets

Calcul de la distance à des ensembles semi-algébriques réels

Christophe Ferrier
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 September 23, 1998. Revised October 1, 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 [#!cf97!#]), allows us to compute distance to semi-algebraic sets. Problem of computing distance can be viewed as non convex minimization problem: $d(u,S) = \inf_{x \in S} \Vert x-u\Vert^2$ , where u is in $\mathbb$ . 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 $d(u,S) = /inf_{x \in S} \Vert x-u\Vert^2$ où $u \in \mathbb$ . 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.

Keywords and phrases: Distance, dual bond, optimality conditions, polynomial systems, interior point methods, semidefinite programming, location of zeros.

AMS Subject Classification: 90C46

Article without figures

What is OpenURL?