Recherche d'un algorithme efficace.

[invite0a547b27]

Salut,

Auriez-vous un algo. rapide pour résoudre les systèmes d'inéquations linéaires (1000 inconnus et 10000 inéquations)?

Merci.
-----

[Deedee81]

Salut,

L'algorithme du simplexe. http://fr.wikipedia.org/wiki/Algorithme_du_simplexe et voir lien.
Il y a quelques algorithmes meilleurs mais celui-là à aussi l'avantage d'être relativement simple.

[invite9dc7b526]

Comment est-ce que tu adaptes la méthode du simplexe pour la résolution d'inéquations? Je vois bien qu'on peut utiliser un algorithme d'optimisation pour résoudre des équations, il suffit de minimiser le carré de la différence, mais pour des inéquation ça me semble moins évident.

[invite0a547b27]

Salut,

L'algorithme du simplexe. http://fr.wikipedia.org/wiki/Algorithme_du_simplexe et voir lien.
Il y a quelques algorithmes meilleurs mais celui-là à aussi l'avantage d'être relativement simple.

Salut,

L'amorce de cette algo commence avec un point vérifiant le système or c'est ceux que je veux savoir s'il y a ou pas de solution pour le système.

[A voir en vidéo sur Futura]

[invite0a547b27]

Salut,

Auriez-vous un algo. rapide pour résoudre les systèmes d'inéquations linéaires (1000 inconnus et 10000 inéquations)?

Merci.

Un algo qui donne si le système à des solutions ou non, serait parfait.

[Deedee81]

Salut,

Comment est-ce que tu adaptes la méthode du simplexe pour la résolution d'inéquations? Je vois bien qu'on peut utiliser un algorithme d'optimisation pour résoudre des équations, il suffit de minimiser le carré de la différence, mais pour des inéquation ça me semble moins évident.

Ben le simplexe c'est pour les inéquations, justement. Mais oui, en effet, il faut une relation à optimiser. J'avais mal compris le besoin :

L'amorce de cette algo commence avec un point vérifiant le système or c'est ceux que je veux savoir s'il y a ou pas de solution pour le système.

Problème plus simple mais je ne sais pas comment le résoudre (j'ai une idée en tête avec ajout de variable et calcul du déterminant mais c'est tirer au canon sur une mouche. Il doit y avoir beaucoup plus simple).

[invite0a547b27]

...Problème plus simple mais je ne sais pas comment le résoudre (j'ai une idée en tête avec ajout de variable et calcul du déterminant mais c'est tirer au canon sur une mouche. Il doit y avoir beaucoup plus simple).

Tant que cela marche, je suis preneur, calcul d'un déterminant avec moins de 10 000 variables c'est bon pour moi.

[Deedee81]

Salut,

Tant que cela marche, je suis preneur, calcul d'un déterminant avec moins de 10 000 variables c'est bon pour moi.

Pour simuler des égalités, j'ajouterais 10000 variables. On a alors un systèmes de 10000 équations linéaires à 11000 inconnues. On peut vérifier ensuite la compatibilité par les méthodes habituelles des systèmes d'équations linéaires (rang de la matrice et tout ça).

Franchement j'ai l'impression d'écraser une mouche avec un gant de boxe.

J'espère qu'un mathématicien va venir nous donner un petit coup de main.

[Deedee81]

Bigzouille, je me rend compte que ce n'est pas suffisant. Ces nouvelles variables ne peuvent pas avoir n'importe quelle valeur. Désolé,

[Amanuensis]

Auriez-vous un algo. rapide pour résoudre les systèmes d'inéquations linéaires (1000 inconnus et 10000 inéquations)?

S'il y a dix fois plus d'inéquations que d'inconnues, la première éventualité qui vient à l'esprit est qu'il n'y a pas de solution!

L'algo consiste à éliminer un maximum d'inéquations, en les combinant linéairement: cela va amener soit un constat de contradiction, soit à au maximum 2000 inéquations (il me semble).

L'idée est la même que la triangularisation d'une matrice (pivot de Gauss).

En gros (sous toute réserve):

Séparer les inéquations en deux ensembles selon le signe du coefficient de la première inconnue.

Pour chaque ensemble appliquer le pivot de Gauss. Il reste (au plus) 2 inéquations avec le coeff de la première inconnue non nul.

Recommencer sur les autres et les n-1 inconnues restantes, avec la seconde inconnue. Etc.

