Discussion :

[Julien N]

Bonjour,

J'espère que je suis dans la bonne section. Si ce n'est pas le cas n'hésitez pas à déplacer ce message.

Je bosse sur un problème d'optimisation: la répartition optimale de vecteurs pousées sur un navire (positionnement dynamique). Ce problème s'écrit comme suit:



Le problème est résolu en temps réel, c'est à dire toutes les x secondes. Les contraintes d'inégalité reflètent les contraintes physiques des propulseurs (variations max d'un pas de temps à l'autre), autrement dit les bornes du problème. Le problème est convexe par construction.

J'utilise un module d'optimisation Python pour problèmes de ce genre qui fonctionne très bien (cvxpy, pour info). Cependant ce module nécessite pas mal de dépendances qui ne sont pas aisées à installer pour un néophyte en Python. C'est pourquoi je souhaite proposer une alternative en utilisant un autre solver: la méthode SLSQP de optimize du module SciPy (A noter, j'ai parfaitement conscience que cette dernière est bien moins adaptée à mon problème). Or pour ce module j'ai besoin d'initialiser la variable u. Et c'est là que je sèche.

Jusqu'à présent je me contentais de definir u0, l'initial guess de la fonction d'optimisation, comme étant la solution trouvée au pas de temps précédent. La solution ne devant pas changer énormément d'un pas de temps à l'autre. Or, certaines contraintes des propulseurs font que mon problème doit être scindé en plusieurs sous problèmes convexes. Toutes les combinaisons de sous-problèmes sont testées, et la meilleure est conservée. La conséquence est que u0 ne satisfait pas nécessairement les contraintes (les bornes) du problème. Ce qui a pour effet de rallonger le temps de calcul, voir de créer une instabilité dans la résolution du problème.

D'où ma question, existe-il une solution mathématique permettant de définir une valeur pour u0 qui soit déjà à l'intérieur des bornes du problème? Je pense peut-être à trouver u minimisant A.u - b (les contraintes en question).

En me relisant j'ai l'impression que mon message n'est pas hyper clair... je peux apporter plus de précision si besoin.

Merci!

Ju

[valentin03]

Si tu mets des formules, il faut en expliciter les termes.
Pour attester que tu sais de quoi tu parle.

[Julien N]

Pas de soucis. Mais honêtement je ne pense pas que cela apporte quoi que ce soit, si ce n'est de la confusion. La formulation utilisée est la forme classique d'un problème d'optimisation quadratique. Seul le choix du nom des variables change.

Dans le cas présent:

• u est un vecteur colonne 2Nx1, avec N le nombre de propulseurs. u est composé de couples uix, uiy avec i l'indice du propulseur. Je traite le problème dans un repère cartésien. C'est u que l'on cherche.
• W est une matrice de poids, 2Nx2N.
• B est la matrice de configuration de taille 3x2N. Elle relie u au torseur global des efforts produits (Fx, Fy et Mz). B.u=Tau est la contrainte d'égalité à satisfaire, soit que le torseur des efforts produit soit égal à celui demandé.
• A et b sont les matrices représentant les contraintes d'inégalités. Elles sont contruites en définissant un polygone convexe pour chaque propulseur représentant l'espace dans lequel la solution peut se trouver. La dimension du polygone pouvant varier, les dimensions de A et b également.

J

[dourouc05]

Peut-être en résolvant un autre problème d'optimisation ? Idéalement, linéaire, histoire de ne pas y perdre trop de temps. Je pense à ceci :




Tu seras sûr de respecter les contraintes s'il existe une solution à ton problème initial. Là, SciPy te propose des fonctions d'optimisation linéaire qui n'ont pas besoin de point initial.

[Julien N]

Utiliser une première optimisation c'est une solution en effet. Dans ce cas je me contenterais de trouver u minimisant A.u. En effet, je ne suis pas assuré de trouver une solution satisfaisant la contrainte d'égalité. Pour pallier à ce problème j'utilise une variable de relachement (slack variable en anglais) non décrite dans mon précédent post.

Une autre solution serait de modifier la solution précédente en la projetant dans l'espace admissible. Si la solution n'est pas faisable (A.u>b), alors modifier u de sorte à ce que ce soit le cas.

Je me disais que ce genre de considération doit être assez courant et qu'une méthode préconisée existe déjà.

J

[dourouc05]

À te lire, je pense à des choses comme un gradient projeté, tu pourrais reprendre l'étape de projection ? Surtout, si tu projettes sur des contraintes linéaires, c'est encore assez gentil.