Arc-Search Techniques for Interior-Point Methods
Ce livre traite d'un domaine important de l'optimisation numérique, appelé méthode du point intérieur. Ce sujet est populaire depuis les années 1980, lorsque les gens ont progressivement réalisé que tous les algorithmes du simplexe ne convergeaient pas en temps polynomial et que de nombreux algorithmes du point intérieur pouvaient être prouvés comme convergeant en temps polynomial.
Cependant, pendant longtemps, il y a eu un écart notable entre les limites polynomiales théoriques des algorithmes du point intérieur et l'efficacité de ces algorithmes. Les stratégies importantes pour l'efficacité des calculs sont devenues des obstacles à la preuve de bonnes bornes polynomiales. Plus les stratégies étaient utilisées dans les algorithmes, plus les bornes polynomiales étaient mauvaises.
Pour aggraver encore le problème, l'algorithme prédicteur-correcteur (MPC) de Mehrotra (l'algorithme de point intérieur le plus populaire et le plus efficace jusqu'à récemment) utilise toutes les bonnes stratégies et ne parvient pas à prouver la convergence.
Par conséquent, l'algorithme MPC n'est pas polynomial, ce qui est un problème critique pour la méthode du simplexe. Ce livre traite des développements récents qui permettent de résoudre ce dilemme.
Il se compose de trois parties principales. La première, qui comprend les chapitres 1, 2, 3 et 4, présente certains des algorithmes les plus importants au cours du développement de la méthode du point intérieur vers les années 1990, la plupart d'entre eux étant largement connus. L'objectif principal de cette partie est d'expliquer le dilemme décrit ci-dessus en analysant les bornes polynomiales de ces algorithmes et en résumant l'expérience de calcul qui leur est associée.
La deuxième partie, qui comprend les chapitres 5, 6, 7 et 8, décrit comment résoudre le dilemme étape par étape en utilisant des techniques de recherche d'arcs. À la fin de cette partie, un algorithme très efficace avec la borne polynomiale la plus basse est présenté. La dernière partie, qui comprend les chapitres 9, 10, 11 et 12, étend les techniques de recherche d'arcs à des problèmes plus généraux, tels que la programmation quadratique convexe, le problème de complémentarité linéaire et la programmation semi-définie.
| ISBN : | 9780367510091 |
| Auteur : | |
| Éditeur : | |
| Langue : | anglais |
| Reliure : | Broché |
| Année de publication : | 2022 |
| Nombre de pages : | 306 |
Actuellement disponible, en stock.