Et ensuite, vérifier la compatibilité entre les 2000 (au plus) inéquations obtenues, en remontant et combinant les inéquations de manière à n'avoir que (au plus) 1000 formes linéaires indépendantes.

[Amanuensis]

Mouais...

L'algo ne marche pas si facilement (je laisse découvrir où est l'erreur)... Mais la piste doit être bonne. À creuser.

[Médiat]

Qu'est-ce qui interdit de construire un système de 10000 inéquations linéaires avec 2 inconnus qui ne soit pas simplifiable ?

[Amanuensis]

Je sors

[invite0a547b27]

Salut,



Pour simuler des égalités, j'ajouterais 10000 variables. On a alors un systèmes de 10000 équations linéaires à 11000 inconnues. On peut vérifier ensuite la compatibilité par les méthodes habituelles des systèmes d'équations linéaires (rang de la matrice et tout ça).

Franchement j'ai l'impression d'écraser une mouche avec un gant de boxe.

J'espère qu'un mathématicien va venir nous donner un petit coup de main.

Salut,

Effectivement (pour ton deuxième message).

[invite0a547b27]

S'il y a dix fois plus d'inéquations que d'inconnues, la première éventualité qui vient à l'esprit est qu'il n'y a pas de solution!

L'algo consiste à éliminer un maximum d'inéquations, en les combinant linéairement: cela va amener soit un constat de contradiction, soit à au maximum 2000 inéquations (il me semble).

L'idée est la même que la triangularisation d'une matrice (pivot de Gauss).

En gros (sous toute réserve):

Séparer les inéquations en deux ensembles selon le signe du coefficient de la première inconnue.

Pour chaque ensemble appliquer le pivot de Gauss. Il reste (au plus) 2 inéquations avec le coeff de la première inconnue non nul.

Recommencer sur les autres et les n-1 inconnues restantes, avec la seconde inconnue. Etc.

Et ensuite, vérifier la compatibilité entre les 2000 (au plus) inéquations obtenues, en remontant et combinant les inéquations de manière à n'avoir que (au plus) 1000 formes linéaires indépendantes.

J'ai testé et cela bloque car au bout d'un certains rang toutes les inéquations finissent par avoir même signe et donc impossible d'aller plus loin.

[invite0a547b27]

Est ce que ce problème possède un algo polynomiale ?

Maintenant que j'y réfléchis il est peut-être NP-difficile.

[Médiat]

Bonjour,

Qu'entendez-vous par "résoudre les systèmes d'inéquations linéaires", si je prends l'exemple simple :



Qu'attendez-vous comme réponse ?

[invite0a547b27]

Bonjour,

Qu'entendez-vous par "résoudre les systèmes d'inéquations linéaires", si je prends l'exemple simple :



Qu'attendez-vous comme réponse ?

Salut,

J'aimerais savoir :
1/ s'il y a des solutions ou non.
ou bien 2/ une solution (2,0) ici par exemple.

[invite6dffde4c]

Bonjour.
Je pense que l’orientation de Deedee81 vers les méthodes de programmation linéaire est une très bonne idée à creuser.
Je suis allé relire ce que Numerical Recipes dit à propos du Simplex. Effectivement, la méthode de base demande de partir d’une solution possible, pour aller chercher l’optimum par la suite.
Il y a le « primal dual algorithm » et le « composite simplex algorithm » qui cherchent une solution possible et simultanément cherchent une solution optimale.
Mon édition de Numerical Récipes est un peu vieillotte (1989). Il faudrait regarder une édition plus récente.

Mais la programmation linéaire peut être utilisée pour trouver une solution faisable puis, l’optimum.
On transforme chaque inéquation en une composante de l’évaluation de la fonction économique (la fonction à optimiser), simplement en faisant une calcul de ce type :

Pour chacune des inéquations de la forme f_i(x1, x2, …) < 0
En :
if f_i(…) < 0 return 0 ;
else
return f_i(…)^2;

Et la fonction économique est l’addition de toutes les valeurs retournées.

J’ai adapté une méthode d’optimisation sans contraintes (Powell) en optimisation avec contraintes par cette méthode. Elle s’est avérée très efficace pour les exemples du Himmelblau.

Mais le nombre de contraintes était très faible, ainsi que la puissance de calcul des ordinateurs de l’époque.
Au revoir.

[invite0a547b27]

