Une découverte : l'optimization convexe est NP-difficile

Salut,



Cordialement.

$For example, let the problem sat : $\{x_1x_2,(1-x_1)x_2(1-x_3),x_3\}$

\\Then the convex optimization problem is minimize :

\\$F(x)=\max\{f_1(x),f_2(x)\}$

\\where $f_1(x)=-\ln(1+x_1+x_2)\times \ln(1+(1-x_1)+x_2+(1-x_3))\times \ln(1+x_3)$

\\$f_2(x)=\max\{x_1^2-x_1,x_2^2-x_2,x_3^2-x_3\}-\ln(2)^3$

\\with $\forall i=1..3, 0\leq x_i \leq 1$

\\If the $\min$ is $-\ln(2)^3$ then there is solution, else there are not.

Bonjour,

En fait cela avait été déjà découvert, mais il me semble que ce site est le seul où est publié concrétement une méthode générale pour convexifier un probleme sat.

Bonne journée.

Bonjour Dattier,
C'est le type de problème que l'on peut résoudre avec la méthode de Monte-Carlo.
D'ailleurs, d'après quelques échanges, je ne suis pas sûr que notre ami Beagle sache l'intérêt de cette méthode.
Penses-tu que je devrais ouvrir un fil pour expliquer cela ?

Dlzlogic a écrit:Penses-tu que je devrais ouvrir un fil pour expliquer cela ?

C'est toi qui voit.

Si tu sais résoudre en un temps raisonnable ce genre de problème, alors tu es l'empreur du pétrole...

Bof, j'ai pas vraiment compris.
Je trouve F proche de -0.21.
Doit-on donner les valeurs de x1, x2 et x3 ?
Les formules me paraissent étonnantes.
Mais ce n'est pas la valeur maximum, qui est égale à 0.

Après lectures, j'ai l'impression qu'il y a une finesse qui m'échappe.