- Manuel traitant de manière systématique les principes et l’ensemble des algorithmes de l’optimisation mathématique, en couvrant à la fois les problèmes continus et discrets
- Présente progressivement diverses approches, des méthodes fondées sur les dérivées aux méthodes probabilistes et évolutionnaires
- Inclut les structures mathématiques nécessaires aux applications réelles, comme les contraintes, la dualité, la programmation linéaire et quadratique
- Chaque chapitre propose un résumé et des exercices afin de combiner apprentissage et pratique
- Diffusé sous licence ouverte de MIT Press (CC BY-NC-ND)
Préface et aperçu
- Ce livre est un manuel consacré à la théorie et à l’implémentation des algorithmes de résolution de problèmes d’optimisation, publié en 2e édition
- Les auteurs sont Mykel J. Kochenderfer et Tim A. Wheeler
- Publié par MIT Press, il est mis à disposition sous licence Creative Commons non commerciale et sans modification
- Après la préface et les remerciements, l’ouvrage se compose de 13 chapitres
- Chaque chapitre est structuré autour de concepts clés, d’un résumé et d’exercices, dans une logique centrée sur l’apprentissage
Chapitre 1. Introduction
- Présente l’histoire de l’optimisation, son déroulement, sa formulation mathématique et ses domaines d’application
- Explique les extrema (
minima) et les conditions d’optimalité (optimality conditions)
- Comprend également un aperçu général, un résumé et des exercices
Chapitre 2. Dérivées et gradients
- Explique la définition et les méthodes de calcul des dérivées à une variable et à plusieurs variables
- Inclut les techniques de différentiation numérique (
numerical differentiation) et de différentiation automatique (automatic differentiation)
- Traite aussi du gradient de régression et des méthodes d’approximation stochastique (SPSA)
Chapitre 3. Encadrement (Bracketing)
- Explique le concept d’unimodalité (
unimodality) et la procédure de recherche d’un intervalle initial
- Présente des algorithmes fondés sur des intervalles, comme la recherche de Fibonacci, la recherche par section dorée et la recherche par approximation quadratique
- Inclut aussi les méthodes Shubert-Piyavskii et de bisection (
bisection)
Chapitre 4. Descente locale (Local Descent)
- Explique les notions d’itération selon une direction de descente (
descent direction iteration) et de taille de pas (step factor)
- Inclut les techniques de recherche linéaire (
line search) et de recherche linéaire approchée
- Traite aussi de l’approche par région de confiance (
trust region) et des conditions d’arrêt
Chapitre 5. Méthodes du premier ordre (First-Order Methods)
- Couvre les principales techniques comme la descente de gradient, le gradient conjugué, le momentum et le momentum de Nesterov
- Présente des algorithmes d’optimisation modernes comme AdaGrad, RMSProp, Adadelta, Adam et Hypergradient Descent
- Fournit un résumé comparatif des caractéristiques de chaque méthode
Chapitre 6. Méthodes du second ordre (Second-Order Methods)
- Explique la méthode de Newton (
Newton’s Method) et la méthode de la sécante (Secant Method)
- Inclut l’algorithme de Levenberg-Marquardt et les méthodes quasi-Newton
- Se conclut par un résumé et des exercices
Chapitre 7. Méthodes directes (Direct Methods)
- Présente notamment la recherche par coordonnées, Powell, Hooke-Jeeves, la recherche par motifs et la méthode du simplexe de Nelder-Mead
- Inclut la technique des rectangles divisés (
Divided Rectangles)
- Met l’accent sur les approches d’optimisation sans dérivées
Chapitre 8. Méthodes stochastiques (Stochastic Methods)
- Traite des approches stochastiques comme la descente bruitée, la recherche adaptative sur maillage et l’optimisation sans dérivées
- Inclut le recuit simulé, l’entropie croisée, les stratégies d’évolution naturelles et l’adaptation de matrice de covariance (CMA)
- Met en avant l’efficacité de l’exploration fondée sur le hasard
Chapitre 9. Méthodes basées sur des populations (Population Methods)
- Explique des techniques d’exploration par population comme les algorithmes génétiques, l’évolution différentielle et l’optimisation par essaim particulaire (PSO)
- Inclut Firefly, Cuckoo Search et des méthodes hybrides
- Résout les problèmes selon une structure d’itération de population (
population iteration)
Chapitre 10. Contraintes (Constraints)
- Explique les concepts de base de l’optimisation sous contraintes (
constrained optimization) et les types de contraintes
- Inclut la méthode des multiplicateurs de Lagrange, les variables d’écart, les méthodes de pénalisation et de point intérieur (
interior point)
- Traite aussi des transformations d’élimination des contraintes (
transformations) et de la méthode des multiplicateurs (method of multipliers)
Chapitre 11. Dualité (Duality)
- Explique le problème dual (
dual problem) et les méthodes primal-dual
- Inclut la montée duale (
dual ascent) et ADMM (Alternating Direction Method of Multipliers)
- Aborde les applications en optimisation distribuée (
distributed methods)
Chapitre 12. Programmation linéaire (Linear Programming)
- Explique la formulation du problème, l’algorithme du simplexe (
Simplex Algorithm) et les certificats duaux (dual certificates)
- Présente de manière systématique la structure de l’optimisation sous contraintes linéaires
Chapitre 13. Programmation quadratique (Quadratic Programming)
- Formule des problèmes incluant une fonction objectif quadratique et des contraintes linéaires
- Traite des problèmes de moindres carrés (
least squares) et des contraintes linéaires d’inégalité
- Inclut la programmation de distance minimale (
least distance programming)
Annexes et autres informations
- Chaque chapitre se termine par un résumé et des exercices
- MIT Press l’a publié dans son édition 2025, avec partage non commercial autorisé (CC BY-NC-ND)
- Composition basée sur LaTeX ; contact : bugs@algorithmsbook.com
4 commentaires
On ne peut pas y accéder pour le moment 😢
https://algorithmsbook.com/optimization/#download
On dirait que le lien a un peu changé maintenant ; on peut consulter ou télécharger le PDF ici.
Merci !!
Avis Hacker News
Je suis ravi de voir le sujet de l’optimisation arriver en une de HN
J’aimerais présenter le site de visualisation LP que j’ai créé. Il permet de voir visuellement comment les algorithmes de programmation linéaire (Linear Programming) réagissent lorsque les contraintes ou la fonction objectif changent
En allant sur la page de démo, un polygone est tracé automatiquement, et on peut observer les itérations de l’algorithme en faisant glisser les sommets ou les droites de contrainte
Ce n’est pas encore totalement abouti, mais je pense que cela peut être amusant à utiliser pour ceux qui aiment l’apprentissage visuel. Les retours sont les bienvenus
Je voudrais partager quelques ressources sur les métaheuristiques
Chez Timefold, où je travaille, nous utilisons des algorithmes comme Tabu Search et Simulated Annealing présentés dans ces livres pour trouver rapidement des solutions quasi optimales
Le diagramme des algorithmes de recherche locale de la documentation Timefold vaut aussi le détour
C’est un manuel d’optimisation sous licence CC de 521 pages, et il a vraiment l’air excellent
Le début traite des algorithmes gradient-based modernes fondés sur l’autodifférentiation (par ex. Adam), et la seconde moitié (chapitre 12) couvre l’optimisation linéaire (simplex, etc.)
Il y a aussi beaucoup d’exercices, et c’était exactement le genre de livre que j’attendais depuis longtemps
Je pense que les algorithmes d’optimisation ne servent pas seulement à résoudre des problèmes, mais constituent aussi une tentative vers un « solveur de problèmes généraliste ». Au lieu que le programme trouve directement la réponse, on définit la forme que la solution devrait prendre, puis on applique une optimisation par-dessus
L’IA actuelle repose aussi sur cette approche
Ce livre de Kochenderfer et son ouvrage précédent Decision Making Under Uncertainty(PDF) font partie de mes livres techniques préférés
Les explications sont claires, les visualisations excellentes, et ils abordent diverses manières de penser l’optimisation au-delà de la gradient descent
Le code est en Julia, mais il n’est pas difficile à transposer dans d’autres langages. Il faut se concentrer sur les concepts plutôt que sur le langage
L’optimisation n’est pas seulement une technique, c’est une manière de penser la résolution de problèmes difficiles
Ce livre est une ressource rare qui couvre à la fois CMA-ES, surrogate model, Gaussian process, etc. en un seul volume
Cela m’aurait vraiment aidé si un tel livre avait existé à l’époque de mes recherches de licence. Avant, ces sujets étaient dispersés entre divers articles et ouvrages
Pendant mon doctorat, j’ai lu ce livre attentivement plusieurs fois. Je travaillais sur les réseaux de neurones et l’analyse numérique, et l’équilibre entre profondeur et étendue y est très réussi
Je l’utilise encore souvent comme ouvrage de référence
J’ai été surpris de voir des métaheuristiques comme Firefly et Cuckoo Search incluses dans le livre
Ces algorithmes ne sont pas jugés fiables dans le monde académique et ont aussi été critiqués dans cet article d’ITOR
Une petite communauté qui étudie uniquement ce type d’approche se cite mutuellement et forme une bulle. Cela suscite aussi régulièrement des controverses dans les conférences
Le chapitre sur l’optimisation multiobjectif était excellent
Je me demande s’il existe d’autres livres ou ressources consacrés à ce sujet
Je me demande si quelqu’un pourrait comparer ce livre avec Numerical Optimization de Nocedal & Wright