Quelles classes de programmes mathématiques peuvent être résolues exactement ou approximativement, en temps polynomial?

Je suis plutôt confus par la littérature sur l'optimisation continue et la littérature TCS sur les types de programmes mathématiques (MP) (continus) qui peuvent être résolus efficacement et ceux qui ne le peuvent pas. La communauté de l'optimisation continue semble affirmer que tous les programmes convexes peuvent être résolus efficacement, mais je crois que leur définition de «efficace» ne coïncide pas avec la définition de TCS.

Cette question m'a beaucoup dérangé ces dernières années et je n'arrive pas à y trouver une réponse claire. J'espère que vous pourrez m'aider à régler cela une fois pour toutes: quelles classes de députés peuvent être résolues exactement en temps polynomial et par quels moyens; et que sait-on de l'approximation de la solution optimale de MP que nous ne pouvons pas résoudre exactement en temps polynomial?

Ci-dessous, je donne une réponse incomplète à cette question qui est peut-être également incorrecte à certains endroits, donc j'espère que vous pourrez vérifier et me corriger aux points où je me trompe. Il énonce également certaines questions auxquelles je ne peux pas répondre.

Nous savons tous que la programmation linéaire peut être résolue exactement en temps polynomial, en exécutant la méthode ellipsoïde ou une méthode de point intérieur, puis en exécutant une procédure d'arrondi. La programmation linéaire peut même être résolue en polynôme temporel dans le nombre de variables face à une famille de LPs avec une très grande quantité de contraintes linéaires, tant qu'on peut lui fournir un "oracle de séparation": un algoritme qui, étant donné un point , détermine si ce point est réalisable ou génère un hyperplan qui sépare le point du polyèdre des points réalisables. De même, la programmation linéaire en polynôme temporel du nombre de contraintes face à une famille de LPs avec une très grande quantité de variables, si l'on fournit un algorithme de séparation pour les duals de ces LPs.

La méthode ellipsoïde est également capable de résoudre des programmes quadratiques en temps polynomial, dans le cas où la matrice dans la fonction objectif est positive (semi?) Définie. Je soupçonne que, en utilisant l'astuce de séparation d'oracle, nous pouvons dans certains cas également le faire si nous avons affaire à un nombre incroyable de contraintes. Est-ce vrai?

Dernièrement, la programmation semi-définie (SDP) a gagné en popularité dans la communauté TCS. On peut les résoudre jusqu'à une précision arbitraire en utilisant des méthodes de point intérieur, ou la méthode ellipsoïde. Je pense que les SDP ne peuvent pas être résolus exactement en raison du problème que les racines carrées ne peuvent pas être calculées exactement. (?) Serait-il alors correct de dire qu'il existe un FPTAS pour SDP? Je ne l'ai vu nulle part, donc ce n'est probablement pas juste. Mais pourquoi?

Nous pouvons résoudre les LP exactement et les SDP avec une précision arbitraire. Qu'en est-il des autres classes de programmes coniques? Pouvons-nous résoudre des programmes de cônes de second ordre jusqu'à une précision arbitraire, en utilisant la méthode ellipsoïde? Je ne sais pas.

Sur quelles classes de députés pouvons-nous utiliser la méthode ellipsoïde? Quelles propriétés un tel MP doit-il satisfaire pour qu'une réponse puisse être donnée avec une précision arbitraire, et de quelles propriétés supplémentaires avons-nous besoin pour pouvoir obtenir une solution exacte en temps polynomial? Mêmes questions pour les méthodes de point intérieur.

Oh, et enfin, qu'est-ce qui fait que les optimiseurs continus disent que les programmes convexes peuvent être résolus efficacement? Est-il vrai qu'une réponse de précision arbitraire à un programme convexe peut être trouvée en temps polynomial? Je ne crois pas, alors sous quels aspects leur définition de «efficace» diffère-t-elle de la nôtre?

Toute contribution est appréciée! Merci d'avance.

Je peux répondre à cette partie:

Serait-il alors correct si je dis qu'il existe un FPTAS pour SDP? Je ne l'ai vu nulle part, donc ce n'est probablement pas juste. Mais pourquoi?

La déclaration est correcte, mais nous ne la voyons pas souvent car une déclaration plus forte tient et est plus importante que cette déclaration plus faible.

Un FPTAS est un algorithme à temps polynomial qui, étant donné un problème et un paramètre de précision 1 ^k , génère une solution approximative (1 + 1 / k ).

Mais pour SDP, la méthode ellipsoïde et la méthode du point intérieur fournissent des algorithmes à temps polynomial qui, étant donné un problème et un paramètre de précision 1 ^k , produisent une solution approximative (1 + 2 ^{- k} ). Notez que le facteur d'approximation est bien meilleur que ce qui est requis pour un FPTAS.

Je ne sais pas si tous les problèmes convexes sont en P, mais je peux répondre à une question connexe: l'optimisation non convexe est NP-difficile. Voir "La programmation quadratique avec une valeur propre négative est NP-difficile" .