Optimisation multivariée à 6 variables et 8 contraintes

Bonsoir à tous

Certains ici se souviennent peut-être que je travaille sur la conception d’un planétaire. Pour plusieurs raisons, il me faut recommencer avec une approche différente. Cette approche me conduit à devoir faire en sorte que le centre de gravité de l’engrenage se trouve le plus proche possible du plan passant par l’axe d’entrée à l’axe de sortie. Je sais calculer la position de ce centre de gravité, et donc sa distance par rapport au plan des axes.

Ce que je cherche à faire maintenant, c’est donc résoudre un problème d’optimisation et j’ai besoin de conseils. En effet, je n’ai jamais eu à étudier cela jusqu’à maintenant et je souhaite vous demander comment bien démarrer dans ce domaine. On trouve bien sûr plein de ressources mais je souhaiterais qu’on m’indique lesquelles sont le plus adaptées à un débutant et dans quelle direction chercher pour mon problème particulier (décrit plus bas).

Une fois la théorie traitée, que me conseilleriez-vous comme système de résolution ? Je peux utiliser Python 3, Scilab, Fortran, Julia ou autre. J’imagine qu’il y a des bibliothèques spécifiques.

Pour décrire précisément le problème auquel je suis confronté, considérons un repère orthonormé $(0\ ; \vec{x}\ ; \vec{y})$ et cinq points: $O$ l’origine, $M_1=(x_1\ ; y_1)$, $M_2=(x_2\ ; y_2)$, $M_3=(x_3\ ; y_3)$ et $S=(0\ ;l)$. Les contraintes sont les suivantes :

1. $0<x_1<x_2<x_3<l$
2. $x_1^2+y_1^2=\left(\frac{Z_1+Z_2}{2}\right)^2$
3. $(x_2-x_1)^2+(y_2-y_1)^2=\left(\frac{Z_3+Z_4}{2}\right)^2$
4. $(x_3-x_2)^2+(y_3-y_2)^2=\left(\frac{Z_5+Z_6}{2}\right)^2$
5. $(l-x_3)^2+y_3^2=\left(\frac{Z_6+Z_7}{2}\right)^2$
6. $x_2^2+y_2^2>\left(\frac{Z_1+Z_5}{2}+\varepsilon\right)^2$
7. $(x_3-x_1)^2+(y_3-y_1)^2>\left(\frac{Z_3+Z_6}{2}+\varepsilon\right)^2$
8. $(l-x_2)^2+y_2^2>\left(\frac{Z_5+Z_7}{2}+\varepsilon\right)^2$

La première condition stipule que les roues dentées doivent être disposées globalement le long de la droite $(OS)$. Les conditions 2, 3 et 4 donnent les conditions d’engrennement. Les trois dernières conditions permettent d’éviter les chevauchement.

Je cherche à minimiser $y$ en faisant varier $x_1$, $x_2$, $x_3$, $y_1$, $y_2$ et $y_3$ dans la relation suivante :

Les valeurs de tous les autres paramètres sont constantes connues.

Le problème est-il posé correctement ?

Par la suite, j’enviseage de résoudre trois voire quatre de ces problèmes sous forme de système pour optimiser l’intégralité du système mais il faut commencer petit.

Merci d’avance pour votre aide.

J’ai du mal à voir ce qu’est $y$ dont tu donnes la relation en fonction des $m_i$ et $y_i$. Que sont les $m_i$ ? Pour savoir si ton problème physique est bien posé il me semble important de clarifier cela.

Je ne suis pas sûr de bien tout comprendre parce qu’il y a un certain nombre de variable non définis. Par exemple, les $z_i$, $m_i$ et $\epsilon$ ne sont pas définis. À moins qu’elles ne rentrent toutes dans le "les valeurs de tous les autres paramètres sont connues".

Si seul les $x_i$ et $y_i$ sont variables, cela veux dire que tu as un problème d’optimisation linéaire (la fonction de coût est linéaire) avec des contraintes quadratiques. Si je ne me trompe pas, ce n’est pas plus simple qu’un problème d’optimisation quadratique avec contraintes quadratiques. Tu n’as donc pas beaucoup de chance, parce que c’est bien plus compliqué qu’un simple problème d’optimisation linéaire.

Je doute que ce soit le cas ici, mais s’il est possible de modifier ton problème pour avoir quelque chose de linéaire, ça aiderait beaucoup.

La deuxième chose à faire est de regarder si ton problème est convexe. Si je me fie à la page wikipédia sur l’optimisation convexe, les contraintes d’égalités doivent être affines (ce qui n’est pas le cas ici) pour que le problème puisse être convexe.

