optimization deterministe non convexte/ P=NP

[invitec35bc9ea]

Bonjour,
les algos d'optim deterministes genre gradient, newton... sont sensibles aux minimas locaux et donc ne sont applicables qu'aux problèmes coonvexes.
pour une fonction non convexe avec plusieurs optimas locaux, les métaheuristiques genre ga, pso... sont mieux adaptées mais sont stochastiques et non deterministes.
l'optimization non convexe est un probleme NP difficile. cela voudrait dire que l'existance d'un algorithme deterministe résolvant un tel problème prouverait P=NP?
un nouvel algo d'optim nommé "central force optimization" prétend réaliser un tel exploit sans pour autant lier ça au problème P=NP

avis aux spécialistes
-----

[invitec35bc9ea]

ça n'interresse pas grand monde apparemment

[invite4b7b6ddf]

L'existence d'un algo qui résout le problème en temps polynomial et d'une façon déterministe n'implique pas que P=NP, car les problèmes dans la classe NP ne se réduisent "polynomialement" pas au problème d'optimization des fonctions non convexes, pour démontrer que P=NP par exemple, il faut trouver un algo qui résout l'un des problèmes NP-complet, c.à.d, un problème dans la classe NP et tout les autres problèmes dans NP se réduisent polynomialement à lui, un générateur en quelque sorte, comme le TSP, knapsack, 3-SAT, etc ...

Les méta-heuristiques ne sont guère des méthodes mathématiques, sont juste des méthodes basées sur des opérateurs de recherche aléatoire qui étudient pas les propriétés mathématiques du problème afin de le résoudre, souvent ces méthodes donnent une solution acceptable en temps de calcule acceptable, donc il faut pas comparer ces algo aux méthodes genre gradient, newton...