Discussion :

[SKone]

Bonjour,

Après modélisation de mon problème je me retrouve avec un système linéaire contraint. Ce problème là me résiste, je vais essayé de vous l'exposer clairement.

Mais le problème se sont les contraintes.
J'ai des contraintes de borne :
x est un vecteur de dimension n.


Avec:

La plus part du temps min = 0 et max = 1 (pour tous les x, mais il existe des cas où non)
Des contraintes par couple :
Avec :
(i et j sont entre 1 et n avec i différent de j)
Les contraintes de combinaison linéaire L :

Et des contraintes d'exclusion mutuelle E :
Si Alors
J'ai une collection de contrainte L et E... Je n'ai pas de contrôle sur le nombre de ces contraintes.

J'ai voulu résoudre ça avec le multiplicateur de Lagrange il m'a fallu transformer mes contraintes :
J'ai donc :

Et la contrainte d'exclusion mutuelle, je pourrais peut être m'en sortir avec un max :

Qui devient :

Qui lui aussi devient :


Et là j'ai une contrainte avec un "ou" (je voulais essayer de m'en débarasser en passant dans les complèxes peut être à coup de ) et une autre non dérivable.
Mais comme mes contraintes sont non dérivable, j'ai abandonné l'idée d'utiliser le multiplicateur de Lagrange.

Mon est un système sur-contraint, donc j'essaye juste de minimiser sachant où et sont les contraintes de borne de chaque élément i de x.
Les contraintes et sont nombreuses, de l'ordre de 50. Et la taille du système linéaire est de 300 lignes et 150 colonnes. Ce système doit être résolu de l'ordre de 15000-20000 fois.
Dans 99.999% les contraintes sont symétriques et et néglige les cas où elle ne le sont pas (sauf si c'est "gratuit").

Le système devrait avoir plusieurs solutions, ce que je cherche seulement la solution qui minimise .

Je suis ouvert à toute propositions/remarques/questionnement pouvant m'aider à résoudre ce problème, dans un temps (d’exécution) raisonnable (bruteforce est exclu).

Merci

[membreComplexe12]

salut,
c'est galère comme problème ça...
à vrai dire je ne maitrise pas trop ceci mais moi lorsque j'ai un problème
de minimisation sous contrainte j'utilise l'algorithme de Levenberg-Marquardt
qui permet de gérer des contraintes (en appliquant les conditions de Kuhn et Tucker KKT).
essai de regarder de ce côté là à mon avis

[SKone]

Bonjour,

Merci pour ta réponse, je ne connaissais pas cet algorithme mais d'après Wiki :

L’algorithme de Levenberg-Marquardt, ou algorithme LM, permet d'obtenir une solution numérique au problème de minimisation d'une fonction, souvent non linéaire et dépendant de plusieurs variables. L'algorithme interpole l'algorithme de Gauss-Newton et l'algorithme du gradient

Or l'algorithme du gradient se base sur "le gradient" dont une dérivée à une dérivée non continue (le max).

De ce fait je ne pense pas que Levenberg-Marquardt soit utilisable. Est-ce qu'un détail m'a échappé ?

[souviron34]

Le système devrait avoir plusieurs solutions, ce que je cherche seulement la solution qui minimise

Normalement, la méthode "par défaut" d'un système linéaire avec multiples contraintes est un Algorithme du Smplexe (d'ordre n+1) :

il envisage un système "carré" en minimisant l'écart sur les équations restantes, et itère en appliquant un algo de convergence..

Je ne sais pas si d'autres méthodes ont vu le jour...

[membreComplexe12]

salut

De ce fait je ne pense pas que Levenberg-Marquardt soit utilisable. Est-ce qu'un détail m'a échappé ?

effectivement, j'avais pas fait attention au fait que des contraintes étaient non dérivables...
Je ne sais pas ce que ça fait si on utilise l'algo sur un truc dans ce genre (car lui il fait des dérivées numériques donc la non dérivabilité il ne la sent pas forcement).... tu peux toujours essayer pour voir ce que ça donne...

Normalement, la méthode "par défaut" d'un système linéaire avec multiples contraintes est un Algorithme du Smplexe (d'ordre n+1) :
il envisage un système "carré" en minimisant l'écart sur les équations restantes, et itère en appliquant un algo de convergence..
Je ne sais pas si d'autres méthodes ont vu le jour...

Il me semble que le simplexe est seulement pour un syst. lin. avec des contraintes linéaires égalemement.
Il me semble que l'algorithme "Nelder-Mead" (NM) est une généralisation du simplexe de base.
Pour ce qui est de la prise en compte des contraintes avec "NM" je ne sais pas trop, il me semble que certaines personnes au programmé ceci (il me semble que j'etais tombé dessus en fouillant sur le net) mais je ne me rappel plus....

========
sinon, tu peux utiliser des méthodes dites globales comme :
- l'algorithme du recuit simulé (simple à mettre en oeuvre il me semble)
- algorithme générique (je ne connais pas du tout)

mais je ne sais pas si il est possible de gérer les bornes...