Quels sont les avantages / inconvénients des méthodes de point intérieur par rapport à la méthode simplex pour l'optimisation linéaire?

Si je comprends bien, étant donné qu'une solution à un programme linéaire se produit toujours au sommet de son ensemble réalisable polyédrique (si une solution existe et que la valeur optimale de la fonction objective est limitée par le bas, en supposant un problème de minimisation), comment une recherche dans le l'intérieur de la région réalisable serait-il meilleur? T-il converger plus rapidement? Dans quelles circonstances serait-il avantageux d'utiliser la méthode simplex par rapport aux méthodes ponctuelles intérieures? Est-ce que l'un est plus facile à implémenter dans un code que l'autre?

convex-optimization linear-programming Paul
la source

min_{x \in [- 1, 1]} x^{2}

$\min_{x \in [-1, 1]} x^{2}$

x = 0

$x = 0$

Serait-il plus approprié de dire «optimisation linéaire» au lieu de «optimisation convexe»?

Paul

Oui, votre déclaration est correcte. Merci d'avoir édité votre question.

Geoff Oxberry

Le problème avec la méthode simplex est qu'elle ne peut pas être généralisée aux problèmes non linéaires, c'est-à-dire la majorité des problèmes du monde réel.

Réponses:

Basé sur l'expérience personnelle, je dirais que les méthodes simplex sont légèrement plus faciles à comprendre que les méthodes de point intérieur, basées sur l'expérience personnelle de la mise en œuvre à la fois du simplexe primal et d'une méthode de point intérieur de base dans MATLAB dans le cadre d'un cours de programmation linéaire . Les principaux obstacles dans le simplex primal sont de s'assurer que vous implémentez correctement la Phase I et la Phase II, et que vous implémentez correctement une règle anticyclique. Les principaux obstacles à la mise en œuvre d'une méthode de point intérieur pour la programmation linéaire tendent à être davantage liés à la mise en œuvre correcte de la méthode itérative et à la mise à l'échelle du paramètre de barrière en conséquence.

Vous pouvez trouver une discussion plus complète des avantages et des inconvénients de chaque algorithme dans un manuel sur la programmation linéaire, comme Introduction à l'optimisation linéaire par Bertsimas et Tsitsiklis. ( Avertissement: j'ai appris la programmation linéaire de ce manuel et j'ai suivi la programmation linéaire au MIT de la femme de Bertsimas.) Voici quelques notions de base:

Avantages de simplex:

Compte tenu de variables de décision, habituellement converge en opérations avec pivote. $n$ $O(n)$ $O(n)$
Profite de la géométrie du problème: visite les sommets de l'ensemble réalisable et vérifie l'optimalité de chaque sommet visité. (Dans le simplex primal, le coût réduit peut être utilisé pour ce contrôle.)
Bon pour les petits problèmes.

Inconvénients du simplex:

Étant donné variables de décision, vous pouvez toujours trouver une instance de problème où l'algorithme nécessite opérations et pivots pour arriver à une solution. $n$ $O(2^{n})$
Pas très bien pour les gros problèmes, car les opérations de pivotement deviennent coûteuses. Des algorithmes de plan de coupe ou des algorithmes de génération de colonnes retardées comme Dantzig-Wolfe peuvent parfois compenser cette lacune.

Avantages des méthodes de point intérieur:

Avoir une complexité polynomiale asymptotique temporelle de , où est le nombre de bits d'entrée de l'algorithme. $O(n^{3.5}L^2\log{L}\log\log{L})$ $L$
Mieux pour les gros problèmes clairsemés car l'algèbre linéaire requise pour l'algorithme est plus rapide.

Inconvénients des méthodes de point intérieur:

Ce n'est pas aussi satisfaisant intuitivement parce que vous avez raison, ces méthodes ne visitent pas les sommets. Ils errent à travers la région intérieure, convergeant vers une solution en cas de succès.
Pour les petits problèmes, le simplex sera probablement plus rapide. (Vous pouvez construire des cas pathologiques, comme le cube de Klee-Minty.)

Geoff Oxberry
la source

Un bon résumé. Klee-Minty semble en fait être conçu pour confondre les méthodes LP simplex ...

@JM Oui, c'est exactement le but - c'est une construction explicite pour montrer que les méthodes simplexes ne sont pas polynomiales (bien qu'il existe des variantes qui font aussi pleurer les méthodes de point intérieur).

Christian Clason

Merci pour ce post informatif. Je me demande combien de variables rendent le problème important? Douzaines? Des centaines? Milliers?

KjMag

5^{D}

$5^D$

A

$A$

x^{*}

$x^*$

La réponse est simple. Les deux (méthodes du point simplex et du point intérieur) sont un domaine mature d'un point de vue algorithmique. Ils fonctionnent tous les deux très bien dans la pratique. La bonne réputation de l'IPM (méthode des points intérieurs) est due à sa complexité polynomiale dans le pire des cas. Ce n'est pas le cas pour le simplex qui a une complexité combinatoire. Néanmoins, les programmes linéaires combinatoires ne se produisent presque jamais dans la pratique. Pour les problèmes à très grande échelle, l'IP semble être un peu plus rapide, mais ce n'est pas nécessairement la règle. À mon avis, la propriété intellectuelle peut être facile à comprendre et à mettre en œuvre, mais à coup sûr, quelqu'un d'autre peut être en désaccord, et c'est très bien. Maintenant, en LP, si la solution est unique, elle doit certainement être dans un sommet (IP et Simplex font bien ici aussi). La solution peut également être sur une face du polyèdre ou sur un bord auquel cas, le sommet adjacent est (ou les sommets sont) également une solution (encore une fois, IP et simplex font bien). Ils sont donc à peu près les mêmes.

Carlos Ramirez
la source

Je me rends compte que l'exemple que j'ai donné n'était pas un programme linéaire; si vous regardez l'historique des révisions, une version antérieure de cette question demandait de comparer la méthode simplex et les méthodes de point intérieur pour les problèmes d'optimisation convexe. J'ai donné un contre-exemple pour justifier les modifications que j'ai apportées et pour encourager l'affiche originale à corriger sa question, ce qu'il a fait.

Geoff Oxberry