Differences

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

--- commit:2017:01_09 [2017/01/09 11:05] – wautelet
+++ commit:2017:01_09 [2017/01/09 11:36] – wautelet
@@ Line 4: / Line 4: @@
 ==== 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 :
+Bien que négligé par les auteurs des papiers, l'utilisation d'un Line Search fut déjà recommandée par
+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). 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 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 locale (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|External Link]]
+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 :
-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).
+  * 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) :
+  * 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 pour calculer les projections, celà é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. 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 !!).
+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 !
 === 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éral et leur interface ressemble à celui utilisée pour le line search exacte de Romain Boman. </note>
+==== Normale sur une 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 ====