Optimisation continue Problèmes linéaires et non linéaires Coll. Cursus

L'optimisation est une branche récente des mathématiques qui vise à résoudre des problèmes en déterminant la solution qui soit la plus satisfaisante parmi un grand nombre de possibles. Elle est à la base de tout procédé où l'on cherche à obtenir un optimum au moindre coût ; de ce fait, elle est multidisciplinaire.

Les champs de l'optimisation étant très vastes, cet ouvrage est consacré à une famille particulière de problèmes, ceux où toutes les variables sont continues. Il comprend trois parties. La première présente deux chapitres portant sur des notions fondamentales. La deuxième partie expose cinq chapitres traitant des méthodes algorithmiques et de la théorie de l'optimisation linéaire. Enfin, la dernière partie, elle aussi en cinq chapitres, se concentre sur l'analyse et les méthodes non linéaires, avec et sans contraintes.

I - Notions fondamentales d’optimisation

1. Introduction à l’optimisation

1.1 Optimisation : d’hier à aujourd’hui

1.2 Optimalité globale et locale

1.3 Formalisme et terminologie

1.4 Application : congestion routière

1.5 Exercices

2. Modélisation

2.1 Formulation mathématique d’un problème concret

2.2 Classes et familles de problèmes d’optimisation

2.3 Existence d’une solution optimale

2.4 Application : problème de mélanges

2.5 Exercices

II - Optimisation linéaire

3. Méthode du simplexe pour l’optimisation linéaire

3.1 Formes standards d’inégalités et d’égalités en optimisation linéaire

3.2 Idées derrière la méthode du simplexe

3.3 Dictionnaire et solution réalisable

3.4 Application : conception d’un alliage optimal

3.5 Exercices

4. Forme révisée de la méthode du simplexe

4.1 Notation révisée du simplexe

4.2 Méthode du simplexe révisée

4.3 Complexité et vitesse du simplexe

4.4 Application : classification par hyperplan

4.5 Exercices

5. Considérations pratiques en optimisation linéaire

5.1 Dictionnaire initial non réalisable

5.2 Dégénérescence et cyclage

5.3 Règle anti-cyclage de Bland

5.4 Application : le plus grand disque inscrit dans un polygone

5.5 Exercices

6. Théorèmes de dualité faible et forte

6.1 Dual d’un problème linéaire

6.2 Dualité faible

6.3 Dualité forte

6.4 Application : aperçu de l’optimisation en nombres entiers

6.5 Exercices

7. Théorie de la dualité linéaire

7.1 Complémentarité

7.2 Théorème d’alternatives

7.3 Analyse de sensibilité

7.4 Application : théorie des jeux

7.5 Exercices

III - Optimisation non linéaire

8. Convexité

8.1 Ensembles, fonctions et problèmes convexes

8.2 Dérivées secondes et matrices définies positives

8.3 Critère de la deuxième dérivée

8.4 Application : régressions de Ridge et de Lasso

8.5 Exercices

9. Conditions d’optimalité pour le cas sans contraintes

9.1 Approximations de Taylor

9.2 Condition nécessaire d’optimalité de premier ordre

9.3 Conditions nécessaire et suffisante de deuxième ordre

9.4 Application : distance sécuritaire de freinage

9.5 Exercices

10. Méthodes d’optimisation non linéaire sans contraintes

10.1 Vitesse de convergence

10.2 Méthode de Newton pour l’optimisation

10.3 Direction de descente

10.4 Application : algorithme de points intérieurs

10.5 Exercices

11. Recherche linéaire

11.1 Recherche linéaire exacte

11.2 Conditions d’Armijo et de Wolfe

11.3 Convergence globale

11.4 Application : réseaux de neurones

11.5 Exercices

12. Conditions d’optimalité pour le cas contraint

12.1 Multiplicateurs de Lagrange pour contraintes d’égalité

12.2 Contraintes d’inégalité

12.3 Contraintes mixtes et conditions de KKT

12.4 Application : forme d’une chaîne suspendue

12.5 Exercices

IV - Annexe : Solutions

Index

Ce livre s'adresse principalement aux étudiants en mathématiques appliquées en cycles supérieurs, mais aussi aux étudiants en ingénierie. Il présente les intuitions à l'origine de diverses techniques d'optimisation et démontre rigoureusement tous les résultats énoncés, ce qui permet de saisir les rouages des méthodes et leur fonctionnement. De nombreux exemples, figures et exercices facilitent la compréhension.