Bonjour.
Je pense que l’orientation de Deedee81 vers les méthodes de programmation linéaire est une très bonne idée à creuser.
Je suis allé relire ce que Numerical Recipes dit à propos du Simplex. Effectivement, la méthode de base demande de partir d’une solution possible, pour aller chercher l’optimum par la suite.
Il y a le « primal dual algorithm » et le « composite simplex algorithm » qui cherchent une solution possible et simultanément cherchent une solution optimale.
Mon édition de Numerical Récipes est un peu vieillotte (1989). Il faudrait regarder une édition plus récente.

Mais la programmation linéaire peut être utilisée pour trouver une solution faisable puis, l’optimum.
On transforme chaque inéquation en une composante de l’évaluation de la fonction économique (la fonction à optimiser), simplement en faisant une calcul de ce type :

Pour chacune des inéquations de la forme f_i(x1, x2, …) < 0
En :
if f_i(…) < 0 return 0 ;
else
return f_i(…)^2;

Et la fonction économique est l’addition de toutes les valeurs retournées.

J’ai adapté une méthode d’optimisation sans contraintes (Powell) en optimisation avec contraintes par cette méthode. Elle s’est avérée très efficace pour les exemples du Himmelblau.

Mais le nombre de contraintes était très faible, ainsi que la puissance de calcul des ordinateurs de l’époque.
Au revoir.

Salut,

Merci.

[invite0a547b27]

S'il y a dix fois plus d'inéquations que d'inconnues, la première éventualité qui vient à l'esprit est qu'il n'y a pas de solution!

L'algo consiste à éliminer un maximum d'inéquations, en les combinant linéairement: cela va amener soit un constat de contradiction, soit à au maximum 2000 inéquations (il me semble).

L'idée est la même que la triangularisation d'une matrice (pivot de Gauss).

En gros (sous toute réserve):

Séparer les inéquations en deux ensembles selon le signe du coefficient de la première inconnue.

Pour chaque ensemble appliquer le pivot de Gauss. Il reste (au plus) 2 inéquations avec le coeff de la première inconnue non nul.

Recommencer sur les autres et les n-1 inconnues restantes, avec la seconde inconnue. Etc.

Et ensuite, vérifier la compatibilité entre les 2000 (au plus) inéquations obtenues, en remontant et combinant les inéquations de manière à n'avoir que (au plus) 1000 formes linéaires indépendantes.

Effectivement, cela bloque car on obtient très vite des inéquations qui sont de même signe, mais avec la stratégie que tu m'as proposé par MP (changement de variable linéaire), on peut continuer le processus jusqu'à sa fin.

Merci, pour ta réponse simple, évidente et pourtant vrai.

Merci également, à tous les autres participants.

Au revoir.

[Médiat]

N'ayant aucune information sur la solution qui vous a été proposée sous une forme qui ne permet pas aux lecteurs de ce fil d'en avoir connaissance, je n'en dirai rien, mais les solutions proposées publiquement ici-même me poussent à vous rappeler qu'une "combinaison linéaire" d'inégalités permet (dans le cas général) de démontrer des implications, pas des équivalences.

[invite9dc7b526]

On transforme chaque inéquation en une composante de l’évaluation de la fonction économique (la fonction à optimiser), simplement en faisant une calcul de ce type :

Pour chacune des inéquations de la forme f_i(x1, x2, …) < 0
En :
if f_i(…) < 0 return 0 ;
else
return f_i(…)^2;

Et la fonction économique est l’addition de toutes les valeurs retournées.

J’ai adapté une méthode d’optimisation sans contraintes (Powell) en optimisation avec contraintes par cette méthode. Elle s’est avérée très efficace pour les exemples du Himmelblau.

Je me demande si c'est la bonne approche. Ta fonction objectif va être constante et donc à dérivée nulle probablement en pas mal de points. Et d'ailleurs les algorithmes d'optmisation renvoient toujours une solution alors que le problème n'en a peut-être pas.

[invite6dffde4c]

Je me demande si c'est la bonne approche. Ta fonction objectif va être constante et donc à dérivée nulle probablement en pas mal de points. Et d'ailleurs les algorithmes d'optmisation renvoient toujours une solution alors que le problème n'en a peut-être pas.

Bonjour.
Oui. C’est vrai.
Mais si vous ne cherchez qu’une solution possible, alors des que toutes les contraintes sont satisfaites, vous arrêtez.
Mais si vous avez quelque chose à optimiser, alors les contraintes viennent en plus. Éventuellement avec un coefficient multiplicatif.