Si aucune simplification ne t’amène à un problème linéaire ou convexe, tu vas devoir gérer le problème quadratique. Si tu veux chercher des outils, le nom anglais est "quadratically constrained quadratic programming". Vu la proportion de papier de recherche dans les résultats, je ne peux que te souhaiter bonne chance

Bon, j’ai tenté un truc pour ré-exprimer tout en fonction de $\{x_i\}_i$.

Je renomme ton $y$ par $f(\{y_i\}_i) = \frac{(m_2 + m_3)y_1+(m_4+m_5)y_2+m_6y_3}{m_2+m_3+m_4+m_5+m_6+m_7}$ et j’en profite pour réécrire $f(\{y_i\}_i) = \sum_i \alpha_i y_i$ et je te laisse le soin de faire l’identification des $\alpha_i$.

Je suppose aussi, comme tu le suggères dans ton énoncé que la famille $\{Z_i\}_i$ est fixée par avance et chaque $Z_i$ sont des constantes.

Je te laisse aussi refaire les identifications (par flemme de ma part de toute réécrire en $\LaTeX$).

Des contraintes que tu donnes on déduit ceci:

• de (2): $y_1 = D(x_1)$ une fonction de $x_1$ uniquement.
• de (5): $y_2 = G(x_3)$
• de (3): $y_2 = C(x_1, x_2) + y_1$
• de (4): $y_3 = E(x_2, x_3) + y_2$
• de (8) et (6): $y_2 > \max (A(x_2), B(x_2))$
• de (7): $y_3 > F(x_1, x_3) + y_1$

Au final on peut établir deux autres contraintes sur les $x_i$, en plus de (1) grâce aux déductions sur $y_2$: $C(x_1, x_2) + D(x_1) > \max(A(x_2), B(x_2))$ $(*)$ et $E(x_2, x_3) + C(x_1, x_2) > F(x_1, x_3)$ $(**)$.

La fonction $f$ se réécrit $f(\{y_i\}_i) = \alpha_1 D(x_1) + \alpha_2 [C(x_1, x_2) + D(x_1)] + \alpha_3 [E(x_2, x_3) + C(x_1, x_2) + D(x_1)]$ ce donne une relation plus claire entre ta première condition (1) et la fonction à minimiser.

L’étape suivante c’est d’étudier le domaine de validité de $(*)$ et $(**)$. L’étape d’après d’étudier le domaine de chacun des trois éléments de la somme qu’est $f$ sous les contraintes (1), $(*)$, $(**)$ en fonction des $x_1$.

Cela devrait déjà clarifier pas mal les choses. Ensuite tu pourras certainement faire quelques petites simulations numériques et dessins pour voir comment cela se comporte si aucune solution triviale n’apparaît.

EDIT: Après réexpression de $f$ avec les fonctions $D, C, E$ on voit tout de suite qu’il faut minimiser $x_1$, $x_2$ et $x_3$ pour minimiser $f$. Dès lors il faut vraiment étudier le domaine de $(*)$ et $(**)$. Tu devrais obtenir une solution explicite $x_1, x_2, x_3$ données en fonction des $Z_i$ et $\varepsilon$.

Merci pour vos réponses. Comme demandé par KFC, je vais expliquer mon problème plus en détail.

Pour commencer, voici un schéma de l’ensemble : (pour $y_i$, lisez $x_i$.)

On considère un engrenage de sept roues dentées numérotées de 1 à 7 qui s’engrennent dans l’ordre. Chaque roue $i$ a un nombre connu de dents $Z_i$ et une masse connue $m_i$. Les sept roues sont de module 1 donc leur diamètre est égal à $Z_i$. Le centre de la roue 1 est au point $O=(0,0)$, centre du repère $(O,\vec{x},\vec{y})$. Les roues 2 et 3 sont concentriques de centre $M_1=(x_1,y_1)$. Les roues 4 et 5 sont concentriques de centre $M_2=(x_2,y_2)$. Le centre de la roue 6 est $M_3=(x_3,y_3)$. Le centre de la roue 7 est au point $S=(0,\ell)$. La valeur de $\ell$ est connue.

Les $x_i$ et les $y_i$ sont les inconnues du problème.

Pour modéliser l’engrennement entre les roues $i$ et $i+1$, la distance entre les deux centres doit être égale à $(Z_i+Z_{i+1})/2$. Ce sont les relations 2 à 4 de mon premier message.

