Gabrielle Sabatier Une méthode de type Gradient Projeté pour la simulation de systèmes mécaniques avec frottement resultats

De Ensiwiki
Aller à : navigation, rechercher


Une méthode de type Gradient Projeté pour la simulation de systèmes mécaniques avec frottement

Labo LJK
Equipe BIPOP
Encadrants jerome.malick@inria.fr,florent.cadoux@inria.fr

Etudiant

SABATIER, Gabrielle

Introduction

Dans de nombreuses situations en mécanique telles que la dynamique des matériaux granulaires ou la robotique, des corps rigides ou déformables entrent en contact et exercent l'un sur l'autre une force de frottement. La loi de Coulomb est un modèle de frottement physiquement raisonnable tout en restant suffisamment simple pour mener à des modèles que l'on sait "assez souvent" résoudre. Considérons deux corps (1) et (2) en contact ponctuel. Le corps (2) exerce sur le corps (1) une force \vec{r}. La loi de Coulomb assure que l'on se trouve dans l'un des 3 cas suivants :

  • décollement de (1) :  \vec{r} = \vec{0} .
  • adhérence :  \vec{r } \in  K_f .
  • glissement de (1) sur (2) :  \vec{r } \in  \delta (K_f) .
avec K_{f} le cône de frottement défini de la façon suivante :

 K_{f} = \left\lbrace \begin{array}{l} x \; / \; \Vert x_T \Vert \leq f x_N \end{array}\right\rbrace

où f est le coefficient de frottement de glissement, x_T la composante tangentielle du vecteur \vec{x} au plan de contact entre les corps (1) et (2) et x_N la composante normale à celui-ci.

Ainsi, plusieurs problèmes d'optimisation intégrant cette contrainte de Coulomb entrent dans la classe des problèmes d'optimisation sur le cône du second-ordre. Florent Cadoux a déjà développé un logiciel de simulation de systèmes mécaniques avec frottement, utilisant de l'optimisation conique. Le TER a consisté à attaquer le verrou numérique principal au coeur de ce logiciel de simulation. Le problème était de la forme :

 (P) \quad \min\limits_{ x \in K } \; \dfrac{1}{2}x^{t}Qx-b^tx

où, les variables K,Q et b sont définies de la façon suivante :

  •  K \subset R^{N=3n} convexe, fermé, défini comme étant le produit cartésien de n cônes du second ordre de dimension 3, c'est à dire :

K=SOC_3 \times SOC_3 \times ....\times SOC_3

  • Q une matrice carrée semi définie positive.
  • b un vecteur quelconque de R^N.

et le cône SOC_3 est défini comme le demi-cône supérieur du cône classique utilisé en dimension 3 :

 SOC_3 = \left\lbrace  X=(x,y,z) \in R^3 : \sqrt {x^2+y^2} \leq z \right\rbrace

Il s'agissait donc de trouver le minimum d'une fonction sur un ensemble n'ayant pas les "bonnes" propriétés pour appliquer les méthodes classiques vues en cours d'optimisation. L'idée du TER était d'essayer de résoudre ce problème par une approche récente utilisant un algorithme de Gradient Projeté. La méthode consistait jusqu'alors à transformer grâce à diverses astuces le problème (P) en un second problème (P') équivalent ayant la forme suivante :

 
(P') \quad \min\limits_{
\begin{array}{l}
\; y \in Y \\
A y = b
\end{array}} \quad  c^ty

