Differences

This shows you the differences between two versions of the page.

--- commit:2017:01_09 [2017/01/09 10:34] – wautelet
+++ commit:2017:01_09 [2017/01/09 13:30] (current) – [Cas tests ajoutés/supprimés] wautelet
@@ Line 5: / Line 5: @@
 ==== Robustesse Opération de Projection ====
+Jusqu'à présent, très peu considérée dans la communauté du contact, la robustesse et l'efficacité de l'opération de projection est mise en évidence à travers les deux papiers suivants :
+  * Assessment of methods for computing the closest point projection, penetration and gap functions in contact searching problems, Kopacka J. et al., 2015.
+  * On the solvability of closest point projection procedures in contact analysis: Analysis and solution strategy for surfaces of arbitrary geometry, Knoyukhov A. and Schweizerhof K., 2008.
+Bien que négligé par les auteurs du premier papier, l'utilisation d'un Line Search fut déjà recommandée par Heegaard J.H., Curnier A. (Geometric properties of 2D and 3D unilateral large slip contact operators), 1995.
+Pour ne pas changer et comme d'habitude, les auteurs décrivent très peu leur implémentation du line search (Il existe une multitude de line search en fonction de leur contexte d'utilisation !) ou leur implémentation de la modification de la matrice hessienne et renvoient directement vers la littérature.
+Dans le cas de la projection sur une surface ou une courbe, le problème revient à minimiser une fonction distance.
+Dans le cas de la projection orientée sur une surface ou une courbe, le problème revient à résoudre une équation non linéaire (distance d'un point de la courbe/de la surface à la droite vaut zéro).
+En relisant une x fois les opérations de projection orientée, j'ai constaté qu'elle n'était pas correcte sur une courbe (seulement valable en 2D) et ne tenait pas compte des courbures locales (Courbe et Surface), alors que l'on les calcule. Dans le contexte du contact, il est fort probable que ça fonctionne mais dans un contexte différent (ALE par exemple) et je ne suis pas sur du tout que ça fonctionnait correctement ou alors la convergence était relativement lente).
+=== Méthode Hybride - Inexact Line Search ===
+Si la matrice hessienne n'est pas définie positive, nous avons dès lors d'une direction de croissance de la fonction objective. Il suffit tout simplement de prendre l'opposé dans ce cas de figure pour régler le problème !
+Si la direction obtenue est presque perpendiculaire au gradient ou si la matrice hessienne est semi-définie positive (singulière), il suffit de prendre comme direction l'opposé du gradient local (Steepest descent method !).
+Dans le cas d'une minimisation d'une fonction non linéaire, l'utilisation d'un line search exact est totalement inefficace d'où la formulation des conditions dites de Wolfe pour garantir une décroissance suffisante de la fonction objective et de sa courbure. [[http://reference.wolfram.com/language/tutorial/UnconstrainedOptimizationLineSearchMethods.html|Inexact Line Search Methods]]
+Deux line search inexactes sont disponibles et implémentées dans Metafor :
+  * Backtracking line search (Utiliser en général pour la résolution d'équation non linéaire) : il requiert juste l'évaluation de la fonction objective et dans notre cas ici, il faut juste être capable d'évaluer un point sur une surface/une courbe. On garantit que la fonction décroit suffisamment selon la direction obtenue par la matrice hessienne (Procédure de Newton Raphson).
+  * More Thuente line search (State of the art) (Utiliser en général pour la minimisation d'une fonction non linéaire) : il requiert juste l'évaluation de la fonction objective et son gradient et dans notre cas ici, il faut juste être capable d'évaluer un point sur une surface/une courbe et les tangentes au même point. On garantit que la fonction décroit suffisamment selon la direction obtenue par la matrice hessienne (Procédure de Newton Raphson) et aussi que l'on se trouve dans la zone du minimum par un critère sur la courbure. A ma grand surprise, l'algorithme est relativement puissant !
+Finalement, j'ai du réécrire la procédure utilisée pour l'opération de projection, pour éviter de recalculer plusieurs fois les mêmes choses pour des raisons de performances.
+Pour la projection sur les NURBS, il serait peut être intéressant de faire un BFGS method pour calculer les projections, cela éviterait de calculer la matrice hessienne qui est très couteuse pour ce type de surface (Polynôme de degré relativement élevé en fonction de la complexité de la surface).
+=== Modification de la matrice hessienne ===
+Afin de continuer à utiliser la procédure de Newton-Raphson et toujours garantir une diminution de la fonction objective, j'ai implémenté une méthode qui rend la matrice définie positive tout en conservant une matrice bien conditionnée. L'idée est tout simple : on ajoute à la matrice initiale, un multiple de la matrice identité (Ceci s'apparente fortement aux méthodes dites "Trust Region". Elle marche dans le cas d'une matrice définie négative et semi-définie positive. En général, il faut combiner cette méthode avec un backtracking line search et une méthode qui limite la taille de la correction (obligatoire !!) : en effet une division par un nombre proche de la précision machine donne un très grand nombre ! En général, pour une matrice de dimension supérieure à 2, il faut passer par une décomposition Cholesky spéciale qui donne une matrice définie positive, même si la matrice initiale ne l'est pas ! (cf. a revised modified cholesky factorization algorithm, Schnabel R.B. and Eskow E., 1999).
+=== Résumé ===
+Que soit avec l'une ou l'autre méthode, nous avons désormais une garantie de convergence des opérateurs de projection à condition que le point de départ soit suffisamment proche de l'extremum et l'absence de point singulier dans la définition de la surface ou de la courbe (tangente égale à zéro).
+<note important>J'ai de nouveau réactivé l'affichage du warning lorsque l'opération de projection n'a pas réussi ! Dans le cas du contact, on considère que le point n'est pas en contact lorsque la procédure de projection n'a pas réussie ! </note>
+<note important>Les line search implémentés sont suffisamment généraux et leur interface ressemble à celui utilisée pour le line search exacte de Romain Boman. </note>
+==== Normale sur un patch de Coon bilinéaire ====
+J'ai corrigé l'expression de la normale lorsque l'on l'évalue en dehors de son domaine de définition [0 1]x[0 1].
+Sinon, il y avait une différence si on calculait la normale à partir des deux tangentes locales !
 ==== Projection Nurbs Surface ====
@@ Line 11: / Line 58: @@
 J'ai nettoyé l'interface pour le calcul des tangentes, normales, dérivées des tangentes afin d'uniformiser l'ensemble surtout lors du calcul d'un point en dehors du domaine de définition [0 1]x[0 1].
-J'ai fait une correction dans le cas où on évalue une tangente en dehors du domaine de définition [0 1]x[0 1]. On fait une extrapolation selon le paramètre non constant. En réécrivant les équations, j'ai garanti que les tangentes sont continues partout lors de cette extrapolation mais on observe une discontinuité de la dérivée seconde.
+J'ai fait une correction dans le cas où on évalue une tangente en dehors du domaine de définition [0 1]x[0 1]. On fait une extrapolation selon la coordonnée intrinsèque de la surface en dehors du domaine de définition. En réécrivant les équations, j'ai garanti que les tangentes soient continues partout lors de cette extrapolation mais on observe une discontinuité de la dérivée seconde.
+En faisant une recherche bibliographique, je me suis rendu compte que la littérature est très peu fournie à ce niveau-là alors que les logiciels de CAO proposent une extension des surfaces/courbes en dehors de leur domaine de définition. Dans le cas d'une NURBS (les fonctions d'interpolation sont définies par une fonction rationnelle polynomiale), on ne peut pas bêtement l'évaluer en dehors du domaine de définition, car nous pouvons avoir le dénominateur égal à zéro en certains points !
 Dans le cas du cas test du tube, nous observons une singularité au niveau de la définition d'une tangente, car celle-ci vaut zéro. Ceci est normal vu la définition de la surface utilisée.
@@ Line 22: / Line 71: @@
 J'ai ajouté la possibilité d'étendre les surfaces et les courbes en dehors du domaine [0 1]. Ceci permet de visualiser à quoi ressemble ces entités géométriques en dehors de leur domaine de définition. Il ne faut pas oublier que dans le cas des projections multiples, on étend le domaine à [-0.1 1.1].
+On peut demander aussi à calculer les tangentes et les normales par la même occasion.
+==== Line Search Exact ====
+J'ai juste ajouté un interface pour modifier les paramètres du line search exacte. L'algorithme reste inchangé !
 ==== Cas Test ====
@@ Line 31: / Line 86: @@
 <code>
-[a]:
+[a]:mtMath/InexactLineSearch.cpp
+[a]:mtMath/InexactLineSearch.h
 [r]:
 </code>
@@ Line 38: / Line 94: @@
 <code>
-[a]:
+[a]:mtMath/__init__.py
+[a]:mtMath/tests/__init__.py
+[a]:mtMath/tests/backTrackingInexactLineSearch.py
+[a]:mtMath/tests/lineSearch.py
+[a]:mtMath/tests/moreThuenteInexactLineSearch.py
 [r]:
 </code>