L'optimisation convexe permettrais de résoudre sat.

[un_homme]

Salut,

On peut réécrire sat (pb NP-complet) comme un problème d'optimisation convexe :

se traduit par

de plus on ajoute :

, , ,

et pour tout

Le but étant de minimiser .

Si l'on trouve une solution avec c'est que le problème sat à une solution.

Car ainsi, sat deviendrait soluble avec la méthode de ellipsoïde par exemple.

Y-voyez vous une erreur ?

Merci.

[Sylviel]

J'ai un fort doute sur le fait que ta contrainte multiplicative soit convexe.

[un_homme]

Oui, il semble que le polynôme ne soit pas convexe.
Quelle est la forme des polynômes à 2 variables convexes ?