Le problème (P') pouvait alors être résolu grâce au solveur SeDuMi, algorithme d'optimisation sur des cônes symétriques développé par Jos F. Sturm.

Travail réalisé

Les différentes étapes de travail qui ont été réalisées sont les suivantes :

  • recherche des propriétés vérifiées par les solutions de (P).
  • recherche de l'algorithme envisagé pour résoudre le problème en question.
  • implémentation de cet algorithme.
  • tests de validation de l'algorithme.
  • comparaison avec la méthode SeDuMi utilisée jusqu'alors.

Voici un court résumé des points importants du travail effectué.

Une propriété importante des solutions du problème


L'ensemble K est fermé et la fonction quadratique f est continue, coercive sur K. Donc, d'après les propriétés classiques du cours d'Optimisation, il existe une solution au problème (P). On montre de plus facilement l'équivalence suivante :

\text{u est solution de (P)} \Longleftrightarrow u =P_K(u-t \nabla f(u)) \; (t>0)



Implémentation et convergence de l'algorithme


Le coeur de mon travail était la recherche d'un algorithme permettant de résoudre le problème (P) : j'ai retenu un algorithme du type Gradient Projeté. Il s'agit de réaliser l'itération u_k-t_k \nabla f(u_k) (t_k étant le pas de descente), puis de projeter cette itération sur l'ensemble K :

 u_{k+1}= P_K(u_k-t_k \nabla f(u_k))

Le pas  t_k optimal pour une itération donnée est trouvé grâce à une recherche linéaire. On peut montrer la convergence de ce dernier à condition de respecter la contrainte :  0<t_k<\frac{2}{\Vert Q \Vert_2} à chaque itération.
L'implémentation suit le schéma général suivant :

Sabatieg algo.jpg

avec :

  • un point quelconque u_0 appartenant à K
  • un pas t constant ( 0<t<\frac{2}{\Vert Q \Vert_2} ).
  • une précision \varepsilon > 0.
  • un booléen "fini" initialisé à faux.
  • deux entiers MAX1 et MAX2 pour limiter le nombre d'itérations.
  • deux entiers N1 et N2 initialisés à 0 permettant de compter le nombre d'itérations effectuées.

Remarque concernant le critère d'arrêt : Lorsque \Vert u_k - u_{k-1} \Vert \leq \varepsilon avec \varepsilon petit, cela signifie que l'on a à peu près :

 u_{k} \approx u_{k-1} = P_K(u_{k-1}-t_k \nabla f(u_{k-1}))

L'algorithme revient donc bien à trouver un point fixe u tel que : u=P_K(u-\varphi \nabla f(u)), c'est à dire une solution de notre problème.

Comparaison de l'algorithme de type Gradient Projeté avec le solveur SeDuMi


Les algorithmes ont un comportement complètement différent : le solveur SeDumi réalise très peu de trés longues itérations tandis que l'algorithme du gradient projeté réalise énormément d'itérations ultra rapides. Au vu des résultats numériques obtenus, la méthode du Gradient Projeté semble avoir 2 avantages certains :

  • elle coûte bien moins en temps lorsqu'on travaille en grande dimension (cf Courbes ci-dessous), comme c'est le cas dans les problèmes mécaniques sur lesquels travaille Florent Cadoux (produit de centaines de cônes).
  • elle reste cependant meilleure en précision lorsqu'on considère la valeur minimale prise par la fonction f trouvée par la méthode.

Sabatieg comparaison algos.jpg

Conclusion

Mon TER s'inscrivait dans un travail d'amélioration d'un outil numérique utilisé par le logiciel de simulation de systèmes mécaniques avec frottement de Florent Cadoux. Le problème était de la forme : trouver le minimum d'une fonction quadratique sur un produit de cônes du second ordre. L'idée du TER était d'essayer de résoudre ce problème par un algorithme de type gradient projeté. Après l'implémentation d'un tel algorithme, les tests sont concluants : la méthode permet tout autant de gagner en temps de calcul qu'en précision.

Maintenant que les deux algorithmes ont été comparés sur des problèmes quelconques, la prochaine étape aurait consisté à introduire l'algorithme de type Gradient Projeté au sein du logiciel de simulation de systèmes mécaniques avec frottement de Florent Cadoux. Il aurait ainsi été possible de comparer les résultats mécaniques obtenus grâce à ce nouveau constituant avec les anciens. Le logiciel en question étant actuellement soumis à certaines améliorations, il n'a pas été possible que je participe à ce projet.

Références

  • D.P. Bertsekas. On the Goldstein - Levitin - Polyak Gradient Projection Method. IEEE Transactions on automatic control, vol AC-21, April 1976.
  • J.F. Bonnans, J.Ch. Gilbert, C. Lemaréchal and C. Sagastizàbal. Numerical Optimization. Springer.
  • "An optimization-based algorithm for Coulomb's frictional contact" , F. Cadoux, in Esaim: Proceedings, EDP Sciences.
  • J. Malick. Dual Newton methods to solve second order cone least-squares. January 25, 2008.
  • J. Nocedal and S.J. Wright. Numerical Optimization. Springer Second edition.

Documents additionnels