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

31

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.

Bart
la source
6
Le titre de cette question est beaucoup trop large; il semble que ce que vous voulez vraiment savoir, c'est si les programmes convexes peuvent vraiment être résolus en temps polynomial.
Peter Shor
Détaché Bart, tu peux peut-être décomposer les choses en questions spécifiques?
Suresh Venkat
Peter et Suresh, merci pour ces suggestions. D'après ce que j'ai écrit, il est supposé s'ensuivre que je ne m'intéresse pas seulement à la question de savoir si les programmes convexes peuvent être résolus ou approchés en poly-temps. Je m'intéresse essentiellement aux limites des méthodes des ellipsoïdes et des points intérieurs, et j'espère que quelqu'un sait précisément sur quelles classes de députés ils travaillent efficacement. Je pose cette question parce que la littérature actuelle sur ce sujet n'est pas claire à ce sujet (pour moi).
Bart
Personnellement, je pense que ce serait bien d'avoir un bon aperçu de cela sur un seul endroit (comme une réponse à cette question de stackexchange). Cela me semble également être une question tout à fait cohérente. Cependant, comme je suis nouveau dans stackexchannge, je ne connais pas la culture et l'éthique ici .. donc au cas où vous insisteriez, j'essaierai de découvrir comment diviser cette question en plusieurs questions plus petites.
Bart
1
Je pense que la portée de cette question est beaucoup trop large pour avoir une réponse. Les limites des méthodes de l'ellipsoïde et du point intérieur seraient une bonne question, et ce qui peut être fait pour les programmes convexes est une bonne question, mais si vous ne spécifiez pas le type d'algorithme ou le type de programme, vous demandez essentiellement pour un résumé de l'ensemble du domaine de l'optimisation continue dans votre réponse, et c'est à peu près impossible. Ce n'est pas un petit champ. Cependant, si vous laissez votre question telle quelle, il est fort possible que vous obteniez une autre bonne réponse partielle.
Peter Shor

Réponses:

18

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.

Tsuyoshi Ito
la source
Cela nécessite un peu plus de soin car la méthode ellipsoïde et les méthodes de point intérieur nécessitent des conditions supplémentaires pour fonctionner en temps polynomial.
Yoshio Okamoto
Merci pour cela, Tsuyoshi! Yoshio, pourriez-vous clarifier ce que vous entendez par là? Voulez-vous vraiment dire qu'il y a des conditions sur le SDP particulier nécessaire, car sinon le SDP ne peut pas être approximé comme ça en poly-temps? C'est une surprise pour moi dans ce cas, et je serais intéressé à connaître ces conditions. Merci.
Bart
@Bart: Par exemple, si vous regardez les notes de cours de Lovasz cs.elte.hu/~lovasz/semidef.ps , vous pouvez trouver Theorem 3.7 (Page 19) parle de la limite de temps d'exécution de la méthode ellipsoïde pour la minimisation convexe . Là, certaines hypothèses techniques s'imposent.
Yoshio Okamoto
4
rRbûcheR/r
Merci beaucoup pour cela. Cela répond à une très grande partie de ma question. Il semble que ces connaissances puissent être un outil très utile pour les informaticiens théoriques, alors qu'il me semble encore qu'elles ne sont pas du tout connues et ne sont énoncées presque nulle part. Bizarre.
Bart