Salut,
je ne sais pas trop si je trouverais une réponse ici mais je sais qu'Hubbard est pas mal calé en la matière, et pourquoi pas Stef ou quelqu'un que j'aurais oublié, qui pourrait me donner des idées. Donc voila, si vous passez par là ^^
Je bosse actuellement sur un problème d'optimisation dont l'algorithme est centralisé : par exemple si le rôle de mon algorithme est de planifier les tâches d'un CPU, toutes les tâches envoient leurs info à un aggrégateur, qui réalise la planification après avoir reçu toutes les infos. Le problème de la centralisations c'est que si on a beaucoup de tâches CPU à planifier, il va falloir beaucoup de puissance de calcul, ce dont on ne peut pas forcément se permettre lorsqu'on est dans un système embarqué par exemple.
J'aimerais décentraliser cet algorithme : faire en sorte qu'il n'y ai plus d'aggrégateur, et que je divise mon problème en plusieurs sous problèmes, qui seront résolu directement par mes tâches CPU par exemple. L'ensemble des solutions a ces sous problèmes me permettra de trouver la solution au gros problème.
Pour faire ça il y a plusieurs méthodes mathématiques, dont une particulièrement qui est l'optimisation convexe. J'ai donc convexifié mon problème d'optimisation via les conditions de Karush Kuhn Tucker, et j'y ai appliqué la décomposition duale.
Mon problème c'est que je ne trouve pas de sous problèmes, et pourtant j'ai refais le calcul plusieurs fois pour être sûr de ne pas m'être trompé. J'ai également appliqué la décomposition primale mais ça ne m'avance pas plus. Le soucis c'est que la fonction objective de mon problème d'optimisation est de la forme suivante : f(x) = max x, et je souhaite minimiser f(x), j'ai donc un truc dans le style : min max f(x).
Je crois me rappeler que la fonction de type f(x) = max x est convexe, mais je n'en suis pas sûr et j'ai un peu de mal à le prouver.
J'ai donc deux questions :
1) Quelqu'un à des infos sur la convexité de mon f(x) ?
2) Est-il possible qu'un problème convexe ne puisse pas être décomposé en sous-problème convexe ? Ca me paraît étrange si on suit la définition des ensembles convexes.
Merci !
This post was edited by Bremen on Apr 18 2017 02:41am