Pour que l’engrenage fonctionne, il ne faut pas que certaines roues se touchent. Les engrennement 1-5, 2-6 et 5-7 sont à éviter absolument. Je demande à ce que la distance entre les cercles correspondants soit au moins égale à une $\varepsilon$ qui est fixée à l’avance. C’est à dire que la distance entre les centres des roues $i$ et $j$ doit être égale à $(Z_i+Z_j)/2+\varepsilon$. Ce sont les relations 6 à 8. On pourrait aussi écrire des relations pour les roues 2 et 4 mais elles seront forcément vérifiées si les autres le sont.

Pour terminer, la conception de l’ensemble impose que l’engrenage fasse un zigzag et que toutes les roues se suivent le long de l’axe $(OS)$, donc que $0<x_1<x_2<x_3<\ell$.

Le but du problème est de faire en sorte que le centre de gravité de cet engrenage se situe au plus près de l’axe $(OS)$. Malheureusement, la valeur de $\ell$ ne permet pas d’aligner tous les points, c’est pourquoi il faut le meilleur compromis. Il faut noter que la roue 1 doit être ignorée du calcul pour des raisons pratiques ; elle est seulement présente dans les relations de contraintes. En ramenant chaque roue à un point pesant, le centre de gravité $G=(x,y)$ du système peut être déterminé par la relation

ce qui donne, pour la composante selon $\vec{y}$, la relation donnée dans mon premier message.

Si tu fixes la position de ton engrenage $Z_6$, ton problème n’a plus qu’une seul variable : la position angulaire (par rapport a O) de $M_1$ qui fixe la position de $M_2$ affin d’être tangent a $Z_3$ et $Z_6$.

Comme $Z_6$ doit être léger par rapport aux autre tu fixes arbitrairement une position raisonnable (celle de ton dessins semble pas mal) Et tu exprimes $x_2$ et $y_2$ en fonction de $\theta$, tu injectes dans ta formule du centre de gravité, tu résous pour $\theta$.

Et… roulez jeunesse ? (ou y peut etre une bourde quelque part … je sais pas il est tard !)

Je n’avais pas du tout visualise ca comme cela mais mes calculs restent justes. D’ailleurs cela correspond a l’intuition de Vael: $y_3$ n’apparait qu’une fois dans la fonction a minimiser. Cependant, je ne suis pas sur que tu t’en sortes reellement en parametrisant par $y_3$. Au mieux tu auras une solution quasi-optimale.

Par contre, passer en polaire dans le repere $(O, x, OM_1)$ pourrait surement alleger les calculs.

Posons $m=\sum_{i=1}^{i=7}m_i$ et $X_{ij}=(Z_i+Z_j)/2$.

En réécrivant $f$ sous la forme $f(\{x_i\}_i)=\sum_i\alpha_i y_i$ et en faisant l’identification des $\alpha_i$, on trouve :

À partir des contraintes, j’arrive à trouver les fonctions $A$, $B$, $D$ et $G$ mais pas les fonctions $C$, $E$ et $F$. Je crois que KFC a fait une erreur : on a $y_3=G(x_3)$ et pas $y_2=G(x_3)$.

Les trois fonctions manquantes me posent toutes le même problème. Je n’arrive pas à isoler de terme simple $y_i$ et en même temps à n’avoir qu’une fonction qui ne dépend que de $x_i$ et $x_j$. Par exemple, pour $C$ :

Ensuite, je vois à peu près comment faire.

J’ai essayé de mettre le problème en coordonnées polaires après avoir eu cette idée indépendamment. C’est possible mais le problème ne se simplifie pas. Cela introduit même des fonctions trigonométriques en sus des termes quadratiques.

Le problème global peut-il se simplifier si on cherche uniquement des solutions discrètes ? Par exemple, si je me limite à des $x_i$ et $y_i$ entiers.

Les problèmes discrets sont en général bien plus durs que les problèmes continues (pas d’existence du concept de dérivée par exemple). L’exemple typique est le problème d’optimisation linéaire et d’optimisation linéaire en nombre entier. Je te laisse te renseigner pour la culture si l’envie t’en dit.

J’ai l’inverse de toi pour $A$ et $B$. J’ai la même chose pour $D$ et $G$. Pour $C$ j’ai isolé $y_2$ dans l’équation $(3)$ ce qui donne $y_2 = C(x_1, x_2) + y_1$ et donc $C(x_1, x_2) = \sqrt{ {X^{2}_{34}} - (x_2 - x_1)^2 }$. $E$ est obtenu de la même manière, en isolant $y_3$ dans $(4)$ et donne $E(x_2, x_3) = \sqrt{X_{56}^2 - (x_3 - x_2)^2}$. Finalement, $F$ provient de la $(7)$ avec $F(x_1, x_3) = \sqrt{(X_{36} + \varepsilon)^2 - (x_3 - x_1)^2}$.