Pouvez-vous nous dire quel est le problème que vous essayez de résoudre ?
Je suis curieux de connaître un problème avec 10 000 variables et autant de contraintes.

Et non, les algorithmes d’optimisation n’envoient pas de solutions fausses. Ce qui peut leur arriver est de ne pas arriver à les trouver (pour des fonctions merdiques comme celle des exemples type du Himmelblau) ou qu’ils vous donnent des optimums locaux. Et ça c’est imparable. Le seul moyen de le vérifier est d’exécuter le même problème avec des points de départ différents et voir s’il aboutit toujours à la même solution. Au bout d’un nombre certain d’essais vous pouvez commencer à parier un café que ce n’est pas un optimum local. Mais vous n’êtes jamais sur.
Au revoir.

[invite897e49b2]

par programmation linéaire tu peux faire en sorte de transformer tes inégalités en EGALITE en ajoutant des variables artificielles
il faut pas se tromper dans les changements de base ...

[invite0a547b27]

Bonjour.
Oui. C’est vrai.
Mais si vous ne cherchez qu’une solution possible, alors des que toutes les contraintes sont satisfaites, vous arrêtez.
Mais si vous avez quelque chose à optimiser, alors les contraintes viennent en plus. Éventuellement avec un coefficient multiplicatif.

Pouvez-vous nous dire quel est le problème que vous essayez de résoudre ?
Je suis curieux de connaître un problème avec 10 000 variables et autant de contraintes.

Et non, les algorithmes d’optimisation n’envoient pas de solutions fausses. Ce qui peut leur arriver est de ne pas arriver à les trouver (pour des fonctions merdiques comme celle des exemples type du Himmelblau) ou qu’ils vous donnent des optimums locaux. Et ça c’est imparable. Le seul moyen de le vérifier est d’exécuter le même problème avec des points de départ différents et voir s’il aboutit toujours à la même solution. Au bout d’un nombre certain d’essais vous pouvez commencer à parier un café que ce n’est pas un optimum local. Mais vous n’êtes jamais sur.
Au revoir.

Bonjour,

Je suis désolé de n'avoir pas répondu plus tôt mais j'étais occupé.

Pour ce qui est du problème que je cherche à résoudre il s'agit d'un problème d'IA.

Le problème est le suivant on a une fonction booléenne de (1000 variables x_1,..,x_1000) pour lequel on a qu'un accès aléatoire et on cherche à l'approximé par quelque chose.

Une bonne approximation est à cherché parmi ces fonctions : A_1*x_1+....+A_n*x_n>1 ou <-1 (selon que la fonction booléenne dit 1 ou 0).

Pourquoi sont-elles de bons candidates ?
Disons que cette fonction réponds 0.501 bien.

Donc on fait 10^5 tirages que l'on ajoute alors cette inéquations est surement juste...

Et ainsi par la résolution de système d'inéquation on obtient une fonction solution.

Si vous avez des questions n'hésiter pas.

[invite0a547b27]

Remarque on peut ajouter des variables pour avoir une approximation correcte :

A_0+ A_1*x_1+....+A_n*x_n+A_1,2*x_1 *x_2+....

[invite6dffde4c]

Bonjour.
Merci pour ces explications.
Mais je dois avouer que j’ai du mal à « voir » l’énoncé lui-même.
Notamment, « approcher une fonction booléenne par quelque chose ».
Je crois comprendre que la fonction est inconnue et on cherche une qui lui « ressemble ».

Le problème au départ, c’est quoi ? Je parierais un café que pour avoir autant de variables c’est une reconnaissance d’images.
Mais remarquez que j’ai mis la phrase au conditionnel.
Au revoir.

[invite0a547b27]

Bonjour.
Merci pour ces explications.
Mais je dois avouer que j’ai du mal à « voir » l’énoncé lui-même.
Notamment, « approcher une fonction booléenne par quelque chose ».
Je crois comprendre que la fonction est inconnue et on cherche une qui lui « ressemble ».

Le problème au départ, c’est quoi ? Je parierais un café que pour avoir autant de variables c’est une reconnaissance d’images.
Mais remarquez que j’ai mis la phrase au conditionnel.
Au revoir.

Vous me devriez un café alors...

Remarquez que j'ai utilisé moi aussi le conditionnel.

Au revoir.

[invite0a547b27]

PS : j'ai oublié de répondre à la question : il s'agit de cryptanalyse.