Observe que dans chacune des fonctions qui apparaît dans $f(\{y_i\}_i) = \alpha_1 D(x_1) + \alpha_2 [C(x_1, x_2) + D(x_1)] + \alpha_3 [E(x_2, x_3) + C(x_1, x_2) + D(x_1)]$, il s’agit toujours de la forme suivante: $F(x_i, x_j) = \sqrt{k - (x_i - x_j)^2}$ avec $k$ une quantité positive, et surtout $i > j$ qui induit donc par la contrainte $(1)$ que $x_i > x_j > 0$ et donc le terme $(x_i - x_j)^2$ est toujours positif, de telle sorte que minimiser $F(x_i, x_j)$ revient à minimiser $x_j$ et maximiser $x_i$. L’exception c’est $D$ qui ne dépend que de $x_1$ et qui est minimisé lorsque $x_1$ est maximisé.

Il n’est pas possible de faire une optimisation terme à terme dans la somme pour la simple et bonne raison que les termes ont des variables communes avec des objectifs différents: dans $D$ on veut maximiser $x_1$ et dans $C$ on veut le minimiser.

Du coup, je pense qu’avant d’essayer de faire des calculs de dérivés, il vaut mieux essayer de déterminer le domaine de validité pour $x_1$, $x_2$ et $x_3$ à partir des équations suivantes notamment:

• $C(x_1, x_2) + D(x_1) > \max(A(x_1), B(x_2))$
• $E(x_2, x_3) + C(x_1, x_2) > F(x_1, x_3)$

En étudiant le signe de $A(x_1) - B(x_2)$ tu devrais trouver une condition explicite sur $x_1$ en fonction notamment de $l$ et des $\varepsilon$, $X_{57}$ et $X_{15}$ afin de choisir $A > B$ ou l’inverse (à priori les deux sont possibles en choisissant bien la valeur de $x_2$).

Du coup il faut étudier $C(x_1, x_2) + D(x_1) > A(x_2)$ avec la contrainte associée trouvée ci-dessus, puis le cas opposé $C(x_1, x_2) + D(x_1) > B(x_2)$. Cela devrait te donner une contrainte entre $x_1$ et $x_2$ supplémentaire (en fait deux par disjonction des cas).

Il reste ensuite à étudier $E(x_2, x_3) + C(x_1, x_2) > F(x_1, x_3)$, toujours suivant l’un ou l’autre des hypothèses sur $x_2$.

Je n’ai pas fait les calculs donc je me trompe peut-être mais cela devrait faire apparaître des choses plus intéressantes sans trop de calculs.

J’ai renommé les fonctions :

À propos de l’équation $(*)$, j’ai étudié $f_6<f_8$ qui me donne la valeur critique $x_{2c}$ de $x_2$ pour avoir $f_6=f_8$ :

Ensuite, sachant que ce qui se trouve sous les racines du membre de gauche de l’équation doit être positif, on a deux nouvelles équations :

La nouvelle condition est donc $X_{12}>x_1>x_2-X_{34}$ si $x_2<x_{2c}$.

Ça doit être le même principe pour $x_2>x_{2c}$, mais est-ce que c’est bon jusque là ?

Yo je remonte ce truc (pas taper !). Du coup je vois que ton planétaire est dessiné, finalement comment as tu fais ?

Ce n’est pas le même planétaire. Celui dont il est question ici est le premier est le plus complexe. Celui sur lequel j’ai travaillé ces derniers mois en est un autre, plus simple, qui est (ou plutôt qui était) destiné à tester certains points de la fabrication. Ce nouveau planétaire a mis en sommeil l’ancien pour un temps indéterminé et le problème d’optimisation avec.

J’avais de grosses difficultés avec ce problème d’optimisation. Mes relations de contraintes n’étaient pas forcément exactes ou au moins adaptées. Pour aller plus vite, j’avais aussi écrit un programme qui teste de façon systématique toutes les combinaisons possibles afin d’avoir rapidement des résultats. Ça fonctionne, bien entendu, mais c’est évidemment lent.

Je pense y revenir mais pas avant d’avoir mon prototype. Merci quand même de t’y intéresser depuis tout ce temps